C++鏈表基本操作

1、C+鏈表基本操作我們知道，數(shù)組式計算機根據(jù)事先定義好的數(shù)組類型與長度自動為其分配一連續(xù)的存儲單元，相同數(shù)組的位置和距離都是固定的鏈表是一種動態(tài)數(shù)據(jù)結構，他的特點是用一組任意的存儲單元（可以是連續(xù)的，也可以是不連續(xù)的）存放數(shù)據(jù)元素。鏈表中每一個元素成為“結點”，每一個結點都是由數(shù)據(jù)域和指針域組成的，每個結點中的指針域指向下一個結點。Head是“頭指針”，表示鏈表的開始，用來指向第一個結點，而最后一個指針的指針域為NULL(空地址)，表示鏈表的結束?？梢钥闯鲦湵斫Y構必須利用指針才能實現(xiàn)，即一個結點中必須包含一個指針變量，用來存放下一個結點的地址。實際上，鏈表中的每個結點可以用若干個數(shù)據(jù)和若干個指針

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

3、(int aDate);/鏈表結點的刪除void Outputlist();/鏈表結點的輸出Node*Gethead()return head;2 鏈表結點的訪問由于鏈表中的各個結點是由指針鏈接在一起的，其存儲單元文筆是連續(xù)的，因此，對其中任意結點的地址無法向數(shù)組一樣，用一個簡單的公式計算出來，進行隨機訪問。只能從鏈表的頭指針（即head）開始，用一個指針p先指向第一個結點，然后根據(jù)結點p找到下一個結點。以此類推，直至找到所要訪問的結點或到最后一個結點（指針為空）為止。下面我們給出上述鏈表的輸出函數(shù)；void list:outputlist()Node*current=head;while(c

4、urrent!=NULL)cout<<current->Data<<" "current=current->next;cout<<endl;3 鏈表結點的插入如果要在鏈表中的結點a之前插入結點b，則需要考慮下面幾點情況。（1） 插入前鏈表是一個空表，這時插入新結點b后。（2） 若a是鏈表的第一個結點，則插入后，結點b為第一個結點。（3）若鏈表中存在a,且不是第一個結點，則首先要找出a的上一個結點a_k，然后使a_k的指針域指向b，在令b的指針域指向a，即可完成插入。（4） 如鏈表中不存在a，則插在最后。先找到鏈表的最后一個結點

5、a_n，然后使a_n的指針域指向結點b，而b指針的指針為空。以下是鏈表類的結點插入函數(shù)，顯然其也具有建立鏈表的功能。void list:insertlist(int aDate,int bDate) /設aDate是結點a中的數(shù)據(jù)，bDate是結點b中的數(shù)據(jù)       Node*p,*q,*s; /p指向結點a，q指向結點a_k，s指向結點b       s=(Node*)new(Node); /動態(tài)分配一個新結點     

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

7、      s->next=NULL;                 else            if(p->Data=aDate) /若a是第一個結點         &

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

9、160;                    else                              &#

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

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

12、60;                           if(p->Data=aDate) /若有結點a                    

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

14、#160;   s->next=p;                                            else /若沒有結點a；&#

15、160;                                            p->next=s;     

16、;                      s->next=NULL;                           

17、;       4 鏈表結點的刪除如果要在鏈表中刪除結點a并釋放被刪除的結點所占的存儲空間，則需要考慮下列幾種情況。（1） 若要刪除的結點a是第一個結點，則把head指向a的下一個結點。（2）若要刪除的結點a存在于鏈表中，但不是第一個結點，則應使a得上一個結點a_k-1的指針域指向a的下一個結點a_k+1。（3） 空表或要刪除的結點a不存在，則不做任何改變。void list:deletelist(int aDate) /設aDate是要刪除的結點a中的數(shù)據(jù)成員Node*p,*q; /p用于指向結點a,q用于指向結a的前一個結點p=h

18、ead;if(p=NULL) /若是空表return;if(p->Data=aDate) /若a是第一個結點head=p->next;delete p;elsewhile(p->Data!=aDate&&p->next!=NULL) /a既不是頭結點也不是終結點，則查找結點aq=p;p=p->next;if(p->Data=aDate) /若有結點aq->next=p->next;delete p;例題；利用以上三個鏈表操作成員函數(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) /設aData是結點a中的數(shù)據(jù)，bData是結點b中的數(shù)據(jù)Node*p,*q,*s; /p指向結點a，q

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

21、;s->next=p;else /若沒有結點a；p->next=s;s->next=NULL;void list:deletelist(int aData) /設aData是要刪除的結點a中的數(shù)據(jù)成員Node*p,*q; /p用于指向結點a,q用于指向結a的前一個結點p=head;if(p=NULL) /若是空表return;if(p->Data=aData) /若a是第一個結點head=p->next;delete p;elsewhile(p->Data!=aData&&p->next!=NULL) /查找結點aq=p;p=p->

22、;next;if(p->Data=aData) /若有結點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首結點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首結點for(i=0;i<10;i+)B.insertlist(B.gethead()->Data,Datai); /在首結點處順序向后插入cout<<"n鏈表B:

24、"B.outputlist();B.deletelist(67);cout<<"刪除元素67后"B.outputlist();程序運行結果為鏈表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) /鏈表的計數(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指向第一個節(jié)點 q=p->next; /q指向第二個節(jié)點 while (q!=NULL) /如果沒到鏈尾 /以第一次循環(huán)為例 r=q->next; /r暫時存儲第三個節(jié)點 q->next=p; /沒執(zhí)行此句前，q->next指向第三個節(jié)點 /執(zhí)行之后，q->next指向第一個節(jié)點p p=q; /之后p指向第二個節(jié)點 q=r; /q指向第三個節(jié)點 /即.p=>q=>r.變

33、為 .p<=q<=r. head->next=NULL; /最后原來的鏈頭變?yōu)殒溛?，把它指向NULL。 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;遞歸時,head可以分別用 head ，head1,head2 .headn-

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

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

37、把它們合并成一個鏈表依然有序。（循環(huá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;/已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序。（遞歸方法）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ù)的定義不難看出，這個函數(shù)定義中遞歸調用時形參發(fā)生改變，即是當前節(jié)點的下一個節(jié)點，每一次遞歸都按照這個規(guī)律逐次遍歷兩個有序鏈表的每一個節(jié)點，判斷大小后使head指向數(shù)據(jù)域較小的節(jié)點，由堆?？臻g的思想可知遞歸到最后指向NULL時才返回兩個鏈表的某一個頭節(jié)點，而此時head->next=head2，head=head1鏈表的最后一個節(jié)點，該語句就使得這樣一個指向關系確立起來。以上均通過理想的有序鏈表，即鏈表1的任何一個數(shù)據(jù)值都小于鏈表2來做分析，其他的情況討論方式類似

46、。Node* Delete(Node* head , int num) /刪除節(jié)點    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->