循环链表
循环链表是指链表的尾节点的Next指针域指向头节点。
循环链表判空条件，头节点的后继指向自己。
代码实现
下面的实现中，增加了头节点（头节点进代表链表地址，不含有值，第一个含有值的节点是首节点）。
Node类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
public class Node<T>
{
private T data; //数据域
private Node<T> next; //引用域
//数据域属性
public T Data { get => data; set => data = value; }
//引用域属性
internal Node<T> Next { get => next; set => next = value; }
//构造器
public Node(T val, Node<T> p) {
Data = val;
Next = p;
}
//构造器
public Node(Node<T> p) {
Next = p;
}
//构造器
public Node(T val) {
Data = val;
}
//构造器
public Node() {
Data = default(T);
Next = null;
}
}
}
SingleCycle接口
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
interface SingleCycleDs<T>
{
int GetLength(); //求长度
void Clear(); //清空操作
bool IsEmpty(); //判断线性表是否为空
void Append(T item); //附加操作
void Insert(T item, int i); //插入
void Delete(int i); //删除操作
T GetElem(int i); //取表元
int Locate(T value); //按值查找
void Reverse(); //逆置
}
}
SingleCycle类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test
{
class SingleCycle<T> : SingleCycleDs<T>
{
Node<T> head; //头节点
//头节点属性
public Node<T> Head { get => head; set => head = value; }
//构造器
public SingleCycle() {
head = new Node<T>();
head.Next = head;
}
/// <summary>
/// 附加元素到尾部
/// </summary>
/// <param name="item">元素</param>
public void Append(T item)
{
Node<T> p = new Node<T>(item);
Node<T> c = head;
//头节点为空时，直接修改头节点和新增节点的引用
if (IsEmpty()) {
head.Next = p;
p.Next = head;
return;
}
//遍历至最后一个节点
while (c.Next != head) {
c = c.Next;
}
//将新增元素挂载到末尾
c.Next = p;
p.Next = head;
}
/// <summary>
/// 清空链表
/// </summary>
public void Clear()
{
head.Next = head;
}
/// <summary>
/// 删除节点
/// </summary>
/// <param name="i">删除节点的位置</param>
public void Delete(int i)
{
//链表为空
if (IsEmpty() || i < 1)
{
Console.WriteLine("链表为空或位置错误");
return;
}
//删除头节点
if (i == 1)
{
head.Next = head.Next.Next;
return;
}
//遍历位置删除节点
Node<T> c = head.Next; //目标节点
Node<T> p = new Node<T>(); //目标节点的前驱节点
int j = 1;
while (c.Next != head && j < i)
{
/* 记录当前节点，
* 因为当前节点为下一次遍历的前驱节点，
* 当遍历到目标节点时，可以直接用其前驱节点操作。
*/
p = c;
c = c.Next;
++j;
}
//遍历到位置
if (j == i)
{
Console.WriteLine(j);
Console.WriteLine(p.Next.Data);
//用前驱节点来跳过目标节点，直接挂载目标节点的后继节点到其前驱节点上
p.Next = p.Next.Next;
Console.WriteLine("删除成功");
}
//未找到位置
else {
Console.WriteLine("位置不正确");
}
}
/// <summary>
/// 根据位置获取元素值
/// </summary>
/// <param name="i">元素位置</param>
/// <returns>元素数据域值</returns>
public T GetElem(int i)
{
//链表为空时返回默认值。
if (IsEmpty()) {
Console.WriteLine();
return default(T);
}
//返回第一个元素的值
if (i == 1) {
return head.Next.Data;
}
//遍历查找并返回
Node<T> c = head.Next;
int j = 1;
while (c.Next != head && j < i) {
c = c.Next;
++j;
}
//遍历找到
if (j == i)
{
return c.Data;
}
else {
Console.WriteLine("位置不正确");
}
return default(T);
}
/// <summary>
/// 获取列表长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
if (IsEmpty()) {
return 0;
}
Node<T> c = head.Next;
int i = 1;
while (c.Next != head) {
c = c.Next;
++i;
}
return i;
}
/// <summary>
/// 插入节点
/// </summary>
/// <param name="item">插入的元素值</param>
/// <param name="i">插入位置</param>
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("链表为空或位置错误");
}
//插入到首节点位置
if (i == 1) {
Node<T> c = head.Next; //保存首节点
head.Next = new Node<T>(item); //将新节点插入到头节点后
head.Next.Next = c; //将首节点设为新节点的后继
return;
}
//遍历位置插入
Node<T> c1 = head.Next;
Node<T> p = new Node<T>();
int j = 1;
while (c1.Next != head && j < i)
{
p = c1;
c1 = c1.Next;
++j;
}
//遍历找到
if (j == i)
{
p.Next = new Node<T>(item);
p.Next.Next = c1;
}
else
{
Console.WriteLine("位置不正确");
}
}
//判断链表是否为空
public bool IsEmpty()
{
return head.Next == head;
}
/// <summary>
/// 根据节点值查找位置
/// </summary>
/// <param name="value">节点值</param>
/// <returns>节点位置</returns>
public int Locate(T value)
{
int i = 1;
Node<T> c = head.Next;
/* 这里的判断条件要不能写c.Next，
* 因为当目标值为最后一个节点的值时，c.Next==head会成立
* 所以要让循环多遍历一次，
* 当c时头节点时说明列表已遍历完毕，这时如果还未找到，说明不存在。
* 注意：要将比较语句写在逻辑判断后面，
* 因为head=null，当c=head时，比较语句会抛异常。
* 所以要先比较c==head来中断后面的语句。
*/
while (c != head && !c.Data.Equals(value))
{
c = c.Next;
++i;
}
if (c == head)
{
Console.WriteLine("不存在这样的节点");
return -1;
}
else {
return i;
}
}
public void Reverse()
{
throw new NotImplementedException();
}
}
}
Program类
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;
namespace test
{
class Program
{
static void Main(string[] args)
{
SingleCycle<string> link = new SingleCycle<string>();
//添加元素
link.Append("123");
link.Append("567");
link.Append("jqk");
link.Append("qwe");
//link.Clear();
//link.Delete(5);
//Console.WriteLine(link.GetElem(4));
//Console.WriteLine(link.GetLength());
//link.Insert("asd", 4);
Console.WriteLine(link.Locate("1231"));
//输出
Node<string> c = link.Head.Next;
while (c != link.Head)
{
Console.WriteLine(c.Data);
c = c.Next;
}
Console.Read();
}
}
}
网友评论