C#数据结构（一）线性表

最近要给一个打算学.net的朋友准备些资料，同时自己在数据结构方面也有些薄弱，所以打算从头看看。
弄了一个电子版的C#数据结构，把书里的代码敲了敲，颇有收益。打算整理一下，如果您也跟我一样有空不妨跟着再学学。

线性表是最简单、最基本、最常用的数据结构。
线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
这种一对一的关系指的是数据元素之间的位置关系，即：
（1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；
（2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。

1、线性表

    /// <summary>
    /// 1、线性表   
    /// 线性表的接口表示
    /// </summary>
    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);         //按值查找 
        //---补充
        void Reverse();              //倒置（任何线性表都可以倒置）
    }

2、顺序表

 /// <summary>
    /// 2、顺序表   
    /// 线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，
    /// 用这种方式存储的线性表叫顺序表(Sequence List)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    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;
        }
        //倒置
        public void Reverse()
        {
            T tmp = default(T);
            int len = GetLength();
            for (int i = 0; i < len / 2; i++)
            {
                tmp = data[i];
                data[i] = data[len - 1 - i];
                data[len - 1 - i] = tmp;
            }
        }
    }

    顺序表的几个例子

  /// <summary>
    /// 顺序表的几个例子
    /// </summary>
    public class OpSeqList
    {
        //顺序表倒置
        //算法思路：把第一个元素与最后一个元素交换，把第二个元素与倒数第二个元素交换。一般地，把第 i 个元素与第 n-i 个元素交换，i 的取值范围是 0 到 n/2
        public void ReversSeqList(SeqList<int> L)
        {
            int tmp = 0;
            int len = L.GetLength();
            for (int i = 0; i < len / 2; i++)
            {
                tmp = L[i];
                L[i] = L[len - 1 - i];
                L[len - 1 - i] = tmp;
            }
        }
        //有数据类型为整型的顺序表 La 和 Lb，其数据元素均按从小到大的升
        //序排列，编写一个算法将它们合并成一个表 Lc，要求 Lc 中数据元素也按升序排列。 
        //算法思路：依次扫描 La 和 Lb 的数据元素，比较 La 和 Lb 当前数据元素的值，将较小值的数据元素赋给 Lc，如此直到一个顺序表被扫描完，然后将未完
        //的那个顺序表中余下的数据元素赋给 Lc 即可。Lc 的容量要能够容纳 La 和 Lb两个表相加的长度。
        public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb)
        {
            SeqList<int> Lc = new SeqList<int>(La.Maxsize + Lb.Maxsize);
            int i = 0;
            int j = 0;
            int k = 0;
            //La 和 Lb都有元素
            while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1)))
            {
                if (La[i] < Lb[j])
                {
                    Lc.Append(La[i++]);
                }
                else
                {
                    Lc.Append(Lb[j++]);
                }
            }
            //La中还有数据元素
            while (i < (La.GetLength() - 1))
            {
                Lc.Append(La[i++]);
            }
            //Lb中还有数据元素
            while (j < (Lb.GetLength() - 1))
            {
                Lc.Append(Lb[j++]);
            }
            return Lc;
        }
        //已知一个存储整数的顺序表La，试构造顺序表 Lb，要求顺序表 Lb中只包含顺序表 La 中所有值不相同的数据元素
        //算法思路：先把顺序表 La 的第 1 个元素赋给顺序表 Lb，然后从顺序表 La的第 2 个元素起，每一个元素与顺序表Lb中的每一个元素进行比较，如果不相同，则把该元素附加到顺序表 Lb的末尾。 
        public SeqList<int> Purge(SeqList<int> La)
        {
            SeqList<int> Lb = new SeqList<int>(La.Maxsize);
            Lb.Append(La[0]);
            for (int i = 1; i < La.GetLength(); i++)
            {
                int j = 0;
                for (j = 0; j < Lb.GetLength(); j++)
                {
                    if (La[i].CompareTo(Lb[j]) == 0)
                    {
                        break;
                    }
                }
                //没有相同的数据元素，将a表中的数据元素附加到b表的末尾。
                if (j > Lb.GetLength() - 1)
                {
                    Lb.Append(La[i]);
                }
            }
            return Lb;
        }
        //
        public void Run()
        {
            /*
            SeqList<int> L = new SeqList<int>(5);
            L.Append(10);
            L.Append(20);
            L.Append(30);
            L.Append(40);
            L.Append(50);

            // L.Delete(2);
            //L.Insert(60, 2);
            for (int i=0;i<L.GetLength();i++)
            {
                Console.WriteLine(L[i]);
            }
            Console.WriteLine("**************");
            //ReversSeqList(L);
            L.Reverse();
            for (int i = 0; i < L.GetLength(); i++)
            {
                Console.WriteLine(L[i]);
            }
            */

            /*
            SeqList<int> La = new SeqList<int>(50);
            for (int i = 0; i < 50; i++)
            {
                La.Append(i);
            }
            SeqList<int> Lb = new SeqList<int>(30);
            for (int i = 0; i < 30; i++)
            {
                Lb.Append(i + 10000);
            }
            SeqList<int> Lc = Merge(La, Lb);
            for (int i = 0; i < Lc.GetLength(); i++)
            {
                Console.WriteLine(Lc[i]);
            }
             */

            SeqList<int> La = new SeqList<int>(5);
            La.Append(1);
            La.Append(2);
            La.Append(3);
            La.Append(2);
            La.Append(3);
            SeqList<int> Lb = Purge(La);
            for (int i = 0; i < Lb.GetLength(); i++)
            {
                Console.WriteLine(Lb[i]);
            }

        }
    }

3、单链表

    /// <summary>
    /// 3、单链表  
    /// 链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可
    /// 以是连续的，也可以是不连续的） 。那么，怎么表示两个数据元素逻辑上的相邻
    /// 关系呢？即如何表示数据元素之间的线性关系呢？为此，在存储数据元素时，除
    /// 了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。
    /// </summary>
    public class LinkList<T> : IlistDS<T>
    {
        private Node<T> head;
        public Node<T> Head
        {
            get { return head; }
            set { this.head = value; }
        }
        public Node<T> Next
        {
            get { return head.Next; }
            set { head.Next = value; }
        }
        public LinkList()
        {
            head = null;
        }
        public int GetLength() //思路：最后一个节点的next为null
        {
            int len = 0;
            Node<T> Node = head;
            while (Node != null)
            {
                len++;
                Node = Node.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;
            if (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
        }
        //前插操作
        public void Insert(T item, int i)
        {
            if (IsEmpty() || i < 0)
            {
                Console.WriteLine("链表为空或位置错误");
                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;
            }
            else
            {
                Console.WriteLine("Position is error!");
            }
            return;

        }
        //后插操作
        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.Next != null && j < i)
            {
                p = p.Next;
                ++j;
            }

            if (j == i)
            {
                Node<T> q = new Node<T>(item);
                q.Next = p.Next;//核心
                p.Next = q;//核心
            }
            else
            {
                Console.WriteLine("Position is error!");
            }
            return;
        }
        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);
            }
        }
        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);
            }
        }
        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;
        }
        //在头部插入结点建立单链表的算法如下： 
        public LinkList<int> CreateLListHead()
        {
            int d;
            LinkList<int> L = new LinkList<int>();
            d = Int32.Parse(Console.ReadLine());
            while (d != -1)
            {
                Node<int> p = new Node<int>(d);
                p.Next = L.Head;
                L.Head = p;
                d = Int32.Parse(Console.ReadLine());
            }

            return L;
        }
        //在尾部插入结点建立单链表的算法如下： 
        public LinkList<int> CreateListTail()
        {
            Node<int> R = new Node<int>();
            int d;
            LinkList<int> L = new LinkList<int>();
            R = L.Head;
            d = Int32.Parse(Console.ReadLine());
            while (d != -1)
            {
                Node<int> p = new Node<int>(d);
                if (L.Head == null)
                {
                    L.Head = p;
                }
                else
                {
                    R.Next = p;
                }
                R = p;
                d = Int32.Parse(Console.ReadLine());
            }
            if (R != null)
            {
                R.Next = null;
            }
            return L;
        }

        public void Reverse()
        {
            Node<T> p = head.Next;
            Node<T> q = new Node<T>();
            head.Next = null;
            while (p != null)
            {
                q = p;
                p = p.Next;
                q.Next = head.Next;
                head.Next = q;
            }
        }

    }

    /// <summary>
    /// 单链表节点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Node<T>
        {
            private T data;         //数据域
            private Node<T> next;   //引用域

            public Node(T t, Node<T> p)
            {
                this.data = t;
                this.next = p;
            }
            public Node(T t)
            {
                this.data = t;
                this.next = null;
            }
            public Node(Node<T> p)
            {
                this.next = p;
            }
            public Node()
            {
                this.data = default(T);
                this.next = null;
            }

            public T Data
            {
                get { return data; }
                set { data = value; }
            }
            public Node<T> Next
            {
                get { return next; }
                set { next = value; }
            }
        }

    /// <summary>
    /// 单链表的几个例子
    /// </summary>
    public class OpLinkList
    {
        //单链表的倒置
        public void ReversLinkList(LinkList<int> H)
        {
            Node<int> p = H.Next;
            Node<int> q = new Node<int>();
            H.Next = null;
            while (p != null)
            {
                q = p;
                p = p.Next;
                q.Next = H.Next;
                H.Next = q;
            }
        } 
    }

  C#中的线性表

  非泛型Ilist接口继承自ICollection和IEnumerable，是所有线性表的基接口。

  ArrayList（顺序表）、ListDictionary、StringCollection、StringDictionary继承自Ilist。

  泛型Ilist<T>接口继承自ICollection<T>、IEnumerable<T>、IEnumerable。是所有泛型线性表的基接口。

  List<T>等一些集合类实现了Ilist<T>。

  List<T>是 ArrayList 在泛型中的替代品。List<T>的性能比 ArrayList 有很大改变。

  1、ArrayList 默认的 Capacity 是 16，而 List<T>的默认 Capacity是 4；

  2、List<T>的方法不是虚拟方法（ArrayList 的方法是虚拟方法） ，这样可以利用函数内联来提高性能（虚函数不可以被内联）；

--

C#数据结构下载：CSharp数据结构(2.0版)电子书.rar