-
c#实现链表
链表：链表是用一组任意的存储单元来存储线性表中的数据元素。为此，在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像，称为结点(Node)。把存储据元素本身信息的域叫结点的数据域，把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域。
节点类:
using System;
using System.Collections.Generic;
using System.Text;
namespace DateStructrues.Lists.Node
{
/// <summary>
/// 节点类。
/// </summary>
/// <typeparam name="T"></typeparam>
public class DNode<T>
{
#region Fields
//
//数据域
//
T _data;
//
//地址域(下一个)
//
DNode<T> _next;
//
//地址域(上一个)
//
DNode<T> _prev;
#endregion
#region Constructor
/// <summary>
/// 构造器
/// </summary>
/// <param name="value"></param>
public DNode(T value)
{
_data = value;
}
/// <summary>
/// 构造器
/// </summary>
/// <param name="value"></param>
/// <param name="prev"></param>
/// <param name="next"></param>
public DNode(T value, DNode<T> prev, DNode<T> next)
{
_data = value;
_prev = prev;
_next = next;
}
/// <summary>
/// 构造器
/// </summary>
public DNode() { }
#endregion
#region Properties
/// <summary>
/// 地址域属性（上一个）。
/// </summary>
public DNode<T> Prev
{
get
{
return _prev;
}
set
{
_prev = value;
}
}
/// <summary>
/// 地址域属性(下一个)。
/// </summary>
public DNode<T> Next
{
get
{
return _next;
}
set
{
_next = value;
}
}
/// <summary>
/// 数据域属性。
/// </summary>
public T Data
{
get
{
return _data;
}
set
{
_data = value;
}
}
#endregion
}
}
链表：
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace DateStructrues.Lists.Node
{
/// <summary>
/// 链表
/// </summary>
/// <typeparam name="T">数据类型</typeparam>
public class LinkList<T> : IList<T>
{
#region Fields
//
// 头节点
//
Node<T> head;
//
// 尾节点
//
Node<T> rear;
//
// 记录节点的个数
//
int count;
#endregion
#region Methods
/// <summary>
/// 通过遍历，求链表的长度。
/// </summary>
/// <returns>长度</returns>
public int GetCount()
{
int count = 0;
Node<T> p = head;
while (p != null)
{
count++;
p = p.Next;
}
return count;
}
/// <summary>
/// 获得节点。
/// </summary>
/// <param name="index">索引</param>
/// <returns>对应的节点</returns>
public Node<T> GetNodeByIndex(int index)
{
if (index < 0)
{
return null;
}
Node<T> p = head;
int count = 0;
while (p != null)
{
if (index == count)
{
return p;
}
count++;
p = p.Next;
}
return null;
}
/// <summary>
/// 复制
/// </summary>
/// <returns></returns>
public LinkList<T> Copy()
{
LinkList<T> tmp = new LinkList<T>();
tmp.head = new Node<T>(head.Data);
Node<T> p1 = tmp.head;
Node<T> p2 = head.Next;
while (p2 != null)
{
Node<T> tmpNode = new Node<T>(p2.Data);
p1.Next = tmpNode;
p1 = p1.Next;
p2 = p2.Next;
}
return tmp;
}
/// <summary>
/// 倒序
/// </summary>
public void Revers()
{
Node<T> p = head.Next;
Node<T> q = new Node<T>();
head.Next = null;
while (p != null)
{
q = p;
p = p.Next;
q.Next = head.Next;
head.Next = q;
}
}
/// <summary>
/// 合并
/// </summary>
/// <param name="Ha"></param>
/// <param name="Hb"></param>
/// <returns></returns>
public static LinkList<int> Merge(LinkList<int> Ha, LinkList<int> Hb)
{
LinkList<int> Hc = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = Hb.head;
Node<int> s = new Node<int>();
Hc = Ha;
Hc.head = null;
while (p != null && q != null)
{
if (p.Data < q.Data)
{
s = p;
p = p.Next;
}
else
{
s = q;
q = q.Next;
}
Hc.Add(s.Data);
}
if (p == null)
{
p = q;
}
while (p != null)
{
s = p;
p = p.Next;
Hc.Add(s.Data);
}
return Hc;
}
/// <summary>
/// 合并,由于同上一个合并方法签名相同,即不能重载
/// </summary>
/// <param name="Ha"></param>
/// <param name="Hb"></param>
/// <returns></returns>
public static LinkList<int> Merge2(LinkList<int> Ha, LinkList<int> Hb)
{
LinkList<int> Hc = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = Hb.head;
Node<int> s = new Node<int>();
Hc = Ha;
Hc.head = null;
//两个表非空
while (p != null && q != null)
{
if (p.Data < q.Data)
{
s = p;
p = p.Next;
}
else
{
s = q;
q = q.Next;
}
s.Next = Hc.head;
Hc.head = s;
}
//第2个表非空而第1个表为空
if (p == null)
{
p = q;
}
//将两表中的剩余数据元素附加到新表的末尾
while (p != null)
{
s = p;
p = p.Next;
s.Next = Hc.head;
Hc.head = s;
}
return Hc;
}
/// <summary>
/// 取消
/// </summary>
/// <param name="Ha"></param>
/// <returns></returns>
public static LinkList<int> Purge(LinkList<int> Ha)
{
LinkList<int> Hb = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = new Node<int>();
Node<int> s = new Node<int>();
s = p;
p = p.Next;
s.Next = null;
Hb.head = s;
while (p != null)
{
s = p;
p = p.Next;
q = Hb.head;
while (q != null && q.Data != s.Data)
{
q = q.Next;
}
if (q == null)
{
s.Next = Hb.head;
Hb.head = s;
}
}
return Hb;
}
#endregion
#region Properties
/// <summary>
/// 数组模式，主要用于调试时查看。
/// </summary>
public T[] ArrayMode
{
get
{
T[] arr = new T[Count];
Node<T> p = head;
int count = 0;
while (p != null)
{
arr[count] = p.Data;
p = p.Next;
count++;
}
return arr;
}
}
#endregion
#region IList<T> 成员
/// <summary>
/// 求元素所在的索引。
/// </summary>
/// <param name="item">要查找的元素</param>
/// <returns>所在索引</returns>
public int IndexOf(T item)
{
// 用于遍历链表
Node<T> p = head;
// 计数器
int count = 0;
while (p != null)
{
if (p.Data.Equals(item))
{
return count;
}
count++;
// 移到下一个节点
p = p.Next;
}
return -1;
}
/// <summary>
/// 插入元素。
/// </summary>
/// <param name="index">索引</param>
/// <param name="item">要插入的项</param>
public void Insert(int index, T item)
{
int count = 1;
Node<T> p = head;
Node<T> v = new Node<T>(item);
if (index == 0)
{
if (head == null)
{
rear = v;
}
v.Next = head;
head = v;
this.count++;
return;
}
while (p != null)
{
if (count == index)
{
if (p.Next == null)
rear = v;
v.Next = p.Next;
p.Next = v;
this.count++;
break;
}
p = p.Next;
count++;
}
}
/// <summary>
/// 以索引方式删除元素
/// </summary>
/// <param name="index">索引</param>
public void RemoveAt(int index)
{
int count = 0;
if (index == 0)
{
head = head.Next;
this.count--;
return;
}
Node<T> p = head;
Node<T> prev = head;
while (p != null)
{
if (count == index)
{
prev.Next = p.Next;
this.count--;
if (p.Next == null)
{
rear = prev;
}
break;
}
prev = p;
p = p.Next;
count++;
}
}
/// <summary>
/// 以索引方式访问
/// </summary>
/// <param name="index">索引</param>
/// <returns>对应的元素</returns>
public T this[int index]
{
get
{
try
{
Node<T> p = GetNodeByIndex(index);
return p.Data;
}
catch (NullReferenceException)
{
throw new IndexOutOfRangeException("索引超出数组界限。");
}
}
set
{
try
{
Node<T> p = GetNodeByIndex(index);
p.Data = value;
}
catch (NullReferenceException)
{
throw new IndexOutOfRangeException("索引超出数组界限。");
}
}
}
#endregion
#region ICollection<T> 成员
/// <summary>
/// 向链表末尾，追加元素
/// </summary>
/// <param name="item">要追加的元素</param>
public void Add(T item)
{
Node<T> p = new Node<T>(item);
if (head == null)
{
head = p;
// 将这个节点设为末尾。
rear = p;
this.count = 1;
return;
}
rear.Next = p;
rear = p;
count++;
}
/// <summary>
/// 清空
/// </summary>
public void Clear()
{
head = null;
rear = null;
}
/// <summary>
/// 是否包含元素
/// </summary>
/// <param name="item">检查是否包含的元素</param>
/// <returns>是否存在</returns>
public bool Contains(T item)
{
int index = IndexOf(item);
return (index != -1);
}
/// <summary>
/// 将数据拷贝到数组
/// </summary>
/// <param name="array">准备的数组</param>
/// <param name="arrayIndex">开始的索引</param>
public void CopyTo(T[] array, int arrayIndex)
{
ArrayMode.CopyTo(array, arrayIndex);
}
/// <summary>
/// 获得此链表的元素个数
/// </summary>
public int Count
{
get
{
return GetCount();
}
}
/// <summary>
/// 获得是否是只读。
/// </summary>
public bool IsReadOnly
{
get
{
return false;
}
}
/// <summary>
/// 删除元素
/// </summary>
/// <param name="item">将要被删除的元素</param>
/// <returns>是否成功删除</returns>
public bool Remove(T item)
{
Node<T> prev = null;
Node<T> p = head;
while (p != null)
{
if (p.Data.Equals(item))
{
if (prev != null)
prev.Next = p.Next;
else
head = head.Next;
this.count--;
return true;
}
prev = p;
p = p.Next;
}
return false;
}
#endregion
#region IEnumerable<T> 成员
public IEnumerator<T> GetEnumerator()
{
throw new Exception("The method or operation is not implemented.");
}
#endregion
#region IEnumerable 成员
IEnumerator IEnumerable.GetEnumerator()
{
throw new Exception("The method or operation is not implemented.");
}
#endregion
}
}
链表：
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace DateStructrues.Lists.Node
{
/// <summary>
/// 链表
/// </summary>
/// <typeparam name="T">数据类型</typeparam>
public class LinkList<T> : IList<T>
{
#region Fields
//
// 头节点
//
Node<T> head;
//
// 尾节点
//
Node<T> rear;
//
// 记录节点的个数
//
int count;
#endregion
#region Methods
/// <summary>
/// 通过遍历，求链表的长度。
/// </summary>
/// <returns>长度</returns>
public int GetCount()
{
int count = 0;
Node<T> p = head;
while (p != null)
{
count++;
p = p.Next;
}
return count;
}
/// <summary>
/// 获得节点。
/// </summary>
/// <param name="index">索引</param>
/// <returns>对应的节点</returns>
public Node<T> GetNodeByIndex(int index)
{
if (index < 0)
{
return null;
}
Node<T> p = head;
int count = 0;
while (p != null)
{
if (index == count)
{
return p;
}
count++;
p = p.Next;
}
return null;
}
/// <summary>
/// 复制
/// </summary>
/// <returns></returns>
public LinkList<T> Copy()
{
LinkList<T> tmp = new LinkList<T>();
tmp.head = new Node<T>(head.Data);
Node<T> p1 = tmp.head;
Node<T> p2 = head.Next;
while (p2 != null)
{
Node<T> tmpNode = new Node<T>(p2.Data);
p1.Next = tmpNode;
p1 = p1.Next;
p2 = p2.Next;
}
return tmp;
}
/// <summary>
/// 倒序
/// </summary>
public void Revers()
{
Node<T> p = head.Next;
Node<T> q = new Node<T>();
head.Next = null;
while (p != null)
{
q = p;
p = p.Next;
q.Next = head.Next;
head.Next = q;
}
}
/// <summary>
/// 合并
/// </summary>
/// <param name="Ha"></param>
/// <param name="Hb"></param>
/// <returns></returns>
public static LinkList<int> Merge(LinkList<int> Ha, LinkList<int> Hb)
{
LinkList<int> Hc = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = Hb.head;
Node<int> s = new Node<int>();
Hc = Ha;
Hc.head = null;
while (p != null && q != null)
{
if (p.Data < q.Data)
{
s = p;
p = p.Next;
}
else
{
s = q;
q = q.Next;
}
Hc.Add(s.Data);
}
if (p == null)
{
p = q;
}
while (p != null)
{
s = p;
p = p.Next;
Hc.Add(s.Data);
}
return Hc;
}
/// <summary>
/// 合并,由于同上一个合并方法签名相同,即不能重载
/// </summary>
/// <param name="Ha"></param>
/// <param name="Hb"></param>
/// <returns></returns>
public static LinkList<int> Merge2(LinkList<int> Ha, LinkList<int> Hb)
{
LinkList<int> Hc = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = Hb.head;
Node<int> s = new Node<int>();
Hc = Ha;
Hc.head = null;
//两个表非空
while (p != null && q != null)
{
if (p.Data < q.Data)
{
s = p;
p = p.Next;
}
else
{
s = q;
q = q.Next;
}
s.Next = Hc.head;
Hc.head = s;
}
//第2个表非空而第1个表为空
if (p == null)
{
p = q;
}
//将两表中的剩余数据元素附加到新表的末尾
while (p != null)
{
s = p;
p = p.Next;
s.Next = Hc.head;
Hc.head = s;
}
return Hc;
}
/// <summary>
/// 取消
/// </summary>
/// <param name="Ha"></param>
/// <returns></returns>
public static LinkList<int> Purge(LinkList<int> Ha)
{
LinkList<int> Hb = new LinkList<int>();
Node<int> p = Ha.head;
Node<int> q = new Node<int>();
Node<int> s = new Node<int>();
s = p;
p = p.Next;
s.Next = null;
Hb.head = s;
while (p != null)
{
s = p;
p = p.Next;
q = Hb.head;
while (q != null && q.Data != s.Data)
{
q = q.Next;
}
if (q == null)
{
s.Next = Hb.head;
Hb.head = s;
}
}
return Hb;
}
#endregion
#region Properties
/// <summary>
/// 数组模式，主要用于调试时查看。
/// </summary>
public T[] ArrayMode
{
get
{
T[] arr = new T[Count];
Node<T> p = head;
int count = 0;
while (p != null)
{
arr[count] = p.Data;
p = p.Next;
count++;
}
return arr;
}
}
#endregion
#region IList<T> 成员
/// <summary>
/// 求元素所在的索引。
/// </summary>
/// <param name="item">要查找的元素</param>
/// <returns>所在索引</returns>
public int IndexOf(T item)
{
// 用于遍历链表
Node<T> p = head;
// 计数器
int count = 0;
while (p != null)
{
if (p.Data.Equals(item))
{
return count;
}
count++;
// 移到下一个节点
p = p.Next;
}
return -1;
}
/// <summary>
/// 插入元素。
/// </summary>
/// <param name="index">索引</param>
/// <param name="item">要插入的项</param>
public void Insert(int index, T item)
{
int count = 1;
Node<T> p = head;
Node<T> v = new Node<T>(item);
if (index == 0)
{
if (head == null)
{
rear = v;
}
v.Next = head;
head = v;
this.count++;
return;
}
while (p != null)
{
if (count == index)
{
if (p.Next == null)
rear = v;
v.Next = p.Next;
p.Next = v;
this.count++;
break;
}
p = p.Next;
count++;
}
}
/// <summary>
/// 以索引方式删除元素
/// </summary>
/// <param name="index">索引</param>
public void RemoveAt(int index)
{
int count = 0;
if (index == 0)
{
head = head.Next;
this.count--;
return;
}
Node<T> p = head;
Node<T> prev = head;
while (p != null)
{
if (count == index)
{
prev.Next = p.Next;
this.count--;
if (p.Next == null)
{
rear = prev;
}
break;
}
prev = p;
p = p.Next;
count++;
}
}
/// <summary>
/// 以索引方式访问
/// </summary>
/// <param name="index">索引</param>
/// <returns>对应的元素</returns>
public T this[int index]
{
get
{
try
{
Node<T> p = GetNodeByIndex(index);
return p.Data;
}
catch (NullReferenceException)
{
throw new IndexOutOfRangeException("索引超出数组界限。");
}
}
set
{
try
{
Node<T> p = GetNodeByIndex(index);
p.Data = value;
}
catch (NullReferenceException)
{
throw new IndexOutOfRangeException("索引超出数组界限。");
}
}
}
#endregion
#region ICollection<T> 成员
/// <summary>
/// 向链表末尾，追加元素
/// </summary>
/// <param name="item">要追加的元素</param>
public void Add(T item)
{
Node<T> p = new Node<T>(item);
if (head == null)
{
head = p;
// 将这个节点设为末尾。
rear = p;
this.count = 1;
return;
}
rear.Next = p;
rear = p;
count++;
}
/// <summary>
/// 清空
/// </summary>
public void Clear()
{
head = null;
rear = null;
}
/// <summary>
/// 是否包含元素
/// </summary>
/// <param name="item">检查是否包含的元素</param>
/// <returns>是否存在</returns>
public bool Contains(T item)
{
int index = IndexOf(item);
return (index != -1);
}
/// <summary>
/// 将数据拷贝到数组
/// </summary>
/// <param name="array">准备的数组</param>
/// <param name="arrayIndex">开始的索引</param>
public void CopyTo(T[] array, int arrayIndex)
{
ArrayMode.CopyTo(array, arrayIndex);
}
/// <summary>
/// 获得此链表的元素个数
/// </summary>
public int Count
{
get
{
return GetCount();
}
}
/// <summary>
/// 获得是否是只读。
/// </summary>
public bool IsReadOnly
{
get
{
return false;
}
}
/// <summary>
/// 删除元素
/// </summary>
/// <param name="item">将要被删除的元素</param>
/// <returns>是否成功删除</returns>
public bool Remove(T item)
{
Node<T> prev = null;
Node<T> p = head;
while (p != null)
{
if (p.Data.Equals(item))
{
if (prev != null)
prev.Next = p.Next;
else
head = head.Next;
this.count--;
return true;
}
prev = p;
p = p.Next;
}
return false;
}
#endregion
#region IEnumerable<T> 成员
public IEnumerator<T> GetEnumerator()
{
throw new Exception("The method or operation is not implemented.");
}
#endregion
#region IEnumerable 成员
IEnumerator IEnumerable.GetEnumerator()
{
throw new Exception("The method or operation is not implemented.");
}
#endregion
}
}
