学习C#数据结构之线性表

清疚 2022-05-19 13:12 195阅读 0赞

**什么是线性表**

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

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

自己定义一个线性表接口

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 index);
            T Delete(int index);
            T this[int index] { get; }
            T GetEle(int index);
            int Locate(T value);
        }
    }

创建一个类继承接口

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        //顺序表实现方式
        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 GetEle(index);
                }
            }
    
            public void Add(T item)
            {
                if (count == data.Length) //当前数组已经存满
                {
                    Console.WriteLine("当前顺序表已经存满，不允许再存入");
                }
                else
                {
                    data[count] = item;
                    count++;
                }
            }
    
            public void Clear()
            {
                count = 0;
            }
    
            public T Delete(int index)
            {
                T temp = data[index];
                for(int i = index+1; i <count; i++)
                {
                    data[i - 1] = data[i];
                }
                count--;
                return temp;
            }
    
            public T GetEle(int index)
            {
                if(index >= 0 && index <= count - 1)
                {
                    return data[index];
                }
                else
                {
                    Console.WriteLine("索引不存在");
                    return default(T);
                }
            }
    
            public int GetLength()//取得数据的个数
            {
                return count;
            }
    
            public void Insert(T item, int index)
            {
                for (int i = count - 1; i >= index; i--)
                {
                    data[i + 1] = data[i];
                }
                data[index] = 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<string> strList = new List<string>();
                //strList.Add("123");
                //strList.Add("456");
                //strList.Add("789");
                //Console.WriteLine(strList[1]);
                //strList.Remove("789");
                //Console.WriteLine(strList.Count);
                //strList.Clear();
                //Console.WriteLine(strList.Count);
                //Console.ReadKey();
    
                //使用我们自己的顺序表
                SeqList<string> seqList = new SeqList<string>();
                seqList.Add("123");
                seqList.Add("456");
                seqList.Add("789");
                Console.WriteLine(seqList[0]);
                Console.WriteLine(seqList.GetEle(0));
    
                seqList.Insert("777", 1);
                for(int i =0;i<seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");
                }
                Console.WriteLine();
    
                seqList.Delete(0);
                for (int i = 0; i < seqList.GetLength(); i++)
                {
                    Console.Write(seqList[i] + " ");
                }
                Console.WriteLine();
                seqList.Clear();
                Console.WriteLine(seqList.GetLength());
                Console.ReadKey();
            }
        }
    }

结果如下图

![70][]

**单链表**

Node.cs

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        class Node<T>
        {
            //单链表的结点
            private T data;
            private Node<T> next;//指针 用来指向下一个元素
            public Node()
            {
                data = default(T);
                next = null;
            }
    
            public Node(T value)
            {
                data = value;
                next = null;
            }
    
            public Node(T data,Node<T> next)
            {
                this.data = data;
                this.next = next;
            }
    
            public Node(Node<T> next)
            {
                this.next = next;
            }
    
            public T Data
            {
                get { return data; }
                set { data = value; }
            }
    
            public Node<T> Next 
            {
                get { return next; }
                set { next = value; }
            }
        }
    }

LinkList.cs

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 = 1; 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 index)
            {
                T data = default(T);
                if(index == 0)
                {
                    data = head.Data;
                    head = head.Next;
                }
                else
                {
                    Node<T> temp = head;
                    for (int i = 1; i <= index - 1; i++)
                    {
                        //让temp向后移动位置
                        temp = temp.Next;
                    }
                    Node<T> preNode = temp;
                    Node<T> currentNode = temp.Next;
                    data = currentNode.Data;
                    Node<T> nextNode = currentNode.Next;
                    preNode.Next = nextNode;
                }
                return data;
            }
    
            public T GetEle(int index)
            {
                return this[index];
            }
    
            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 index)
            {
                Node<T> newNode = new Node<T>(item);
                if(index == 0)//插入到头结点
                {
                    newNode.Next = head;
                    head = newNode;
                }
                else
                {
                    Node<T> temp = head;
                    for(int i = 1; i <= index - 1; i++)
                    {
                        //让temp向后移动位置
                        temp = temp.Next;
                    }
                    Node<T> preNode = temp;
                    Node<T> currentNode = temp.Next;
                    preNode.Next = newNode;
                    newNode.Next = currentNode;
                }
            }
    
            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;
                }
            }
        }
    }

[70]: /images/20220519/31520be5ff4a4b2b9d6a252700fa6544.png