我曾經去一家游戲公司面試時遇到一個筆試題，大意就是說有一群人出去旅游，在河中遇到了大風，然後用轉盤決定誰在留在船上，誰自己跳下去自行解決生存問題。大家圍成一個圈，啟動轉盤，轉盤指向誰就從睡開始數數，當有人數到13時，誰就跳下去，然後從下一個人開始從頭數，當再有人數到13時，繼續上一個循環。
當時題意沒看太明白，我直接用了一個單向鏈表解決那個事情，結果最後運行的結果總是剩下最開始的兩口人，最後在跟面試官談的時候才猛然想起圍成一個圈其實就應該用循環鏈表來解決這個問題。
下面看看循環鏈表的示意圖：
循環鏈表與單項鏈表唯一的區別就是單向鏈表尾部不指向任何元素，而循環鏈表的尾部指向鏈表的頭部，示例代碼如下：
using System;
using System.Collections.Generic;
using System.Text;
namespace DataStructure
{
/// <summary>
/// 循環鏈表
/// </summary>
/// <typeparam name="T"></typeparam>
public class LoopLink<T> : IListDS<T>
{
/// <summary>
/// 鏈表頭屬性
/// </summary>
private LoopLinkNode<T> head;
public LoopLinkNode<T> Head
{
set
{
head = value;
head.Next = head;
}
get { return head; }
}
/// <summary>
/// 構造函數，構造空鏈表
/// </summary>
public LoopLink()
{
this.head = null;
}
/// <summary>
/// 構造函數
/// </summary>
/// <param name="head"></param>
public LoopLink(LoopLinkNode<T> head)
{
this.head = head;
this.head.Next = this.head;
}
/// <summary>
/// 實現索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public LoopLinkNode<T> this[int index]
{
set
{
if (IsEmpty())
throw new Exception("鏈表為空");
if (index < 0 || index > this.GetLength() - 1)
throw new Exception("索引超出鏈表長度");
LoopLinkNode<T> node = head;
for (int i = 0; i < index; i++)
{
node = node.Next;
}
node.Data = value.Data;
node.Next = value.Next;
}
get
{
if (IsEmpty())
throw new Exception("鏈表為空");
if (index < 0 || index > this.GetLength() - 1)
throw new Exception("索引超出鏈表長度");
LoopLinkNode<T> node = head;
for (int i = 0; i < index; i++)
{
node = node.Next;
}
return node;
}
}
/// <summary>
/// 獲取鏈表長度
/// </summary>
/// <returns></returns>
public int GetLength()
{
if (IsEmpty())
return 0;
int length = 1;
LoopLinkNode<T> temp = head;
while (temp.Next != head)
{
temp = temp.Next;
length++;
}
return length;
}
/// <summary>
/// 清空鏈表所有元素
/// </summary>
public void Clear()
{
this.head = null;
}
/// <summary>
/// 檢查鏈表是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (head == null)
return true;
return false;
}
/// <summary>
/// 檢查鏈表是否已滿
/// </summary>
/// <returns></returns>
public bool IsFull()
{
return false;
}
/// <summary>
/// 在鏈表的最末端添加一個新項
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
if (IsEmpty())
{
this.Head = new LoopLinkNode<T>(item);
return;
}
LoopLinkNode<T> node = new LoopLinkNode<T>(item);
LoopLinkNode<T> temp = head;
while (temp.Next != head)
{
temp = temp.Next;
}
temp.Next = node;
node.Next = head;
}
/// <summary>
/// 在鏈表的指定位置添加一個新項
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
if (IsEmpty())
throw new Exception("數據鏈表為空");
if (index < 0 || index > this.GetLength())
throw new Exception("給定索引超出鏈表長度");
LoopLinkNode<T> temp = new LoopLinkNode<T>(item);
LoopLinkNode<T> node = head;
if (index == 0)
{
while (node.Next != head)
{
node = node.Next;
}
node.Next = temp;
temp.Next = this.head;
return;
}
for (int i = 0; i < index - 1; i++)
{
node = node.Next;
}
LoopLinkNode<T> temp2 = node.Next;
node.Next = temp;
temp.Next = temp2;
}
/// <summary>
/// 刪除鏈表指定位置的項目
/// </summary>
/// <param name="index"></param>
public void Delete(int index)
{
if (IsEmpty())
throw new Exception("鏈表為空，沒有可清除的項");
if (index < 0 || index > this.GetLength() - 1)
throw new Exception("給定索引超出鏈表長度");
LoopLinkNode<T> node = head;
if (index == 0)
{
while (node.Next != head)
{
node = node.Next;
}
this.head = head.Next;
node.Next = this.head;
return;
}
for (int i = 0; i < index - 1; i++)
{
node = node.Next;
}
node.Next = node.Next.Next;
}
/// <summary>
/// 獲取鏈表指定位置的元素的值
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetItem(int index)
{
if (index < 0 || index > this.GetLength() - 1)
throw new Exception("索引超出鏈表長度");
LoopLinkNode<T> node = head;
for (int i = 0; i < index; i++)
{
node = node.Next;
}
return node.Data;
}
/// <summary>
/// 根據給定的值查找鏈表中哪個元素為這個值，如果鏈表中存在兩個元素值相同，則取排在鏈表前面的元素
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
if (IsEmpty())
throw new Exception("鏈表為空");
LoopLinkNode<T> node = head;
int index = 0;
while (node.Next != head)
{
if (node.Data.Equals(value))
return index;
else
index++;
node = node.Next;
}
if (node.Data.Equals(value))
return index;
else
return -1;
}
}
public class LoopLinkNode<T>
{
private T data;
private LoopLinkNode<T> next;
public T Data
{
set { data = value; }
get { return data; }
}
public LoopLinkNode<T> Next
{
set { next = value; }
get { return next; }
}
public LoopLinkNode()
{
data = default(T);
next = null;
}
public LoopLinkNode(T data)
{
this.data = data;
next = null;
}
public LoopLinkNode(T data, LoopLinkNode<T> item)
{
this.data = data;
this.next = item;
}
}
}
摘自 魯信的專欄
