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

逃离我推掉我的手 2022-03-12 08:42 207阅读 0赞

** 什么是线性表**

线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：（ 1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；（ 2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。

线性表就是位置有先后关系，一个接着一个排列的数据结构。

**CLR中的线性表**

c\# 1.1 提供了一个非泛型接口IList接口，接口中的项是object,实现了IList解扣子的类有ArrayList,ListDictionary,StringCollection,StringDictionary.

c\# 2.0 提供了泛型的IList<T>接口，实现了List<T>接口的类有List<T>

**线性表的接口定义**

public interface IListDS<T> \{

int GetLength(); //求长度

void Clear(); //清空操作

bool IsEmpty(); //判断线性表是否为空

void Add(T item); //附加操作

void Insert(T item, int i); //插入操作

T Delete(int i); //删除操作

T GetElem(int i); //取表元

T this\[int index\]\{get;\}//定义一个索引器 获取元素

int Locate(T value); //按值查找

**线性表的实现方式**

线性表的实现方式有下面几种：顺序表、单链表、双向链表、循环链表

**使用自带的线性表List来进行操作**

![20190305165922990.png][]

**顺序表**

在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)，如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。

![2019030517030229.png][]

**顺序表的存储**

假设顺序表中的每个数据元素占w个存储单元，设第i个数据元素的存储地址为Loc(ai)，则有：

Loc(ai)= Loc(a1)+(i-1)\*w 1≤i≤n式中的Loc(a1)表示第一个数据元素a1的存储地址，也是顺序表的起始存储地址，称为顺序表的基地址(Base Address)。也就是说，只要知道顺序表的基地址和每个数据元素所占的存储单元的个数就可以求出顺序表中任何一个数据元素的存储地址。并且，由于计算顺序表中每个数据元素存储地址的时间相同，所以顺序表具有任意存取的特点。(可以在任意位置存取东西)

C\#语言中的数组在内存中占用的存储空间就是一组连续的存储区域，因此，数组具有任意存取的特点。所以，数组天生具有表示顺序表的数据存储区域的特性。

**顺序表的实现**

首先定义一个线性表的通用接口

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        //定义一个线性表表接口
        interface IListDS<T>
        {
            int GetLength(); //求长度
            void Clear(); //清空操作
            bool IsEmpty(); //判断线性表是否为空
            void Add(T item); //附加操作
            void Insert(T item, int i); //插入操作
            T Delete(int i); //删除操作
            T GetElem(int i); //取表元
            T this[int index] { get; }//定义一个索引器 获取元素
            int Locate(T value); //按值查找
        }
    }

定义一个顺序表的类，并实现它的基础功能

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        /// <summary>
        /// 顺序表实现方式
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class SeqList<T> : IListDS<T>
        {
            private T[] data;//用来存储数据
            private int count = 0;//表示存了多少个数据
    
            public SeqList(int size)//size就是最大容量
            {
                data = new T[size];
                count = 0;
            }
    
            public SeqList() : this(10)//调用上面的方法，默认构造函数 容量是10
            {
    
            }
    
            public T this[int index]
            {
                get
                {
                    return GetElem(index);
                }
            }
    
            public void Add(T item)
            {
                if (count == data.Length)//当前顺序表已经存满
                {
                    Console.WriteLine("当前顺序表已经存满！");
                }
                else
                {
                    data[count++] = item;
                }
            }
    
            public void Clear()
            {
                count = 0;
            }
    
            public T Delete(int i)
            {
                T temp = data[i];
                for(int index = i;index < count-1;index++)
                {
                    data[index] = data[index + 1];
                }
                count--;
                return temp;
            }
    
            public T GetElem(int i)
            {
                if (i >= 0 && i <= count - 1)
                {
                    return data[i];
                }
                else
                {
                    Console.WriteLine("索引不存在！");
                    return default(T);//返回一个T类型的默认值
                }
            }
    
            public int GetLength()
            {
                return count;
            }
    
            public void Insert(T item, int i)
            {
                for (int index = count - 1; index >= i; index--)
                {
                    data[index + 1] = data[index];
                }
                data[i] = item;
                count++;
    
            }
    
            public bool IsEmpty()
            {
                return count == 0;
            }
    
            public int Locate(T value)
            {
                for(int i = 0; i < count; i++)
                {
                    if (data[i].Equals(value))
                    {
                        return i;
                    }
                }
                return -1;
            }
        }
    }

验证我们建立的顺序表

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        class Program
        {
            static void Main(string[] args)
            {
                //1.使用BCL中自带的List线性表
                //List<int> intList = new List<int>();
                //intList.Add(1);
                //intList.Add(2);
                //intList.Add(3);
                //intList.Remove(1);
                //Console.WriteLine(intList.Count);
                //Console.WriteLine(intList[1]);//通过索引器访问元素
                //intList.Clear();
                //Console.WriteLine(intList.Count);
                //Console.ReadKey();
    
                //使用我们自己的线性表
                SeqList<String> seqList = new SeqList<string>();
                seqList.Add("123");
                seqList.Add("456");
                seqList.Add("789");
    
                Console.WriteLine(seqList.GetElem(0));//123
                Console.WriteLine(seqList[0]);//123
                seqList.Insert("777", 1);
    
                for (int i = 0; i < seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");//123 777 456 789
                }
                Console.WriteLine();
                seqList.Delete(0);
                for (int i = 0; i < seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");//777 456 789
                }
                Console.WriteLine();
                seqList.Clear();
                Console.WriteLine(seqList.GetLength());//0
    
                Console.ReadKey();
    
            }
        }
    }

![20190305201854588.png][]

**单链表**

顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻。因此，在顺序表中查找任何一个位置上的数据元素非常方便，这是顺序存储的优点。但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率。线性表的另外一种存储结构——链式存储(Linked Storage)，这样的线性表叫链表(Linked List)。链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此，在对链表进行插入和删除时不需要移动数据元素，但同时也失去了顺序表可随机存储的优点。

**单链表的存储**

链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。那么，怎么表示两个数据元素逻辑上的相邻关系呢？即如何表示数据元素之间的线性关系呢？为此，在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image)，称为结点(Node)。把存储据元素本身信息的域叫结点的数据域(Data Domain)，把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域(Reference Domain)。因此，线性表通过每个结点的引用域形成了一根“链条”，这就是“链表”名称的由来。

如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表(Singly Linked List)。把该引用域叫 next。单链表结点的结构如图所示，图中 data 表示结点的数据域。

![20190306195713280.png][]

**链式存储结构**

下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70][]

另外一种表示形式

![20190306195754102.png][]

**单链表节点定义**

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        /// <summary>
        /// 单链表的结点
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class Node<T>
        {
            private T data;//存储数据
            private Node<T> next;//用来指向下一个元素的指针
    
            public Node(T value)
            {
                data = value;
                next = null;
            }
    
            public Node(T value, Node<T> next)
            {
                this.data = value;
                this.next = next;
            }
    
            public Node(Node<T> next)
            {
                this.next = next;
            }
    
            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; }
            }
    
        }
    }

定义一个单链表的类，并实现它的基础功能

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        class LinkList<T> : IListDS<T>
        {
            private Node<T> head;//存储一个头结点
    
            public LinkList()
            {
                head = null;
            }
    
            public T this[int index]
            {
                get
                {
                    Node<T> temp = head;
                    for (int i = 0; i < index; i++)
                    {
                        temp = temp.Next;
                    }
                    return temp.Data;
                }
            }
    
            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;
                }
            }
    
            public void Clear()
            {
                head = null;
            }
    
            public T Delete(int i)
            {
                T data = default(T);
                if (i == 0)
                {
                    data = head.Data;
                    head = head.Next;
                }
                else
                {
                    Node<T> temp = head;
                    for (int index = 0; index < i - 1; index++)
                    {
                        temp = temp.Next;
                    }
                    Node<T> preNode = temp;
                    Node<T> currentNode = temp.Next;
                    data = currentNode.Data;
                    preNode.Next = currentNode.Next;
                }
                return data;
            }
    
            public T GetElem(int i)
            {
                return this[i];
            }
    
            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;
            }
    
            public void Insert(T item, int i)
            {
                Node<T> newNode = new Node<T>(item);
                if (i == 0)//插入到头结点
                {
                    newNode.Next = head;
                    head = newNode;
                }
                else
                {
                    Node<T> temp = head;
                    for (int index = 0; index < i - 1; index++)
                    {
                        temp = temp.Next;
                    }
                    Node<T> preNode = temp;
                    Node<T> currentNode = temp.Next;
                    newNode.Next = currentNode;
                    preNode.Next = newNode;
                }
            }
    
            public bool IsEmpty()
            {
                return head == null;
            }
    
            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;
                }
            }
        }
    }

验证我们的单链表

//使用我们自己的单链表
                LinkList<String> seqList = new LinkList<string>();
                seqList.Add("123");
                seqList.Add("456");
                seqList.Add("789");
    
                Console.WriteLine(seqList.GetElem(0));//123
                Console.WriteLine(seqList[0]);//123
                seqList.Insert("777", 1);
    
                for (int i = 0; i < seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");//123 777 456 789
                }
                Console.WriteLine();
                seqList.Delete(0);
                for (int i = 0; i < seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");//777 456 789
                }
                Console.WriteLine();
                seqList.Clear();
                Console.WriteLine(seqList.GetLength());//0
                Console.ReadKey();

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1][]

**双向链表**

前面介绍的单链表允许从一个结点直接访问它的后继结点，所以, 找直接后继结点的时间复杂度是 O(1)。但是,要找某个结点的直接前驱结点，只能从表的头引用开始遍历各结点。如果某个结点的 Next 等于该结点，那么，这个结点就是该结点的直接前驱结点。也就是说，找直接前驱结点的时间复杂度是 O(n)， n是单链表的长度。当然，我们也可以在结点的引用域中保存直接前驱结点的地址而不是直接后继结点的地址。这样，找直接前驱结点的时间复杂度只有 O(1)，但找直接后继结点的时间复杂度是 O(n)。如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1)，那么，需要在结点中设两个引用域，一个保存直接前驱结点的地址，叫 prev，一个直接后继结点的地址，叫 next，这样的链表就是双向链表(Doubly Linked List)。双向链表的结点结构示意图如图所示。

![20190310150835869.png][]

**双向链表节点实现**

public class DbNode<T>
    {
        private T data; //数据域
        private DbNode<T> prev; //前驱引用域
        private DbNode<T> next; //后继引用域
    //构造器
        public DbNode(T val, DbNode<T> p)
        {
            data = val;
            next = p;
        }
    
    //构造器
    
        public DbNode(DbNode<T> p)
        {
            next = p;
        }
    
    //构造器
        public DbNode(T val)
        {
            data = val;
            next = null;
        }
    
    //构造器
        public DbNode()
        {
            data = default(T);
            next = null;
        }
    
    //数据域属性
        public T Data
        {
            get { return data; }
            set { data = value; }
        }
    
    //前驱引用域属性
        public DbNode<T> Prev
        {
            get { return prev; }
            set { prev = value; }
        }
    
    //后继引用域属性
        public DbNode<T> Next
        {
            get { return next; }
            set { next = value; }
        }
    }

**双向链表插入示意图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2][]

**循环链表**

有些应用不需要链表中有明显的头尾结点。在这种情况下，可能需要方便地从最后一个结点访问到第一个结点。此时，最后一个结点的引用域不是空引用，而是保存的第一个结点的地址（如果该链表带结点，则保存的是头结点的地址），也就是头引用的值。带头结点的循环链表(Circular Linked List)如图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3][]

[20190305165922990.png]: /images/20220312/931a0e92477f48fea10ad18b4be2e076.png
[2019030517030229.png]: /images/20220312/8704d48b5508453ea1705efbb8b52d9f.png
[20190305201854588.png]: /images/20220312/1bb24df250434c9497dd76598634ce1d.png
[20190306195713280.png]: /images/20220312/072dfbfe042e4339bcefcede66a8f60f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70]: /images/20220312/0a04550df6294ba5b5543fbbadb1a25e.png
[20190306195754102.png]: /images/20220312/118a344b03f44409a741b533f0a9c63e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1]: /images/20220312/d114ea8d80de4be1bd2f1272b83139e4.png
[20190310150835869.png]: /images/20220312/fdf579fe453e44459b54fb830535506a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2]: /images/20220312/c22712a414ff4501922e9e5bc90fd20e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3]: /images/20220312/5698a162a2ca4bf18406b10ab17e961d.png