public interface IListDS<T> {
int GetLength();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
T Delete(int index);
T this[int index] { get; }
T GetEle(int index);
int Locate(T value);
}
順序表(線性表)實(shí)現(xiàn)方式
/// <summary>
/// 順序表實(shí)現(xiàn)方式
/// </summary>
/// <typeparam name="T"></typeparam>
public class SequList<T> : IListDS<T>
{
private T[] data;//用來存儲(chǔ)數(shù)據(jù)
private int count = 0;//表示存了多少數(shù)據(jù)
public SequList(int Size) {
data = new T[Size];
count = 0;
}
public SequList():this(10) {//默認(rèn)構(gòu)造函數(shù)容量是10
}
/// <summary>
/// 定義一個(gè)索引器 獲取元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return GetEle(index);
}
}
/// <summary>
/// 添加一個(gè)元素
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
if (count == data.Length)
{//說明當(dāng)前順序表已存滿舱馅，不允許再存入
Debug.Log("當(dāng)前數(shù)值已經(jīng)存滿");
}
else {
data[count] = item;
count++;
}
}
/// <summary>
/// 清空操作
/// </summary>
public void Clear()
{
count = 0;
}
/// <summary>
/// 刪除操作
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T Delete(int index)
{
T temp = data[index];
for (int i = index+1; i < count; i++)
{
data[i - 1] = data[i];//把數(shù)據(jù)向前移動(dòng)
}
count--;
return data[index];
}
/// <summary>
/// 取表元
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetEle(int index)
{
if (index >= 0 && index <= count - 1)//索引存在
{
return data[index];
}
else {
Debug.Log("索引不存在");
return default(T);
}
}
/// <summary>
/// 取得數(shù)據(jù)的長(zhǎng)度
/// </summary>
/// <returns></returns>
public int GetLength()
{
return count;
}
/// <summary>
/// 插入值
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
for (int i = count-1 ; i >= index; i--)
{
data[i + 1] = data[i];
}
data[index] = item;
count++;
}
/// <summary>
/// 判斷是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return count == 0;
}
/// <summary>
/// 按值查找
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
for (int i = 0; i < count; i++)
{
if (data[i].Equals(value)) {
return i;
}
}
return -1;
}
單鏈表的節(jié)點(diǎn)
/// <summary>
/// 單鏈表的節(jié)點(diǎn)
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
private T date;//存儲(chǔ)數(shù)據(jù)
private Node<T> next;//指針指向下一個(gè)元素
public Node(T value)
{
date = value;
next = null;
}
public Node(T value, Node<T> next)
{
this.date = value;
this.next = next;
}
public Node(Node<T> next)
{
this.next = next;
}
public Node() {
date = default(T);
next = null;
}
public T Data {
get { return date; }
set { Data = value; }
}
public Node<T> Next
{
get { return next; }
set { next = value; }
}
單鏈表的實(shí)現(xiàn)
/// <summary>
/// 實(shí)現(xiàn)單鏈表的功能
/// </summary>
/// <typeparam name="T"></typeparam>
public class LinkList<T> : IListDS<T>
{
private Node<T> head;//存儲(chǔ)一個(gè)頭結(jié)點(diǎn)
public LinkList() {
head = null;
}
/// <summary>
/// 定義一個(gè)索引器 獲取元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
Node<T> temp = head;
for (int i = 0; i <=index; i++)
{
temp = temp.Next;
}
return temp.Data;
}
}
/// <summary>
/// 添加一個(gè)元素
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
Node<T> newNode = new Node<T>(item);//根據(jù)新的數(shù)據(jù)創(chuàng)建一個(gè)新的節(jié)點(diǎn)
if (head == null)
{
head = newNode;
}
else {
Node<T> temp = head;
while (true) {
if (temp.Next != null)
{
temp = temp.Next;
}
else {
break;
}
}
temp.Next = newNode;
}
}
/// <summary>
/// 清空操作
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 刪除操作
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T Delete(int index)
{
T data = default(T);
if (index == 0)
{//刪除到頭結(jié)點(diǎn)
head = head.Next;
}
else
{
Node<T> temp = head;
for (int i = 0; i <= index - 1; i++)
{
//讓temp向后移動(dòng)一個(gè)位置
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
data = currentNode.Data;
Node<T> nextNode = temp.Next.Next;
preNode.Next = nextNode;
}
return data;
}
/// <summary>
/// 取表元
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetEle(int index)
{
return this[index];
}
/// <summary>
/// 求長(zhǎng)度
/// </summary>
/// <returns></returns>
public int GetLength()
{
if (head == null) return 0;
Node<T> temp = head;
int count = 1;
while (true) {
if (temp.Next != null) {
count++;
temp = temp.Next;
} else {
break;
}
}
return count;
}
/// <summary>
/// 插入值
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
Node<T> newNode = new Node<T>(item);
if (index == 0)
{//插入到頭結(jié)點(diǎn)
newNode.Next = head;
head = newNode;
}
else {
Node<T> temp = head;
for (int i = 0; i <=index-1; i++)
{
//讓temp向后移動(dòng)一個(gè)位置
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
preNode.Next = newNode;
newNode.Next = currentNode;
}
}
/// <summary>
/// 判斷是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head == null;
}
/// <summary>
/// 按值查找
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
Node<T> temp = head;
if (temp == null)
{
return -1;
}
else
{
int index = 0;
while (true)
{
if (temp.Data.Equals(value))
{
return index;
}
else
{
if (temp.Next != null)
{
temp = temp.Next;
}
else
{
break;
}
}
}
return -1;
}
}
