C++鏈表基本操作

1、C+鏈表基本操作我們知道，數(shù)組式計(jì)算機(jī)根據(jù)事先定義好的數(shù)組類型與長度自動(dòng)為其分配一連續(xù)的存儲(chǔ)單元，相同數(shù)組的位置和距離都是固定的鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲(chǔ)單元(可以是連續(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)镹ULL(空地址)，表示鏈表的結(jié)束?？梢钥磳珂湵斫Y(jié)構(gòu)必須利用指針才能實(shí)現(xiàn)，即一個(gè)結(jié)點(diǎn)中必須包含一個(gè)指針變量，用來存放下一個(gè)結(jié)點(diǎn)的地址。實(shí)際上，鏈表中的每個(gè)結(jié)點(diǎn)可以用若干個(gè)數(shù)據(jù)和若干個(gè)

2、指針。結(jié)點(diǎn)中只有一個(gè)指針的鏈表稱為單鏈表，這是最簡(jiǎn)單的鏈表結(jié)構(gòu)。structNodeintData;Node*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ù)。classlistNode*head;public:list()head=NULL;voidinsertlist(intaDate,intbDate);/鏈表結(jié)點(diǎn)的插入voidDeletelist(int

3、aDate);/鏈表結(jié)點(diǎn)的刪除voidOutputlist();鏈表結(jié)點(diǎn)的輸出Node*Gethead()returnhead;2. 鏈表結(jié)點(diǎn)的訪問由于鏈表中的各個(gè)結(jié)點(diǎn)是由指針鏈接在一起的，其存儲(chǔ)單元文筆是連續(xù)的，因此，對(duì)其中任意結(jié)點(diǎn)的地址無法向數(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ù)；voidlist:outputlist()Node*current=head;while(current!=

4、NULL)cout<vcurrent->Datavv""current=current->next;coutvvendl;鏈表結(jié)點(diǎn)的插入如果要在鏈表中的結(jié)點(diǎn)a之前插入結(jié)點(diǎn)b，則需要考慮下面幾點(diǎn)情況。(1) 插入前鏈表是一個(gè)空表，這時(shí)插入新結(jié)點(diǎn)b后。(2) 若a是鏈表的第一個(gè)結(jié)點(diǎn)，則插入后，結(jié)點(diǎn)b為第一個(gè)結(jié)點(diǎn)。(3)若鏈表中存在a,且不是第一個(gè)結(jié)點(diǎn)，則首先要找岀a的上一個(gè)結(jié)點(diǎn)a_k，然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。(4)如鏈表中不存在a，則插在最后。先找到鏈表的最后一個(gè)結(jié)點(diǎn)a_n，然后使a_n的指針域指向結(jié)點(diǎn)b，而b指針的指針

5、為空。以下是鏈表類的結(jié)點(diǎn)插入函數(shù)，顯然其也具有建立鏈表的功能。voidlist:insertlist(intaDate,intbDate)/設(shè)aDate是結(jié)點(diǎn)a中的數(shù)據(jù)，bDate是結(jié)點(diǎn)b中的數(shù)據(jù)Node*p,*q,*s;/ps=(Node*)new(Node);/s->Data=bDate;/p=head;if(head=NULL)/指向結(jié)點(diǎn)a，q指向結(jié)點(diǎn)a_k，s指向結(jié)點(diǎn)b動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)設(shè)b為此結(jié)點(diǎn)若是空表，使b作為第一個(gè)結(jié)點(diǎn)head=s;s->next=NULL;若a是第一個(gè)結(jié)點(diǎn)elseif(p->Data=aDate)/s_>next=p;head=s;el

6、se查找結(jié)點(diǎn)awhile(p->Data!=aDate&&p->next!=NULL)/q=p;p=p->next;if(p->Data=aDate)/若有結(jié)點(diǎn)aq->next=s;s->next=p;else/若沒有結(jié)點(diǎn)a;p->next=s;s->next=NULL;鏈表結(jié)點(diǎn)的刪除如果要在鏈表中刪除結(jié)點(diǎn)a并釋放被刪除的結(jié)點(diǎn)所占的存儲(chǔ)空間，則需要考慮下列幾種情況。(1)若要?jiǎng)h除的結(jié)點(diǎn)a是第一個(gè)結(jié)點(diǎn)，則把head指向a的下一個(gè)結(jié)點(diǎn)。(2)若要?jiǎng)h除的結(jié)點(diǎn)a存在于鏈表中，但不是第一個(gè)結(jié)點(diǎn)，則應(yīng)使a得上一個(gè)結(jié)點(diǎn)a_k-1的指針域指向a的

7、下一個(gè)結(jié)點(diǎn)a_k+1。(3) 空表或要?jiǎng)h除的結(jié)點(diǎn)a不存在，則不做任何改變。voidlist:deletelist(intaDate)/設(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;deletep;elsewhile(p->Data!=aDate&&p->next!=NULL)/a既不是頭結(jié)點(diǎn)也不是終結(jié)點(diǎn)，則查找結(jié)點(diǎn)aq=p;p=p->next;if(p-&g

8、t;Data=aDate)/若有結(jié)點(diǎn)aq_>next=p_>next;deletep;例題；利用以上三個(gè)鏈表操作成員函數(shù)insertlist,deletelist.outputlist,可形成以下的簡(jiǎn)單鏈表操作#include"iostream.h"structNodeintData;Node*next;classlistNode*head;public:list()head=NULL;voidinsertlist(intaData,intbData);voiddeletelist(intaData);voidoutputlist();Node*gethead(

9、)returnhead;；設(shè)aData是結(jié)點(diǎn)a中的數(shù)據(jù)，bData是結(jié)點(diǎn)b中voidlist:insertlist(intaData,intbData)/的數(shù)據(jù)Node*p,*q,*s;/ps=(Node*)new(Node);/s->Data=bData;/p=head;if(head=NULL)/head=s;s->next=NULL;elseif(p->Data=aData)/指向結(jié)點(diǎn)a,q指向結(jié)點(diǎn)a_k,s指向結(jié)點(diǎn)b動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)設(shè)b為此結(jié)點(diǎn)若是空表，使b作為第一個(gè)結(jié)點(diǎn)若a是第一個(gè)結(jié)點(diǎn)s->next=p;head=s;else查找結(jié)點(diǎn)a查找結(jié)點(diǎn)awhile(

10、p->Data!=aData&&p->next!=NULL)q=p;p=p->next;if(p->Data=aData)/若有結(jié)點(diǎn)aq->next=s;s->next=p;else/若沒有結(jié)點(diǎn)a；p->next=s;s->next=NULL;設(shè)aData是要?jiǎng)h除的結(jié)點(diǎn)a中的數(shù)據(jù)成員設(shè)aData是要?jiǎng)h除的結(jié)點(diǎn)a中的數(shù)據(jù)成員voidlist:deletelist(intaData)/Node*p,*q;p用于指向結(jié)點(diǎn)a,q用于指向結(jié)a的前一個(gè)結(jié)點(diǎn)p=head;if(p=NULL)/若是空表return;if(p->Data=a

11、Data)/若a是第一個(gè)結(jié)點(diǎn)head=p->next;deletep;elsewhile(p->Data!=aData&&p->next!=NULL)/查找結(jié)點(diǎn)aq=p;p=p_>next;if(p->Data=aData)/若有結(jié)點(diǎn)aq->next=p->next;deletep;voidlist:outputlist()Node*current=head;while(current!=NULL)cout<vcurrent->Datavv""current=current->next;coutvv

12、endl;voidmain()listA,B;建立鏈表A首結(jié)點(diǎn)順序向后插入intData10=25,41,16,98,5,67,9,55,1,121;A.insertlist(0,Data0);/for(inti=1;iv10;i+)A.insertlist(0,Datai);/coutvv"n鏈表A:"A.outputlist();A.deletelist(Data7);coutvv"刪除元素Data7后A. outputlist();insertlist(O,DataO);/建立鏈表B首結(jié)點(diǎn)for(i=0;i<10;i+)B.insertlist(B.g

13、ethead()->Data,Datai);/在首結(jié)點(diǎn)處順序向后插入cout«"n鏈表B:"B.outputlist();B.deletelist(67);coutvv"刪除元素67后"B.outputlist();程序運(yùn)行結(jié)果為下面是楊輝三角的代碼：鏈表A；25，41，16，98，5，67，9，55，1，121刪除元素Data7后；25，41，16，98，5，67，9，1，121鏈表B；121，1，55，9，67，5，98，16，41，25，刪除元素67后；121，1，55，9，5，98，16，41，25#include<iost

14、ream>#include<iomanip>usingnamespacestd;intmain()constintn=11;inti,j,ann;for(i=1;i<n;i+)aii=1;ai1=1;for(i=3;i<n;i+)for(j=2;j<=i-1;j+)aij=ai-1j-1+ai-1j;for(i=1;i<n;i+)for(j=1;j<=i;j+)coutvvsetw(5)vvaijvv"coutvvendl;coutvvendl;return0;#include<iostream,h>#include<

15、string.h>structNodeintnum;Node*next;；Node*Create()/鏈表創(chuàng)建intn=0;Node*p1,*p2,*head;p1=p2=newNode;cin>>p1->num;head=NULL;while(p1->num!=0)if(n=1)head=p1;elsep2_>next=p1;p2=p1；p1=newNode;cin>>p1->num;n+;p2->next=NULL;returnhead;intListLength(NodeL)/鏈表的計(jì)數(shù)Nodep=L;intcount=0;wh

16、ile(p->next)count+;p=p->next;returncount;/鏈表的查找intSearch(Node&L,intvalue)Nodep=L;intindex=0;while(p)if(p->num=value)returnindex;p=p->next;index+;return0;voidPrint(Node*head)/輸出鏈表Node*p=head;while(p)coutvvp->num<<""p=p->next;coutvvendl;voidDestruct(Node*head)/清空鏈

17、表Node*current=head,*temp=NULL;while(current)temp=current;current=current->next;deletetemp;/鏈表逆序（循環(huán)方法）Node*ReverseList(Node*head)Node*p,*q,*r;p=head;q=p->next;while(q!=NULL)/一開始p指向第一個(gè)節(jié)點(diǎn)q指向第二個(gè)節(jié)點(diǎn)/如果沒到鏈尾/以第一次循環(huán)為例r=q_>next;/r暫時(shí)存儲(chǔ)第三個(gè)節(jié)點(diǎn)q_>next=p;/沒執(zhí)行此句前，q->next指向第三個(gè)節(jié)點(diǎn)/執(zhí)行之后，q->next指向第一個(gè)節(jié)點(diǎn)p

18、p=q;/之后p指向第二個(gè)節(jié)點(diǎn)q=r;/q指向第三個(gè)節(jié)點(diǎn)head->next=NULL;/即.p=>q=>r.變?yōu)閜v=qv=r./最后原來的鏈頭變?yōu)殒溛玻阉赶騈ULL。head=p;/原來的鏈尾變成鏈頭returnhead;/鏈表逆序(遞歸方法)Node*ReverseList2(Node*head)if(!head)returnNULL;Node*temp=ReverseList2(head->next);if(!temp)returnhead;head->next->next=head;head->next=NULL;returntemp;遞

19、歸時(shí),head可以分別用head遞歸時(shí),head可以分別用head,head1,head2headn-1,headn來表示總共n+1個(gè)節(jié)點(diǎn)temp=ReverseList2(head->next);temp=ReverseList2(head->next);此句的遞歸一直將參數(shù)傳進(jìn)來的。Node*head遞歸至Uheadn然后判斷下列語句:elseif(!headn->next)returnheadn;將返回值傳給temp,此時(shí)temp句，返回上一級(jí)即是headn-1指向鏈尾，由于在此次返回，故此次沒有執(zhí)行最后的else的那部分的語那一級(jí),繼續(xù)執(zhí)行下面的headn-1->

20、;next->next=headn-1;headn-1->next=NULL;/headn-1->next=NULL;/此兩句將最后兩個(gè)逆序連接returntemp;賦值,因?yàn)橘x值,因?yàn)?之后返回temp比上一層的temp即是執(zhí)行temp=ReverseList2(head->next)遞歸的口都是在這里的，如果說好理解點(diǎn)也可以將temp來編號(hào)同理在返回temp后,繼續(xù)執(zhí)行headn-2->next->next=headn-2;headn-2->next=NULL;returntemp;一直到head時(shí)即是原鏈表的第一個(gè)節(jié)點(diǎn)，在對(duì)其head->n

21、ext=NULL后,此時(shí)以temp所指向的節(jié)點(diǎn)為鏈頭的逆序鏈表就形成了./已知兩個(gè)鏈表headl和head2各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。(循環(huán)方法)(保留所有結(jié)點(diǎn)，即便大小相同)Node*Merge(Node*head1,Node*head2)if(head1=NULL)returnhead2;if(head2=NULL)returnhead1;if(head1->num<=head2->num)head=head1;head1=head1->next;elsehead=head2;head2=head2->next;Node*temp=head;w

22、hile(head1!=NULL&&head2!=NULL)if(head1->num<=head2->num)temp->next=head1;head1=head1->next;temp=temp->next;elsetemp->next=head2;head2=head2->next;temp=temp->next;if(head1=NULL)temp->next=head2;if(head2=NULL)temp->next=head1;returnhead;各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。hea

23、d1,Node*head2)各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。head1,Node*head2)(遞歸方法)/已知兩個(gè)鏈表headl和head2Node*MergeRecursive(Node*if(headl=NULL)returnhead2;if(head2=NULL)returnhead1;Node*head=NULL;if(head1->num<head2->num)head=head1;head->next=MergeRecursive(head1->next,head2);elsehead=head2;head->next=MergeRecursive(head1,head2->next);returnhead;從遞歸函數(shù)的定義不難看出，這個(gè)函數(shù)定義中遞歸調(diào)用時(shí)形參發(fā)生改變，即是當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，每一次遞歸都按照這個(gè)規(guī)律逐次遍歷兩個(gè)有序鏈表的每一個(gè)節(jié)點(diǎn)，判斷大小后使head指向數(shù)據(jù)域較小的節(jié)點(diǎn)，由堆?？臻g的思想可知遞歸到最后指向NULL時(shí)才