用单链表解决线性表的编程问题

红太狼 2021-09-18 03:26 224阅读 0赞

用单链表解决线性表的编程问题 ：

链表分为单链表，双链表，循环列表等多种类型。

在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像，成为结点（Node）。把存储数据元素本身信息的域成为节点的数据域，把存储与它相邻数据元素的存储地址信息的域称为结点的引用域。

如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表称为单链表。

单链表是最简单的链表，其中每个结点指向列表中的下一个结点，最后一个结点不指向任何其他结点，它指向NULL。这意味着指向NULL的结点代表列表结束。

带头节点单链表的结点示意图：

![201902251250039.png][]

代码实现：

using System;
    
    namespace 用单链表解决线性表的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
        interface IlinarList<T>
        {
            void InsertNode(T a, int i);//插入数据元素(这里只讲前插)。插入结点有3种情况：开头插入，中间插入，末尾插入
            void DeleteNode(int i);     //删除数据元素.
            T SearchNode(int i);//查找表元素
            T SearchNode(T value);//定位元素
            int GetLength();//求表长度
            void Clear();//清空操作
            bool IsEmpty();//判断线性表是否为空
        }
    
        //单链表的结点
        class SNode<T>
        {
            private T data;//数据域
            private SNode<T> next;//引用域
    
            //数据域属性
            public T Data
            {
                get { return data; }
                set { data = value; }
            }
    
            //引用域属性
            public SNode <T> Next
            {
                get { return next; }
                set { next = value; }
            }
    
            public SNode (T val,SNode <T> p)
            {
                data = val;
                next = p;
            }
            public SNode(T val)
            {
                data = val;
                next = null;
            }
            public SNode (SNode <T> p)
            {
                next = p;
                data = default(T);
            }
            public SNode()
            {
                data = default(T);
                next = null;
            }
        }
    
        class SLinkList<T> : IlinarList<T>
        {
            private SNode<T> start;//单链表的头引用
            private int length;//单链表的长度
    
            /// <summary>
            /// 初始化单链表，即创建一个空的单链表
            /// </summary>
            public SLinkList() 
            {
                start = null;
            }
    
            /// <summary>
            /// 判断单链表是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if(start ==null)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 清空单链表
            /// </summary>
            public void Clear()
            {
                start = null;
            }
    
            /// <summary>
            /// 求单链表的长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return length;
            }
    
            /// <summary>
            /// 删除单链表的第i个数据元素
            /// </summary>
            /// <param name="i"></param>
            public void DeleteNode(int i)
            {
                if(IsEmpty ()||i<1||i>length)
                {
                    Console.WriteLine("Link is empty or Position is error");
                }
    
                SNode<T> current = start;
                if (i == 1)
                {
                    start = current.Next;
                    length--;
                    return;
                }
    
                SNode<T> previous = null;
                int j = 1;
                while (j < i&&current .Next !=null )
                {
                    previous = current;
                    current = current.Next;            
                    j++;
                }
                if (j == i)
                {
                    previous.Next = current.Next;
                    current = null;
                    length--;
                }
                else
                {
                    Console.WriteLine("The node is not exist");
                }
            }
    
            /// <summary>
            /// 在单链表末尾追加数据元素
            /// </summary>
            /// <param name="a"></param>
            public void InsertNode(T a)
            {
                if(start ==null) //这里我觉得还可以写成 if(IsEmpty())
                {
                    start = new SNode<T>(a);
                    length++;
                    return;
                }else
                {
                    SNode<T> current = start;
                    while (current.Next !=null)
                    {
                        current = current.Next;
                    }
                    current.Next = new SNode<T>(a);
                    length++;
                }
            }
    
            /// <summary>
            /// 在单链表的第i个数据元素的位置前插入一个数据元素
            /// </summary>
            /// <param name="a"></param>
            /// <param name="i"></param>
            public void InsertNode(T a, int i)
            {
                if(i<1||i>length + 1)
                {
                    Console.WriteLine("Position is error");
                    return;
                }
                SNode<T> newnode = new SNode<T>(a);
    
                //在空链表或第一个元素前插入第一个元素
                if (i == 1)
                {
                    newnode.Next = start;
                    start = newnode;
                    length++;
                    return;
                }
    
                //在单链表的两个元素之间插入一个元素
                SNode<T> current = start;
                SNode<T> previous = null;
                int j = 1;
                while (current !=null &&j<i)
                {
                    previous = current;
                    current = current.Next;
                    j++;
                }
                if (j == i)
                {
                    previous.Next = newnode;
                    newnode.Next = current;
                    length++;
                }
            }
    
            /// <summary>
            /// 获得单链表的第i个数据元素
            /// </summary>
            /// <param name="i"></param>
            /// <returns></returns>
            public T SearchNode(int i)
            {
                if(IsEmpty() || i < 1 || i > length)
                {
                    Console.WriteLine("List is empty or Position is error");
                    return default(T);
                }
                SNode<T> current = start;
                int j = 1;
                while (j<i&&current .Next !=null)
                {
                    current = current.Next;
                    j++;
                }
                if (j == i)
                {
                    return current.Data;
                }else
                {
                    Console.WriteLine("The node is not exist");
                    return default(T); 
                }
                
            }
    
            /// <summary>
            /// 在单链表中查找值为value的数据元素
            /// </summary>
            /// <param name="value"></param>
            /// <returns></returns>
            public T SearchNode(T value)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("List is empty");
                    return default(T);
                }
                SNode<T> current = start;
    
                int i = 1;
                while (current != null && !current.Data.ToString().Contains(value.ToString()))
                {
                    current = current.Next;
                    i++;
                }
    
                //while (current != null && !current.Data.ToString().Contains(value.ToString())) //我觉得这样也可以，没有必要添加i
                //{
                //    current = current.Next;
                //}
    
                if (current !=null)
                {
                    return current.Data;
                }else
                {
                    return default(T);
                }
            }
        }
    }

[201902251250039.png]: /images/20210725/b1541cc099314a8291c7340248e202e9.png