10.5.2 鏈表的操作

1、LOGOLOGO鏈表的基本操作（建立、輸出、插入新結(jié)點(diǎn)、刪除結(jié)點(diǎn)）Teacher teaching designCONTENTS 目 錄鏈表的創(chuàng)建鏈表的結(jié)點(diǎn)插入鏈表的結(jié)點(diǎn)刪除鏈表的輸出創(chuàng)建單向鏈表PART 01 定義鏈表的數(shù)據(jù)結(jié)構(gòu)。創(chuàng)建一個(gè)空表將新結(jié)點(diǎn)的指針成員賦值為空。若是空表，將新結(jié)點(diǎn)連接到表頭；若是非空表，將新結(jié)點(diǎn)接到表尾。判斷一下是否有后續(xù)結(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束。12344創(chuàng)建單向鏈表利用malloc( )函數(shù)向系統(tǒng)申請(qǐng)分配一個(gè)結(jié)點(diǎn)。5分兩步走一是先把頭指針head賦值給新結(jié)點(diǎn)的指針成員，讓新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)；再把新結(jié)點(diǎn)的地址賦給頭指針head成為鏈表的第一個(gè)結(jié)點(diǎn)。

2、鏈?zhǔn)兹腈湻绞绞菍⑿陆Y(jié)點(diǎn)的地址賦值給最后一個(gè)結(jié)點(diǎn)的指針成員，因此設(shè)置一個(gè)尾指針rear指針鏈表的最后一個(gè)結(jié)點(diǎn)，為新結(jié)點(diǎn)作準(zhǔn)備。將新結(jié)點(diǎn)入鏈后，新結(jié)點(diǎn)成為最后一個(gè)結(jié)點(diǎn)，不斷更新尾指針的指向，讓rear指向新入鏈的結(jié)點(diǎn)。鏈尾入鏈創(chuàng)建單向鏈表建立一條單向鏈表并輸出各結(jié)點(diǎn)的值，鏈表除了有一個(gè)指針成員之外，只有一個(gè)整型成員，數(shù)據(jù)由用戶輸入。(采用鏈?zhǔn)兹腈湹姆绞?添加標(biāo)題內(nèi)容struct number int n; struct number *next; ; /*定義鏈表的數(shù)據(jù)結(jié)構(gòu)*/#define LEN sizeof(struct number) /*宏定義*/struct number *creat

3、（） /*建立鏈表函數(shù)*/ struct number *head,*p;/*定義指向鏈表的指針變量*/ int a;char ch; head=NULL;printf(“是否輸入結(jié)點(diǎn)的數(shù)據(jù)？(Y/N)”); while(toupper(ch=getche()=Y)/*循環(huán)一次，連接一個(gè)結(jié)點(diǎn)*/ p=(struct number *)malloc(LEN);/*分配新結(jié)點(diǎn)單元*/ printf(“n輸入”); scanf(“%d”,&p-n); p-next=head; /*新結(jié)點(diǎn)指向原來(lái)的首結(jié)點(diǎn)*/ head=p; /*新結(jié)點(diǎn)成為新的首結(jié)點(diǎn)*/ printf(“是否繼續(xù)輸入結(jié)點(diǎn)的數(shù)據(jù)

4、？(Y/N)”);return (head);創(chuàng)建單向鏈表struct node /*鏈表節(jié)點(diǎn)的結(jié)構(gòu)* / int num; struct node *next; ;struct node *creat(struct node *head) /*函數(shù)返回的是與結(jié)點(diǎn)相同類(lèi)型的指針*/struct node *p1,*p2;p1=p2=(struct node*) malloc(sizeof(struct node); /*申請(qǐng)新結(jié)點(diǎn)*/scanf(%d,&p1-num) ; / * 輸入結(jié)點(diǎn)的值* /p1-next=NULL; / * 將新結(jié)點(diǎn)的指針置為空* /while(p1-num0

5、) / * 輸入節(jié)點(diǎn)的數(shù)值大于0 * /if (head=NULL) head=p1; / * 空表，接入表頭* /else p2-next=p1; / * 非空表，接到表尾* /p2 = p1 ;p1=(struct node *)malloc(sizeof(struct node); 申/請(qǐng)* 下一個(gè)新節(jié)點(diǎn)*/scanf(%d,&p1-num); / *輸入結(jié)點(diǎn)的值* /return head; /*返回鏈表的頭指針* /創(chuàng)建一個(gè)存放正整數(shù)（輸入-999做結(jié)束標(biāo)志）的單鏈表在鏈表的創(chuàng)建過(guò)程中，鏈表的頭指針是非常重要的參數(shù)。因?yàn)閷?duì)鏈表的輸出和查找都要從鏈表的頭開(kāi)始，所以鏈表創(chuàng)建成功后

6、，要返回一個(gè)鏈表頭結(jié)點(diǎn)的地址，即頭指針。采用鏈尾入鏈的方式struct number *creat() struct number *head,*p,*rear; int count=0; char ch; head=NULL;reat=NULL;printf(“是否輸入結(jié)點(diǎn)的數(shù)據(jù)？(Y/N)”);while(toupper(ch=getche()=Y)/*循環(huán)一次，連接一個(gè)結(jié)點(diǎn)*/ p=(struct number *)malloc(LEN);/*分配新結(jié)點(diǎn)單元*/ printf(“n輸入”); scanf(“%d”,&p-n); p-next=NULL; if(count=0) h

7、ead=p; rear=p else rear-next=p; rear=p; count+;printf(“是否繼續(xù)輸入結(jié)點(diǎn)的數(shù)據(jù)？(Y/N)”);return head;鏈表的插入PART 02structint num; /*學(xué)生學(xué)號(hào)* /char str20; /*姓名* /struct node *next; ;首先定義鏈表的結(jié)構(gòu)鏈表的插入鏈表的插入有三種情況插入的節(jié)點(diǎn)可以在表頭、表中或表尾。假定我們按照以學(xué)號(hào)為順序建立鏈表，則插入的節(jié)點(diǎn)依次與表中節(jié)點(diǎn)相比較，找到插入位置。由于插入的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成修改，所以定義插入節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類(lèi)型的指針

8、。鏈表的插入if (nnum) / *找到插入位置* /if (head=p2) / * 插入位置在表頭* /head=p1;p1-next=p2;else /*插入位置在表中* /p3-next=p1;p1-next=p2;else /*插入位置在表尾* /p2-next=p1;p1-next=NULL;return(head); / * 返回鏈表的頭指針* /結(jié)點(diǎn)的插入函數(shù)struct node *insert(head,pstr,n) struct node *head; / *鏈表的頭指針* /char *pstr;int n; struct node *p1,*p2,*p3;p1=(

9、struct node*)malloc(sizeof(struct node);strcpy(p1-str,pstr); / * 寫(xiě)入節(jié)點(diǎn)的姓名字串* /p1-num=n; / * 學(xué)號(hào)* /p2=head;if (head=NULL) / * 空表* / head=p1; p1-next=NULL;/ *新節(jié)點(diǎn)插入表頭* / else /*非空表* /while(np2-num&p2-next!=NULL)p3=p2 ;p2=p2-next; / * 跟蹤鏈表增長(zhǎng)* /在前例形成鏈表的基礎(chǔ)上，插入一個(gè)新結(jié)點(diǎn)，則需要先定位其插入點(diǎn)。例：生成一個(gè)結(jié)點(diǎn)并輸入其成員n的值，將其插入到已建好鏈

10、表中第一個(gè)值大于新結(jié)點(diǎn)n值的結(jié)點(diǎn)前面。鏈表的插入（第二種情形）插入的結(jié)點(diǎn)位置在最后語(yǔ)句是：p-next=NULL;表示將新結(jié)點(diǎn)的指針域成員置為NULL；q1-next=p;或者q2-next-next=p;讓前一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)；（第一種情形）插入的結(jié)點(diǎn)在中間位置，則插入語(yǔ)句為：p-next=q1;表示讓新結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)；q2-next=p;表示讓前一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)；鏈表的刪除PART 03為了刪除單鏈表中某個(gè)結(jié)點(diǎn)，可設(shè)置兩個(gè)活動(dòng)指針，從鏈?zhǔn)椎芥溛菜阉鞔齽h的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后將此前驅(qū)結(jié)點(diǎn)的指針域指向待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)，最后釋放被刪結(jié)點(diǎn)所占存儲(chǔ)空間即可。鏈表的刪除struct numbe

11、r *delete(struct number *head) struct number *p1,*p2,*q1,*q2; p1=head; q1=head; while(q1!=NULL) if（p1-nq1-n） p1=q1;p2=q2; q2=q1; q1=q1-next; if(p1=head) head=p1-next;/*要?jiǎng)h除的是第一個(gè)結(jié)點(diǎn)*/ else p2-next=p1-next;/*待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向待刪結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)。*/ return (head);刪除函數(shù)編寫(xiě)在鏈表中搜索成員n值最小的結(jié)點(diǎn)，將該結(jié)點(diǎn)刪除鏈表的刪除void delete_node(struct

12、 node *h，int i)/*在帶頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)*/struct node *p,*q;int k=0; p=h;while (p!=NULL&knext;k+;if (k!=i-1) printf(“刪除結(jié)點(diǎn)的位置i不合法”);else q=p-next; p-next=q-next; free(q);在帶頭結(jié)點(diǎn)的單鏈表中，刪除其第i個(gè)結(jié)點(diǎn)，如果第i個(gè)結(jié)點(diǎn)不存在，則輸出信息：“刪除結(jié)點(diǎn)的位置i不合法。鏈表的刪除案例分析交流提升PART 04建立如圖所示的存儲(chǔ)結(jié)構(gòu)（即每個(gè)節(jié)點(diǎn)兩個(gè)域，data是數(shù)據(jù)域，next是指向節(jié)點(diǎn)的指針域，請(qǐng)將定義補(bǔ)充完整）。struct no

13、de char data;_; ;解析1struct node * next;答案2添加標(biāo)題內(nèi)容鏈表中結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型通常是結(jié)構(gòu)體類(lèi)型，除了各種類(lèi)型的數(shù)據(jù)成員外，必須有一個(gè)特殊的成員：指向相同結(jié)構(gòu)體數(shù)據(jù)的指針變量以下程序運(yùn)行后的輸出結(jié)果是（ ）。struct NODE int num; struct NODE *next;main() struct NODE s3=1, 0,2, 0,3, 0, *p, *q, *r; int sum=0; s0.next=s+1;s1.next=s+2;s2.next=s; p=s; q=p-next; r=q-next; sum+=q-next-num;sum+=r-next-next-num; printf(%dn, sum); 案例分析 交流提升已知head指向單鏈表的第一個(gè)節(jié)點(diǎn)，以下程序調(diào)用函數(shù)print輸出這一單向鏈表。請(qǐng)?jiān)谶x擇正確內(nèi)容填空。struct student int info; struct student *link; ; void print(struct student * he