最近開(kāi)始看數(shù)據(jù)結(jié)構(gòu)，該系列筆記簡(jiǎn)單記錄總結(jié)下所學(xué)的知識(shí)，更詳細(xì)的推薦博主StrayedKing的數(shù)據(jù)結(jié)構(gòu)系列，筆記部分也摘抄了博主總結(jié)的比較好的內(nèi)容。

一些基本概念和術(shù)語(yǔ)

數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。

數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常由下列4類基本結(jié)果：

（1）集合

（2）線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系；

（3）樹(shù)形結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系；

（4）圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。

數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中由兩種不同的表示方法：順序映像和非順序映像，據(jù)此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序映像和特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序映像的特點(diǎn)是借助表示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

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

（1）有窮性 一個(gè)算法必須總是（對(duì)任何合法的輸入值）在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。

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

（3）可行性 一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。

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

（5）輸出 一個(gè)算法有一個(gè)或多個(gè)的輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

線性表——順序存儲(chǔ)結(jié)構(gòu)

線性表的順序的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

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

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

一般來(lái)說(shuō)，線性表的第i個(gè)數(shù)據(jù)元素a_i的存儲(chǔ)位置為：

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

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

只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

若表長(zhǎng)為n，為刪除或插入元素的時(shí)間復(fù)雜度為O(n)。

單鏈表強(qiáng)調(diào)元素在邏輯上緊密相鄰，所以首先想到用數(shù)組存儲(chǔ)。但是普通數(shù)組有著無(wú)法克服的容量限制，在不知道輸入有多少的情況下，很難確定出一個(gè)合適的容量。對(duì)此，一個(gè)較好的解決方案就是使用動(dòng)態(tài)數(shù)組。首先用malloc申請(qǐng)一塊擁有指定初始容量的內(nèi)存，這塊內(nèi)存用作存儲(chǔ)單鏈表元素，當(dāng)錄入的內(nèi)容不斷增加，以至于超出了初始容量時(shí)，就用calloc擴(kuò)展內(nèi)存容量，這樣就做到了既不浪費(fèi)內(nèi)存，又可以讓單鏈表容量隨輸入的增加而自適應(yīng)大小。

單鏈表順序存儲(chǔ)結(jié)構(gòu)如下圖：

?

單鏈表強(qiáng)調(diào)元素在邏輯上緊密相鄰，所以首先想到用數(shù)組存儲(chǔ)。但是普通數(shù)組有著無(wú)法克服的容量限制，在不知道輸入有多少的情況下，很難確定出一個(gè)合適的容量。對(duì)此，一個(gè)較好的解決方案就是使用動(dòng)態(tài)數(shù)組。首先用malloc申請(qǐng)一塊擁有指定初始容量的內(nèi)存，這塊內(nèi)存用作存儲(chǔ)單鏈表元素，當(dāng)錄入的內(nèi)容不斷增加，以至于超出了初始容量時(shí)，就用calloc擴(kuò)展內(nèi)存容量，這樣就做到了既不浪費(fèi)內(nèi)存，又可以讓單鏈表容量隨輸入的增加而自適應(yīng)大小。

單鏈表順序存儲(chǔ)結(jié)構(gòu)如下圖：

線性表——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)刪除與插入更方便，不用來(lái)回移動(dòng)大量元素。但與此對(duì)應(yīng)的是存取指定位置元素時(shí)將變得費(fèi)勁，因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)中，通過(guò)數(shù)組下標(biāo)就可以獲取第i個(gè)元素，但是在鏈?zhǔn)酱鎯?chǔ)中，必須由頭指針或尾指針（如果有的話）開(kāi)始遍歷整個(gè)鏈表直至尋找到需要的元素。在元素的查找效率方面，此兩種存儲(chǔ)結(jié)構(gòu)無(wú)明顯差異。

最后一個(gè)結(jié)點(diǎn)指針通常為NULL。如果將最后一個(gè)結(jié)點(diǎn)的指針指向開(kāi)頭，那么這個(gè)鏈表就成了循環(huán)單鏈表。

有頭結(jié)點(diǎn)的單鏈表：有時(shí)，在單鏈表的第一個(gè)節(jié)點(diǎn)之前附設(shè)一個(gè)節(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)指針指向的結(jié)點(diǎn)數(shù)據(jù)域?yàn)榭?#xff0c;指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針（即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置）。頭結(jié)點(diǎn)的存在僅僅是作為標(biāo)記單鏈表的開(kāi)始，有頭結(jié)點(diǎn)的單鏈表在操作時(shí)更加方便，不用專門為頭結(jié)點(diǎn)的增刪情況寫(xiě)額外代碼，這一點(diǎn)可以在實(shí)際應(yīng)用中加以體會(huì)。

單鏈表鏈?zhǔn)酱鎯?chǔ)也用到了動(dòng)態(tài)分配內(nèi)存。值得注意的是，由于頭結(jié)點(diǎn)的指針本身就是個(gè)結(jié)構(gòu)指針，所以在初始化、創(chuàng)建、銷毀等需要改變頭結(jié)點(diǎn)指針的地方，則要注意函數(shù)形參為二級(jí)指針，即指向頭指針的指針。新手很容易犯的錯(cuò)誤是該用二級(jí)指針的地方使用了一級(jí)指針，這樣做的后果就是明明函數(shù)內(nèi)分配了所需內(nèi)存，但是外面卻訪問(wèn)不到，也可能明明函數(shù)內(nèi)銷毀掉的內(nèi)存，外面還可以訪問(wèn)到。這樣不僅會(huì)引起內(nèi)存訪問(wèn)差錯(cuò)，甚至?xí)鸪绦虮罎?#xff0c;所以，這一點(diǎn)很值得引起重視。

線性表——靜態(tài)鏈表

靜態(tài)鏈表用數(shù)組存放數(shù)據(jù)，存取方式模擬了系統(tǒng)的malloc分配和free回收機(jī)制。

書(shū)中的描述如下：

//-----線性表的靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)-----// #define MAXSIZE 1000 typedef struct{ElemType data;int cur; }componet,SlineList[MAXSIZE];

數(shù)組的一個(gè)分量表示一個(gè)結(jié)點(diǎn)，同時(shí)用游標(biāo)（指示器cur）代替指針指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置，數(shù)組的第零分量可看成頭結(jié)點(diǎn)，其指針域表示鏈表的第一個(gè)結(jié)點(diǎn)。這種存儲(chǔ)結(jié)構(gòu)仍需要預(yù)先分配一個(gè)較大的空間，但在作線性表的插入和刪除操作時(shí)不需要移動(dòng)元素，僅需修改指針，故仍具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)。

假設(shè)SWieSLinkList型變量，則S[0].cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置，若設(shè)i = s[0].cur，則S[i].data存儲(chǔ)線性表的第一個(gè)數(shù)據(jù)元素，且S[i].cur指示第二個(gè)結(jié)點(diǎn)在數(shù)組中的位置。一般情況，若第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則S[i].cur指示第k+1個(gè)結(jié)點(diǎn)的位置。因此在靜態(tài)鏈表中實(shí)現(xiàn)線性表的操作和動(dòng)態(tài)鏈表相似，以整形游標(biāo)i代替動(dòng)態(tài)指針p，i = S[i].cur的操作實(shí)為指針后移（類似與p = p->next）。

在《數(shù)據(jù)結(jié)構(gòu)》原書(shū)中，對(duì)靜態(tài)鏈表的表述是有些復(fù)雜的，這里對(duì)其進(jìn)行了適當(dāng)簡(jiǎn)化，但中心思想不變。

靜態(tài)鏈表是特殊的順序表，它從數(shù)組（一塊連續(xù)的內(nèi)存）中孕育，但行為卻類似于單鏈表，它反映出了鏈?zhǔn)絾捂湵碓谙到y(tǒng)中實(shí)現(xiàn)的本質(zhì)。靜態(tài)鏈表依靠自身的一個(gè)游標(biāo)來(lái)實(shí)現(xiàn)單鏈表中結(jié)構(gòu)指針的作用，所以，在存取元素時(shí)，一方面要考慮靜態(tài)鏈表內(nèi)部的游標(biāo)變動(dòng)，另一方面也要考慮整個(gè)空間中剩余內(nèi)存的游標(biāo)變化，因?yàn)檎麄€(gè)內(nèi)存塊同樣也是通過(guò)游標(biāo)來(lái)鏈接的。

靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)及存取機(jī)制如下圖：

?

?

靈活應(yīng)用typedef來(lái)創(chuàng)造新類型，比如在靜態(tài)空間SPACE定義時(shí)，將整個(gè)結(jié)構(gòu)數(shù)組看做了一個(gè)新的類型Component。

關(guān)于靜態(tài)鏈表的一些操作書(shū)中的我看不太明白，參考了博客《數(shù)據(jù)結(jié)構(gòu)——靜態(tài)鏈表》

幾個(gè)注意點(diǎn)如下：

初始化時(shí)別忘了將最后一個(gè)指針域指向0；

分配空閑結(jié)點(diǎn)時(shí)總是取頭結(jié)點(diǎn)之后的第一個(gè)空閑結(jié)點(diǎn)，如果空閑鏈表非空，調(diào)整頭結(jié)點(diǎn)的值；

回收結(jié)點(diǎn)時(shí)總是將回收的結(jié)點(diǎn)放在頭結(jié)點(diǎn)之后。

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

線性鏈表——循環(huán)鏈表

循環(huán)鏈表就是頭尾相連，表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。

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

線性鏈表——雙向鏈表

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

?

若d為指向表中某一結(jié)點(diǎn)的指針，則有d->next->prior = d->prior->next = d

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/wwf828/p/9503821.html

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。