C#上機題 - 雙向循環鏈表

本文繼續《C#上機題的OO - 策略模式》中的題目，但這是使用的是雙向循環鏈表。當第一次看到這題我首先想到的是循環鏈表，但題目要求面向對象的方法，汗~

首先是雙向鏈表的節點類

1　///　<summary>
2　　///　雙向鏈表節點
3　　///　</summary>
4　　///　<typeparam　name="T"></typeparam>
5　　public　class　DoubleLinkNode<T>
6　　{
7　　　public　DoubleLinkNode()　{　}
8　　　public　DoubleLinkNode(T　item)
9　　　{
10　　　　Value　=　item;
11　　　}
12　　　///　<summary>
13　　　///　節點值
14　　　///　</summary>
15　　　public　T　Value　{　get;　set;　}
16　　　///　<summary>
17　　　///　下一個節點
18　　　///　</summary>
19　　　public　DoubleLinkNode<T>　Next　{　get;　set;　}
20　　　///　<summary>
21　　　///　前一個節點
22　　　///　</summary>
23　　　public　DoubleLinkNode<T>　Previous　{　get;　set;　}
24　　　public　override　string　ToString()
25　　　{
26　　　　return　Value.ToString();
27　　　}
28　}

這裡使用的是泛型類，他的優勢就不討論了，下面是循環鏈表類

///　<summary>
　　　　///　雙向循環鏈表
　　　　///　</summary>
　　　　///　<typeparam　name="T"></typeparam>
　　　　public　class　CircleList<T>　:　IEnumerable<T>
　　　　{
　　　　　　　　private　int　currentIndex;
　　　　　　　　private　DoubleLinkNode<T>　current;
　　　　　　　　///　<summary>
　　　　　　　　///　頭節點
　　　　　　　　///　</summary>
　　　　　　　　public　DoubleLinkNode<T>　First　{　get;　private　set;　}
　　　　　　　　///　<summary>
　　　　　　　　///　尾節點
　　　　　　　　///　</summary>
　　　　　　　　public　DoubleLinkNode<T>　Last　{　get;　private　set;　}
　　　　　　　　///　<summary>
　　　　　　　　///　節點數
　　　　　　　　///　</summary>
　　　　　　　　public　int　Count　{　get;　private　set;　}
　　　　　　　　///　<summary>
　　　　　　　　///　索引
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="index"></param>
　　　　　　　　///　<returns></returns>
　　　　　　　　public　DoubleLinkNode<T>　this[int　index]
　　　　　　　　{
　　　　　　　　　　　　get
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　if　(Count　-　index　<　index)
　　　　　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　　　　　currentIndex　=　Count　-　1;
　　　　　　　　　　　　　　　　　　　　current　=　Last;
　　　　　　　　　　　　　　　　　　　　while　(currentIndex　>　0)
　　　　　　　　　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　　　　　　　　　if　(currentIndex　==　index)　break;
　　　　　　　　　　　　　　　　　　　　　　　　currentIndex--;
　　　　　　　　　　　　　　　　　　　　　　　　current　=　current.Previous;
　　　　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　else
　　　　　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　　　　　Reset();
　　　　　　　　　　　　　　　　　　　　while　(currentIndex　<　Count　-　1)
　　　　　　　　　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　　　　　　　　　if　(currentIndex　==　index)　break;
　　　　　　　　　　　　　　　　　　　　　　　　currentIndex++;
　　　　　　　　　　　　　　　　　　　　　　　　current　=　current.Next;
　　　　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　return　current;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　在尾部添加節點
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="node"></param>
　　　　　　　　public　void　AddLast(DoubleLinkNode<T>　node)
　　　　　　　　{
　　　　　　　　　　　　if　(Last　==　null)　Last　=　node;
　　　　　　　　　　　　if　(First　==　null)　First　=　node;
　　　　　　　　　　　　Last.Next　=　node;
　　　　　　　　　　　　node.Previous　=　Last;
　　　　　　　　　　　　Last　=　node;
　　　　　　　　　　　　node.Next　=　First;
　　　　　　　　　　　　First.Previous　=　node;
　　　　　　　　　　　　Count++;
　　　　　　　　　　　　Last.Next　=　First;
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　在尾部添加節點
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="item"></param>
　　　　　　　　public　void　AddLast(T　item)
　　　　　　　　{
　　　　　　　　　　　　DoubleLinkNode<T>　node　=　new　DoubleLinkNode<T>(item);
　　　　　　　　　　　　AddLast(node);
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　移除節點
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="node"></param>
　　　　　　　　public　void　Remove(DoubleLinkNode<T>　node)
　　　　　　　　{
　　　　　　　　　　　　node.Previous.Next　=　node.Next;
　　　　　　　　　　　　node.Next.Previous　=　node.Previous;
　　　　　　　　　　　　Count--;
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　移除節點
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="item"></param>
　　　　　　　　public　void　Remove(T　item)
　　　　　　　　{
　　　　　　　　　　　　DoubleLinkNode<T>　node　=　Find(o　=>　o.Value.Equals(item));
　　　　　　　　　　　　if　(node　==　null)　return;
　　　　　　　　　　　　Remove(node);
　　　　　　　　　　　　Count--;
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　查找節點
　　　　　　　　///　</summary>
　　　　　　　　///　<param　name="match"></param>
　　　　　　　　///　<returns></returns>
　　　　　　　　public　DoubleLinkNode<T>　Find(Predicate<DoubleLinkNode<T>>　match)
　　　　　　　　{
　　　　　　　　　　　　Reset();
　　　　　　　　　　　　while　(currentIndex　<　Count)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　if　(match(current))
　　　　　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　　　　　return　current;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　currentIndex++;
　　　　　　　　　　　　　　　　current　=　current.Next;
　　　　　　　　　　　　}
　　　　　　　　　　　　return　null;
　　　　　　　　}
　　　　　　　　public　IEnumerator<T>　GetEnumerator()
　　　　　　　　{
　　　　　　　　　　　　Reset();
　　　　　　　　　　　　while　(currentIndex　<　Count)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　yield　return　current.Value;
　　　　　　　　　　　　　　　　current　=　current.Next;
　　　　　　　　　　　　　　　　currentIndex++;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　IEnumerator　IEnumerable.GetEnumerator()
　　　　　　　　{
　　　　　　　　　　　　return　this.GetEnumerator();
　　　　　　　　}
　　　　　　　　public　override　string　ToString()
　　　　　　　　{
　　　　　　　　　　　　string　s　=　string.Empty;
　　　　　　　　　　　　Reset();
　　　　　　　　　　　　while　(currentIndex　<　Count)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　s　+=　string.Format("Node:{0}　　　NextNode:{1}　　　PreviousNode:{2}\r\n",　current,　current.Next,　current.Previous);
　　　　　　　　　　　　　　　　currentIndex++;
　　　　　　　　　　　　　　　　current　=　current.Next;
　　　　　　　　　　　　}
　　　　　　　　　　　　return　s;
　　　　　　　　}
　　　　　　　　///　<summary>
　　　　　　　　///　清除
　　　　　　　　///　</summary>
　　　　　　　　public　void　Clear()
　　　　　　　　{
　　　　　　　　　　　　Count　=　0;
　　　　　　　　　　　　First　=　null;
　　　　　　　　　　　　Last　=　null;
　　　　　　　　}
　　　　　　　　private　void　Reset()
　　　　　　　　{
　　　　　　　　　　　　currentIndex　=　0;
　　　　　　　　　　　　current　=　First;
　　　　　　　　}
　　　　}

由於沒用使用DoubleLinkNode<T>[] 來存儲數據，所以索引的處理顯得非常的麻煩（如果用了數組就存在鏈表的容量問題），希望高手們能給出好的方法。

下面就是具體實現了

class　Program
{
　static　void　Main(string[]　args)
　{
　　//初始化數據
　　CircleList<Person>　list　=　new　CircleList<Person>();
　　for　(int　i　=　0;　i　<　17;　i++)
　　{
　　　list.AddLast(new　Person(i　+　1));
　　}
　　//當前報數人
　　DoubleLinkNode<Person>　current　=　list.First;
　　//報數序號
　　int　k　=　0;
　　//循環報數
　　while　(list.Count　>　1)
　　{
　　　k++;
　　　Console.WriteLine(string.Format("{0}:{1}",　current.Value.Id,　k));
　　　if　(k　%　3　==　0)
　　　　list.Remove(current);
　　　current　=　current.Next;
　　}
　　Console.WriteLine(string.Format("Last　Person:{0}",　current.Value.Id));
　　Console.Read();
　}
}
///　<summary>
///　玩家
///　</summary>
public　class　Person
{
　public　Person(int　id)
　{
　　this.Id　=　id;
　}
　public　int　Id　{　get;　set;　}
}

下面是結果