快捷導(dǎo)航

C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘三鏈表

更新時間：2012年11月01日 20:54:26 作者：

這節(jié)我們討論鏈表的基本操作，并且畫圖以證明，下屆中我們將討論雙向鏈表，環(huán)形鏈表應(yīng)用舉例

上文我們討論了一種最簡單的線性結(jié)構(gòu)——順序表，這節(jié)我們要討論另一種線性結(jié)構(gòu)——鏈表。

什么是鏈表了，不要求邏輯上相鄰的數(shù)據(jù)元素在物理存儲位置上也相鄰存儲的線性結(jié)構(gòu)稱之為鏈表。舉個現(xiàn)實中的例子吧，假如一個公司召開了視頻會議的吧，能在北京總公司人看到上海分公司的人，他們就好比是邏輯上相鄰的數(shù)據(jù)元素，而物理上不相連。這樣就好比是個鏈表。鏈表分為①單鏈表，②單向循環(huán)鏈表，③雙向鏈表，④雙向循環(huán)鏈表。

介紹各種各樣鏈表之前，我們要明白這樣一個概念。什么是結(jié)點。在存儲數(shù)據(jù)元素時，除了存儲數(shù)據(jù)元素本身的信息外，還要存儲與它相鄰的數(shù)據(jù)元素的存儲地址信息。這兩部分信息組成該數(shù)據(jù)元素的存儲映像(Image)，稱為結(jié)點(Node)。在c語言這些面向過程語言中，實現(xiàn)節(jié)點是通過指針的形式，在。net中，是通過模擬指針——類對象嵌套的形式。

然后，首先，介紹單鏈表。如果結(jié)點的引用域只存儲該結(jié)點直接后繼結(jié)點的存儲地址，則該鏈表叫單鏈表(Singly Linked List)。把該引用域叫 next。單鏈表結(jié)點的結(jié)構(gòu)如圖所示，圖中 data表示結(jié)點的數(shù)據(jù)域。

現(xiàn)實中，就像一隊盲人過馬路。如圖所示

把單鏈表結(jié)點看作是一個類，類名為 Node<T>。單鏈表結(jié)點類的實現(xiàn)如下所示。

復(fù)制代碼代碼如下:

public class Node<T> 
{ 
//一隊盲人過馬路 存儲的是盲人的姓名 
private T data; //數(shù)據(jù)域 存儲數(shù)據(jù)的對象 
//一隊盲人過馬路 指向的是下一個盲人對象。 
private Node<T> next; //引用域 指向下一個對象 

//構(gòu)造器 
public Node(T val, Node<T> p) 
{ 
data = val; 
next = p; 
} 

//構(gòu)造器 
public Node(Node<T> p) 
{ 
next = p; 
} 

//構(gòu)造器 
public Node(T val) 
{ 
data = val; 
next = null; 
} 

//構(gòu)造器 
public Node() 
{ 
data = default(T); 
next = null; 
} 

//數(shù)據(jù)域?qū)傩?
public T Data 
{ 
get 
{ 
return data; 
} 
set 
{ 
data = value; 
} 
} 

//引用域?qū)傩?
public Node<T> Next 
{ 
get 
{ 
return next; 
} 
set 
{ 
next = value; 
} 
} 
}

下圖是線性表(a1,a2,a3,a4,a5,a6)對應(yīng)的鏈式存儲結(jié)構(gòu)示意圖。

單鏈表類 LinkList<T>源代碼的實現(xiàn)說明如下所示。首先申明一下，他繼承與IListDS這個接口。

//這是一個盲人過馬路的類的模擬

public class LinkList<T> : IListDS<T> {

//排在第一個位置的盲人

private Node<T> head; //單鏈表的頭引用

//頭引用屬性
public Node<T> Head
{
get
{
return head;
}

set
{
head = value;
}
}

//構(gòu)造器

//開始的時候一個盲人都沒有，頭結(jié)點指向為空的位置。沒有排頭的盲人
public LinkList()
{
head = null;
}

//這里我們求盲人隊伍的長度，從第一個盲人數(shù)起，然后第二個，第三個。就以此類推。。。這樣子盲人的隊伍的長度就得出來了啊。

//求單鏈表的長度
public int GetLength()
{
Node<T> p = head;

int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}

//不讓盲人排隊，就是讓這個隊的頭都不存在

//清空單鏈表
public void Clear()
{
head = null;
}

//判斷一個盲人隊列的是不是為空，看他的頭部是不是有人

//判斷單鏈表是否為空
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}

//在單鏈表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
//這里如果沒有盲人排隊的話，就在隊列的頭部進行了

if (head == null)
{
head = q;
return;
}
//不懂的，一切盡在圖例中

//如果有人排隊，就從頭遍歷，讓他從沒人的地方加入到隊伍中去并且把這個隊列的指針指向后面。
p = head;
while (p.Next != null)
{
p = p.Next;
}

p.Next = q;

不懂的一切盡在圖例中

這個方法的算法復(fù)雜度是O(n)
}

//就是在一隊中增加了插隊的人員

//在單鏈表的第i個結(jié)點的位置前插入一個值為item的結(jié)點
public void Insert(T item, int i)
{
if (IsEmpty() | | i < 1)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//是頭結(jié)點的位置，就把他的頭執(zhí)政指向與他，把另外指針與他　　

if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
//不懂的，如圖所示：

//而這個是將其循環(huán)到隊列相應(yīng)的位置，在將從頭其插入到這個位置

Node<T> p = head;
Node<T> r = new Node<T>();
int j = 1;

while (p.Next != null&& j < i)
{
r = p;
p = p.Next;
++j;
}

if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}

一切盡在圖例中

}

這個方法的算法復(fù)雜度O(n)

//刪除單鏈表的第i個結(jié)點
public T Delete(int i)
{

//是不是盲人排隊的或者排隊的位置不是正確的這就返回了一個錯誤信息
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is
error!");
return default(T);
}
//是頭結(jié)點的的就返回第二個節(jié)點頂?shù)降谝粋€節(jié)點的位置

Node<T> q = new Node<T>();

if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
此步驟為O(1)

//不是的頭位置的吧，就尋找相應(yīng)位置的節(jié)點，在進行刪除。他這個排隊前面的人指向后面的人。這就是新的隊伍了沒找到，就返回錯誤。
Node<T> p = head;
int j = 1;

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 ith node is not exist!");
return default(T);
}