线性表-顺序表和单链表的定义与基本操作

线性表接口定义：IListDS.cs

    public interface IListDS<T>
    {
        int GetLength(); //求长度
        void Clear(); //清空操作
        bool IsEmpty(); //判断线性表是否为空
        void Append(T item); //附加操作
        void Insert(T item, int i); //插入操作
        T Delete(int i); //删除操作
        T GetElem(int i); //取表元
        int Locate(T value); //按值查找
    }

顺序表的实现：SeqListDS.cs

 public class SeqList<T> : IListDS<T>
    {
        private int maxsize; //顺序表的容量
        private T[] data; //数组，用于存储顺序表中的数据元素
        private int last; //指示顺序表最后一个元素的位置
        //索引器
        public T this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //最后一个数据元素位置属性
        public int Last
        {
            get
            {
                return last;
            }
        }
        //容量属性
        public int Maxsize
        {
            get
            {
                return maxsize;
            }
            set
            {
                maxsize = value;
            }
        }
        //构造器
        public SeqList(int size)
        {
            data = new T[size];
            maxsize = size;
            last = -1;
        }
        //求顺序表的长度
        public int GetLength()
        {
            return last + 1;
        }
        //清空顺序表
        public void Clear()
        {
            last = -1;
        }
        //判断顺序表是否为空
        public bool IsEmpty()
        {
            if (last == -1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        //判断顺序表是否为满
        public bool IsFull()
        {
            if (last == maxsize - 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        //在顺序表的末尾添加新元素
        public void Append(T item)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            data[++last] = item;
        }
        //在顺序表的第i个数据元素的位置插入一个数据元素
        public void Insert(T item, int i)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            if (i < 1 || i > last + 2)
            {
                Console.WriteLine("Position is error!");
                return;
            }
            if (i == last + 2)
            {
                data[last + 1] = item;
            }
            else
            {
                for (int j = last; j >= i - 1; --j)
                {
                    data[j + 1] = data[j];
                }
                data[i - 1] = item;
            }
            ++last;
        }
        //删除顺序表的第i个数据元素
        public T Delete(int i)
        {
            T tmp = default(T);
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return tmp;
            }
            if (i < 1 || i > last + 1)
            {
                Console.WriteLine("Position is error!");
                return tmp;
            }
            if (i == last + 1)
            {
                tmp = data[last--];
            }
            else
            {
                tmp = data[i - 1];
                for (int j = i; j <= last; ++j)
                {
                    data[j] = data[j + 1];
                }
            }
            --last;
            return tmp;
        }
        //获得顺序表的第i个数据元素
        public T GetElem(int i)
        {
            if (IsEmpty() || (i < 1) || (i > last + 1))
            {
                Console.WriteLine("List is empty or Position is error!");
                return default(T);
            }
            return data[i - 1];
        }
        //在顺序表中查找值为value的数据元素
        public int Locate(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            int i = 0;
            for (i = 0; i <= last; ++i)
            {
                if (value.Equals(data[i]))
                {
                    break;
                }
            }
            if (i > last)
            {
                return -1;
            }
            return i;
        }
    }

单链表的实现：LinkListDS.cs

    public class Node<T>
    {
        private T data; //数据域
        private Node<T> next; //引用域
        //构造器
        public Node(T val, Node<T> p)
        {
            data = val;
            next = p;
        }
        //构造器
        public Node(Node<T> p)
        {
            next = p;
        }
        //构造器
        public Node(T val)
        {
            data = val;
            next = null;
        }
        //构造器
        public Node()
        {
            data = default(T);
            next = null;
        }
        //数据域属性
        public T Data
        {
            get
            {
                return data;
            }
            set
            {
                data = value;
            }
        }
        //引用域属性
        public Node<T> Next
        {
            get
            {
                return next;
            }
            set
            {
                next = value;
            }
        }
    }
    public class LinkList<T> : IListDS<T>
    {
        private Node<T> head; //单链表的头引用
        //头引用属性
        public Node<T> Head
        {
            get
            {
                return head;
            }
            set
            {
                head = value;
            }
        }
        //构造器
        public LinkList()
        {
            head = null;
        }
        //求单链表的长度
        public int GetLength()
        {
            Node<T> p = head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }
        //清空单链表
        public void Clear()
        {
            head = null;
        }
        //判断单链表是否为空
        public bool IsEmpty()
        {
            if (head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        //在单链表的末尾添加新元素
        public void Append(T item)
        {
            Node<T> q = new Node<T>(item);
            Node<T> p = new Node<T>();
            if (head == null)
            {
                head = q;
                return;
            }
            p = head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
        }
        //在单链表的第i个结点的位置前插入一个值为item的结点
        public void Insert(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }
            if (i == 1)
            {
                Node<T> q = new Node<T>(item);
                q.Next = head;
                head = q;
                return;
            }
            Node<T> p = head;
            Node<T> r = new Node<T>();
            int j = 1;
            while (p.Next != null && j < i)
            {
                r = p;
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p;
                r.Next = q;
            }
        }
        //在单链表的第i个结点的位置后插入一个值为item的结点
        public void InsertPost(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }
            if (i == 1)
            {
                Node<T> q = new Node<T>(item);
                q.Next = head.Next;
                head.Next = q;
                return;
            }
            Node<T> p = head;
            int j = 1;
            while (p != null && j < i)
            {
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p.Next;
                p.Next = q;
            }
        }
        //删除单链表的第i个结点
        public T Delete(int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("Link is empty or Position is error!");
                return default(T);
            }
            Node<T> q = new Node<T>();
            if (i == 1)
            {
                q = head;
                head = head.Next;
                return q.Data;
            }
            Node<T> p = head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                ++j;
                q = p;
                p = p.Next;
            }
            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                Console.WriteLine("The ith node is not exist!");
                return default(T);
            }
        }
        //获得单链表的第i个数据元素
        public T GetElem(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return default(T);
            }
            Node<T> p = new Node<T>();
            p = head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                ++j;
                p = p.Next;
            }
            if (j == i)
            {
                return p.Data;
            }
            else
            {
                Console.WriteLine("The ith node is not exist!");
                return default(T);
            }
        }
        //在单链表中查找值为value的结点
        public int Locate(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            Node<T> p = new Node<T>();
            p = head;
            int i = 1;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                ++i;
            }
            return i;
        }
    }