數(shù)據(jù)結(jié)構(gòu)中鏈表及常見操作(已修改)
2025-07-12 21:12 本頁面
【正文】 鏈表1 定義鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)。使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。在計算機科學(xué)中，鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)可以用來生成其它類型的數(shù)據(jù)結(jié)構(gòu)。鏈表通常由一連串節(jié)點組成，每個節(jié)點包含任意的實例數(shù)據(jù)（data fields）和一或兩個用來指向明上一個或下一個節(jié)點的位置的鏈接（links）。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序，數(shù)據(jù)的訪問往往要在不同的排列順序中轉(zhuǎn)換。而鏈表是一種自我指示數(shù)據(jù)類型，因為它包含指向另一個相同類型的數(shù)據(jù)的指針（鏈接）。鏈表允許插入和移除表上任意位置上的節(jié)點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。2 結(jié)構(gòu) 單向鏈表鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節(jié)點，而最后一個節(jié)點則指向一個空值。一個單向鏈表的節(jié)點被分成兩個部分。第一個部分保存或者顯示關(guān)于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址。單向鏈表只可向一個方向遍歷。鏈表最基本的結(jié)構(gòu)是在每個節(jié)點保存數(shù)據(jù)和到下一個節(jié)點的地址，在最后一個節(jié)點保存一個特殊的結(jié)束標(biāo)記，另外在一個固定的位置保存指向第一個節(jié)點的指針，有的時候也會同時儲存指向最后一個節(jié)點的指針。一般查找一個節(jié)點的時候需要從第一個節(jié)點開始每次訪問下一個節(jié)點，一直訪問到需要的位置。 雙向鏈表每個節(jié)點有兩個連接：一個指向前一個節(jié)點，（當(dāng)此“連接”為第一個“連接”時，指向空值或者空列表）；而另一個指向下一個節(jié)點，（當(dāng)此“連接”為最后一個“連接”時，指向空值或者空列表）雙向鏈表可以從任何一個節(jié)點訪問前一個節(jié)點，當(dāng)然也可以訪問后一個節(jié)點，以至整個鏈表。一般是在需要大批量的另外儲存數(shù)據(jù)在鏈表中的位置的時候用。 循環(huán)鏈表在一個循環(huán)鏈表中, 首節(jié)點和末節(jié)點被連接在一起。這種方式在單向和雙向鏈表中皆可實現(xiàn)。要轉(zhuǎn)換一個循環(huán)鏈表，你開始于任意一個節(jié)點然后沿著列表的任一方向直到返回開始的節(jié)點。指向整個列表的指針可以被稱作訪問指針。循環(huán)鏈表中第一個節(jié)點之前就是最后一個節(jié)點，反之亦然。3 鏈表常見用途 常用于組織刪除、檢索較少，而添加、遍歷較多的數(shù)據(jù)。4 鏈表和數(shù)組的區(qū)別 數(shù)組在內(nèi)存中是逐個存放的，也就是說倘若數(shù)組的第一個元素在地址A,則數(shù)組第二個元素就在地址A+1。而鏈表則不是，鏈表每個節(jié)點沒有相對固定的位置關(guān)系。某個節(jié)點在地址A其后的節(jié)點不一定是A+1,而在內(nèi)存的其他空閑區(qū)域，呈現(xiàn)一種隨機的狀態(tài)。 數(shù)組一旦顯式的被申明后，其大小就固定了，不能動態(tài)進行擴充。而鏈表則可以，可以動態(tài)生成節(jié)點并且添加到已有的鏈表中。 鏈表靈活，但是空間和時間額外耗費較大；數(shù)組大小固定，元素位置固定，但是操作不靈活，且容易浪費空間，但是時間耗費較小，尤其是元素變化不大的時候效率很高。雙向鏈表比單向的更靈活，但是空間耗費也更大。 從內(nèi)存存儲來看，(靜態(tài))數(shù)組從棧中分配空間, 對于程序員方便快速,但是自由度小；鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩。 附錄：（鏈表的部分常見操作）1 單向鏈表/*線性表的單鏈表存儲結(jié)構(gòu)*/typedef struct LNode{ ElemType data。 struct LNode *next。}LNode, *LinkList。 /*帶有頭結(jié)點的單鏈表的基本操作(12個)*/void InitList(LinkList *L){ /* 操作結(jié)果：構(gòu)造一個空的線性表L */ *L=(LinkList)malloc(sizeof(struct LNode))。 /* 產(chǎn)生
電大資料相關(guān)推薦
鄂ICP備17016276號-1