循环列表的实现

我们将在单链表的基础上讨论循环链表的实现，循环链表中的节点node沿用单链表中的节点。循环链表的算法思想基本上与单链表没有什么差异，唯一比较大的差异就是原来我们通过判断node.next==null来判断链表的结束，现在改成判断node.next==Head，因为我们已经把尾节点链接到头节点上，在逻辑上形成循环链表。具体的代码如下所示

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace DataStructure

{

    /// <summary>

    /// 循环链表

    /// </summary>

    /// <typeparam name="T">类型</typeparam>

    class LoopList<T>:IListDS<T>

    {

        class Node<T>

        {

            private T data;

            /// <summary>

            /// 数据域

            /// </summary>

            public T Data

            {

                get {return data;}

                set { data = value;}

            }

            private Node<T> next;

            /// 引用域

            public Node<T> Next

                get {return next;}

                set { next = value;}

            //头结点构造函数

            public Node(Node<T> node)

                :this(default(T), node)

            //普通结点构造函数

            public Node(T data, Node<T> node)

                this.Data = data;

                this.Next = node;

            /// 空构造函数

            public Node()

                :this(default(T),null)

            //尾结点构造函数

            public Node(T data)

                :this(data,null)

        }

        Node<T> Head;//头节点

        Node<T> Rear;//尾节点

        public LoopList()

        public LoopList(T[] t)

            this.Head =new Node<T>(t[0]);

            Node<T> Last;

            Last = Head;

            for(int i =1; i < t.Length; i++)

                //尾插入法

                Last.Next =new Node<T>(t[i]);

                Last = Last.Next;

            Rear = Last;

            Last.Next = Head;

        /// <summary>

        /// 在结尾附加一个元素

        /// </summary>

        /// <param name="item">元素</param>

        /// <returns>操作的状态</returns>

        public States Append(T item)

            //(1)头结点没有

            if(Head ==null)

                Head =new Node<T>(item,Rear);

                return States.Success;

            if(Rear==null)

                Rear =new Node<T>(item, Head);

            //在尾节点后面附加一个节点

            Rear.Next =new Node<T>(item, Head);

            //新附加在链表后面的节点变成尾节点

            Rear = Rear.Next;

            return States.Success;

        /// 清空

        publicvoid Clear()

            this.Head =null;

            this.Rear =null;

        /// 删除

        /// <param name="index"></param>

        /// <param name="states"></param>

        /// <returns></returns>

        public T Delete(int index,out States states)

            bool isIndexTrue = index <0|| index >=this.GetLength();

            if(IsEmpty()==true|| isIndexTrue)

                states = States.Fail;

                returndefault(T);

            //找到指定的结点

            Node<T> Current = Head;

            Node<T> Previous = Head;

            int Count =0;

            while(Count != index && Current.Next != Head)

                Previous = Current;

                Current = Current.Next;

                Count++;

            T ValueToDel = Current.Data;

            //是否是头结点

            if(Count ==0)

                if(this.GetLength()==1)

                {

                    Head = Rear =null;

                }

                else

                    Head = Current.Next;

                    Rear.Next = Head;

            //是否是普通的结点

            if(Count !=0&& Current.Next !=null)

                Previous.Next = Current.Next;

            //是否是最后一个结点

            if(Count !=0&& Current.Next ==null)

                Previous.Next = Head;

                Rear = Previous;

            //删除结点

            states = States.Success;

            return ValueToDel;

        public T GetElem(int i)

            bool isIndexTrue = i <0|| i >=this.GetLength();

            if(IsEmpty()==true||isIndexTrue)

            Node<T> Last = Head;

            while(Count != i && Last.Next != Head)

            return Last.Data;

        /// 获取链表的长度

        publicint GetLength()

                return0;

            while(Last.Next != Head)//通过判断是否是Head（头节点），判断当前元素是否是最后一个节点

            return++Count;

        public States Insert(T item,int index)

            bool isIndexTrue = index <0|| index >this.GetLength();

            if(isIndexTrue)

                return States.Fail;

            //如果链表为空

            if(IsEmpty()==true)

                Head =new Node<T>(item);

            //如果是第一个结点

            if(index ==0)

                Node<T> node =new Node<T>(item);

                node.Next = Head;

                Head = node;

                if(Rear!=null)

            //如果是普通的结点

            while(Count != index -1&& Previous.Next != Head)//因为要取到插入位置的前一个节点所以用Count != index-1的判断

                Previous = Previous.Next;

            }          

            //如果是最后一个结点

            if(this.GetLength()== index)

                Previous.Next =new Node<T>(item);

                Previous.Next.Next = Head;

                Rear = Previous.Next;

            if(Count == index -1)

                node.Next = Previous.Next;

                Previous.Next = node;

        /// 判断链表是否为空

        /// <returns>是否为空</returns>

        publicbool IsEmpty()

            return Head ==null?true:false;

        publicint Locate(T value,out States states)

            int Index =0;

            while(Last.Next != Head &&(!value.Equals(Last.Data)))

                Index++;

            return Index;

    }

}

 本文转自陈哈哈博客园博客，原文链接http://www.cnblogs.com/kissazi2/p/3193975.html如需转载请自行联系原作者

kissazi2