数据结构C#版线性表(Data Structure)之单链表(LinkList)
2010-10-17 14:15:36 来源：WEB开发网 闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚�
闂傚倸鍊风粈渚€骞夐敓鐘插瀭闁汇垹鐏氬畷鏌ユ煙閹殿喖顣奸柛搴＄У閵囧嫰骞掗幋婵冨亾閻㈢ǹ纾婚柟鐐灱濡插牊绻涢崱妤冃℃繛宀婁簽缁辨捇宕掑鎵佹瀸闂佺懓鍤栭幏锟�
濠电姷鏁告慨顓㈠箯閸愵喖宸濇い鎾寸箘閹规洟姊绘笟鈧ḿ褍煤閵堝悿娲Ω閳轰胶鍔﹀銈嗗笂閼冲爼鍩婇弴銏＄厪闁搞儮鏅涙禒褏绱掓潏鈺佷槐闁轰焦鎹囬弫鎾绘晸閿燂拷闂傚倸鍊风欢姘缚瑜嶈灋闁圭虎鍠栫粻顖炴煥閻曞倹瀚� 闂傚倸鍊烽懗鑸电仚缂備胶绮〃鍛村煝瀹ュ鍗抽柕蹇曞У閻庮剟姊虹紒妯哄闁圭⒈鍋嗛惀顏囶樄闁哄本娲樼换婵婄疀閺囩姷鐛ラ梻浣哄帶婢瑰﹥绂嶅⿰鍫氣偓鏃堝礃椤忎礁浜鹃柨婵嗛婢ь喖霉閻樻瑥瀚粻楣冩煕椤愩倕鏋庨柣蹇嬪劜閵囧嫰寮村Ο鍝勫Е濡炪們鍨洪悷鈺呭箖閳╁啯鍎熼柕鍥у簻閹凤拷
核心提示：每个元素至少具有二个属性：data和next，data用来存放数据，数据结构C#版线性表(Data Structure)之单链表(LinkList)，而next用来指出它后面的元素是谁(有点“指针”的意思)，链表中的元素，下面是单链表的实现:using System;using System.T
每个元素至少具有二个属性：data和next。data用来存放数据，而next用来指出它后面的元素是谁(有点“指针”的意思)。
链表中的元素，通常也称为节点Node，下面是泛型版本的Node.cs
namespace 线性表
{
public class Node<T>
{
private T data;
private Node<T> next;
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
public Node(Node<T> p)
{
next = p;
}
public Node(T val)
{
data = val;
next = null;
}
public Node()
{
data = default(T);
next = null;
}
public T Data
{
get { return data; }
set { data = value; }
}
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
}
链表在存储上并不要求所有元素按顺序存储，因为用节点的next就能找到下一个节点，这好象一根“用珠子串成的链子”，要找到其中的某一颗珠子，只要从第一
颗节点(通常称为Head节点)开始，不断根据next指向找到下一个，直到找到需要的节点为止。
链表中需要有一个Head节点做为开始，这跟顺序表有所不同，下面是单链表的实现:
using System;
using System.Text;
namespace 线性表
{
public class LinkList<T> : IListDS<T>
{
private Node<T> head;
public Node<T> Head
{
get { return head; }
set { head = value; }
}
public LinkList()
{
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()
{
Node<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)
{
Node<T> d = new Node<T>(item);
Node<T> n = new Node<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最开头插入
if (i == 0)
{
Node<T> q = new Node<T>(item);
q.Next = Head;//把"头"改成第二个元素
head = q;//把自己设置为"头"
return;
}
Node<T> n = head;
Node<T> d = new Node<T>();
int j = 0;
//找到位置i的前一个元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //说明是在最后节点插入(即追加)
{
Node<T> q = new Node<T>(item);
n.Next = q;
q.Next = null;
}
else
{
if (j == i)
{
Node<T> q = new Node<T>(item);
d.Next = q;
q.Next = n;
}
}
}
/// <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)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = 0;
while (p != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
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);
}
Node<T> q = new Node<T>();
if (i == 0)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = 0;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
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);
}
Node<T> p = new Node<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;
}
Node<T> p = new Node<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()
{
LinkList<T> result = new LinkList<T>();
Node<T> t = this.head;
result.Head = new Node<T>(t.Data);
t = t.Next;
//(把当前链接的元素从head开始遍历，逐个插入到另一个空链表中，这样得到的新链表正好元素顺序跟原链表是相反的)
while (t!=null)
{
result.InsertBefore(t.Data, 0);
t = t.Next;
}
this.head = result.head;//将原链表直接挂到"反转后的链表"上
result = null;//显式清空原链表的引用，以便让GC能直接回收
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node<T> n = this.head;
sb.Append(n.Data.ToString() + ",");
while (n.Next != null)
{
sb.Append(n.Next.Data.ToString() + ",");
n = n.Next;
}
return sb.ToString().TrimEnd(',');
}
}
}
中查找“数据结构C#版线性表(Data Structure)之单链表(LinkList)”更多相关内容
中查找“数据结构C#版线性表(Data Structure)之单链表(LinkList)”更多相关内容更多精彩
赞助商链接
