C語言程序設(shè)計(jì)實(shí)用教程-第15章鏈表

《C語言程序設(shè)計(jì)實(shí)用教程》Powerpoint制作：耿祥義張躍平第15章鏈表2010-10主要內(nèi)容及難點(diǎn)

2010-10概述當(dāng)需要?jiǎng)討B(tài)地減少或增加數(shù)據(jù)項(xiàng)時(shí)，可以使用鏈表這種數(shù)據(jù)結(jié)構(gòu)。鏈表是由假設(shè)干個(gè)稱作節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組成的一種數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)含有一個(gè)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的地址〔單鏈表〕，或含有一個(gè)數(shù)據(jù)并含有上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的地址〔雙鏈表〕。對(duì)于本章例子中的的C程序，在用VC++6.0時(shí)，要建立相應(yīng)的工程，并將源文件加到工程中。2010-1015.1初識(shí)鏈表用以下結(jié)構(gòu)體類型變量在內(nèi)存形成的結(jié)構(gòu)來模擬情報(bào)人員的之間形成的關(guān)系，如圖15.1所示。這種結(jié)構(gòu)就是一個(gè)鏈表。structPeoson{intnumber;char*name;structPeoson*next;};1．鏈表的頭指針：指向鏈表的第一個(gè)節(jié)點(diǎn)〔頭節(jié)點(diǎn)〕的structPeoson類型的指針變量head稱作鏈表的頭指針。2．鏈表的名字：用頭指針的名字來命名鏈表的名字。3．鏈表的索引與長(zhǎng)度：鏈表中節(jié)點(diǎn)的個(gè)數(shù)稱作鏈表的長(zhǎng)度。4．節(jié)點(diǎn)的指針域與數(shù)據(jù)域：一個(gè)節(jié)點(diǎn)中含有一個(gè)指針〔變量〕，名字通常為next，next中存放著下一個(gè)節(jié)點(diǎn)的地址。next指針變量在當(dāng)前節(jié)點(diǎn)中所占用的內(nèi)存區(qū)域稱作節(jié)點(diǎn)的指針域。節(jié)點(diǎn)中還含有存放數(shù)據(jù)的一些變量，這些變量在當(dāng)前節(jié)點(diǎn)中所占有的內(nèi)存稱作節(jié)點(diǎn)的數(shù)據(jù)域。2010-1015.2鏈表與節(jié)點(diǎn)本節(jié)使用的結(jié)構(gòu)體類型如下：typedefstructPeoson{ intnumber; char*name; structPeoson*next;}PERSON;當(dāng)聲明一個(gè)PERSON類型的指針變量，即給出鏈表的頭指針，但頭指針未指向PERSON類型的變量，比方頭指針head：PERSON*head=NULL;那么稱head是一個(gè)空鏈表?？真湵碇袩o任何節(jié)點(diǎn)。15.2.1空鏈表2010-1015.2.2鏈表的節(jié)點(diǎn)◆構(gòu)造節(jié)點(diǎn)：void*malloc(unsignedintsize)函數(shù)為節(jié)點(diǎn)分配內(nèi)存空間，并返回該內(nèi)存空間的首地址。例如，為了構(gòu)造出一個(gè)PERSON類型的節(jié)點(diǎn)，需進(jìn)行如下的操作：PERSON*node;node=malloc(sizeof(PERSON));◆使用節(jié)點(diǎn)中的成員node->number=10016;node->name="張三";◆刪除節(jié)點(diǎn)voidfree(void*p)函數(shù)用來釋放〔自由〕malloc函數(shù)分配的內(nèi)存空間，例如free(node);◆動(dòng)態(tài)鏈表如果鏈表的節(jié)點(diǎn)是用malloc函數(shù)分配的內(nèi)存，那么就可以使用free函數(shù)釋放該節(jié)點(diǎn)的內(nèi)存。這樣的鏈表也被稱作動(dòng)態(tài)鏈表。2010-1015.2.3創(chuàng)立一個(gè)簡(jiǎn)單的鏈表創(chuàng)立有3個(gè)節(jié)點(diǎn)的鏈表，步驟如下：1．創(chuàng)立一個(gè)空鏈表head2．添加第1個(gè)節(jié)點(diǎn)nodeOne3．添加第2個(gè)節(jié)點(diǎn)nodeTwo4．添加最后一個(gè)節(jié)點(diǎn)nodeThree。例子1(example15_1.c)根據(jù)上述步驟的編寫的代碼。

2010-1015.3頭插法創(chuàng)立鏈表_1本節(jié)使用的結(jié)構(gòu)體類型如下：typedefstructnode{ charch; structnode*next;}NODE;頭插法建立鏈表就是每次向鏈表添加的新節(jié)點(diǎn)將作為鏈表的頭節(jié)點(diǎn)，鏈表的原節(jié)點(diǎn)的索引依次增1。假設(shè)有鏈表head。頭插法的步驟如下：1創(chuàng)立一個(gè)新節(jié)點(diǎn)newNode,代碼如下newNode=malloc(sizeof(NODE));2將新節(jié)點(diǎn)的指針域中的next指針〔變量〕的值設(shè)置為頭指針的值，代碼如下：newNode->next=head3讓頭指針指向新節(jié)點(diǎn)，代碼如下：head=newNode;經(jīng)過上述步驟后，newNode就是鏈表head的頭節(jié)點(diǎn)?！羧绻鹔ead是空鏈表,進(jìn)過步驟2和3之后，鏈表head的結(jié)構(gòu)如圖15.6?！羧绻鹔ead是非空鏈表,進(jìn)過步驟2和3之后，鏈表head的結(jié)構(gòu)如圖15.7。2010-1015.3頭插法創(chuàng)立鏈表_2例子2(example15_2.c)使用頭插法建立了具有6個(gè)節(jié)點(diǎn)的鏈表，并輸出了鏈表節(jié)點(diǎn)中的數(shù)據(jù)。2010-1015.4尾插法創(chuàng)立鏈表尾插法建立鏈表就是每次向鏈表添加的新節(jié)點(diǎn)將作為鏈表的尾節(jié)點(diǎn)。尾插法的步驟如下：1．創(chuàng)立一個(gè)新節(jié)點(diǎn)newNode，代碼如下：newNode=malloc(sizeof(NODE));2．如果鏈表head是空鏈表，設(shè)置新節(jié)點(diǎn)是尾節(jié)點(diǎn)，將頭節(jié)點(diǎn)指向新節(jié)點(diǎn)，代碼如下：newNode->next=head;head=newNode;如果鏈表head是非空鏈表，找到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn),將當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)的指針域中的next指針〔變量〕指向新節(jié)點(diǎn)，將新節(jié)點(diǎn)設(shè)置為尾節(jié)點(diǎn)。代碼如下：NODE*foundEndNode=head;while((foundEndNode-next)!=NULL){foundEndNode=foundEndNode->next;}foundEndNode->next=newNode;newNode->next=NULL;經(jīng)過上述步驟后，newNode就是鏈表head的尾節(jié)點(diǎn)例子3(example15_3.c)使用頭插法建立了具有6個(gè)節(jié)點(diǎn)的鏈表,并輸出了鏈表節(jié)點(diǎn)中的數(shù)據(jù)。2010-1015.5鏈表的插入操作在鏈表的第i個(gè)節(jié)點(diǎn)和第i+1個(gè)節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)的步驟如下：1在鏈表中尋找第i個(gè)節(jié)點(diǎn)：NODE*getNode(NODE*head,inti){ intm=1;NODE*node_i=head; while((node_i->next!=NULL)&&(m<i)){ node_i=node_i->next; m++; } if(m==i) returnnode_i; else returnNULL;}2創(chuàng)立一個(gè)新節(jié)點(diǎn)newNode：newNode=malloc(sizeof(NODE));3將新節(jié)點(diǎn)的next指針指向第i+1個(gè)節(jié)點(diǎn)，將第i個(gè)節(jié)點(diǎn)中的next指針指向新節(jié)點(diǎn),代碼如下：newNode->next=node_i->next;node_i->next=newNode;經(jīng)過上述步驟后，newNode成為鏈表的第i+1個(gè)節(jié)點(diǎn)，而原來的第i+1個(gè)節(jié)點(diǎn)以及之后后的各個(gè)節(jié)點(diǎn)的索引依次增1。例子4(example15_4.c)使用尾插法建立了具有6個(gè)節(jié)點(diǎn)的鏈表，然后在第3和第4個(gè)節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)中的數(shù)據(jù)是字符'@'。插入新節(jié)點(diǎn)后，程序輸出了鏈表節(jié)點(diǎn)中的數(shù)據(jù)。2010-1015.6鏈表的刪除操作使用malloc函數(shù)為節(jié)點(diǎn)分配內(nèi)存空間，例如：NODE*node;node=malloc(sizeof(NODE));當(dāng)從鏈表中刪除節(jié)點(diǎn)node后，必須使用free函數(shù)釋放該節(jié)點(diǎn)所占用的內(nèi)存，即執(zhí)行代碼：free(node);釋放節(jié)點(diǎn)node占用的內(nèi)存。1．刪除鏈表head的頭節(jié)點(diǎn)的代碼如下：NODE*temp=head;//保存頭節(jié)點(diǎn)的地址;head=head->next;//將頭指針指向頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)free(temp);//釋放頭節(jié)點(diǎn)的內(nèi)存2．刪除鏈表head的第i個(gè)節(jié)點(diǎn)〔i>1〕的步驟如下：〔1〕找到鏈表中的第i-1個(gè)節(jié)點(diǎn)，代碼如下：foreNode=getNode(head,i-1);//見上一節(jié)中的getNode函數(shù)〔2〕刪除foreNode的后繼節(jié)點(diǎn)，代碼如下：node_i=foreNode->next;//保存第i個(gè)節(jié)點(diǎn)的地址foreNode->next=node_i->next//將第i-1個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)設(shè)置為鏈表的第i+1個(gè)節(jié)點(diǎn)〔3〕釋放第i個(gè)節(jié)點(diǎn)的內(nèi)存，代碼如下：free(node_i);例子5(example15_5.c)首先使用頭插法建立了具有6個(gè)節(jié)點(diǎn)的鏈表，然后刪除第3個(gè)節(jié)點(diǎn)〔該節(jié)點(diǎn)中的數(shù)據(jù)是字符D〕。刪除節(jié)點(diǎn)后，程序輸出了鏈表節(jié)點(diǎn)中的數(shù)據(jù)。2010-1015.7綜合舉例假設(shè)鏈表head有N個(gè)節(jié)點(diǎn)。

◆向左旋轉(zhuǎn)的操作是：如果1<m≤N，將第m個(gè)節(jié)點(diǎn)設(shè)置成鏈表的第m-1個(gè)節(jié)點(diǎn)，如果m=1，將第m個(gè)節(jié)點(diǎn)，即頭節(jié)點(diǎn)，設(shè)置成鏈表的尾節(jié)點(diǎn)，即設(shè)置成第N個(gè)節(jié)點(diǎn)。◆向右旋轉(zhuǎn)的操作是：如果1≤m<N，將第m個(gè)節(jié)點(diǎn)設(shè)置成鏈表的第m+1個(gè)節(jié)點(diǎn)，如果m=N，將第m個(gè)節(jié)點(diǎn)，即尾節(jié)點(diǎn)，設(shè)置成鏈表的頭節(jié)點(diǎn)，即設(shè)置成第1個(gè)節(jié)點(diǎn)。例子6(example15_6.c,rotate.c,create.c,getNode.c,input.c)旋轉(zhuǎn)有5個(gè)節(jié)點(diǎn)的鏈表，將鏈表向左旋轉(zhuǎn)了5次。15.7.1旋轉(zhuǎn)鏈表2010-1015.7.2圍圈留一圍圈留一”問題：“假設(shè)干個(gè)人圍成一圈，從某個(gè)人開始順時(shí)針數(shù)到第3個(gè)人，該人從圈中退出，然后繼續(xù)順時(shí)針數(shù)到第3個(gè)人，該人從圈中退出，依此類推，程序輸出圈中最后剩下的人”。“圍圈留一”問題可以簡(jiǎn)化為旋轉(zhuǎn)鏈表，例如用鏈表的節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)區(qū)依次存放m個(gè)代表圈中人的號(hào)碼的正整數(shù)1，2，…m。那么鏈表向左旋轉(zhuǎn)2次后，此時(shí)鏈表的頭節(jié)點(diǎn)應(yīng)該是要退出圈中的人，這時(shí)只要?jiǎng)h除鏈表的頭節(jié)點(diǎn)即可。例子7(example15_7.c,rotate.c,create.c,getNo