鍊錶是一種採用什麼儲存結構儲存的線性表

鍊錶是一種採用「鍊式」儲存結構儲存的線性表。鍊錶的資料元素所佔的儲存單元位址可以是連續的，也可以是不連續的，可依需求暫時、動態地申請分配對應的儲存空間，資料元素之間的邏輯關係可以用「鏈」來表達。

本教學操作環境：windows7系統、Dell G3電腦。

為了克服順序表儲存結構的缺點，充分利用儲存空間和提高運作效率，線性表可以採用另一種儲存結構－鍊式儲存結構。 線性表的鍊式儲存結構簡稱「鍊錶（link list）」

一、鍊錶概述

鍊錶的資料元素所佔的儲存單元位址可以是連續的，也可以是不連續的，可根據需要暫時、動態地申請分配相應的儲存空間，資料元素之間的邏輯關係可以用「鏈」來表達。

鍊錶的插入和刪除不需要移動資料元素，只需要修改鏈即可實現。

鍊錶分類：

1.以鍊錶記憶體分配實作的方式分類

①動態鍊錶

②靜態鍊錶

#2 .依連結方式分類

①單鍊錶

②循環鍊錶

③雙鍊錶

（它們皆為動態鍊錶）

二、單鍊錶的定義

1.定義

為了表示每個資料元素ai與其直接後繼資料元素ai 1之間的邏輯關係，對於每個資料元素ai，除了儲存本身的資訊外，還需要儲存一個指示其直接後繼的資訊（後繼的儲存位置-位址）。

儲存資料元素資訊的域稱為資料域，儲存直接後繼位置的域稱為指標域 #，指標域中儲存的資訊稱為指標或鏈。

這兩部分資訊組成資料元素ai的儲存映像，稱為結點。

n個結點鏈成一個鍊錶，即線性表（a1,a2,a3,...,an）的鍊式儲存結構，因為鍊錶的每個結點只包含一個指標域，所以稱為單鍊錶。

對於線性表來說，總有個頭有個尾，鍊錶也不例外。 鍊錶中指向單鍊錶第一個結點的指標叫做頭指標，整個鍊錶的存取必須從頭指標開始進行，之後的每個結點都是上個結點的後繼指標指向的位置。 鍊錶的最後一個結點的指標為「空（通常用NULL表示）」－空指標。

為了方便實現鍊錶的各種運算，在單鍊錶的第一個資料結點之前設一個相同類型的結點，該結點稱為頭結點。

頭結點的資料域可以儲存一個特殊的標誌資訊如鍊錶的長度，也可以不儲存任何資料。

鍊錶的第一個資料結點和最後一個結點又稱為首結點和尾結點。

 2.頭指標與頭結點的異同點

頭指標：

• 頭指標是指標中指向第一個結點的指針，若鍊錶有頭結點，則是指向頭結點的指針。
• 頭指標具有標識作用，常用頭指標冠以鍊錶的名字。
• 無論鍊錶是否為空，頭指標皆不為空。 頭指標是鍊錶的必要元素。

頭結點：

•  頭結點是為了操作的統一和方便而設立的，放在第一個元素的結點之前，其資料域一般無意。
• 有了頭結點，對在第一元素結點前插入結點和刪除第一個結點，其操作與其他結點的操作就統一了。
• 頭結點不一定是鍊錶必須要素。

 3.程式碼示範

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

#

三、单链表的操作

1.插入操作

1）插入模拟

假设存储元素e的结点为s,将s插入到ai结点后面，如何操作？

思考：两句插入代码能否交换？

不能，如果调换过来，会导致ai 1等后面的元素无法找到，因为s的指针域没有指向ai 1的地址。

2）单链表第i个数据插入结点的算法思路

•  声明一个结点p指向链表的第一个结点，初始化j=1;
• 当j
• 若到链表末尾p为空，则说明第i个元素不存在；若查找成功，生成一个空节点s（使用malloc函数）
• 将数据元素e赋值給s->data,即为s->data=e;
• 插入标准语句：s->next=p->next；p->next=s;
• 返回成功。

2.删除操作

1）删除模拟

假设存储元素ai的结点为q,要实现将结点q删除单链表的操作。

2）单链表删除第i个数据结点的算法思路

•  声明一个结点p指向链表的第一个结点，初始化j=1;
• 当j
• 若到链表末尾p为空，则说明第i个元素不存在；若查找成功，将删除结点p->next赋值給q
• 插入标准语句：p->next=q->next；
• 将q结点赋值給e,即为e=q->data;
• 释放q结点
• 返回成功。

四、单链表结构和顺序表结构对比

存储方式：

• 顺序表用一段连续的存储单元依次存储线性表中的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表元素

时间性能：

①查找

• 顺序表O(1)
• 单链表O(n)

②插入和删除

• 顺序表O(n)
• 单链表O(1)

空间性能：

• 顺序表需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要预分配存储空间，需要多少都可以分配，元素个数不受限制

更多相关知识，请访问常见问题栏目！

以上是鍊錶是一種採用什麼儲存結構儲存的線性表的詳細內容。更多資訊請關注PHP中文網其他相關文章！