C語(yǔ)言鏈表專題復(fù)習(xí)

本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！鏈表專題復(fù)習(xí)數(shù)組作為存放同類數(shù)據(jù)的集合，給我們?cè)诔绦蛟O(shè)計(jì)時(shí)帶來(lái)很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時(shí)要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來(lái)，在程序設(shè)計(jì)中針對(duì)不同問(wèn)題有時(shí)需要30個(gè)元素大小的數(shù)組，有時(shí)需要50個(gè)數(shù)組元素的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的最大需求來(lái)定義數(shù)組，常常會(huì)造成一定存儲(chǔ)空間的浪費(fèi)。我們希望構(gòu)造動(dòng)態(tài)的數(shù)組，隨時(shí)可以調(diào)整數(shù)組的大小，以滿足不同問(wèn)題的需要。鏈表就是我們需要的動(dòng)態(tài)數(shù)組。它是在程序的執(zhí)行過(guò)程中根據(jù)需要有數(shù)據(jù)存儲(chǔ)就向系統(tǒng)要求申請(qǐng)存儲(chǔ)空間，決不構(gòu)成對(duì)存儲(chǔ)區(qū)的浪費(fèi)。鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：?jiǎn)捂湵怼⒀h(huán)鏈表、雙向鏈表，下面只介紹單向鏈表。單鏈表圖7-3是單鏈表的結(jié)構(gòu)。單鏈表有一個(gè)頭節(jié)點(diǎn) head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問(wèn)需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無(wú)論在表中訪問(wèn)那一個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開(kāi)始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，寫作為NULL。圖7-3還給出這樣一層含義，鏈表中的各節(jié)點(diǎn)在內(nèi)存的存儲(chǔ)地址不是連續(xù)的，其各節(jié)點(diǎn)的地址是在需要時(shí)向系統(tǒng)申請(qǐng)分配的，系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址?？匆幌骆湵砉?jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義：structnode{intnum;structnode*p;};p是指向與節(jié)點(diǎn)類型完全相在鏈表節(jié)點(diǎn)的定義中，除一個(gè)整型的成員外，成員同的指針。在鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點(diǎn)就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未定義成功的數(shù)據(jù)類型。這是在C中唯一規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。單鏈表的創(chuàng)建過(guò)程有以下幾步：1)定義鏈表的數(shù)據(jù)結(jié)構(gòu)。2)創(chuàng)建一個(gè)空表。3)利用malloc()函數(shù)向系統(tǒng)申請(qǐng)分配一個(gè)節(jié)點(diǎn)。4)將新節(jié)點(diǎn)的指針成員賦值為空。若是空表，將新節(jié)點(diǎn)連接到表頭；若是非空表，將新節(jié)點(diǎn)接到表尾。5)判斷一下是否有后續(xù)節(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到 3)，否則結(jié)束。單鏈表的輸出過(guò)程有以下幾步1)找到表頭。本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！若是非空表，輸出節(jié)點(diǎn)的值成員，是空表則退出。3)跟蹤鏈表的增長(zhǎng)，即找到下一個(gè)節(jié)點(diǎn)的地址。轉(zhuǎn)到2)。下列是用尾插法創(chuàng)建鏈表新開(kāi)辟的節(jié)點(diǎn)總是插在表末[例7-5]創(chuàng)建一個(gè)存放正整數(shù)（輸入負(fù)數(shù)時(shí)做結(jié)束標(biāo)志）的單鏈表，并打印輸出。#include<stdlib.h>/包*含malloc()的頭文件*/#include<stdio.h>structnode/*鏈表節(jié)點(diǎn)的結(jié)構(gòu)*/{intnum;structnode*next; };main(){structnode*creat();/*函數(shù)聲明*/voidprint();structnode*head;/* 定義頭指針*/head=NULL;/*建一個(gè)空表*/head=creat(head);/*創(chuàng)建單鏈表*/print(head);/*打印單鏈表*/ }/******************************************/structnode*creat(structnode*head)函/數(shù)*返回的是與節(jié)點(diǎn)相同類型的指針*/{structnode*p1,*p2;p1=p2=(structnode*)malloc(sizeof(structnode)); 申請(qǐng)/*新節(jié)點(diǎn)*/scanf("%d",&p1->num);/* 輸入節(jié)點(diǎn)的值*/p1->next=NULL;/* 將新節(jié)點(diǎn)的指針置為空 */while(p1->num>0)/*輸入節(jié)點(diǎn)的數(shù)值大于 0*/{if(head==NULL)head=p1;/* 空表，接入表頭*/elsep2->next=p1;/*非空表，接到表尾*/p2=p1;p1=(structnode*)malloc(sizeof(structnode));申/請(qǐng)*下一個(gè)新節(jié)點(diǎn)*/scanf("%d",&p1->num);/*輸入節(jié)點(diǎn)的值*/}returnhead;/*返回鏈表的頭指針*/ }/*******************************************/voidprint(structnode*head) 輸/*出以head為頭的鏈表各節(jié)點(diǎn)的值 */{structnode*temp;temp=head;/*取得鏈表的頭指針*/while(temp!=NULL)/* 只要是非空表*/{printf("%6d",temp->num);/* 輸出鏈表節(jié)點(diǎn)的值*/本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！temp=temp->next;/*跟蹤鏈表增長(zhǎng)*/ } }在鏈表的創(chuàng)建過(guò)程中，鏈表的頭指針是非常重要的參數(shù)。因?yàn)閷?duì)鏈表的輸出和查找都要從鏈表的頭開(kāi)始，所以鏈表創(chuàng)建成功后，要返回一個(gè)鏈表頭節(jié)點(diǎn)的地址，即頭指針。下列是用頭插法創(chuàng)建鏈表新開(kāi)辟的結(jié)點(diǎn)總是作為表頭結(jié)點(diǎn)程序清單位：#include<stdio.h>#include<stdlib.h>structnode{intnum;structnode*next;};structnode*creat(structnode*head){structnode*top;/*top為新開(kāi)辟的結(jié)點(diǎn)*/top=(structnode*)malloc(sizeof(structnode));scanf(“%d”,&top->num);while(top->num>=0)｛top->next=head; /* 原來(lái)的第一個(gè)結(jié)點(diǎn)接在新開(kāi)辟的結(jié)點(diǎn)后面 */head=top;/*新開(kāi)辟結(jié)點(diǎn)作表頭結(jié)點(diǎn)，也就是說(shuō)插在表頭*/top=(structnode*)malloc(sizeof(structnode));scanf(“%d”,&top->num); }returnhead; }單鏈表的插入與刪除在鏈表這種特殊的數(shù)據(jù)結(jié)構(gòu)中，鏈表的長(zhǎng)短需要根據(jù)具體情況來(lái)設(shè)定，當(dāng)需要保存數(shù)據(jù)時(shí)向系統(tǒng)申請(qǐng)存儲(chǔ)空間，并將數(shù)據(jù)接入鏈表中。對(duì)鏈表而言，表中的數(shù)據(jù)可以依此接到表尾或連結(jié)到表頭，也可以視情況插入表中；對(duì)不再需要的數(shù)據(jù)，將其從表中刪除并釋放其所占空間，但不能破壞鏈表的結(jié)構(gòu)。這就是下面將介紹的鏈表的插入與刪除。鏈表的刪除在鏈表中刪除一個(gè)節(jié)點(diǎn)，用圖 7-4描述如下：[例7-6]創(chuàng)建一個(gè)學(xué)生學(xué)號(hào)及姓名的單鏈表，即節(jié)點(diǎn)包括學(xué)生學(xué)號(hào)、姓名及指向下一個(gè)節(jié)點(diǎn)的指針，鏈表按學(xué)生的學(xué)號(hào)排列。再?gòu)逆I盤輸入某一學(xué)生姓名，將其從鏈表中刪除。首先定義鏈表的結(jié)構(gòu)：從圖7-4中看到，從鏈表中刪除一個(gè)節(jié)點(diǎn)有三種情況，即刪除鏈表頭節(jié)點(diǎn)、刪除鏈表的中間節(jié)點(diǎn)、刪除鏈表的尾節(jié)點(diǎn)。題目給出的是學(xué)生姓名，則應(yīng)在鏈表中從頭到尾依此查找各節(jié)點(diǎn)，并與各節(jié)點(diǎn)的學(xué)生姓名比較，若相同，則查找成功，否則，找不到節(jié)點(diǎn)。由于刪除的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成丟失，所以定義刪除節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。structnode*delet(structnode*head,char*pstr)/*head為頭指針，刪除 pstr所在節(jié)點(diǎn)*/{structnode*temp,*p;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！temp=head;/*鏈表的頭指針*/if(head==NULL)/* 鏈表為空*/printf("\nListisnull!\n");else/*非空表*/{temp=head;while(strcmp(temp->str,pstr)!=0&&temp->next!=NULL)/*若節(jié)點(diǎn)的字符串與輸入字符串不同，并且未到鏈表尾*/{p=temp;temp=temp->next;/* 跟蹤鏈表的增長(zhǎng)，即指針后移 */}if(strcmp(temp->str,pstr)==0)/* 找到字符串*/{if(temp==head){/* 表頭節(jié)點(diǎn)*/printf("deletestring:%s\n",temp->str);head=head->next;free(temp);/*釋放被刪節(jié)點(diǎn)*/}else{p->next=temp->next;/*表中節(jié)點(diǎn)*/printf("deletestring:%s\n",temp->str);free(temp);} }elseprintf("\nnofindstring!\n"); /*沒(méi)找到要?jiǎng)h除的字符串

*/}return(head);/*返回表頭指針*/ }鏈表的插入首先定義鏈表的結(jié)構(gòu)：struct{intnum;/*學(xué)生學(xué)號(hào)*/charstr[20];/*姓名*/structnode*next;};7-5所示。在建立的單鏈表中，插入節(jié)點(diǎn)有三種情況，如圖插入的節(jié)點(diǎn)可以在表頭、表中或表尾。假定我們按照以學(xué)號(hào)為順序建立鏈表，則插入的節(jié)點(diǎn)依次與表中節(jié)點(diǎn)相比較，找到插入位置。由于插入的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成修改，所以定義插入節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。節(jié)點(diǎn)的插入函數(shù)如下：structnode*insert(head,pstr,n)/*插入學(xué)號(hào)為n、姓名為pstr的節(jié)點(diǎn)*/structnode*head;/*鏈表的頭指針*/char*pstr;intn;{structnode*p1,*p2,*p3;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！p1=(structnode*)malloc(sizeof(structnode))分;配/*一個(gè)新節(jié)點(diǎn)*/strcpy(p1->str,pstr);/*寫入節(jié)點(diǎn)的姓名字串*/p1->num=n;/*學(xué)號(hào)*/p2=head;if(head==NULL)/* 空表*/{head=p1;p1->next=NULL;/* 新節(jié)點(diǎn)插入表頭*/}else{/*非空表*/while(n>p2->num&&p2->next!=NULL)/*輸入的學(xué)號(hào)小于節(jié)點(diǎn)的學(xué)號(hào)，并且未到表尾 */{p3=p2;p2=p2->next;/* 跟蹤鏈表增長(zhǎng)*/}if(n<=p2->num)/*找到插入位置*/if(head==p2)/* 插入位置在表頭*/{head=p1;p1->next=p2;}else{/*插入位置在表中*/p3->next=p1;p1->next=p2;}else{/*插入位置在表尾*/p2->next=p1;p1->next=NULL;}}return(head);/* 返回鏈表的頭指針*/ }實(shí)例[例7-7]創(chuàng)建包含學(xué)號(hào)、姓名節(jié)點(diǎn)的單鏈表。其節(jié)點(diǎn)數(shù)任意個(gè)，表以學(xué)號(hào)為序，低學(xué)號(hào)的在前，高學(xué)號(hào)的在后，以輸入姓名為空作結(jié)束。在此鏈表中，要求刪除一個(gè)給定姓名的節(jié)點(diǎn)，并插入一個(gè)給定學(xué)號(hào)和姓名的節(jié)點(diǎn)。include"stdlib.h"include"malloc.h"structnode/*節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)*/{intnum;charstr[20];本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！structnode*next;main()

};{/*函數(shù)聲明*/structnode*creat();structnode*insert();structnode*delet();voidprint();structnode*head;charstr[20];intn;head=NULL;/*做空表*/head=creat(head);/*調(diào)用函數(shù)創(chuàng)建以head為頭的鏈表*/print(head)；/*調(diào)用函數(shù)輸出節(jié)點(diǎn)*/printf("\ninputinsertednum,name:\n");gets(str);/*輸入學(xué)號(hào)*/n=atoi(str);gets(str);/*輸入姓名*/head=insert(head,str,n); 將/*節(jié)點(diǎn)插入鏈表*/print(head)；/*調(diào)用函數(shù)輸出節(jié)點(diǎn)*/printf("\ninputdeletedname:\n");gets(str);/*輸入被刪姓名*/head=delet(head,str);/調(diào)*用函數(shù)刪除節(jié)點(diǎn)*/print(head);/*調(diào)用函數(shù)輸出節(jié)點(diǎn)*/return; }/*** 創(chuàng)建鏈表************/structnode*creat(structnode*head){chartemp[30];structnode*pl,*p2;pl=p2=(structnode*)malloc(sizeof(structnode));printf("inputnum,name:\n;")printf("exit:doubletimesEnter!\n");gets(temp);gets(p1->str);pl->num=atoi(temp);pl->next=NULL;while(strlen(pl->str)>0{if(head==NULL)head=pl ；elsep2->next=p1;P2=pl；pl=(structnode*)malloc(sizeof(structnode));printf("inputnum,name:\n");printf("exit:doubletimesEnter!\n");本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！gets(temp);gets(pl->str);p1->num=atoi(temp);p1->next=NULL;returnhead;}

}/********** 插入節(jié)點(diǎn)**********/structnode*insert(head,pstr,n);structnode*head;char*pstr;intn;{structnode*pl,*p2,*p3;p1=(structnode*)malloc(sizeof(structnode));strcpy(p1->str,pstr);p1->num=n;p2=head;if(head==NULL){head=pl;pl->next=NULL;}else{while(n>p2->num&&p2->next!=NULL){p3=P2p2=p2->next;}if(n<=p2->num)if(head==p2){head=pl;pl->next=p2;}else{p3->next=pl;pl->next=p2;}else{p2->next=pl;pl->next=NULL;}}return(head);}/***** 刪除節(jié)點(diǎn)*************/structnode*delet(structnode*head,char*pstr){structnode*temp,*p;structnode*p=head;本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！temp=head;if(head==NULL)printf("\nListisnull!\n");else{temp=head;while(strcmp(temp->str,pstr)!=O&&temp->next!=NULL){p=temp;temp=temp->next,}if(strcmp(temp->str,pstr)==0){if(temp==head){head=head->next;free(temp);}else{p->next=temp->next;printf("deletestring:%s\n",temp->str);free(temp);} }elseprintf("\nnofindstring!\n");}return(head); }/********** 鏈表各節(jié)點(diǎn)的輸出

**********/voidprint(structnode*head){structnode*temp;temp=head;while(temp!=NULL){printf("\n%d----%s\n",temp->num ，temp->str)；temp=temp->next ； }return; }帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)鏈表的區(qū)別：題目中沒(méi)說(shuō)明，就當(dāng)不帶頭結(jié)點(diǎn)，除非明確規(guī)定了帶頭結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的鏈表的第一個(gè)結(jié)點(diǎn)沒(méi)有數(shù)據(jù)域，只有指針域。例如要計(jì)算鏈表中所有結(jié)點(diǎn)數(shù)據(jù)的和，應(yīng)定義一個(gè)指向結(jié)構(gòu)體結(jié)點(diǎn)的指針，指向鏈表的第一個(gè)含數(shù)據(jù)的結(jié)點(diǎn)，給它賦值時(shí)，應(yīng)是structnode*p=head->next;其中head為鏈表的頭指針。因?yàn)轭^結(jié)點(diǎn)不含數(shù)據(jù)，頭結(jié)點(diǎn)指向的結(jié)點(diǎn)才開(kāi)始帶數(shù)據(jù)。如果是不帶頭結(jié)點(diǎn)的鏈表，第一個(gè)結(jié)點(diǎn)就含數(shù)據(jù)，因此，給它賦值時(shí)，應(yīng)是本文檔如對(duì)你有幫助，請(qǐng)幫忙下載支持！附：常見(jiàn)算法用鏈表實(shí)現(xiàn)查找算法例：如果有如下鏈表結(jié)構(gòu)：structst｛

charname[20];

/*

學(xué)生姓名

*/intcj;

/*

學(xué)生成績(jī)*/structst*next;};如果鏈表已創(chuàng)建正確，要求輸入一個(gè)學(xué)生姓名，查找該生成績(jī)，并輸出該生姓名，成績(jī)，以及該生