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é)束。可以看出鏈表結(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é)構(gòu)。struct Nodeint Data;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ù)。class listNode*head;public:list()head=NULL;void insertlist(int aDate,int bDate);/鏈表結(jié)點(diǎn)的插入void Deletelist

3、(int aDate);/鏈表結(jié)點(diǎn)的刪除void Outputlist();/鏈表結(jié)點(diǎn)的輸出Node*Gethead()return head;2 鏈表結(jié)點(diǎn)的訪問由于鏈表中的各個(gè)結(jié)點(diǎn)是由指針鏈接在一起的，其存儲(chǔ)單元文筆是連續(xù)的，因此，對(duì)其中任意結(jié)點(diǎn)的地址無法向數(shù)組一樣，用一個(gè)簡單的公式計(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(c

4、urrent!=NULL)cout<<current->Data<<" "current=current->next;cout<<endl;3 鏈表結(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)

5、a_n，然后使a_n的指針域指向結(jié)點(diǎn)b，而b指針的指針為空。以下是鏈表類的結(jié)點(diǎn)插入函數(shù)，顯然其也具有建立鏈表的功能。void list:insertlist(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)     

6、  s->Data=bDate; /設(shè)b為此結(jié)點(diǎn)        p=head;      if(head=NULL) /若是空表，使b作為第一個(gè)結(jié)點(diǎn)                    head=s;      

7、      s->next=NULL;                 else            if(p->Data=aDate) /若a是第一個(gè)結(jié)點(diǎn)         &

8、#160;                       s->next=p;                  head=s;       &#

9、160;                    else                              &#

10、160; while(p->Data!=aDate&&p->next!=NULL)/查找結(jié)點(diǎn)a                                        

11、0;       q=p;                             p=p->next;            

12、60;                           if(p->Data=aDate) /若有結(jié)點(diǎn)a                    

13、60;                         q->next=s;                       &

14、#160;   s->next=p;                                            else /若沒有結(jié)點(diǎn)a；&#

15、160;                                            p->next=s;     

16、;                      s->next=NULL;                           

17、;       4 鏈表結(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的下一個(gè)結(jié)點(diǎn)a_k+1。（3） 空表或要?jiǎng)h除的結(jié)點(diǎn)a不存在，則不做任何改變。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=h

18、ead;if(p=NULL) /若是空表return;if(p->Data=aDate) /若a是第一個(gè)結(jié)點(diǎn)head=p->next;delete p;elsewhile(p->Data!=aDate&&p->next!=NULL) /a既不是頭結(jié)點(diǎn)也不是終結(jié)點(diǎn)，則查找結(jié)點(diǎn)aq=p;p=p->next;if(p->Data=aDate) /若有結(jié)點(diǎn)aq->next=p->next;delete p;例題；利用以上三個(gè)鏈表操作成員函數(shù)insertlist,deletelist.outputlist,可形成以下的簡單鏈表操作#incl

19、ude"iostream.h"struct Nodeint Data;Node*next;class listNode*head;public:list()head=NULL;void insertlist(int aData,int bData);void deletelist(int aData);void outputlist();Node*gethead()return head;void list:insertlist(int aData,int bData) /設(shè)aData是結(jié)點(diǎn)a中的數(shù)據(jù)，bData是結(jié)點(diǎn)b中的數(shù)據(jù)Node*p,*q,*s; /p指向結(jié)點(diǎn)a，q

20、指向結(jié)點(diǎn)a_k，s指向結(jié)點(diǎn)bs=(Node*)new(Node); /動(dòng)態(tài)分配一個(gè)新結(jié)點(diǎn)s->Data=bData; /設(shè)b為此結(jié)點(diǎn)p=head;if(head=NULL) /若是空表，使b作為第一個(gè)結(jié)點(diǎn)head=s;s->next=NULL;elseif(p->Data=aData) /若a是第一個(gè)結(jié)點(diǎn)s->next=p;head=s;elsewhile(p->Data!=aData && p->next!=NULL)/查找結(jié)點(diǎn)aq=p;p=p->next;if(p->Data=aData) /若有結(jié)點(diǎn)aq->next=s

21、;s->next=p;else /若沒有結(jié)點(diǎn)a；p->next=s;s->next=NULL;void list:deletelist(int aData) /設(shè)aData是要?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=aData) /若a是第一個(gè)結(jié)點(diǎn)head=p->next;delete p;elsewhile(p->Data!=aData&&p->next!=NULL) /查找結(jié)點(diǎn)aq=p;p=p->

22、;next;if(p->Data=aData) /若有結(jié)點(diǎn)aq->next=p->next;delete p;void list:outputlist()Node*current=head;while(current!=NULL)cout<<current->Data<<" "current=current->next;cout<<endl;void main()list A,B;int Data10=25,41,16,98,5,67,9,55,1,121;A.insertlist(0,Data0); /建立

23、鏈表A首結(jié)點(diǎn)for(int i=1;i<10;i+)A.insertlist(0,Datai); /順序向后插入cout<<"n鏈表A:"A.outputlist();A.deletelist(Data7);cout<<"刪除元素Data7后"A.outputlist();B.insertlist(0,Data0); /建立鏈表B首結(jié)點(diǎn)for(i=0;i<10;i+)B.insertlist(B.gethead()->Data,Datai); /在首結(jié)點(diǎn)處順序向后插入cout<<"n鏈表B:

24、"B.outputlist();B.deletelist(67);cout<<"刪除元素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 <iostream>#include <iomanip>using namespace st

25、d;int main()const int n=11;int i,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+)cout<<setw(5)<<aij<<" "cout<<endl;cout<<endl;return 0;#include <iostream,h> #include <st

26、ring.h>struct Node    int num ;    Node *next ;Node* Create() /鏈表創(chuàng)建    int n=0;    Node *p1,*p2,*head;    p1=p2=new Node;    cin>>p1->num;    head=NULL;    while (p1-&g

27、t;num!=0)            if (n=1)                    head=p1;                else  &

28、#160;      p2->next=p1;        p2=p1;        p1=new Node;        cin>>p1->num;        n+;      

29、60; p2->next=NULL;    return head;int ListLength(Node L) /鏈表的計(jì)數(shù) Node p=L; int count=0; while(p->next) count+; p=p->next; return count;int Search(Node &L , int value) /鏈表的查找Node p=L; int index=0; while(p) if(p->num= value)return index; p=p->next; index+; return 0;voi

30、d Print(Node *head) /輸出鏈表    Node* p=head;    while (p)            cout<<p->num<<" "        p=p->next;        cout<<endl;

31、void Destruct(Node *head) /清空鏈表    Node *current = head, *temp = NULL; while (current)            temp = current;        current = current ->next;        delete t

32、emp;    Node *ReverseList(Node *head) /鏈表逆序（循環(huán)方法） Node *p,*q,*r; p=head; /一開始p指向第一個(gè)節(jié)點(diǎn) q=p->next; /q指向第二個(gè)節(jié)點(diǎn) while (q!=NULL) /如果沒到鏈尾 /以第一次循環(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 p=q; /之后p指向第二個(gè)節(jié)點(diǎn) q=r; /q指向第三個(gè)節(jié)點(diǎn) /即.p=>q=>r.變

33、為 .p<=q<=r. head->next=NULL; /最后原來的鏈頭變?yōu)殒溛玻阉赶騈ULL。 head=p; /原來的鏈尾變成鏈頭 return head; Node *ReverseList2(Node *head) /鏈表逆序（遞歸方法）     if (!head)            return NULL;        Node *temp = ReverseLis

34、t2 (head->next);    if (!temp)            return head;        head->next->next = head;    head->next = NULL;    return temp;遞歸時(shí),head可以分別用 head ，head1,head2 .headn-

35、1, headn來表示總共n+1個(gè)節(jié)點(diǎn)temp = ReverseList2( head->next ); 此句的遞歸一直將參數(shù)傳進(jìn)來的。Node* head 遞歸到 headn 然后判斷下列語句：else if( !headn->next ) return headn; 將返回值傳給temp,此時(shí)temp指向鏈尾 ,由于在此次返回,故此次沒有執(zhí)行最后的else的那部分的語句,返回上一級(jí)即是 headn-1 那一級(jí),繼續(xù)執(zhí)行下面的 headn-1->next->next = headn-1; headn-1->next = NULL; /此兩句將最后兩個(gè)逆序連接,

36、 return temp; /之后返回temp比上一層的temp即是執(zhí)行temp = ReverseList2( head->next )賦值,因?yàn)檫f歸的口都是在這里的,如果說好理解點(diǎn)也可以將temp來編號(hào)同理 在返回temp后,繼續(xù)執(zhí)行 headn-2->next->next = headn-2; headn-2->next = NULL; return temp; .一直到 head時(shí) 即是原鏈表的第一個(gè)節(jié)點(diǎn),在對(duì)其head->next = NULL后,此時(shí)以 temp 所指向的節(jié)點(diǎn)為鏈頭的逆序鏈表就形成了./已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)

37、把它們合并成一個(gè)鏈表依然有序。（循環(huán)方法）/(保留所有結(jié)點(diǎn)，即便大小相同）Node *Merge(Node *head1 , Node *head2)    if ( head1 = NULL)        return head2 ;    if ( head2 = NULL)        return head1 ;    if ( head1->num

38、 < =head2->num )            head = head1 ;        head1= head1->next;         else            head = head2 ; &#

39、160;      head2 = head2->next ;        Node *temp = head ;    while ( head1 != NULL && head2 != NULL)            if ( head1->num <= head2->num )  

40、0;                 temp->next = head1 ;         head1 = head1->next ;temp =temp->next;                else

41、                    temp->next = head2;          head2 = head2->next ;temp =temp->next;             &

42、#160;  if (head1 = NULL) temp->next = head2;    if (head2 = NULL) temp->next = head1;    return head;/已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。（遞歸方法）Node *MergeRecursive(Node *head1 , Node *head2)    if ( head1 = NULL )    &#

43、160;   return head2 ;    if ( head2 = NULL)        return head1 ;    Node *head = NULL ;    if ( head1->num < head2->num )            head = head1 ;

44、60;       head->next = MergeRecursive(head1->next,head2);        else            head = head2 ;        head->next = MergeRecursive(head1,head2->

45、;next);        return head ; 從遞歸函數(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í)才返回兩個(gè)鏈表的某一個(gè)頭節(jié)點(diǎn)，而此時(shí)head->next=head2，head=head1鏈表的最后一個(gè)節(jié)點(diǎn)，該語句就使得這樣一個(gè)指向關(guān)系確立起來。以上均通過理想的有序鏈表，即鏈表1的任何一個(gè)數(shù)據(jù)值都小于鏈表2來做分析，其他的情況討論方式類似

46、。Node* Delete(Node* head , int num) /刪除節(jié)點(diǎn)    if (head=NULL)            cout<<"List is Null"<<endl;        return head;        Node *p1,*p2; 

47、60;  p1=head;    while (p1->num!=num && p1->next)              p2=p1;        p1=p1->next;        if (p1->num=num)            if (p1=head)                    head=p1->