C語言-鏈表課件

科學和諧創(chuàng)新自主C語言鏈表單鏈表單鏈表單鏈表的定義單鏈表的基本操作遍歷（遞歸和非遞歸遍歷）插入（插入4種情況，重點）建立刪除將一個鏈表排序將兩個有序鏈表合并將一個鏈表逆置約瑟夫問題1、單鏈表的定義最簡單的是單鏈表，單鏈表中每個節(jié)點由兩個字段組成：數(shù)據(jù)字段和指針字段，數(shù)據(jù)字段表示元素的本身信息，指針字段指明下個元素的位置。單鏈表用來表示線性結構。例如線性表（a1,a2,…,an)可以表示為：C語言定義鏈表的結構如下typedefstructNode{intdata;structNode*next;}NODE;

a1heada2/\an……帶有頭節(jié)點的單鏈表一般各種資料表示鏈表有兩種，一種是帶頭節(jié)點的，一種是使用頭指針的（不帶頭節(jié)點的）。帶頭節(jié)點的就是有一個專門的頭節(jié)點h，它的后繼指向鏈表的第一個元素。使用頭指針的沒有專門的頭節(jié)點，只有一個指針h指向鏈表的第一個元素單鏈表的遍歷2、鏈表的遍歷（顯示鏈表）設head為鏈表的頭指針，首先從head所指的節(jié)點開始打印，沿著鏈的方向向右遍歷，直到到最后一個節(jié)點，下面是一個打印鏈表的遞歸函數(shù)。voidlprint(NODE*head){if(head!=NULL){printf(“%d\t”,head->data);lprint(head->next);}許多問題中，有時候為了操作方便，需要在第一個節(jié)點之前增加一個特殊的節(jié)點，稱為頭節(jié)點，它的data字段不含信息或根據(jù)問題的需要存放特殊信息。2、鏈表的遍歷（顯示鏈表）一個非遞歸算法以下函數(shù)disp()用于顯示頭節(jié)點為*h的鏈表的所有節(jié)點數(shù)據(jù)域。voiddisp(structNode*h){structNode*p=h;printf("輸出鏈表:");if(p==NULL)printf("空表\n");else{while(p->next!=NULL){printf("%4d",p->data);p=p->next;}printf("%4d\n",p->data);}}單鏈表的插入3、鏈表的插入(頭指針的情況下）對于插入有以下幾種情況在一個空鏈表上插入一個元素。

（即要插入位置前方和后方均無元素）從鏈表表頭處插入一個元素

（即要插入的位置前方無元素，后方有元素）從鏈表結尾處處插入一個元素

（即要插入的位置后方五元素，前方有元素）從鏈表的中間插入

（即要插入的位置前方和后方均有元素）其中第三種情況可以按照第四種情況處理，但有一定特殊性所以將其分開注意：產生新的節(jié)點必須用malloc或者calloc開辟空間在空鏈表上插入一個元素實現(xiàn)的語句：p->next=NULL;h=p;在鏈表的表頭插入一個元素完成插入后表頭指針要指向新的表頭節(jié)點實現(xiàn)的語句：p->next=h;h=p;在鏈表結尾出插入一個元素不涉及頭節(jié)點的變動首先要用一個循環(huán)語句找到qq=h;while(q->next!=NULL)q=q->next;然后執(zhí)行插入語句：q->next=p;p->next=NULL;在鏈表中間插入一個元素這種情況不涉及頭節(jié)點的變動假如被插入位置的后方特征是數(shù)據(jù)項為x則可以執(zhí)行循環(huán)語句q=h;while(q->next->data!=x){q=q-next;}確保找到被插入地方的前方節(jié)點q,然后執(zhí)行插入語句：p->next=q->next;q->next=p;注意語句順序3、鏈表的插入(有單獨頭節(jié)點的情況下）由于增加了表頭節(jié)點，不用象沒有頭節(jié)點的情況時，區(qū)分是否插入點在表頭，所以對于插入只有兩種情況從鏈表結尾處處插入一個元素

（即要插入的位置后方五元素，前方有元素）從鏈表的中間插入

（即要插入的位置前方和后方均有元素）其中第一種情況可以按照第二種情況處理，但有一定特殊性（語句的順序可以換）所以將其分開在鏈表結尾出插入一個元素首先要用一個循環(huán)語句找到qq=h;while(q->next!=NULL)q=q->next;然后執(zhí)行插入語句：p->next=NULL;q->next=p;在鏈表中間插入一個元素假如被插入位置的后方特征是數(shù)據(jù)項為x則可以執(zhí)行循環(huán)語句q=h;while(q->next->data!=x){q=q-next;}確保找到被插入地方的前方節(jié)點q,然后執(zhí)行插入語句：p->next=q->next;q->next=p;注意語句順序4、鏈表的建立鏈表的建立就是鏈表從無到有的過程建立一個頭節(jié)點，并指向NULL，就建立了一個空的鏈表建立有n個元素的鏈表有三個階段建立頭節(jié)點并指向NULL（建立了一個空的鏈表）插入第一個元素（插入的第一種情況）在表頭或者表尾連續(xù)插入其他n-1個元素（反復執(zhí)行插入的第二，第三種情況）建立帶有單獨頭節(jié)點的鏈表，先建立頭節(jié)點structNode*create(){structNode*head,*p,*q;intn;head=(structNode*)malloc(sizeof(structNode));head->next=NULL;//第一階段，建立一個頭節(jié)點，并指向NULLp=head;while(1){printf("請輸入一個正整數(shù),0代表結束:");scanf("%d",&n);if(n<=0)break;else{q=(structNode*)malloc(sizeof(structNode));q->data=n;//產生要插入的節(jié)點

p->next=q;//執(zhí)行插入的過程，第一次插入的時候p=head所以就是head->next=q;q->next=NULL;p=q;}}returnhead;}單鏈表的刪除鏈表的刪除對于只有頭指針的鏈表分為兩種情況刪除的是第一個節(jié)點，即緊跟頭節(jié)點的節(jié)點刪除的不是第一個節(jié)點對于有頭節(jié)點的鏈表的刪除就比較簡單，有兩種情況，兩種情況可以合并為一種注意俠義的刪除僅僅指脫離鏈表前驅后繼的關系，并不是真正刪除那個節(jié)點。如果被脫離的那個節(jié)點確實沒有用處了，應該用free收回內存。鏈表的刪除（只有有單獨頭指針）

刪除的是第一個節(jié)點，即頭節(jié)點指向的元素時首先要用一個指針記錄刪除前的頭節(jié)點p=h;然后執(zhí)行修改頭指針的語句：h=h->next;如果刪除的節(jié)點沒有用處的話應該釋放空間free(p);鏈表的刪除（只有有單獨頭指針）

刪除的是中間節(jié)點時首先要找到p以及p的前驅q然后執(zhí)行刪除語句：q->next=p-next;當p為第一個元素時候，p的前驅是h即q=h;注意上面一步僅僅是將p指向的那個節(jié)點脫離鏈表，并沒有將那個節(jié)點刪除如果這時候p指向的那個節(jié)點已經沒有用處了，應該回收那個節(jié)點占用的內存free(p);鏈表的刪除（有單獨頭節(jié)點）首先要找到p以及p的前驅q然后執(zhí)行刪除語句：q->next=p-next;當p為第一個元素時候，p的前驅是h即q=h;注意上面一步僅僅是將p指向的那個節(jié)點脫離鏈表，并沒有將那個節(jié)點刪除如果這時候p指向的那個節(jié)點已經沒有用處了，應該回收那個節(jié)點占用的內存free(p);整個過程和只有頭指針的第二種情況完全一樣單鏈表的排序鏈表的排序（按照升序排列）不同于數(shù)組，鏈表的排序不用改變每個節(jié)點里面的值，只需要改變節(jié)點和節(jié)點之間的連接關系。思路1,類似選擇排序，每次找出最小的，脫離原鏈表，插入在新鏈表的末尾先把最小的元素的那個節(jié)點找出來，刪除在原鏈表的位置，自己作為新的鏈表的頭節(jié)點把最小的元素的那個節(jié)點找出來，刪除在原鏈表的位置，插入在新鏈表頭節(jié)點的后面。然后在原鏈表中依次找到最小的那個節(jié)點，在原鏈表中刪除，插入在新的鏈表中，插入的位置在新鏈表上次插入的那個節(jié)點之后。思路2，類似冒泡排序如果相鄰元素無序，則交換，注意現(xiàn)在鏈表中交換是要改變節(jié)點的連接關系，而不是改變節(jié)點。相鄰元素交換應該為先執(zhí)行刪除操作，再執(zhí)行插入操作排序步驟的圖示（有頭節(jié)點的情況）排序步驟的圖示（有頭節(jié)點的情況）voidsort(structNode**h){structNode*p,*h1,*q,*pmin,*pminpre,*newp;h1=(structNode*)malloc(sizeof(structNode));//新的頭節(jié)點

newp=h1;while((*h)->next!=NULL){//當老鏈表沒有元素節(jié)點的時候才完畢

pmin=(*h)->next;pminpre=*h;q=pmin;p=pminpre;while(q->next!=NULL){//當老鏈表遍歷一趟完畢，找到這一趟的最小值

q=q->next;p=p->next;if(q->data<pmin->data){ pmin=q;pminpre=p;}}pminpre->next=pmin->next;//原鏈表中刪除節(jié)點pminnewp->next=pmin;//新鏈表的末尾增加節(jié)點pminnewp=pmin;newp->next=NULL;}*h=h1;//老的頭節(jié)點賦值為新的頭節(jié)點，想一想為什么形參要定義為Node**h而不Node*h}鏈表的排序上述是對有頭節(jié)點的鏈表排序對于僅有頭指針的鏈表（無頭節(jié)點的鏈表）排序要稍微復雜一些，這是由于僅有頭指針鏈表刪除一個節(jié)點的時候，要區(qū)分是不是第一個節(jié)點，是第一個節(jié)點的話要修改頭指針。單鏈表的逆置將一個鏈表逆置思路：將原鏈表元素按照順序取出來（刪除和原鏈表脫離的關系，但并不刪除節(jié)點），然后插入在新鏈表的第一個元素的位置上。

對于僅有頭指針和有頭節(jié)點兩種情況程序會有些差別：1、有頭節(jié)點的時候，每次在頭節(jié)點后執(zhí)行插入操作即可。2、僅有頭指針的時候，每次在頭指針前面插入元素，然后更新頭指針。將一個鏈表逆置圖示（有頭節(jié)點的情況）將一個鏈表逆置代碼（有頭節(jié)點的情況）reverse(structNode**head){structNode*p,*newhead,*p1;p=(*head)->next;newhead=head;newhead->next=NULL;while(p!=NULL){p1=p;//p1為每次取出的節(jié)點

p=p->next;//讀取下一個節(jié)點

p1->next=newhead->next;//插入在新鏈表的表頭的前面

newhead->next=p1;}*head=newhead;//將新的表頭賦值給形參的表頭}將一個鏈表逆置過程的圖示（只有頭指針情況）將一個鏈表逆置(僅有頭指針的情況)思路：將原鏈表第一個元素取出來（刪除和原鏈表脫離的關系，但并不刪除節(jié)點），然后作為新鏈表的表頭節(jié)點，用一個新的頭指針指向它。然后按照順序將原鏈表的每個節(jié)點取出，插入在新鏈表頭節(jié)點的前面，同時更新新鏈表的頭節(jié)點指針指向的位置（即執(zhí)行在鏈表的表頭插入一個元素）reverse(structNode**head){structNode*p,*newhead,*p1;

p=*head;newhead=NULL;

while(p!=NULL){

p1=p;

//p1為每次取出的節(jié)點

p=p->next;//讀取下一個節(jié)點

p1->next=newhead;//插入在新鏈表的表頭的前面

newhead=p1;

//更新新鏈表的表頭位置

}

*head=newhead;

//將新的表頭賦值給形參的表頭}兩個有序單鏈表的合并將兩個有序鏈表合并思路：建立一個新個頭節(jié)點，分別在兩個鏈表遍歷，每次比較應該插入哪個節(jié)點，然后加入到新鏈表的末尾。將兩個有序鏈表合并圖示將兩個有序鏈表合并圖示將兩個有序鏈表合并圖示將兩個有序鏈表合并圖示代碼//將兩個有序鏈表合并structNode*unite(structNode*h1,structNode*h2){structNode*p1,*p2,*p3,*h3,*add;h3=(structNode*)malloc(sizeof(structNode));p3=h3;h3->next=NULL;