10.5.2 鏈表的操作

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

2、鏈?zhǔn)兹腈湻绞绞菍⑿陆Y(jié)點的地址賦值給最后一個結(jié)點的指針成員，因此設(shè)置一個尾指針rear指針鏈表的最后一個結(jié)點，為新結(jié)點作準(zhǔn)備。將新結(jié)點入鏈后，新結(jié)點成為最后一個結(jié)點，不斷更新尾指針的指向，讓rear指向新入鏈的結(jié)點。鏈尾入鏈創(chuàng)建單向鏈表建立一條單向鏈表并輸出各結(jié)點的值，鏈表除了有一個指針成員之外，只有一個整型成員，數(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é)點的數(shù)據(jù)？(Y/N)”); while(toupper(ch=getche()=Y)/*循環(huán)一次，連接一個結(jié)點*/ p=(struct number *)malloc(LEN);/*分配新結(jié)點單元*/ printf(“n輸入”); scanf(“%d”,&p-n); p-next=head; /*新結(jié)點指向原來的首結(jié)點*/ head=p; /*新結(jié)點成為新的首結(jié)點*/ printf(“是否繼續(xù)輸入結(jié)點的數(shù)據(jù)

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

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

6、，要返回一個鏈表頭結(jié)點的地址，即頭指針。采用鏈尾入鏈的方式struct number *creat() struct number *head,*p,*rear; int count=0; char ch; head=NULL;reat=NULL;printf(“是否輸入結(jié)點的數(shù)據(jù)？(Y/N)”);while(toupper(ch=getche()=Y)/*循環(huán)一次，連接一個結(jié)點*/ p=(struct number *)malloc(LEN);/*分配新結(jié)點單元*/ 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é)點的數(shù)據(jù)？(Y/N)”);return head;鏈表的插入PART 02structint num; /*學(xué)生學(xué)號* /char str20; /*姓名* /struct node *next; ;首先定義鏈表的結(jié)構(gòu)鏈表的插入鏈表的插入有三種情況插入的節(jié)點可以在表頭、表中或表尾。假定我們按照以學(xué)號為順序建立鏈表，則插入的節(jié)點依次與表中節(jié)點相比較，找到插入位置。由于插入的節(jié)點可能在鏈表的頭，會對鏈表的頭指針造成修改，所以定義插入節(jié)點的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針

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é)點的插入函數(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); / * 寫入節(jié)點的姓名字串* /p1-num=n; / * 學(xué)號* /p2=head;if (head=NULL) / * 空表* / head=p1; p1-next=NULL;/ *新節(jié)點插入表頭* / else /*非空表* /while(np2-num&p2-next!=NULL)p3=p2 ;p2=p2-next; / * 跟蹤鏈表增長* /在前例形成鏈表的基礎(chǔ)上，插入一個新結(jié)點，則需要先定位其插入點。例：生成一個結(jié)點并輸入其成員n的值，將其插入到已建好鏈

10、表中第一個值大于新結(jié)點n值的結(jié)點前面。鏈表的插入（第二種情形）插入的結(jié)點位置在最后語句是：p-next=NULL;表示將新結(jié)點的指針域成員置為NULL；q1-next=p;或者q2-next-next=p;讓前一個結(jié)點指向新結(jié)點；（第一種情形）插入的結(jié)點在中間位置，則插入語句為：p-next=q1;表示讓新結(jié)點指向后一個結(jié)點；q2-next=p;表示讓前一個結(jié)點指向新結(jié)點；鏈表的刪除PART 03為了刪除單鏈表中某個結(jié)點，可設(shè)置兩個活動指針，從鏈?zhǔn)椎芥溛菜阉鞔齽h的結(jié)點的前驅(qū)結(jié)點，然后將此前驅(qū)結(jié)點的指針域指向待刪結(jié)點的后繼結(jié)點，最后釋放被刪結(jié)點所占存儲空間即可。鏈表的刪除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é)點*/ else p2-next=p1-next;/*待刪結(jié)點的前一個結(jié)點指向待刪結(jié)點的后一個結(jié)點。*/ return (head);刪除函數(shù)編寫在鏈表中搜索成員n值最小的結(jié)點，將該結(jié)點刪除鏈表的刪除void delete_node(struct

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

13、de char data;_; ;解析1struct node * next;答案2添加標(biāo)題內(nèi)容鏈表中結(jié)點的數(shù)據(jù)類型通常是結(jié)構(gòu)體類型，除了各種類型的數(shù)據(jù)成員外，必須有一個特殊的成員：指向相同結(jié)構(gòu)體數(shù)據(jù)的指針變量以下程序運行后的輸出結(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指向單鏈表的第一個節(jié)點，以下程序調(diào)用函數(shù)print輸出這一單向鏈表。請在選擇正確內(nèi)容填空。struct student int info; struct student *link; ; void print(struct student * he