鏈表動(dòng)態(tài)內(nèi)存分配應(yīng)用舉例鏈表上

1、鏈表 動(dòng)態(tài)內(nèi)存分配應(yīng)用舉例 鏈表 上鏈表-動(dòng)態(tài)內(nèi)存分配應(yīng)用舉例（鏈表）（上）2011-03-24 20 : 22動(dòng)態(tài)內(nèi)存分配 應(yīng)用舉例（鏈表）我們知道，數(shù)組式計(jì)算機(jī)根據(jù)事先定義好的數(shù)組類型與長(zhǎng)度自動(dòng)為其分配 一連續(xù)的存儲(chǔ)單元，相同數(shù)組的位置和距離都是固定的，也就是說，任何一個(gè) 數(shù)組元素的地址都可一個(gè)簡(jiǎn)單的公式計(jì)算出來，因此這種結(jié)構(gòu)可以有效的對(duì)數(shù) 組元素進(jìn)行隨機(jī)訪問。但若對(duì)數(shù)組元素進(jìn)行插入和刪除操作，則會(huì)引起大量數(shù) 據(jù)的移動(dòng)，從而使簡(jiǎn)單的數(shù)據(jù)處理變得非常復(fù)雜，低效。為了能有效地解決這 些問題，一種稱為鏈表數(shù)據(jù)結(jié)構(gòu)得到了廣泛應(yīng)用。1. 鏈表概述：鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲(chǔ)單

2、 元（可以是連續(xù)的，也可以是不連續(xù)的）存放數(shù)據(jù)元素。鏈表中每一個(gè)元素成為結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成的， 每個(gè)結(jié)點(diǎn)中的指針域指向下一個(gè)結(jié)點(diǎn)。 Head是頭指針，表示鏈表的開始，用 來指向第一個(gè)結(jié)點(diǎn)，而最后一個(gè)指針的指針域?yàn)?NULL，表示鏈表的結(jié)束。可以看出鏈表結(jié)構(gòu)必須利用指針才能實(shí)現(xiàn)，即一個(gè)結(jié)點(diǎn)中必須包含一個(gè)指 針變量，用來存放下一個(gè)結(jié)點(diǎn)的地址。實(shí)際上，鏈表中的每個(gè)結(jié)點(diǎn)可以用若干個(gè)數(shù)據(jù)和若干個(gè)指針。結(jié)點(diǎn)中只有 一個(gè)指針的鏈表稱為單鏈表，這是最簡(jiǎn)單的鏈表結(jié)構(gòu)。再C+中實(shí)現(xiàn)一個(gè)單鏈表結(jié)構(gòu)比較簡(jiǎn)單。例如，可定義單鏈表結(jié)構(gòu)的最簡(jiǎn) 單形式如下struct Nodeint Data ；Nod

3、e*next ；這里用到了結(jié)構(gòu)體類型。其中，*next是指針域，用來指向該結(jié)點(diǎn)的下一 個(gè)結(jié)點(diǎn)；Data是一個(gè)整形變量，用來存放結(jié)點(diǎn)中的數(shù)據(jù)。當(dāng)然， Data可以是任 何數(shù)據(jù)類型，包括結(jié)構(gòu)體類型或類類型。在此基礎(chǔ)上，我們?cè)诙x一個(gè)鏈表類list ，其中包含鏈表結(jié)點(diǎn)的插入，刪 除，輸出等功能的成員函數(shù)。class listNode*head;public :list()head=NULL ； void insertlist(int aDate,int bDate)； / 鏈表結(jié)點(diǎn)的插入void Deletelist(int aDate)； / 鏈表結(jié)點(diǎn)的刪除void Outputlist() ；

4、/鏈表結(jié)點(diǎn)的輸出Node*Gethead()return head ； 2. 鏈表結(jié)點(diǎn)的訪問由于鏈表中的各個(gè)結(jié)點(diǎn)是由指針鏈接在一起的，其存儲(chǔ)單元文筆是連續(xù)的， 因此，對(duì)其中任意結(jié)點(diǎn)的地址無(wú)法向數(shù)組一樣，用一個(gè)簡(jiǎn)單的公式計(jì)算出來， 進(jìn)行隨機(jī)訪問。只能從鏈表的頭指針(即head)開始，用一個(gè)指針p先指向第一 個(gè)結(jié)點(diǎn)，然后根據(jù)結(jié)點(diǎn)p找到下一個(gè)結(jié)點(diǎn)。以此類推，直至找到所要訪問的結(jié) 點(diǎn)或到最后一個(gè)結(jié)點(diǎn)(指針為空)為止。下面我們給出上述鏈表的輸出函數(shù)；void list : outputlist()Node*current=head ；while(curre nt ! =NULL)cout curre n

5、t-Data ;curre nt=curre nt-n ext；cout endl ;3. 鏈表結(jié)點(diǎn)的插入如果要在鏈表中的結(jié)點(diǎn)a之前插入結(jié)點(diǎn)b,則需要考慮下面幾點(diǎn)情況。插入前鏈表是一個(gè)空表，這時(shí)插入新結(jié)點(diǎn)b后。若a是鏈表的第一個(gè)結(jié)點(diǎn)，則插入后，結(jié)點(diǎn)b為第一個(gè)結(jié)點(diǎn)。若鏈表中存在a,且不是第一個(gè)結(jié)點(diǎn)，則首先要找出a的上一個(gè)結(jié)點(diǎn)a_k,然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。如鏈表中不存在a，則插在最后。先找到鏈表的最后一個(gè)結(jié)點(diǎn)a_n，然后使a_n的指針域指向結(jié)點(diǎn)b,而b指針的指針為空。以下是鏈表類的結(jié)點(diǎn)插入函數(shù)，顯然其也具有建立鏈表的功能void list : insert

6、list(int aDate,int bDate)/設(shè) aDate 是結(jié)點(diǎn) a 中的數(shù)據(jù)，bDate是結(jié)點(diǎn)b中的數(shù)據(jù)Node*p,*q,*s ; /p指向結(jié)點(diǎn)a, q指向結(jié)點(diǎn)a_k, s指向結(jié)點(diǎn)b s=(Node*)new(Node) ; /動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)s-Data=bDate ; / 設(shè) b 為此結(jié)點(diǎn)p=head；if(head=NULL)若是空表，使b作為第一個(gè)結(jié)點(diǎn)head=s；s-next=NULL;else if(p-Data=aDate)/ 若 a 是第一個(gè)結(jié)點(diǎn)s-n ext=p ；head=s；elsewhile(p-Data ！ =aDate&p-next ！ =NULL)

7、/ 查找結(jié)點(diǎn) aq=p;p=p-next ;if(p-Data=aDate)/若有結(jié)點(diǎn) aq-next=s ;s-n ext=p ;else/若沒有結(jié)點(diǎn)a；p-next=s ;s-next=NULL;4. 鏈表結(jié)點(diǎn)的刪除如果要在鏈表中刪除結(jié)點(diǎn)a并釋放被刪除的結(jié)點(diǎn)所占的存儲(chǔ)空間，貝嚅要 考慮下列幾種情況。若要?jiǎng)h除的結(jié)點(diǎn)a是第一個(gè)結(jié)點(diǎn)，則把head指向a的下一個(gè)結(jié)點(diǎn)。若要?jiǎng)h除的結(jié)點(diǎn)a存在于鏈表中，但不是第一個(gè)結(jié)點(diǎn)，則應(yīng)使a得上一個(gè)結(jié)點(diǎn)a_k-1的指針域指向a的下一個(gè)結(jié)點(diǎn)a_k+1?？毡砘蛞?jiǎng)h除的結(jié)點(diǎn)a不存在，則不做任何改變。以下是鏈表類的結(jié)點(diǎn)刪除函數(shù)。void list : deletelist(int aDate)/設(shè) aDate 是要?jiǎng)h除的結(jié)點(diǎn) a 中的數(shù)據(jù)成員Node*p,*q ； /p用于指向結(jié)點(diǎn)a,q用于指向結(jié)a的前一個(gè)結(jié)點(diǎn)p=head；if(p=NULL) 若是空表return ；if(p-Data=aDate)/ 若 a 是第一個(gè)結(jié)點(diǎn)head=p-next ；d