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

《線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)它是一種簡(jiǎn)單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。暴露的問(wèn)題l在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；l對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用；l線性表的容量難以擴(kuò)充。1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元（可以連續(xù)，也可以不連續(xù)）存儲(chǔ)線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一

2、個(gè)表示它的直接后繼元素存儲(chǔ)位置的信息。假設(shè)有一個(gè)線性表（a,b,c,d），可用下圖2所示的形式存儲(chǔ)：2線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖3術(shù)語(yǔ)表示每個(gè)數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點(diǎn)；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）；表示直接后繼元素存儲(chǔ)地址的部分被稱為指針或指針域（next）。單鏈表簡(jiǎn)化為下圖描述形式headd^^cba單鏈表結(jié)構(gòu)示意圖4其中，head是頭指針，它指向單鏈表中的第一個(gè)結(jié)點(diǎn)，這是單鏈表操作的入口點(diǎn)。由于最后一個(gè)結(jié)點(diǎn)沒有直接后繼結(jié)點(diǎn)，所以，它的指針域放入一個(gè)特殊的值NULL。NULL值在圖示中常用（^）符號(hào)表示。帶頭結(jié)點(diǎn)的單鏈表為了簡(jiǎn)化對(duì)鏈表的操作，

3、人們經(jīng)常在鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱為頭結(jié)點(diǎn)。這樣可以免去對(duì)鏈表第一個(gè)結(jié)點(diǎn)的特殊處理。（頭結(jié)點(diǎn)中數(shù)據(jù)域根據(jù)需要存放一些便于操作的信息，如元素個(gè)數(shù)等；或不存放任何信息。其引入使得所有鏈表（即使是空表）的值都不為NULL。）如下圖所示：headd^cba帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)示意圖5鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)（1）線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致；（2）在對(duì)線性表操作時(shí)，只能通過(guò)頭指針進(jìn)入鏈表，并通過(guò)每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會(huì)造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，具有這種特點(diǎn)的存取方式被稱為順序存取方式。6在C語(yǔ)言中，實(shí)現(xiàn)

4、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義typedefstrcutLNode{//結(jié)點(diǎn)類型ElemTypedata;structLNode*next;}LNode;typedefstruct{//鏈表類型LNode*head;}LinkList;72.3.2典型操作的算法實(shí)現(xiàn)1.初始化鏈表L：創(chuàng)建帶頭結(jié)點(diǎn)的空鏈表。intInitList(LinkList*L){L->head=(*LNode)malloc(sizeof(LNode));//為頭結(jié)點(diǎn)分配存儲(chǔ)單元if(L->head){L->head->next=NULL;returnOK;}elsereturnERROR;}82.銷毀鏈表L

5、：刪除鏈表中包括頭結(jié)點(diǎn)在內(nèi)所有結(jié)點(diǎn)。voidDestoryList(LinkList*L){LNode*p;while(L->head){//依次刪除鏈表中的所有結(jié)點(diǎn)p=L->head;L->head=L->head->next;free(p);}}//從頭結(jié)點(diǎn)開始刪，直到刪完為止。93.清空鏈表L：刪除鏈表中除頭結(jié)點(diǎn)外的所有結(jié)點(diǎn)。voidClearList(LinkList*L){LNode*p;while(L->head->next){p=L->head->next;//p指向鏈表中頭結(jié)點(diǎn)后面的第一個(gè)結(jié)點(diǎn)L->head->next=p->next;//刪除p結(jié)點(diǎn)free(p)

6、;//釋放p結(jié)點(diǎn)占據(jù)的存儲(chǔ)空間}}//從頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)開始刪，直到刪完為止。104.求鏈表L的長(zhǎng)度intListLength(LinkListL){LNode*p;intlen;for(p=L.head,len=0;p->next==NULL;p=p->next,len++);return(len);循環(huán)條件表達(dá)式重復(fù)執(zhí)行的語(yǔ)句}115.判斷鏈表L是否為空。intListEmpty(LinkListL){if(L.head->next==NULL)returnTRUE;elsereturnFALSE;}126.通過(guò)e返回鏈表L中第i個(gè)數(shù)據(jù)元素的內(nèi)容voidGetElem(L

7、inkListL,inti,EntryType*e){LNode*p;intj;//j為計(jì)數(shù)器，記載所經(jīng)過(guò)的結(jié)點(diǎn)數(shù)目if(i<1

8、

9、i>ListLength(L))exitERROR;//檢測(cè)i值的合理性for(p=L.head,j=0;j!=i;p=p->next,j++);//找到第i個(gè)結(jié)點(diǎn)*e=p->data;//將第i個(gè)結(jié)點(diǎn)的內(nèi)容賦給e指針?biāo)赶虻拇鎯?chǔ)單元中}137.在鏈表L中檢索值為e的數(shù)據(jù)元素LNode*LocateELem(LinkListL,EntryTypee)