數(shù)據(jù)結(jié)構(gòu)中鏈表及常見操作-全文預(yù)覽
【正文】 ist L) /* 不改變L */{ /* 初始條件：L已存在。 free(p)。 if(*L) (*L)next=(*L)prior=*L。}2 雙向鏈表/* 線性表的雙向鏈表存儲結(jié)構(gòu) */typedef struct DuLNode{ ElemType data。操作結(jié)果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)vi() */ LinkList p=Lnext。 free(q)。 } if(!pnext||ji1) /* 刪除位置不合理 */ return ERROR。 while(pnextamp。 pnext=s。 } if(!p||ji1) /* i小于1或者大于表長 */ return ERROR。 while(pamp。 } p=pnext。} Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e){ /* 初始條件：線性表L已存在 */ /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼， */ /* 返回OK。 /* q為p的后繼 */ if(qdata==cur_e) { *pre_e=pdata。 p=pnext。 */ /* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */ int i=0。 } if(!p||ji) /* 第i個元素不存在 */ return ERROR。 /* p指向第一個結(jié)點 */ while(pamp。 } return i。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù) */ int i=0。 } Lnext=NULL。 p=Lnext。 free(*L)。 (*L)next=NULL。 struct LNode *next。 鏈表靈活，但是空間和時間額外耗費(fèi)較大；數(shù)組大小固定，元素位置固定，但是操作不靈活，且容易浪費(fèi)空間，但是時間耗費(fèi)較小，尤其是元素變化不大的時候效率很高。而鏈表則不是，鏈表每個節(jié)點沒有相對固定的位置關(guān)系。指向整個列表的指針可以被稱作訪問指針。一般是在需要大批量的另外儲存數(shù)據(jù)在鏈表中的位置的時候用。單向鏈表只可向一個方向遍歷。2 結(jié)構(gòu) 單向鏈表鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序，數(shù)據(jù)的訪問往往要在不同的排列順序中轉(zhuǎn)換。使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機(jī)內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。由于不必須按順序存儲，鏈表在插入的時候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)。鏈表通常由一連串節(jié)點組成，每個節(jié)點包含任意的實例數(shù)據(jù)（data fields）和一或兩個用來指向明上一個或下一個節(jié)點的位置的鏈接（links）。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。第一個部分保存或者顯示關(guān)于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址。 雙向鏈表每個節(jié)點有兩個連接：一個指向前一個節(jié)點，（當(dāng)此“連接”為第一個“連接”時，指向空值或者空列表）；而另一個指向下一個節(jié)點，（當(dāng)此“連接”為最后一個“連接”時，指向空值或者空列表）雙向鏈表可以從任何一個節(jié)點訪問前一個節(jié)點，當(dāng)然也可以訪問后一個節(jié)點，以至整個鏈表。要轉(zhuǎn)換一個循環(huán)鏈表，你開始于任意一個節(jié)點然后沿著列表的任一方向直到返回開始的節(jié)點。4 鏈表和數(shù)組的區(qū)別 數(shù)組在內(nèi)存中是逐個存放的，也就是說倘若數(shù)組的第一個元素在地址A,則數(shù)組第二個元素就在地址A+1。而鏈表則可以，可以動態(tài)生成節(jié)點并且添加到已有的鏈表中。 附錄：（鏈表的部分常見操作）1 單向鏈表/*線性表的單鏈表存儲結(jié)構(gòu)*/
電大資料相關(guān)推薦
鄂ICP備17016276號-1