循环列表的实现
我们将在单链表的基础上讨论循环链表的实现,循环链表中的节点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;
}
}
}
作者:kissazi2
出处:http://www.cnblogs.com/kissazi2/
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载:http://www.cnblogs.com/kissazi2/p/3193975.html
定义一个方法,功能是找出一个数组中第一个只重复出现2次的元素,没有则返回null。例如:数组元素为 [1,3,4,2,6,3,4,2,3],重复两次的元素为4和2,但是元素4排在2的前面,则结果返回 定义一个方法,功能是找出一个数组中第一个只重复出现2次的元素,没有则返回null。例如:数组元素为 [1,3,4,2,6,3,4,2,3],重复两次的元素为4和2,但是元素4排在2的前面,则结果返回
相关文章
- 批处理命令for循环_批处理获取某个目录大小
- html图片左右无缝循环滚动示例
- JAVA(集合类)——使用For循环遍历ArrayList[通俗易懂]
- VBA: 最优化算法(二分法、黄金分割法、循环迭代法)的代码实现
- 队列的基本概念详解,循环队列、链式队列的C++详细实现
- 【说站】python事件循环如何使用?
- matlab循环语句for_MATLAB以下选择语句错误的是
- 上手python之while循环和for循环
- 抽丝剥茧C语言(中阶)分支语句和循环语句
- C++ for循环详解
- MySQL循环语句简单查询实例(mysql循环语句查询)
- 循环管理Redis中的键值对(循环redis key)
- PHP提取数据库内容中的图片地址并循环输出
- AndroidHandler之消息循环的深入解析
- jQuery实现列表自动循环滚动鼠标悬停时停止滚动
- Javafor-each循环使用难题2例(高级使用方法)
- jQuery循环滚动新闻列表示例代码