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

素颜马尾好姑娘i 2021-09-18 03:28 284阅读 0赞

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

双向链表：在结点中设连个引用域，一个保存直接前驱节点的地址，叫prev，一个直接后继结点的地址，叫next。

双向链表相对单向链表只是多了一个字段prev。

代码实现：

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 DbNode<T>
        {
            private T data;//数据域
            private DbNode<T> prev;//前驱引用域
            private DbNode<T> next;//后驱引用域
    
            //构造器
            public DbNode()
            {
                data = default(T);
                next = null;
            }
            public DbNode(T val)
            {
                data = val;
                next = null;
            }
            public DbNode(DbNode<T> p)
            {
                next = p;
            }
            public DbNode(T val, DbNode<T> p)
            {
                data = val;
                next = p;
            }
    
            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; }
            }
        }
    
        class DlinkList<T> : IlinarList<T>
        {
            private DbNode<T> start;//双向链表的头引用
            private int length;//双链表的长度
    
            /// <summary>
            /// 初始化双向链表
            /// </summary>
            public DlinkList()
            {
                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 (i < 1 || i > length)
                {
                    Console.WriteLine("Position is error");
                    return;
                }
                DbNode<T> current = start;
                if (i == 1)
                {
                    start = current.Next;
                    current = null;
                    length--;
                }
                DbNode<T> previous = null;
                int j = 1;
                while (j<i&&current .Next !=null)
                {
                    previous = current;
                    current = current.Next;
                    j++;
                }
    
                if (i == j)
                {
                    previous.Next = current.Next;
                    if(current .Next !=null )  //不加判断是否可以？
                    current.Next.Prev = previous;
                    previous = null; //为什么？
                    current = null;
                    length--;
                }
                else
                {
                    Console.WriteLine("The node is not exist");
                }
    
                //if (i == j) //这种方式是否可以？
                //{
                //    previous.Next = current.Next;
                //    current.Next.Prev = previous;
                //    current = null;
                //    length--;
                //}
                //else
                //{
                //    Console.WriteLine("The node is not exist");
                //}
            }
    
            /// <summary>
            /// 在双向链表的末尾追加数据元素
            /// </summary>
            /// <param name="a"></param>
            public void InsertNode(T a)
            {
                DbNode<T> newnode = new DbNode<T>(a);
    
                if (IsEmpty())
                {
                    start = newnode;
                    length++;
                    return;
                }
    
                DbNode<T> current = start;
                while (current .Next !=null)
                {
                    current = current.Next;
                }
                current.Next = newnode;
                newnode.Prev = current;
                newnode.Next = null;
                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||IsEmpty())
                {
                    Console.WriteLine("List is empty or Position is error");
                    return;
                }
    
                DbNode<T> newnode = new DbNode<T>(a);
                if (i == 1)
                {
                    newnode.Next = start;
                    start = newnode;
                    length++;
                    return;
                }
    
                DbNode<T> current = start;
                DbNode<T> previous = null;
    
                int j = 1;
                while (j < i && current!= null)
                {
                    previous = current;
                    current = current.Next;
                    j++;
                }
                if (j == i)
                {
                    newnode.Next = current;
                    newnode.Prev = previous;
    
                    if (current != null)
    
                    current.Prev = newnode;
                    previous.Next = newnode;
    
                    length++;
                }
    
                这样可以吗？
                //int j = 1;
                //while (j<i &&current .Next !=null)
                //{
                //    previous = current;
                //    current = current.Next;
                //    j++;
                //}
                //if (j == i)
                //{
                //    newnode.Next = current;
                //    newnode.Prev = previous;
                //    current.Prev = newnode;
                //    previous.Next = newnode;
    
                //    length++;
                //}
            }
    
            /// <summary>
            /// 获得双向链表的第i个数据元素
            /// </summary>
            /// <param name="i"></param>
            /// <returns></returns>
            public T SearchNode(int i)
            {
                if(i<1||i>length ||IsEmpty())
                {
                    Console.WriteLine("List is empty or Position is error");
                    return default(T);
                }
    
                DbNode<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);
                }
    
                DbNode<T> current = start;
                int i = 1;
                while (current !=null &&!current .Data .ToString ().Contains (value .ToString()))
                {
                    current = current.Next;
                    i++;
                }
                if(current !=null)
                {
                    return current.Data;
                }else
                {
                    return default(T);
                }
            }
        }
    }