Jimmy.Yang 通过本文主要向大家介绍了马桶c的个人空间,c站,欲情 c max,维生素c,奔驰c200等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
本文实例讲述了C#数据结构之双向链表(DbLinkList)。分享给大家供大家参考，具体如下：
这是继上一篇《C#数据结构之单链表(LinkList)实例详解》的继续，对于双向链接，节点上除了Next属性外，还要有Prev属性用来指向前一个节点，DbNode定义如下：
namespace 线性表
{
public class DbNode<T>
{
private T data;
private DbNode<T> prev;
private DbNode<T> next;
public DbNode(T data, DbNode<T> next,DbNode<T> prev)
{
this.data = data;
this.next = next;
this.prev = prev;
}
public DbNode(T data, DbNode<T> next)
{
this.data = data;
this.next = next;
this.prev = null;
}
public DbNode(DbNode<T> next)
{
this.data = default(T);
this.next = next;
this.prev = null;
}
public DbNode(T data)
{
this.data = data;
this.next = null;
this.prev = null;
}
public DbNode()
{
data = default(T);
next = null;
prev = null;
}
public T Data
{
set { this.data = value; }
get { return this.data; }
}
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
}
</div>
双链表的插入操作要稍微复杂一点，示意图如下：
同样对于删除操作，也要额外处理prev指向
完整实现DbLinkList<T>：
using System;
using System.Text;
namespace 线性表
{
public class DbLinkList<T> : IListDS<T>
{
private DbNode<T> head;
public DbNode<T> Head
{
get { return head; }
set { head = value; }
}
public DbLinkList()
{
head = null;
}
/// <summary>
/// 类索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return this.GetItemAt(index);
}
}
/// <summary>
/// 返回单链表的长度
/// </summary>
/// <returns></returns>
public int Count()
{
DbNode<T> p = head;
int len = 0;
while (p != null)
{
len++;
p = p.Next;
}
return len;
}
/// <summary>
/// 清空
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head == null;
}
/// <summary>
/// 在最后附加元素
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
DbNode<T> d = new DbNode<T>(item);
DbNode<T> n = new DbNode<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
d.Prev = n;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最开头插入
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head;//把"头"改成第二个元素
head.Prev = q;
head = q;//把自己设置为"头"
return;
}
DbNode<T> n = head;
DbNode<T> d = new DbNode<T>();
int j = 0;
//找到位置i的前一个元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //说明是在最后节点插入(即追加)
{
DbNode<T> q = new DbNode<T>(item);
n.Next = q;
q.Prev = n;
q.Next = null;
}
else
{
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
d.Next = q;
q.Prev = d;
q.Next = n;
n.Prev = q;
}
}
}
/// <summary>
/// 在位置i后插入元素item
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertAfter(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head.Next;
head.Next.Prev = q;
head.Next = q;
q.Prev = head;
return;
}
DbNode<T> p = head;
int j = 0;
while (p != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = p.Next;
if (p.Next != null)
{
p.Next.Prev = q;
}
p.Next = q;
q.Prev = p;
}
else
{
Console.WriteLine("Position is error!");
}
}
/// <summary>
/// 删除位置i的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T RemoveAt(int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
DbNode<T> q = new DbNode<T>();
if (i == 0)
{
q = head;
head = head.Next;
head.Prev = null;
return q.Data;
}
DbNode<T> p = head;
int j = 0;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
p.Next.Prev = q;
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The node is not exist!");
return default(T);
}
}
/// <summary>
/// 获取指定位置的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetItemAt(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}
DbNode<T> p = new DbNode<T>();
p = head;
if (i == 0)
{
return p.Data;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The node is not exist!");
return default(T);
}
}
//按元素值查找索引
public int IndexOf(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}
DbNode<T> p = new DbNode<T>();
p = head;
int i = 0;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
i++;
}
return i;
}
/// <summary>
/// 元素反转
/// </summary>
public void Reverse()
{
DbLinkList<T> result = new DbLinkList<T>();
DbNode<T> t =