我们将在单链表的基础上讨论循环链表的实现，循环链表中的节点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;
/// <summary>
/// 引用域
/// </summary>
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;
}
/// <summary>
/// 空构造函数
/// </summary>
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);
return States.Success;
}
//在尾节点后面附加一个节点
Rear.Next =new Node<T>(item, Head);
//新附加在链表后面的节点变成尾节点
Rear = Rear.Next;
return States.Success;
}
/// <summary>
/// 清空
/// </summary>
publicvoid Clear()
{
this.Head =null;
this.Rear =null;
}
/// <summary>
/// 删除
/// </summary>
/// <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)
{
returndefault(T);
}
Node<T> Last = Head;
int Count =0;
while(Count != i && Last.Next != Head)
{
Last = Last.Next;
Count++;
}
return Last.Data;
}
/// <summary>
/// 获取链表的长度
/// </summary>
/// <returns></returns>
publicint GetLength()
{
if(Head ==null)
{
return0;
}
Node<T> Last;
Last = Head;
int Count =0;
while(Last.Next != Head)//通过判断是否是Head（头节点），判断当前元素是否是最后一个节点
{
Last = Last.Next;
Count++;
}
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)
{
Rear.Next = Head;
}
}
//如果是普通的结点
Node<T> Previous = Head;
int Count =0;
while(Count != index -1&& Previous.Next != Head)//因为要取到插入位置的前一个节点所以用Count != index-1的判断
{
Previous = Previous.Next;
Count++;
}
//如果是最后一个结点
if(this.GetLength()== index)
{
Previous.Next =new Node<T>(item);
Previous.Next.Next = Head;
Rear = Previous.Next;
return States.Success;
}
if(Count == index -1)
{
Node<T> node =new Node<T>(item);
node.Next = Previous.Next;
Previous.Next = node;
}
return States.Success;
}
/// <summary>
/// 判断链表是否为空
/// </summary>
/// <returns>是否为空</returns>
publicbool IsEmpty()
{
return Head ==null?true:false;
}
publicint Locate(T value,out States states)
{
if(IsEmpty()==true)
{
states = States.Fail;
return0;
}
Node<T> Last = Head;
int Index =0;
while(Last.Next != Head &&(!value.Equals(Last.Data)))
{
Last = Last.Next;
Index++;
}
states = States.Success;
return Index;
}
}
}