數據結構(C#)：循環鏈表（1）

循環鏈表可以是單鏈表，也可以是雙鏈表。鏈表的尾節點的後繼節點指向頭結點便成了循環鏈表。

我們在這裡繼承雙鏈表實現循環鏈表，當到達雙鏈表的表尾時，讓游標指向第0個節點；當到達雙鏈表 的開頭時，讓游標指向結尾節點，這樣就實現了循環雙鏈表。結尾用一個經典的約瑟夫問題來作循環鏈表 的應用示例。

1.循環鏈表代碼：

/*
* File　　 :　 CircularlyLinkedList.cs
* Author　 :　 Zhenxing Zhou
* Date　　 :　 2008-12-07
* Blog　　 :　 http://www.xianfen.Net/
*/
using System;

namespace Xianfen.Net.DataStructure
{
　　 public class CircularlyLinkedList<T> : DoubleLinkedList<T>
　　 {
　　　　 private DoubleLinkedListNode<T> m_CurrentNode;
　　　　 private int m_CurrentIndex;

　　　　 public int CurrentIndex
　　　　 {
　　　　　　 get { return m_CurrentIndex; }
　　　　 }

　　　　 public CircularlyLinkedList()
　　　　　　 : base()
　　　　 {
　　　　　　 m_CurrentNode = m_Head.Next;
　　　　　　 m_CurrentIndex = 0;
　　　　 }

　　　　 public CircularlyLinkedList(T t)
　　　　　　 : base(t)
　　　　 {
　　　　　　 m_CurrentNode = m_Head.Next;
　　　　　　 m_CurrentIndex = 0;
　　　　 }

　　　　 public T GetCurrent()
　　　　 {
　　　　　　 if (m_Count == 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException();
　　　　　　 }

　　　　　　 return m_CurrentNode.Value;
　　　　 }

　　　　 public T GetNext()
　　　　 {
　　　　　　 if (m_Count == 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException();
　　　　　　 }

　　　　　　 if (m_CurrentNode != null)
　　　　　　 {
　　　　　　　　 m_CurrentNode = m_CurrentNode.Next;
　　　　　　　　 m_CurrentIndex++;
　　　　　　 }

　　　　　　 if (m_CurrentNode == null)
　　　　　　 {
　　　　　　　　 m_CurrentNode = m_Head.Next;
　　　　　　　　 m_CurrentIndex = 0;
　　　　　　 }

　　　　　　 return m_CurrentNode.Value;
　　　　 }

　　　　 public T GetPrevious()
　　　　 {
　　　　　　 if (m_Count == 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException();
　　　　　　 }

　　　　　　 if (m_CurrentNode != null)
　　　　　　 {
　　　　　　　　 m_CurrentNode = m_CurrentNode.Prior;
　　　　　　　　 m_CurrentIndex--;
　　　　　　 }

　　　　　　 if (m_CurrentNode == null || m_CurrentNode == m_Head)
　　　　　　 {
　　　　　　　　 m_CurrentNode = m_Tail;
　　　　　　　　 m_CurrentIndex = m_Count - 1;
　　　　　　 }

　　　　　　 return m_CurrentNode.Value;
　　　　 }
　　 }
}