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

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

我們在這裡繼承雙鏈表實現循環鏈表，當到達雙鏈表的表尾時，讓游標指向第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;
　　　　 }
　　 }
}

2.用循環鏈表解決約瑟夫問題

問題描述：N個人圍成圓圈，從1開始報數，到第M個人令其出列，然後下一個人繼續從1開始報數，到 第M個人令其出列，如此下去，直到只剩一個人為止。顯示最後一個人為剩者。

代碼：

const int M = 9;
const int N = 7;
CircularlyLinkedList<int> list = new CircularlyLinkedList<int>();

//填充循環鏈表
for (int i = 1; i < M; i++)
{
　　 list.Add(i);
}

int tempCounter = 0;

while (list.Count > 1)
{
　　 tempCounter++;
　　 list.GetPrevious();

　　 // 選中者出列
　　 if (tempCounter == N)
　　 {
　　　　 tempCounter = 0;
　　　　 Console.WriteLine(list.GetCurrent() + " 出列！");
　　　　 list.RemoveAt(list.CurrentIndex);
　　 }
}

Console.WriteLine(list.GetNext() + " 為剩者");

運行結果：

2 出列！
3 出列！
1 出列！
7 出列！
4 出列！
8 出列！
6 出列！
5 為剩者如果把上面高亮顯示的語句改為：list.GetNext();

運行結果變為：

7 出列！
6 出列！
8 出列！
2 出列！
5 出列！
1 出列！
3 出列！
4 為剩者