## 双向链表

2018年05月06日 ⁄ 综合 ⁄ 共 4972字 ⁄ 字号 评论关闭

C#实现：

1接口

2实现

（1）双向链表节点类，参考单链表的节点类
public class DBNode<T>
{
private T data;              //数据域
private DBNode<T> next;        //后继
private DBNode<T> prev;        //前驱
public T Data
{
get { return data; }
set { data = value; }
}
public DBNode<T> Next
{
get { return next; }
set { next = value; }
}
public DBNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DBNode()
{
data = default(T);
prev = null;
next = null;
}
public DBNode(T val)
{
data = val;
next = null;
prev = null;
}
}
(2) 双向链表操作类实现

{

{

set { header = value; }
}
{
}
/// <summary>
/// 获取长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
/// <summary>
/// 清空操作
/// </summary>
public void Clear()
{
}
/// <summary>
/// 判断线性表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
{
return true;
}
else
{
return false;
}
}
/// <summary>
/// 查找节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
private DBNode<T> FindNode(int i)
{
if (IsEmpty())
{
Console.Write("list is empty");
return null;
}
if (i < 1)
{
Console.Write("Index is error");
return null;
}
DBNode<T> current = new DBNode<T>();
int j = 1;
while (current.Next != null && j < i)
{
++j;
current = current.Next;
}
return current;
}
/// <summary>
/// 插入操作,在第i个节点前面
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void Insert(T item, int i)
{
DBNode<T> current = FindNode(i);
DBNode<T> newNode = new DBNode<T>(item);
if (current != null)
{
current.Prev.Next = newNode;
newNode.Next = current;
newNode.Prev = current.Prev;
current.Prev = newNode;
}
else
{
Console.Write("the node is not exist!");
}
}
/// <summary>
/// 插入操作,在第i个节点后面插入item
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertBack(T item, int i)
{
DBNode<T> current = FindNode(i);
DBNode<T> newNode = new DBNode<T>(item);
if (current != null)
{
current.Next.Prev = newNode;
newNode.Prev = current;
newNode.Next = current.Next;
current.Next = newNode;
}
else
{
Console.Write("the node is not exist!");
}
}
/// <summary>
/// 附加操作,线性表未满，将值为item的新元素添加到末尾
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
DBNode<T> newNode = new DBNode<T>(item);
DBNode<T> p = new DBNode<T>();
{
return;
}

while (p.Next != null)
{
p = p.Next;
}
p.Next = newNode;
}

/// <summary>
/// 删除操作
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T Delete(int i)
{
DBNode<T> current = FindNode(i);
if (current != null)
{
current.Prev.Next = current.Next;
current.Next.Prev = current.Prev;
current.Prev = null;
current.Next = null;
return current.Data;
}
else
{
Console.Write("the node is not exist!");
return default(T);
}
}
/// <summary>
/// 取表元
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetElem(int i)
{
DBNode<T> current = FindNode(i);
if (current != null)
{
return current.Data;
}
else
{
Console.Write("the node is not exist!");
return default(T);
}
}

/// <summary>
/// 按值查找
/// </summary>
/// <param name="value"></param>
/// <returns>-1:链表或参数异常;0:节点不存在;1:值代表的位置</returns>
public int Locate(T value)
{
if (IsEmpty())
{
Console.Write("list is empty");
return -1;
}
if (value == null)
{
Console.Write("value is empty");
return -1;
}
DBNode<T> current = new DBNode<T>();
int result = 0;

while (current.Next != null)
{
if (current.Data.Equals(value))
{
result = 1;
}
}
return result;
}
}

【上篇】
【下篇】