寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.靜態鏈表的概述
2.靜態鏈表的實現
???? ?? 靜態鏈表的結點
???? ?? 備用鏈表
???? ?? 靜態鏈表的詳細實現過程
3.靜態鏈表的代碼實現
???? ?? 靜態鏈表初始化
???? ?? 靜態鏈表的提取分配空間
???? ?? 靜態鏈表添加元素
???? ?? 釋放空間
???? ?? 靜態鏈表刪除元素
???? ?? 修改元素
???? ?? 查找元素
4.靜態鏈表的完整代碼實現及演示
5.靜態鏈表和動態鏈表的聯系和區別
???? ?? 靜態鏈表
???? ?? 動態鏈表

1.靜態鏈表的概述

我們了解線性表兩種存儲結構各自的特點，那么，是否存在一種存儲結構，可以融合順序表和鏈表各自的優點，從而 既能快速訪問元素，又能快速增加或刪除數據元素。

使用靜態鏈表存儲數據，數據全部存儲在數組中（和順序表一樣），但存儲位置是隨機的，數據之間"一對一"的邏輯關系通過一個整形變量（稱為"游標"，和指針功能類似）維持（和鏈表類似）。

數據存放到數組中時，給各個數據元素配備一個整形變量，此變量用于指明各個元素的直接后繼元素所在數組中的位置下標，如圖 :

通常，靜態鏈表會將第一個數據元素放到數組下標為 1 的位置（a[1]）中。

上圖中，從 a[1] 存儲的數據元素 1 開始，通過存儲的游標變量 3，就可以在 a[3] 中找到元素 1 的直接后繼元素 2；同樣，通過元素 a[3] 存儲的游標變量 5，可以在 a[5] 中找到元素 2 的直接后繼元素 3，這樣的循環過程直到某元素的游標變量為 0 截止（因為 a[0] 默認不存儲數據元素）。

如上通過 "數組+游標" 的方式存儲具有線性關系數據的存儲結構就是靜態鏈表。

2.靜態鏈表的實現

2.1靜態鏈表的結點

靜態鏈表存儲數據元素也需要自定義數據類型，至少需要包含以下 2 部分信息：

數據域：用于存儲數據元素的值；

游標：其實就是數組下標，表示直接后繼元素所在數組中的位置；

因此，靜態鏈表中節點的構成用 C 語言實現為： typedef struct {int data;//數據域int cur;//游標 }component;

2.2備用鏈表

其實上面顯示的靜態鏈表還不夠完整，靜態鏈表中，除了數據本身通過游標組成的鏈表外，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表。

備用鏈表的作用是：

回收數組中未使用或之前使用過（目前未使用）的存儲空間，留待后期使用。

也就是說，靜態鏈表使用數組申請的物理空間中，存有兩個鏈表，一條連接數據，另一條連接數組中未使用的空間。通常，備用鏈表的表頭位于數組下標為 0（a[0]） 的位置，而數據鏈表的表頭位于數組下標為 1（a[1]）的位置。

靜態鏈表中設置備用鏈表的好處是:

可以清楚地知道數組中是否有空閑位置，以便數據鏈表添加新數據時使用。比如，若靜態鏈表中數組下標為 0 的位置上存有數據，則證明數組已滿。

例如，使用靜態鏈表存儲 {1,2,3}，假設使用長度為 6 的數組 a，則存儲狀態可能如圖所示：
上圖備用鏈表上連接的依次是 a[0]、a[2] 和 a[4]，而數據鏈表上連接的依次是 a[1]、a[3] 和 a[5]。

2.3靜態鏈表的詳細實現過程

假設使用靜態鏈表（數組長度為 6）存儲 {1,2,3}，則需經歷以下幾個階段。

1.在數據鏈表未初始化之前，數組中所有位置都處于空閑狀態，因此都應被鏈接在備用鏈表上

當向靜態鏈表中添加數據時，需提前從備用鏈表中摘除節點，以供新數據使用。
備用鏈表摘除節點最簡單的方法是摘除 a[0] 的直接后繼節點；同樣，向備用鏈表中添加空閑節點也是添加作為 a[0] 新的直接后繼節點。因為 a[0] 是備用鏈表的第一個節點，我們知道它的位置，操作它的直接后繼節點相對容易，無需遍歷備用鏈表，耗費的時間復雜度為 O(1)。

2 .因此，在上圖的基礎上，向靜態鏈表中添加元素 1 的過程下圖 所示：

添加元素 2 的過程如圖:

添加元素3的過程如圖

當然我們有時候會看到靜態鏈表最后數組最后一個位置的數據域不存放任何東西，游標域存放首元結點的數組下標(相當于頭結點)

3.靜態鏈表的代碼實現(最后一個數組元素相當于頭結點)

3.1靜態鏈表初始化

void InitArr(component *array) {int i = 0;for (i = 0; i < maxSize; i++) {array[i].cur = i + 1;//將每個數組分量鏈接到一起array[i].data = 0;}array[maxSize - 1].cur = 0;//鏈表最后一個結點的游標值為0 }

3.2靜態鏈表的提取分配空間

int mallocArr(component * array) {//若備用鏈表非空，則返回分配的結點下標，否則返回 0（當分配最后一個結點時，//該結點的游標值為 0）int i = array[0].cur;if (array[0].cur) {array[0].cur = array[i].cur;}return i; }

3.3靜態鏈表添加元素

//向鏈表中插入數據，body表示鏈表的頭結點在數組中的位置，add表示插入元素的位置，num表示要插入的數據 void insertArr(component * array, int body, int add, int num) {int tempBody = body;//tempBody做遍歷結構體數組使用int i = 0, insert = 0;//找到要插入位置的上一個結點在數組中的位置for (i = 1; i < add; i++) {tempBody = array[tempBody].cur;}insert = mallocArr(array);//申請空間，準備插入array[insert].data = num;array[insert].cur = array[tempBody].cur;//新插入結點的游標等于其直接前驅結點的游標array[tempBody].cur = insert;//直接前驅結點的游標等于新插入結點所在數組中的下標 }

3.4釋放空間

void freeArr(component * array, int k) {array[k].cur = array[0].cur;array[0].cur = k; }

3.5靜態鏈表刪除元素

//刪除結點函數，num表示被刪除結點中數據域存放的數據 int deletArr(component * array, int num) {int tempBody =maxSize-1;int del = 0;int newbody = 0;//找到被刪除結點的位置while (array[tempBody].data != num) {tempBody = array[tempBody].cur;//當tempBody為0時，表示鏈表遍歷結束，說明鏈表中沒有存儲該數據的結點if (tempBody == 0) {printf("鏈表中沒有此數據");return 0;}}//運行到此，證明有該結點del = tempBody;tempBody = maxSize-1;//刪除首元結點，需要特殊考慮if (del == array[maxSize-1].cur) {newbody = array[del].cur;array[maxSize-1].cur=newbody; freeArr(array, del);}else{//找到該結點的上一個結點，做刪除操作while (array[tempBody].cur != del) {tempBody = array[tempBody].cur;}//將被刪除結點的游標直接給被刪除結點的上一個結點array[tempBody].cur = array[del].cur;//回收被摘除節點的空間freeArr(array, del);} }

3.6修改元素

void amendElem(component * array, int oldElem, int newElem) {int add = selectNum(array,oldElem);if (add == -1) {printf("無更改元素");return;}array[add].data = newElem; }

3.7查找元素

int selectNum(component * array, int num) {//當游標值為0時，表示鏈表結束int tempBody = maxSize-1; while (array[tempBody].cur != 0) {if (array[tempBody].data == num) {return tempBody;}tempBody = array[tempBody].cur;}//判斷最后一個結點是否符合要求if (array[tempBody].data == num) {return tempBody;}return -1;//返回-1，表示在鏈表中沒有找到該元素 }

4.靜態鏈表完整代碼實現及演示

#include <stdio.h> #define maxSize 6 typedef struct {int data;int cur; }component; void InitArr(component *array) {int i = 0;for (i = 0; i < maxSize; i++) {array[i].cur = i + 1;//將每個數組分量鏈接到一起array[i].data = 0;}array[maxSize - 1].cur = 0;//鏈表最后一個結點的游標值為0 } int mallocArr(component * array) {//若備用鏈表非空，則返回分配的結點下標，否則返回 0（當分配最后一個結點時，//該結點的游標值為 0）int i = array[0].cur;if (array[0].cur) {array[0].cur = array[i].cur;}return i; } //初始化幾個元素 void add(component * array) {printf("請輸入你想添加的數據成員的數量：");int n;scanf("%d",&n);for(int i=1;i<=n;i++){printf("請輸入第%d個數據成員：",i);scanf("%d",&array[i].data); }array[0].cur=n+1;array[n].cur=0;array[maxSize-1].cur=1; } //向鏈表中插入數據,add表示插入元素的位置，num表示要插入的數據 void insertArr(component * array, int add, int num) {int tempBody = maxSize-1;//tempBody做遍歷結構體數組使用int i = 0, insert = 0;//找到要插入位置的上一個結點在數組中的位置for (i = 1; i < add; i++) {tempBody = array[tempBody].cur;}insert = mallocArr(array);//申請空間，準備插入array[insert].data = num;array[insert].cur = array[tempBody].cur;//新插入結點的游標等于其直接前驅結點的游標array[tempBody].cur = insert;//直接前驅結點的游標等于新插入結點所在數組中的下標 } void displayArr(component * array) {int tempBody = maxSize-1;//tempBody準備做遍歷使用tempBody=array[tempBody].cur;while (array[tempBody].cur) {printf("%d,%d ", array[tempBody].data, array[tempBody].cur);tempBody = array[tempBody].cur;}printf("%d,%d\n", array[tempBody].data, array[tempBody].cur); } //查找數據域為elem的結點在數組中的位置 int selectNum(component * array, int num) {//當游標值為0時，表示鏈表結束int tempBody = maxSize-1; while (array[tempBody].cur != 0) {if (array[tempBody].data == num) {return tempBody;}tempBody = array[tempBody].cur;}//判斷最后一個結點是否符合要求if (array[tempBody].data == num) {return tempBody;}return -1;//返回-1，表示在鏈表中沒有找到該元素 }//在以body作為頭結點的鏈表中將數據域為oldElem的結點，數據域改為newElem void amendElem(component * array, int oldElem, int newElem) {int add = selectNum(array,oldElem);if (add == -1) {printf("無更改元素");return;}array[add].data = newElem; }void freeArr(component * array, int k) {array[k].cur = array[0].cur;array[0].cur = k; }//刪除結點函數，num表示被刪除結點中數據域存放的數據，函數返回新數據鏈表的表頭位置 int deletArr(component * array, int num) {int tempBody =maxSize-1;int del = 0;int newbody = 0;//找到被刪除結點的位置while (array[tempBody].data != num) {tempBody = array[tempBody].cur;//當tempBody為0時，表示鏈表遍歷結束，說明鏈表中沒有存儲該數據的結點if (tempBody == 0) {printf("鏈表中沒有此數據");return 0;}}//運行到此，證明有該結點del = tempBody;tempBody = maxSize-1;//刪除首元結點，需要特殊考慮if (del == array[maxSize-1].cur) {newbody = array[del].cur;array[maxSize-1].cur=newbody; freeArr(array, del);}else{//找到該結點的上一個結點，做刪除操作while (array[tempBody].cur != del) {tempBody = array[tempBody].cur;}//將被刪除結點的游標直接給被刪除結點的上一個結點array[tempBody].cur = array[del].cur;//回收被摘除節點的空間freeArr(array, del);} } int main() {component array[maxSize];InitArr(array);add(array);int selectAdd;printf("靜態鏈表為：\n");displayArr(array);printf("在第3的位置上插入元素4:\n");insertArr(array, 3, 4);displayArr(array);printf("刪除數據域為1的結點:\n");deletArr(array, 1);displayArr(array);printf("查找數據域為4的結點的位置:\n");selectAdd = selectNum(array, 4);printf("%d\n", selectAdd);printf("將結點數據域為4改為5:\n");amendElem(array, 4, 5);displayArr(array);return 0;}

靜態鏈表和動態鏈表的聯系和區別

5.1靜態鏈表

使用靜態鏈表存儲數據，需要預先申請足夠大的一整塊內存空間，也就是說，靜態鏈表存儲數據元素的個數從其創建的那一刻就已經確定，后期無法更改。
比如，如果創建靜態鏈表時只申請存儲 10 個數據元素的空間，那么在使用靜態鏈表時，數據的存儲個數就不能超過 10 個，否則程序就會發生錯誤。不僅如此，靜態鏈表是在固定大小的存儲空間內隨機存儲各個數據元素，這就造成了靜態鏈表中需要使用另一條鏈表（通常稱為"備用鏈表"）來記錄空間存儲空間的位置，以便后期分配給新添加元素使用，如圖 2 所示。這意味著，如果你選擇使用靜態鏈表存儲數據，你需要通過操控兩條鏈表，一條是存儲數據，另一條是記錄空閑空間的位置。

有一點需要特別的注意：

有的靜態鏈表最后一個數組下標存放的是頭結點，而有的靜態鏈表最后一個數組下標和普通數組下標作用一樣

5.2動態鏈表(普通鏈表)

使用動態鏈表存儲數據，不需要預先申請內存空間，而是在需要的時候才向內存申請。也就是說，動態鏈表存儲數據元素的個數是不限的，想存多少就存多少。
同時，使用動態鏈表的整個過程，你也只需操控一條存儲數據的鏈表。當表中添加或刪除數據元素時，你只需要通過 malloc 或free 函數來申請或釋放空間即可，實現起來比較簡單。

本篇博客轉載C語言中文網

總結

以上是生活随笔為你收集整理的高级线性表——静态链表(最全静态链表解读)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。