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);
}
顺序表(线性表)实现方式
/// <summary>
/// 顺序表实现方式
/// </summary>
/// <typeparam name="T"></typeparam>
public class SequList<T> : IListDS<T>
{
private T[] data;//用来存储数据
private int count = 0;//表示存了多少数据
public SequList(int Size) {
data = new T[Size];
count = 0;
}
public SequList():this(10) {//默认构造函数容量是10
}
/// <summary>
/// 定义一个索引器 获取元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return GetEle(index);
}
}
/// <summary>
/// 添加一个元素
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
if (count == data.Length)
{//说明当前顺序表已存满，不允许再存入
Debug.Log("当前数值已经存满");
}
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];//把数据向前移动
}
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>
/// 取得数据的长度
/// </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;
}
单链表的节点
/// <summary>
/// 单链表的节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
private T date;//存储数据
private Node<T> next;//指针指向下一个元素
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; }
}
单链表的实现
/// <summary>
/// 实现单链表的功能
/// </summary>
/// <typeparam name="T"></typeparam>
public class LinkList<T> : IListDS<T>
{
private Node<T> head;//存储一个头结点
public LinkList() {
head = null;
}
/// <summary>
/// 定义一个索引器 获取元素
/// </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>
/// 添加一个元素
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
Node<T> newNode = new Node<T>(item);//根据新的数据创建一个新的节点
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)
{//删除到头结点
head = head.Next;
}
else
{
Node<T> temp = head;
for (int i = 0; i <= index - 1; i++)
{
//让temp向后移动一个位置
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>
/// 求长度
/// </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)
{//插入到头结点
newNode.Next = head;
head = newNode;
}
else {
Node<T> temp = head;
for (int i = 0; i <=index-1; i++)
{
//让temp向后移动一个位置
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;
}
}
