大話數據結構學習筆記—靜態鏈表學習

c語言真是好東西，它具有指針能力，使得它可以非常容易地操作內存中的地址和數據，這比其他高級語言更加靈活方便。

后來的面向對象的語言，如java、C#等，雖然不使用指針，但是因為啟用了對象引用機制，從某種角度也間接實現了指針的
某些作用。但是對一些Basic、Fortran等早期的編程高級語言，由于沒有指針,鏈表結構按照前面我們的講法，它就沒法實現了。
有人想出來用數組來代替指針。他們是怎么做到的呢？
首先我們讓數組的元素都是由2個數據域組成，data和cur。也就說，數組的每個下標都對應一個data和一個cur。數據域，用來
存放數據元素，也就是我們要處理的數據；而游標相當于單鏈表中的next指針，存放該元素的后繼在數組中的下標。
我們把這種用數組描述的鏈表叫做靜態鏈表。

為了方便插入數據，我們通常會把數據建立的大一些，以便有一些空閑空間可以便于插入時不溢出。

靜態鏈表將數組第一個元素用來指向備用鏈表（鏈表中沒用到的空間）中的第一元素，最后一個元素用來指向第一個存數據的元素相當于頭結點的作用。

數據結構

1、????????用結構體模擬數組成員

a)????typedef struct Element{DataTypedata,int cur}

2、????????用結構體數組模擬靜態鏈表相關算法，長度確定后不可變?。

a)????typedef Element StaticLinkStatic[MAXSIZE]?;

初始化

數組第一個元素指向第一個可用元素也就是第二個元素下標[1]。

數組最后一個元素，類似頭指針作用，指向第一個存放數據元素的下標，空鏈表 cor 為0,其他空閑元素可初始化依次指向其后面一個元素。

插入操作

動態鏈表中分配空間使用malloc函數，但是靜態鏈表中，實質上我們定義鏈表時，空間大小已經確定了，那么我們要插入數據同樣也要一個空間，只不過空間已經在鏈表中分配了只不過是空閑的還沒拿出來用了，我們需要一個類似的函數將空閑位置拿來存入我們需要的數據，這里涉及到幾個要操作的地方

1)???取出一個備用元素后，那么第一個元素指向備用鏈表要改變指向，指向取出元素的后繼元素。其實就是完成分配空間操作。

2)???插入元素時，要找到插入元素位置前一個元素 i-1，需要改變他的cur 指向改為插入元素的 下標，而插入元素 的cur指向 要改為 i-1指向元素的下標。

刪除操作

刪除元素空間，因為是靜態鏈表空間已經固定，不能真正的在內存將其釋放而是將其放到靜態鏈表的備用鏈表中，可以繼續供鏈表所使用。同樣需要類似free函數來釋放元素，操作和插入相反。

1）????????將刪除元素的 前置結點 cur 指向 刪除元素的后置結點的下標

2）????????釋放刪除元素所占位置，將其置為備用鏈中的第一個可用元素

?

其他操作

獲取鏈表元素個數

最后一個元素cur為0 根據這個條件計數

打印鏈表元素

下面看下實現代碼

#define MAXSIZE 500 #define OK 1 #define ERROR 0 #include <stdio.h>typedef int Status; typedef char DataType; typedef struct Element Element; typedef Element StaticLinkList[MAXSIZE];//結構體數組 struct Element {DataType data;//數據int cur;//游標，后繼結點的下標 }; //初始化靜態鏈表 //靜態鏈表將數組第一個元素用來指向備用鏈表中的第一元素，最后一個元素用來指向第一個存數據的元素 相當于頭結點的作用,下標0和num-1 作為對外展示的鏈表元素。 Status initSLL(StaticLinkList sll) {int i = 0;//由于是空鏈表，list[0].cur 指向下標為2到MAXSIZE-2元素備用鏈表，這樣剛好一個指向一個//[0].cur為1 指向下標為1的元素，[1].cur位2指向下標為2的元素，依次類推//注意[MAXSIZE-2]為最后一個可用元素，指向[MAXSIZE-1]元素，做特殊處理，大話數據結構中 沒有做處理。for (i = 0; i < MAXSIZE; i++) {sll[i].cur = i + 1;}sll[MAXSIZE - 2].cur = 0;sll[MAXSIZE - 1].cur = 0;//空鏈表，它的cur是存儲元的第一個位置的下標。return OK; } //創建一個可以使用的下標元素,將備用鏈中的第一個元素下標返回，讓靜態鏈表第一個元素重新指向下一個備用元素。 int mollocEle(StaticLinkList sll) {int i = (sll)[0].cur;if (i) {//有可用的備用元素(sll)[0].cur = (sll)[i].cur;}return i; } //釋放第k個元素的讓其成為備用鏈表中的元素，讓靜態鏈表第一個元素（下標為0）的元素指向它，它指向原來備用鏈第一個元素 void freeEle(StaticLinkList sll,int p) {sll[p].cur = sll[0].cur;sll[0].cur = sll[p].cur;return; }//打印靜態鏈表內容 void printStaticLinkList(StaticLinkList sll) {int begin = sll[MAXSIZE - 1].cur;//找到起始元素Element e;//begin為0 要么為空鏈表 要么鏈表數據遍歷完畢while(begin) {e = sll[begin];printf("%c ", e.data);begin = e.cur;}return; } int lengthSSL(StaticLinkList sll) {int begin = sll[MAXSIZE - 1].cur;int i = 0;//begin 為0 要么為空鏈表 要么鏈表遍歷完畢while (begin){begin = sll[begin].cur;i++;}return i; } //插入位置i，找到i-1元素，將i元素的cur指向i-1的后繼元素，將i-1元素指向插入元素即可 //i不是數組下標而是鏈表中的第i個元素，cur存儲的才是下標 Status insertSLL(StaticLinkList sll, int i, DataType data) {if (i<1 || i>lengthSSL(sll)+1) {//可以插在元素末尾！比如說有5個元素可以插在第6位置，但不能插入到第7個以及后面return ERROR;}int j = mollocEle(sll);if (!j) {//分配空間失敗return ERROR;}int begin = MAXSIZE - 1;//第一次進入循環，找到第一個數據元素for (size_t k = 1; k <= i-1; k++){begin = sll[begin].cur;}//循環結束 begin為i-1個元素的下標sll[j].cur = sll[begin].cur;sll[j].data = data;sll[begin].cur = j;return OK; } //刪除位置i，找到i-1個元素，將第i個元素的cur指向i-1的后繼元素，將i-1元素指向插入元素即可 Status delSLLEle(StaticLinkList sll, int i) {if (i<1 || i>lengthSSL(sll)) {return ERROR;}int begin = MAXSIZE - 1;//第一次進入循環，找到第一個數據元素for (size_t k = 1; k <= i - 1; k++){begin = sll[begin].cur;}//循環結束 begin為i-1個元素的下標int curE = sll[begin].cur;//刪除元素的下標sll[begin].cur = sll[curE].cur;//i-1個元素指向 i+1個元素freeEle(sll,curE);//釋放i元素，放回備用鏈表return OK; } int main() {StaticLinkList L;Status i;i = initSLL(L);printf("初始化L后：L.length=%d\n", lengthSSL(L));/*注意第一個元素必須插入到第一位置！因為空表里面沒有元素，插入位置不在范圍內同樣不能插入插入范圍 1 ~ 現有元素個數+1 都可以*/i = insertSLL(L, 1, 'A');i = insertSLL(L, 2, 'B');i = insertSLL(L, 3, 'C');i = insertSLL(L, 4, 'D');i = insertSLL(L, 5, 'E');printf("\n在L的表尾依次插入ABCDE后：\nL.data=");printStaticLinkList(L);i = insertSLL(L, 3, 'Y');printf("\n在L的“B”與“C”之間插入“Y”后：\nL.data=");printStaticLinkList(L);i = delSLLEle(L, 2);printf("\n在L的刪除“B”后：\nL.data=");printStaticLinkList(L);printf("\n");return 0; }
驗證結果截圖：

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的静态链表相关算法学习的全部內容，希望文章能夠幫你解決所遇到的問題。

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