循環清單的實作

我們将在單連結清單的基礎上讨論循環連結清單的實作，循環連結清單中的節點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