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

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

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

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

4、/鏈表結(jié)點的輸出Node*Gethead()return head ； 2. 鏈表結(jié)點的訪問由于鏈表中的各個結(jié)點是由指針鏈接在一起的，其存儲單元文筆是連續(xù)的， 因此，對其中任意結(jié)點的地址無法向數(shù)組一樣，用一個簡單的公式計算出來， 進行隨機訪問。只能從鏈表的頭指針(即head)開始，用一個指針p先指向第一 個結(jié)點，然后根據(jù)結(jié)點p找到下一個結(jié)點。以此類推，直至找到所要訪問的結(jié) 點或到最后一個結(jié)點(指針為空)為止。下面我們給出上述鏈表的輸出函數(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é)點的插入如果要在鏈表中的結(jié)點a之前插入結(jié)點b,則需要考慮下面幾點情況。插入前鏈表是一個空表，這時插入新結(jié)點b后。若a是鏈表的第一個結(jié)點，則插入后，結(jié)點b為第一個結(jié)點。若鏈表中存在a,且不是第一個結(jié)點，則首先要找出a的上一個結(jié)點a_k,然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。如鏈表中不存在a，則插在最后。先找到鏈表的最后一個結(jié)點a_n，然后使a_n的指針域指向結(jié)點b,而b指針的指針為空。以下是鏈表類的結(jié)點插入函數(shù)，顯然其也具有建立鏈表的功能void list : insert

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

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