最近開始看數據結構，該系列筆記簡單記錄總結下所學的知識，更詳細的推薦博主StrayedKing的數據結構系列，筆記部分也摘抄了博主總結的比較好的內容。

一些基本概念和術語

數據是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。

數據元素是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。有時，一個數據元素可由若干個數據項組成，數據項是數據的不可分割的最小單位。

數據對象是性質相同的數據元素的集合，是數據的一個子集。

數據結構是相互之間存在一種或多種特定關系的數據元素的集合。根據數據元素之間關系的不同特性，通常由下列4類基本結果：

（1）集合

（2）線性結構 結構中的數據元素之間存在一個對一個的關系；

（3）樹形結構 結構中的數據元素之間存在一個對多個的關系；

（4）圖形結構或網狀結構 結構中的數據元素之間存在多個對多個的關系。

數據元素之間的關系在計算機中由兩種不同的表示方法：順序映像和非順序映像，據此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序映像和特點是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；非順序映像的特點是借助表示元素存儲地址的指針表示數據元素之間的邏輯關系。

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；一個算法還具有5個重要特性：

（1）有窮性 一個算法必須總是（對任何合法的輸入值）在執行有窮步之后結束，且每一步都可在有窮時間內完成。

（2）確定性 算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。在任何條件下，算法只有唯一的一條執行路徑，即對相同的輸入只能得到相同的輸出。

（3）可行性 一個算法是能行的，即算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現的。

（4）輸入 一個算法有零個或多個的輸入 ，這些輸入取自于某個特定的對象的集合。

（5）輸出 一個算法有一個或多個的輸出，這些輸出是同輸入有著某些特定關系的量。

線性表——順序存儲結構

線性表的順序的順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。

假設線性表的每個元素需占用l個存儲單元，并一所占的第一個單元的存儲地址作為數據元素的存儲位置。則線性表中第i+1個數據原色的存儲位置LOC(a_i+1)和第i個數據元素的存儲位置LOC(a_i)之間滿足下列關系：

?LOC(a_i+1) = LOC(a_i) + l

一般來說，線性表的第i個數據元素a_i的存儲位置為：

?LOC(a_i) = LOC(a₁) + (i-1) * l

LOC(a₁)指線性表中的第一個數據元素a₁的存儲位置，通常稱做線性表的起始位置或基地址。

只要確定了存儲線性表的起始位置，線性表中任一數據元素都可隨機存取，所以線性表的順序存儲結構是一種隨機存取的存儲結構。

若表長為n，為刪除或插入元素的時間復雜度為O(n)。

單鏈表強調元素在邏輯上緊密相鄰，所以首先想到用數組存儲。但是普通數組有著無法克服的容量限制，在不知道輸入有多少的情況下，很難確定出一個合適的容量。對此，一個較好的解決方案就是使用動態數組。首先用malloc申請一塊擁有指定初始容量的內存，這塊內存用作存儲單鏈表元素，當錄入的內容不斷增加，以至于超出了初始容量時，就用calloc擴展內存容量，這樣就做到了既不浪費內存，又可以讓單鏈表容量隨輸入的增加而自適應大小。

單鏈表順序存儲結構如下圖：

?

單鏈表強調元素在邏輯上緊密相鄰，所以首先想到用數組存儲。但是普通數組有著無法克服的容量限制，在不知道輸入有多少的情況下，很難確定出一個合適的容量。對此，一個較好的解決方案就是使用動態數組。首先用malloc申請一塊擁有指定初始容量的內存，這塊內存用作存儲單鏈表元素，當錄入的內容不斷增加，以至于超出了初始容量時，就用calloc擴展內存容量，這樣就做到了既不浪費內存，又可以讓單鏈表容量隨輸入的增加而自適應大小。

單鏈表順序存儲結構如下圖：

線性表——鏈式存儲結構

鏈式存儲刪除與插入更方便，不用來回移動大量元素。但與此對應的是存取指定位置元素時將變得費勁，因為順序存儲結構中，通過數組下標就可以獲取第i個元素，但是在鏈式存儲中，必須由頭指針或尾指針（如果有的話）開始遍歷整個鏈表直至尋找到需要的元素。在元素的查找效率方面，此兩種存儲結構無明顯差異。

最后一個結點指針通常為NULL。如果將最后一個結點的指針指向開頭，那么這個鏈表就成了循環單鏈表。

有頭結點的單鏈表：有時，在單鏈表的第一個節點之前附設一個節點，稱之為頭結點。頭結點指針指向的結點數據域為空，指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。頭結點的存在僅僅是作為標記單鏈表的開始，有頭結點的單鏈表在操作時更加方便，不用專門為頭結點的增刪情況寫額外代碼，這一點可以在實際應用中加以體會。

單鏈表鏈式存儲也用到了動態分配內存。值得注意的是，由于頭結點的指針本身就是個結構指針，所以在初始化、創建、銷毀等需要改變頭結點指針的地方，則要注意函數形參為二級指針，即指向頭指針的指針。新手很容易犯的錯誤是該用二級指針的地方使用了一級指針，這樣做的后果就是明明函數內分配了所需內存，但是外面卻訪問不到，也可能明明函數內銷毀掉的內存，外面還可以訪問到。這樣不僅會引起內存訪問差錯，甚至會引起程序崩潰，所以，這一點很值得引起重視。

線性表——靜態鏈表

靜態鏈表用數組存放數據，存取方式模擬了系統的malloc分配和free回收機制。

書中的描述如下：

//-----線性表的靜態單鏈表存儲結構-----// #define MAXSIZE 1000 typedef struct{ElemType data;int cur; }componet,SlineList[MAXSIZE];

數組的一個分量表示一個結點，同時用游標（指示器cur）代替指針指示結點在數組中的相對位置，數組的第零分量可看成頭結點，其指針域表示鏈表的第一個結點。這種存儲結構仍需要預先分配一個較大的空間，但在作線性表的插入和刪除操作時不需要移動元素，僅需修改指針，故仍具有鏈式存儲結構的主要優點。

假設SWieSLinkList型變量，則S[0].cur指示第一個結點在數組中的位置，若設i = s[0].cur，則S[i].data存儲線性表的第一個數據元素，且S[i].cur指示第二個結點在數組中的位置。一般情況，若第i個分量表示鏈表的第k個結點，則S[i].cur指示第k+1個結點的位置。因此在靜態鏈表中實現線性表的操作和動態鏈表相似，以整形游標i代替動態指針p，i = S[i].cur的操作實為指針后移（類似與p = p->next）。

在《數據結構》原書中，對靜態鏈表的表述是有些復雜的，這里對其進行了適當簡化，但中心思想不變。

靜態鏈表是特殊的順序表，它從數組（一塊連續的內存）中孕育，但行為卻類似于單鏈表，它反映出了鏈式單鏈表在系統中實現的本質。靜態鏈表依靠自身的一個游標來實現單鏈表中結構指針的作用，所以，在存取元素時，一方面要考慮靜態鏈表內部的游標變動，另一方面也要考慮整個空間中剩余內存的游標變化，因為整個內存塊同樣也是通過游標來鏈接的。

靜態鏈表存儲結構及存取機制如下圖：

?

?

靈活應用typedef來創造新類型，比如在靜態空間SPACE定義時，將整個結構數組看做了一個新的類型Component。

關于靜態鏈表的一些操作書中的我看不太明白，參考了博客《數據結構——靜態鏈表》

幾個注意點如下：

初始化時別忘了將最后一個指針域指向0；

分配空閑結點時總是取頭結點之后的第一個空閑結點，如果空閑鏈表非空，調整頭結點的值；

回收結點時總是將回收的結點放在頭結點之后。

#include <stdio.h> #define N 100 typedef struct{char data;int cur; }SList; void init_sl(SList slist[]){//初始化成空閑靜態鏈表，int i;for(i=0;i<N-1;i++){slist[i].cur=i+1;}slist[N-1].cur=0;//最后一個指針域指向0 } int malloc_sl(SList slist[]){//分配空閑結點int i=slist[0].cur;//總是取頭結點之后的第一個空閑結點做分配，同時空閑鏈表非空，頭結點做調整if (i){slist[0].cur=slist[i].cur;//空閑鏈表頭結點調整指針域 }return i;//返回申請到的空閑結點的數組下標 } void free_sl(SList slist[],int k){//將k結點回收slist[k].cur=slist[0].cur;//總是將回收的結點放在頭結點之后slist[0].cur=k; }

線性鏈表——循環鏈表

循環鏈表就是頭尾相連，表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環，由此，從表中任一結點出發均可找到表中其他結點。

循環鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環條件不是p或p->next是否為空，而是它們是否等于頭指針。

線性鏈表——雙向鏈表

單鏈表的單向性是的從某個結點出發只能順指針往后尋找其他結點，如果要尋找結點的直接前趨，需從表頭指針出發。因此，提出了雙向鏈表，一個結點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。

?

若d為指向表中某一結點的指針，則有d->next->prior = d->prior->next = d

?

?

?

?

?

轉載于:https://www.cnblogs.com/wwf828/p/9503821.html

總結

以上是生活随笔為你收集整理的【数据结构(C语言版)系列一】 线性表的全部內容，希望文章能夠幫你解決所遇到的問題。

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