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

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

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

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

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

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

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

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

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

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

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

//構(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)對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。

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

//這是一個(gè)盲人過馬路的類的模擬

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

//排在第一個(gè)位置的盲人

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

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

set
{
head = value;
}
}

//構(gòu)造器

//開始的時(shí)候一個(gè)盲人都沒有，頭結(jié)點(diǎn)指向?yàn)榭盏奈恢谩]有排頭的盲人
public LinkList()
{
head = null;
}

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

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

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

//不讓盲人排隊(duì)，就是讓這個(gè)隊(duì)的頭都不存在

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

//判斷一個(gè)盲人隊(duì)列的是不是為空，看他的頭部是不是有人

//判斷單鏈表是否為空
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>();
//這里如果沒有盲人排隊(duì)的話，就在隊(duì)列的頭部進(jìn)行了

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

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

p.Next = q;

不懂的一切盡在圖例中

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

//就是在一隊(duì)中增加了插隊(duì)的人員

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

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

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

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;
}

一切盡在圖例中

}

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

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

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

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

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

//不是的頭位置的吧，就尋找相應(yīng)位置的節(jié)點(diǎn)，在進(jìn)行刪除。他這個(gè)排隊(duì)前面的人指向后面的人。這就是新的隊(duì)伍了沒找到，就返回錯(cuò)誤。
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);
}

不懂的如圖所示：

此方法的運(yùn)行時(shí)間復(fù)雜度是O(n)
}

//獲得單鏈表的第i個(gè)數(shù)據(jù)元素

//知道隊(duì)伍我要查詢出隊(duì)伍中第n個(gè)人是那位，
public T GetElem(int i)
{

//如果是空的就返回為錯(cuò)誤的結(jié)果
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}

//從圖接點(diǎn)數(shù) 第n個(gè)的結(jié)果了
Node<T> p = new Node<T>();
p = head;
int j = 1;

while (p.Next != null&& j < i)
{

++j;
p = p.Next;
}
//有著則返回沒有就返回錯(cuò)誤

if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}

不懂的，一切盡在圖例中。