C#數據結構與算法揭秘三鏈表

2020-01-24 03:39:58

字體：大中小

來源：轉載

供稿：網友

上文我們討論了一種最簡單的線性結構――順序表，這節我們要討論另一種線性結構――鏈表。

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

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

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

現實中，就像一隊盲人過馬路。如圖所示

把單鏈表結點看作是一個類，類名為 Node<T>。單鏈表結點類的實現如下所示。

復制代碼代碼如下:

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

下圖是線性表(a1,a2,a3,a4,a5,a6)對應的鏈式存儲結構示意圖。

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

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

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

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

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

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

set
{
head = value;
}
}

//構造器

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

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

//求單鏈表的長度
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;

不懂的一切盡在圖例中

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

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

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

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

//而這個是將其循環到隊列相應的位置，在將從頭其插入到這個位置

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

一切盡在圖例中

}

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

//刪除單鏈表的第i個結點
public T Delete(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 == 1)
{
q = head;
head = head.Next;
return q.Data;
}
此步驟為O(1)

//不是的頭位置的吧，就尋找相應位置的節點，在進行刪除。他這個排隊前面的人指向后面的人。這就是新的隊伍了沒找到，就返回錯誤。
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);
}