計(jì)算機(jī)軟件及應(yīng)用鏈表c++課件

1、第11章 鏈表第1頁，共88頁。教學(xué)目標(biāo)鏈表的概念建立鏈表中指針的運(yùn)用插入刪除結(jié)點(diǎn)的思路與雙指針作用建立循環(huán)鏈表的思路第2頁，共88頁。 鏈表屬于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以類比成一“環(huán)”接一“環(huán)”的鏈條，這里每一“環(huán)”視作一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)串在起形成鏈表。第3頁，共88頁。11.1 舉例說明鏈表的概念第4頁，共88頁。【任務(wù)11.1】某電視臺(tái)希望王小二同學(xué)為他們編一個(gè)程序。該程序可以將節(jié)目串在一起，形成一份有序的節(jié)目預(yù)告。節(jié)目列表有如下三項(xiàng)1、節(jié)目名稱包括新聞聯(lián)播（CCTV News）祖國各地（Motherland）體育之窗（Sports）學(xué)校見聞（College）電影展播（Movie）2、節(jié)目主持人（D

2、irector）3、播放時(shí)間長度（Time）第5頁，共88頁。我們可以將每一個(gè)節(jié)目單獨(dú)放在一個(gè)結(jié)構(gòu)里，用一個(gè)指針把兩個(gè)結(jié)構(gòu)連在一起，一天的節(jié)目形成一條鏈表。用一個(gè)所謂的頭指針 head 指向鏈表的第一個(gè)結(jié)點(diǎn)。如下圖所示節(jié)目2節(jié)目nNULLhead頭指針節(jié)目1下面的程序是建立鏈表的過程。第6頁，共88頁。11.2 建立鏈表的過程第7頁，共88頁。/*/* 程 序 名：11_1.cpp */* 作 者：wuwh */* 編制時(shí)間：2002年11月26日 */* 主要功能：鏈表 */*#include using namespace std;struct ActList/ 定義一個(gè)名為 ActLis

3、t 結(jié)構(gòu)char ActName20;/ 節(jié)目名為字符數(shù)組char director20; / 主持人為字符數(shù)組int Mtime;/ 節(jié)目長度為分鐘ActList *next;/ 指向 ActList 結(jié)構(gòu)的指針;第8頁，共88頁。ActList *head; / 鏈頭指針ActList *Create() / 定義一個(gè)指向 AcitList 結(jié)構(gòu) /的指針函數(shù)，名為 Create ActList *p=NULL; / 指針，指向個(gè)待插入的結(jié)點(diǎn) ActList *q=NULL; / 指針，用于在其后插入結(jié)點(diǎn) head = NULL; / 一開始鏈表為空 int Time; / 節(jié)目時(shí)長，如為

4、0則退出第9頁，共88頁。/ 以下是給新結(jié)點(diǎn)輸入節(jié)目信息cout Time;while(Time != 0) / 當(dāng)該節(jié)目的時(shí)長不為0時(shí)，將其/ 納入鏈表中 p = new ActList;/ 分配內(nèi)存空間給p結(jié)點(diǎn) p-Mtime = Time; / 讓Time賦給p結(jié)點(diǎn)的結(jié) 構(gòu)成員Mtime cout p-ActName; / 輸入節(jié)目名稱 cout p-director; / 輸入主持人第10頁，共88頁。 if (head = NULL) / head為空，要插入第一個(gè) head = p; / 結(jié)點(diǎn)，讓頭指針指向結(jié)點(diǎn)p else / 否則不是頭結(jié)點(diǎn)，應(yīng)將p結(jié)點(diǎn) q-next = p; /

5、 插入到q結(jié)點(diǎn)的后面 q = p; / q指向當(dāng)前最后一個(gè)結(jié)點(diǎn) cout Time;/ 輸入下一個(gè)節(jié)目時(shí)長 / 一旦跳出while循環(huán)，說明有一個(gè)節(jié)目時(shí)長為0if (head != NULL)q-next = NULL; / 讓q所指的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭照f明這已是鏈尾了return(head);/ 返回頭指針第11頁，共88頁。void displayList(ActList *head) cout 顯示節(jié)目列表n; while(head != NULL)/ 當(dāng)指針head不空，則輸出 cout Mtime endl ActName endl director endl next; 第1

6、2頁，共88頁。int main( )/ 主函數(shù)開始 / 調(diào)用子函數(shù)displaList() / 調(diào)用時(shí)的實(shí)參為Create()函數(shù)的返回值 displayList( Create() ); return 0;/ 主函數(shù)結(jié)束第13頁，共88頁。說明1、先從主函數(shù)說起主函數(shù)只有一條語句 displayList(Create( );這是調(diào)用子函數(shù) displayList，該子函數(shù)的形參為 ActList *head 是一個(gè)指向 ActList 結(jié)構(gòu)的名為 head 的指針變量。在主函數(shù)調(diào)用 displayList 時(shí)所用的實(shí)際參數(shù)來自運(yùn)行 Create( ) 函數(shù)的返回值。從 Create( )

7、的定義ActList *Create( )看出 Create( ) 函數(shù)的返回值應(yīng)該是一個(gè)指向 ActList 的指針。主函數(shù)在調(diào)用子函數(shù)時(shí)，又遇到該函數(shù)的實(shí)參又是調(diào)用另一個(gè)函數(shù)之后的返回值。看起來的確顯得復(fù)雜，但是我們耐心分析之后，感到并不難。第14頁，共88頁。2、程序開頭為結(jié)構(gòu)定義。在這里我們稱這樣的一個(gè)結(jié)構(gòu)為一個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)包含兩個(gè)域：數(shù)據(jù)域和指針域int MTime;char ActName20; 數(shù)據(jù)域char director20ActList *next; 指針域結(jié) 點(diǎn)數(shù)據(jù)域中裝有節(jié)目的信息，而指針域裝的是指向另一個(gè)結(jié)點(diǎn)的地址。顯然這是為形成鏈表而專門設(shè)置的。第15頁，共88

8、頁。3、在定義 Create 函數(shù)之前，先定義了一個(gè)指向結(jié)構(gòu)的頭指針 head，即ActList *head;4、定義 Create函數(shù)，該函數(shù)可返回指向 ActList 結(jié)構(gòu)的指針，即ActList *Create( )分析這個(gè)函數(shù)的功能可分如下4塊第16頁，共88頁。 定義ActList *p = NULL;ActList *q = NULL;head = NULL;int Time;定義了兩個(gè)指向結(jié)構(gòu) ActList 的指針 p 和 q，并初始化為空，即未指向任何地址。同時(shí)讓頭指針 head 也為空。再定義一個(gè)臨時(shí)變量 Time，是一個(gè)整型數(shù)。第17頁，共88頁。 提示“輸入節(jié)目時(shí)長”，

9、之后用鍵盤輸入，用了下面兩句：cout Time;這部分程序語句是為下面的 while 循環(huán)做準(zhǔn)備的。如果 Time 不為 0，才做下面的內(nèi)容。第18頁，共88頁。 while( Time != 0 ) 循環(huán)在當(dāng)循環(huán)的循環(huán)體內(nèi)完成建立鏈表的過程。首先給 p 結(jié)點(diǎn)分配內(nèi)存空間。這個(gè)內(nèi)存空間的大小要根據(jù) p 結(jié)點(diǎn)的定義（p 結(jié)點(diǎn)是 ActList 結(jié)構(gòu)）來確定。接著下面就是幾個(gè)賦值語句p-MTime = Time;cout p-ActName;/ 用鍵盤輸入節(jié)目名稱cout p-director;/ 用鍵盤輸入主持人第19頁，共88頁。接著是一個(gè)分支語句if (head=NULL) head=p;

10、這是說如果頭指針為空，表示鏈表還是空的，這時(shí) p 結(jié)點(diǎn)就是第一個(gè)結(jié)點(diǎn)。讓 head 指向 p 結(jié)點(diǎn)。之后讓 q=p; 這是讓 q 指向剛進(jìn)入鏈表的結(jié)點(diǎn)，讓 p 再去指向待加入的結(jié)點(diǎn)。如果 p 結(jié)點(diǎn)已不是第一個(gè)結(jié)點(diǎn)了，head 必不為 NULL，因此要走 else 分支，即else q-next = p;第20頁，共88頁。將此時(shí)的 p 結(jié)點(diǎn)放到 q 所指向的結(jié)點(diǎn)后面。之后讓 q=p; 即讓 q 指向剛進(jìn)入鏈表的結(jié)點(diǎn)，騰出 p 去指向下一個(gè)待加入的結(jié)點(diǎn)。接下來輸入下一個(gè)節(jié)目時(shí)長，cout Time;至此，while 語句的循環(huán)體結(jié)束。當(dāng) Time 值不為0，就會(huì)有結(jié)點(diǎn)加入鏈表，繼續(xù)執(zhí)行循環(huán)體。一

11、旦 Time 為 0，則會(huì)跳出 while 循環(huán)。第21頁，共88頁。執(zhí)行兩條語句if (head != NULL) q-next = NULL;return (head);第一條是說，如果 head 不空說明鏈表已建成，這時(shí) q 一定是最后一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)的指針域置成空，以表明它是鏈尾。第22頁，共88頁。第二條 return (head); 將這條鏈表的頭指針 head 返回。這件事意味著執(zhí)行完 Create函數(shù)后得到 head 指針?biāo)赶虻牡刂罚@個(gè)地址就是鏈表中的第一個(gè)結(jié)點(diǎn)的地址。這時(shí)對(duì)主函數(shù)而言displayList( Create( ) ) 就是dispalyList( head

12、 )調(diào)用 dsplayList(head) 就會(huì)將整個(gè)鏈表從頭至尾輸出。第23頁，共88頁。1、定義 ActList 結(jié)構(gòu)，結(jié)構(gòu)中包含數(shù)據(jù)域和指針域。將一個(gè)結(jié)構(gòu)看作一個(gè)結(jié)點(diǎn)。2、定義一個(gè)指向結(jié)構(gòu)的指針 head，準(zhǔn)備用來指向鏈表的第一個(gè)結(jié)點(diǎn)。3、定義一個(gè)指向ActList 結(jié)構(gòu)的指針函數(shù)，起名為 Create 函數(shù)，該函數(shù)返回的是創(chuàng)建好的鏈的頭指針 head。下面是 Create 函數(shù)所要做的事情： 定義指向 ActList 結(jié)構(gòu)的兩個(gè)指針 p 和 q，定義后立即初始化為 NULL，即不指向任何地址。再讓頭指針 head 為 NULL，也是不指向任何地址，表示該鏈表尚未建立，一個(gè)結(jié)點(diǎn)也沒有。然

13、后定義一個(gè)中間變量“節(jié)目時(shí)長 Time”，當(dāng) Time 為 0 時(shí)，建立鏈表的過程應(yīng)該結(jié)束。建立鏈表的過程可歸納為如下三個(gè)步驟第24頁，共88頁。 下面程序的構(gòu)思是，只要 Time 不為 0，就要構(gòu)建鏈表。構(gòu)建的思路是將一個(gè)一個(gè)的結(jié)點(diǎn)加至鏈表里來。首先給 p 找一個(gè)能夠指向的內(nèi)存空間，我們說這是給 p 結(jié)點(diǎn)分配一片內(nèi)存空間。如下圖建立鏈表的過程可歸納為如下三個(gè)步驟p第25頁，共88頁。 然后，通過鍵盤往這個(gè)空間中裝入與節(jié)目有關(guān)的信息。裝完之后判斷一下 head 為空否，如為空則 p 結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)，讓 head 指向 p 結(jié)點(diǎn)就完成了有一個(gè)結(jié)點(diǎn)的鏈表。之后讓 q 賦值為 p，即使讓 q 指針

14、去指向剛加入鏈表的結(jié)點(diǎn)，將 p 指針騰出來去做下一個(gè)結(jié)點(diǎn)的工作。headpq圖 鏈表的第一個(gè)結(jié)點(diǎn)建成第26頁，共88頁。當(dāng) Time 不為 0，p 又被分配了內(nèi)存空間，形成了第二個(gè)結(jié)點(diǎn)，裝入節(jié)目信息后，判斷 head 不再為空，說明前面已有結(jié)點(diǎn)在鏈表中，這時(shí)要將第二個(gè)結(jié)點(diǎn)放到 q 所指向的結(jié)點(diǎn)的后面。執(zhí)行 q-next = p 之后就完成了。之后再將 q 指針移到第二個(gè)結(jié)點(diǎn)上，將 p 指針騰出來去做下一個(gè)結(jié)點(diǎn)的工作。headpq第27頁，共88頁。指針移到第二個(gè)結(jié)點(diǎn)上，將 p 指針騰出來去做下一個(gè)結(jié)點(diǎn)的工作。headq第三個(gè)結(jié)點(diǎn)加入鏈表的過程為headqp第28頁，共88頁。最末一個(gè)結(jié)點(diǎn)連至鏈

15、表的尾部之后，要在 q 指針?biāo)赶虻淖詈笠粋€(gè)機(jī)誒但的指針域加上一個(gè) NULL，表示這里是鏈尾了，后面再也不連結(jié)點(diǎn)了。headqNULL第29頁，共88頁。練 習(xí)1、按下表順序輸入某班的一個(gè)學(xué)習(xí)小組的成員表：姓名趙達(dá)錢亮孫參李思周蕪武陸鄭琪出生年月19831983198319821983198319821329546將學(xué)習(xí)小組形成一個(gè)鏈表，每人一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)中有4個(gè)成員：姓名、出生年、出生月、指針。建成鏈表后輸出該鏈表。第30頁，共88頁。鏈表結(jié)點(diǎn)的插入第31頁，共88頁。鏈表結(jié)點(diǎn)的插入原則： 插入操作不應(yīng)破壞原鏈接關(guān)系 插入的結(jié)點(diǎn)應(yīng)該在它該在的位置。應(yīng)該有一個(gè)插入位置的查找子過程第32頁，共8

16、8頁。5head61015null128先看下面一個(gè)簡單的例子：已有一個(gè)如圖所示的鏈表。它是按結(jié)點(diǎn)中的整數(shù)域從小到大排序的?，F(xiàn)在要插入一個(gè)結(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)為10。待插入結(jié)點(diǎn)此結(jié)點(diǎn)已插入鏈表第33頁，共88頁。/*/* 程 序 名：7_20.cpp */* 作 者：wuwh */* 編制時(shí)間：2002年12月3日 */* 主要功能：鏈表插入結(jié)點(diǎn) */*#include / 預(yù)編譯命令struct numST/ 結(jié)構(gòu)聲明int num;/ 整型數(shù)numST *next;/ numST結(jié)構(gòu)指針;參考程序第34頁，共88頁。/ 被調(diào)用函數(shù)insert()，兩個(gè)形參分別表示鏈表和待插入的結(jié)點(diǎn)void

17、insert ( numST *&pHead, numST *pNode)/ 函數(shù)體開始struct numST *q,*r;/ 定義結(jié)構(gòu)指針q,r/ 第一種情況，鏈表為空if (pHead=NULL)pHead = pNode;/ 鏈表頭指向pNodereturn;/ 完成插入操作，返回/ 鏈表不為空/ 第二種情況，pNode結(jié)點(diǎn)num值小于等于鏈表頭結(jié)點(diǎn)的num值/ 則將pNode結(jié)點(diǎn)插到鏈表頭部if ( pNode-num num ) pNode-next = pHead;/ 將pNode的next指針指向鏈表頭 pHeadpHead = pNode;/ 將鏈表頭賦值為pNoderetu

18、rn;/ 返回第35頁，共88頁。/ 第三種情況，循環(huán)查找正確位置r = pHead;/ r賦值為鏈表頭q = pHead-next;/ q賦值為鏈表的下一個(gè)結(jié)點(diǎn)while (q!=NULL) / 利用循環(huán)查找正確位置/ 判斷pNode結(jié)點(diǎn)的num是否大于當(dāng)前結(jié)點(diǎn)numif (pNode-num q-num)r = q;/ r賦值為q，即指向q所指的結(jié)點(diǎn)q = q-next;/ q指向鏈表中相鄰的下一個(gè)結(jié)點(diǎn)else/ 找到了正確的位置break;/ 退出循環(huán)/ 將pNode結(jié)點(diǎn)插入正確的位置r-next = pNode;pNode-next = q;第36頁，共88頁。/ 被調(diào)用函數(shù)，形參為n

19、umST結(jié)構(gòu)指針，用于輸出鏈表內(nèi)容void print(numST *pHead)int k=0;/ 整型變量，用于計(jì)數(shù)numST *r=pHead;/ 聲明 r 為 numST 結(jié)構(gòu)指針，/ 并賦值為pHead，即指向鏈表頭while(r != NULL)/ 當(dāng)型循環(huán)，鏈表指針不為空則繼續(xù)/ 循環(huán)體開始cout.width(2);/ 設(shè)置輸出的序號(hào) k 所占的寬度k = k+1;cout k : num next;/ 取鏈表中相鄰的下一個(gè)結(jié)點(diǎn)/ 循環(huán)體結(jié)束/ 函數(shù)體結(jié)束第37頁，共88頁。void main()/ 主函數(shù)開始/ 函數(shù)體開始numST *pMHead=NULL;/ numST

20、型結(jié)構(gòu)指針，鏈表頭numST *pMNode=NULL;/ numST 型結(jié)構(gòu)指針，要插入的結(jié)點(diǎn)/ 兩個(gè)指針均初始化為空/ 分配 3 個(gè) numST 結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表pMHead = new numST;pMHead-next = new numST;pMHead-next-next = new numST;/ 為鏈表中的3個(gè)結(jié)點(diǎn)中的num賦值為5、10和15pMHead-num = 5;pMHead-next-num = 10;pMHead-next-next-num = 15;pMHead-next-next-next = NULL; / 鏈表尾賦值為空/ 構(gòu)造一個(gè)結(jié)點(diǎn)p，用于

21、插入鏈表pMNode = new numST;pMNode-num = 12;pMNode-next = NULL;insert(pMHead, pMNode);/ 調(diào)用insert函數(shù)將結(jié)點(diǎn)pMNode插入鏈表print(pMHead);/ 調(diào)用print函數(shù)，輸出鏈表內(nèi)容/ 與 new 對(duì)應(yīng)，用 delete 釋放空間 / 主函數(shù)結(jié)束第38頁，共88頁。1、定義兩個(gè) numST 型結(jié)構(gòu)指針*pMHead，*pMNode，并初始化 pMHead 和 pMNode 為 NULL;2、分配 3 個(gè) numST 結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表（1）pMHead = new numST;（2）pMHe

22、ad-next = new numST;（3）pMHead-next-next = new numST;先看主函數(shù)pMHead這 3 個(gè) numST 結(jié)構(gòu)的內(nèi)存空間如上圖所示。pMHead-nextpMHead-next-next第39頁，共88頁。下面用賦值語句往這 3 個(gè)空間中放 num 數(shù)據(jù)。最后的一個(gè)結(jié)點(diǎn)為隊(duì)尾，在其指針域存放 NULL。（4）pMHead-num=5;（5）pMHead-next-num=10;（6）pMHead-next-next-num=15;（7）pMHead-next-next-next=NULL;做了這4條之后形成了一條鏈表如下：5pMHead1015NUL

23、L該鏈表的頭結(jié)點(diǎn)由 pMHead 所指向。第40頁，共88頁。3、構(gòu)造一個(gè)結(jié)點(diǎn) pMNode，在 pMNode 結(jié)點(diǎn)的數(shù)據(jù)域放 12，再插入鏈表（1）pMNode = new numST;（2）pMNode-num = 12;（3）pMNode-next = NULL;4、調(diào)用 insert 函數(shù)來插入 pMNode 結(jié)點(diǎn)。語句為 insert(pMHead, pMNode);意思是以將 pMNode 插入到以 pMHead 為隊(duì)頭的鏈表中。但這里在調(diào)用時(shí)，用 pMHead作為實(shí)參，傳遞的是引用，而非傳值。所以在函數(shù)體內(nèi)對(duì)pHead的修改，就等價(jià)于對(duì)pMHead的操作。第41頁，共88頁。這里

24、要講傳值和傳引用的區(qū)別（1）如果是傳值調(diào)用主程序中的調(diào)用語句為 insert(pMHead, pMNode);被調(diào)用函數(shù)為void insert( munST *pHead, numST*pNode);pMHeadpMNode實(shí)際參數(shù)形式參數(shù)pNodepHead第42頁，共88頁。當(dāng)著實(shí)際參數(shù) pMHead 賦給了形式參數(shù) pHead之后，pHead 就指向了已經(jīng)存在了的鏈表，見下圖。51015NULLpHead這時(shí)原來的主函數(shù)中的頭指針 pMHead 就不再起作用了，而是子函數(shù)中的 pHead 起作用。假如現(xiàn)在 pNode 中的結(jié)點(diǎn)數(shù)據(jù)為 4 小于 5，應(yīng)該將 pNode 插入到 pHead

25、 所指向的結(jié)點(diǎn)前，如下圖pMHead第43頁，共88頁。5pMHead1015NULLpHead被調(diào)用函數(shù)無法改變主函數(shù)的 pMHead。雖然在子函數(shù)內(nèi) pHead 被修改，指向了含有四個(gè)結(jié)點(diǎn)的鏈表頭，但當(dāng)函數(shù)返回后，主函數(shù)中的 pMHead 仍然指向鏈表后面的三個(gè)結(jié)點(diǎn)，新插入的結(jié)點(diǎn)并沒有包含進(jìn)去。所以要想將新的插入到最前面的結(jié)點(diǎn)包含進(jìn)去，就必須用傳址或傳引用。4pHead第44頁，共88頁。（2）如果是傳引用調(diào)用主程序中的調(diào)用語句為 insert(pMHead, pMNode);被調(diào)用函數(shù)為void insert(munST *&pHead, numST *pNode);先看 numST *

26、&pHead 是說聲明 pHead 為 numST 結(jié)構(gòu)指針的引用，即pHead 是“指向 numST 結(jié)構(gòu)的指針”的引用。第45頁，共88頁。 主程序中的實(shí)參為鏈表頭指針 pMHead 的引用，傳給被調(diào)用函數(shù)的 pHead，在子函數(shù)中對(duì) pHead 的操作就等價(jià)于對(duì) pMHead 的操作。pMHead(pHead)*pMHead第46頁，共88頁。在主函數(shù)中 pMHead為頭指針，在被調(diào)用的子函數(shù)中 pHead 為頭指針。pHead 和 pMHead 是同一個(gè)單元，只不過分別叫不同的名罷了。當(dāng)然在子函數(shù)中無論插入什么結(jié)點(diǎn)都會(huì)讓 pHead 指向鏈表的頭。自然返回到主函數(shù)后，pMHead也會(huì)是

27、指向同一鏈表的頭。從這個(gè)例子中讀者可以領(lǐng)會(huì)到傳引用調(diào)用與傳值調(diào)用的區(qū)別。5、這樣在子函數(shù)做插入結(jié)點(diǎn)的過程中，頭指針的改變也能反映到主函數(shù)中來。調(diào)用 print 函數(shù)，從 pMHead 開始輸出整個(gè)鏈表的內(nèi)容。第47頁，共88頁。下面我們來研究 insert 函數(shù)前提是主程序已將兩個(gè)實(shí)參傳給了 insert 函數(shù)的兩個(gè)形參，這時(shí) pHead 是 pMHead 的引用，指向鏈表頭，pNode 所指向的就是待插入的一個(gè)結(jié)點(diǎn)。事先定義兩個(gè)結(jié)構(gòu)指針 q 和 r。第48頁，共88頁。第一種情況：pHead=NULL說明主程序傳過來的頭指針為空，即鏈表為空，一個(gè)結(jié)點(diǎn)都不存在。這時(shí)待插入的 pNode 結(jié)點(diǎn)就

28、是鏈表中的第一個(gè)結(jié)點(diǎn)。只要執(zhí)行如下兩條語句即可pHead = pNode; / 將表頭指針指向p結(jié)點(diǎn)return; / 返回主程序在主程序中必然頭指針 pMHead 指向 pMNode 結(jié)點(diǎn)。第49頁，共88頁。第二種情況：pNode 結(jié)點(diǎn)的 num 值小于等于鏈表頭結(jié)點(diǎn)的 num 值，即 pNode-num num 這時(shí)要將 pNode 結(jié)點(diǎn)插入到頭結(jié)點(diǎn)的前面，要執(zhí)行如下三條語句pNode-next=pHead; / 在 pNode 結(jié)點(diǎn)的指針域/ 賦以頭結(jié)點(diǎn)的地址值pHead=pNode;/ 將頭結(jié)點(diǎn)指針 pHead/ 指向 pNode 結(jié)點(diǎn)return;/ 返回主程序第50頁，共88頁。

29、這種情況如下圖（演示）5pHead10415NULLpNodeNULL第51頁，共88頁。第三種情況：前兩種情況，無論遇到哪一種，都會(huì)返回主程序。只要不返回就是這第三種情況，即 pNode 結(jié)點(diǎn)的 num 大于等于頭指針?biāo)赶虻慕Y(jié)點(diǎn)的 num 值。這時(shí)肯定地說 pNode 結(jié)點(diǎn)要插入到頭結(jié)點(diǎn)之后，究竟要插到哪里需要找到應(yīng)該插入的位置。我們?cè)O(shè)指針 r 和指針 q，分別指向相鄰的兩個(gè)結(jié)點(diǎn)，r 在前 q 在后。第52頁，共88頁。當(dāng)著滿足r-num num num時(shí)，pNode 就插在 r 與 q 之間。（演示）5pHead1012pNode15NULLNULLqr第53頁，共88頁。一開始讓 r=

30、pHead，讓 q=pHead-next(1) 當(dāng)指針 q 為空指針時(shí)，說明原鏈表中只有一個(gè)結(jié)點(diǎn)，即 r 指向的結(jié)點(diǎn)，這時(shí)只要將 pNode 結(jié)點(diǎn)接在 r 之后即可。執(zhí)行r-next=pNode;pNode-next=q;第54頁，共88頁。(2) 如果 q!=NULL，說明起碼有兩個(gè)結(jié)點(diǎn)在鏈表中，接著要判 pNode 結(jié)點(diǎn)的 num 值是否大于 q 結(jié)點(diǎn)的 num 值。如果是大，則說明 pNode 應(yīng)插在 q 之后而不是之前，這時(shí)讓 r 和 q 指針同時(shí)后移一步，即r=q;q=q-next;第55頁，共88頁。執(zhí)行(2)在 q!=NULL 的情況下，如果 pNode-num num說明這時(shí)找

31、到了正確的插入位置，退出 while 循環(huán)，將 pNode 結(jié)點(diǎn)插入到 r 后，q 前即可。使用的語句為在下面我們畫出該算法的結(jié)構(gòu)框圖r-next=pNode;pNode-next=q;第56頁，共88頁。第57頁，共88頁。作業(yè)1、按下表順序輸入某班的一個(gè)學(xué)習(xí)小組的成員表希望你將學(xué)習(xí)小組形成一個(gè)鏈表，每人一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)中有四個(gè)成員：姓名、出生年、出生月。指針。在鏈表中生日大者在前，小者在后。建成鏈表后輸出該鏈表。姓名趙達(dá)錢亮孫參李思周蕪武陸鄭琪出 年生 月19831983198319821983198319821329546第58頁，共88頁。2、一年后錢亮同學(xué)調(diào)至其它學(xué)習(xí)小組，希望你編程從

32、原鏈表中刪除錢亮所在結(jié)點(diǎn)，之后輸出該鏈表。提示：原鏈表如下：李思19829head武陸19834趙達(dá)19831孫參19832錢亮19833鄭琪19826周蕪19835NULL查找待刪除的結(jié)點(diǎn)的位置，要從鏈頭找起。(1)如果是鏈頭結(jié)點(diǎn)，即有 head-name = 待刪者 name這時(shí)只要做 head=head-next; 即可(2)如果不是鏈頭結(jié)點(diǎn)，要設(shè)兩個(gè)指針 r 和 q，初始時(shí)讓r=head; q=head-next;第59頁，共88頁。(3)只要 q!=NULL，就比較 q-name 是否為待刪者的name？如果是則讓 r-next=q-next; 如不是，就讓 r 與 q 同時(shí)后移一步

33、，即 r=q; q=q-next; 然后轉(zhuǎn)向(3)(4)如果發(fā)現(xiàn) q 已是NULL，又未找到待刪結(jié)點(diǎn)，則輸出該人不在這個(gè)表中的信息。在原鏈表中一旦查到錢亮所在結(jié)點(diǎn)位置 q，讓r-next = q-next;意味著將孫參所在結(jié)點(diǎn)指向錢亮的指針，不再指向錢亮，而指向武陸第60頁，共88頁。11.3.2 鏈表結(jié)點(diǎn)的刪除void del(numST *&pHead,int num) numST *p = NULL,*q = NULL; /第一種情況，鏈表空 if(pHead = NULL) /鏈表為空，直接返回 return; /第二種情況，鏈表不空，但刪除的是鏈表頭 p = pHead; if( p

34、-num = num) /要?jiǎng)h除的是鏈表頭 pHead = p-next;/鏈表頭指向下一個(gè)結(jié)點(diǎn) delete p; /刪除結(jié)點(diǎn)并釋放空間 return; 第61頁，共88頁。 /第三種情況，鏈表非空且刪除的不是表頭結(jié)點(diǎn)， /需要從表頭起查找要?jiǎng)h除結(jié)點(diǎn) q = p-next; while (q!=NULL) if(q-num = num)/q結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn) p-next = q-next;/將q結(jié)點(diǎn)從鏈表中去掉 delete q; /刪除結(jié)點(diǎn)并釋放空間 return; if(q-numnum) /不存在要?jiǎng)h除的結(jié)點(diǎn) return ; p = q; q = q-next; /while /

35、del第62頁，共88頁。作業(yè)1、按下表順序輸入某班的一個(gè)學(xué)習(xí)小組的成員表希望你將學(xué)習(xí)小組形成一個(gè)鏈表，每人一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)中有四個(gè)成員：姓名、出生年、出生月。指針。在鏈表中生日大者在前，小者在后。建成鏈表后輸出該鏈表。姓名趙達(dá)錢亮孫參李思周蕪武陸鄭琪出 年生 月19831983198319821983198319821329546第63頁，共88頁。2、一年后錢亮同學(xué)調(diào)至其它學(xué)習(xí)小組，希望你編程從原鏈表中刪除錢亮所在結(jié)點(diǎn)，之后輸出該鏈表。提示：原鏈表如下：李思19829head武陸19834趙達(dá)19831孫參19832錢亮19833鄭琪19826周蕪19835NULL查找待刪除的結(jié)點(diǎn)的位置，要

36、從鏈頭找起。(1)如果是鏈頭結(jié)點(diǎn)，即有 head-name = 待刪者 name這時(shí)只要做 head=head-next; 即可(2)如果不是鏈頭結(jié)點(diǎn)，要設(shè)兩個(gè)指針 r 和 q，初始時(shí)讓r=head; q=head-next;第64頁，共88頁。(3)只要 q!=NULL，就比較 q-name 是否為待刪者的name？如果是則讓 r-next=q-next; 如不是，就讓 r 與 q 同時(shí)后移一步，即 r=q; q=q-next; 然后轉(zhuǎn)向(3)(4)如果發(fā)現(xiàn) q 已是NULL，又未找到待刪結(jié)點(diǎn)，則輸出該人不在這個(gè)表中的信息。在原鏈表中一旦查到錢亮所在結(jié)點(diǎn)位置 q，讓r-next = q-ne

37、xt;意味著將孫參所在結(jié)點(diǎn)指向錢亮的指針，不再指向錢亮，而指向武陸第65頁，共88頁。11.4 循 環(huán) 鏈 表第66頁，共88頁。任務(wù)11.2 猴子選大王。n 只猴子圍成一圈，順時(shí)針方向從 1 到 n 編號(hào)。之后從 1 號(hào)開始沿順時(shí)針方向讓猴子從 1，2，m 依次報(bào)數(shù)，凡報(bào)到 m 的猴子，都讓其出圈，取消候選資格。然后不停地按順時(shí)針方向逐一讓報(bào)出 m 者出圈，最后剩下一個(gè)就是猴王。第67頁，共88頁。起始位置猴 王123456783615284猴子被淘汰的順序演示：n=8, m=3第68頁，共88頁。說明：如圖 1 所示有 8 只猴子圍成一圈，m=3。從 1# 猴的位置開始，順時(shí)針 1 至 3

38、 報(bào)數(shù)，第一個(gè)出圈的是 3#；第二個(gè)出圈的是 6#，第 3 個(gè)出圈的是 1#；第 4 個(gè)出圈的是 5#；第 5 個(gè)是 2#，第 6 個(gè)是 8#；第 7 個(gè)是 4#。最后剩下一個(gè)是 7#，它就是猴王。我們用循環(huán)鏈表來模擬這個(gè)選擇過程。第69頁，共88頁。1、定義一個(gè)名為 mon 的結(jié)構(gòu)struct monint num;/ 整數(shù)，表示猴子的編號(hào)mon *next;/ 指針，指向相鄰的下一只猴子;2、將鏈表的頭指針 head 定義為全局變量。mon *head;3、主函數(shù)用鍵盤輸入猴子數(shù) n，輸入數(shù) m，調(diào)用函數(shù) create 建立一個(gè)循環(huán)鏈表，模擬眾猴圍成一圈的情況。該函數(shù)的實(shí)參為 n。調(diào)用函數(shù)

39、 select，模擬 1 至 m 報(bào)數(shù)，讓 n-1 只猴子逐一出列的過程。即在具有n個(gè)結(jié)點(diǎn)的循環(huán)鏈表按報(bào)數(shù) m 刪除結(jié)點(diǎn)的過程。該函數(shù)的實(shí)參為 m，最后輸出猴王的編號(hào)。第70頁，共88頁。4、建立循環(huán)鏈表的函數(shù) create(int nn)其中nn為形式參數(shù)。要從編號(hào) 1 到編號(hào) nn。思路是（1）先做第1個(gè)結(jié)點(diǎn)，讓其中的數(shù)據(jù)域 p-num 賦值為 1，讓指針域賦值為 NULL。之后讓鏈頭指針 head 指向第 1 個(gè)結(jié)點(diǎn)。利用指針 q 記住這個(gè)結(jié)點(diǎn)，以便讓指針p去生成下面的結(jié)點(diǎn)。（2）利用一個(gè)計(jì)數(shù)循環(huán)結(jié)構(gòu)，做出第 2 個(gè)結(jié)點(diǎn)到第 nn 個(gè)結(jié)點(diǎn)。并將相鄰結(jié)點(diǎn)一個(gè)接一個(gè)鏈接到一起。（3）最后一個(gè)

40、結(jié)點(diǎn)要和頭結(jié)點(diǎn)用下一語句鏈接到一起tail = q; tail-next = head;headtailq第71頁，共88頁。5、刪結(jié)點(diǎn)的函數(shù) select( int mm )mm為形式參數(shù)，從 1 至 mm 報(bào)數(shù)，凡報(bào)到 mm 者刪除其所在的結(jié)點(diǎn)。設(shè)計(jì)兩個(gè)指針 p 和 q。一開始讓 q 指向鏈表的尾部 q = tail。讓 p 指向 q 的下一個(gè)結(jié)點(diǎn)。開始時(shí)讓 p 指向 1# 猴所在的結(jié)點(diǎn)。用一個(gè)累加器x，初始時(shí) x = 0，從 1# 猴所在結(jié)點(diǎn)開始讓 x= x+1 =1，如果 mm 是 1 的話，1# 猴所在的 p 結(jié)點(diǎn)就要被刪除。有四條語句：第72頁，共88頁。cout“被刪掉的猴子號(hào)為

41、”numnext = p-next;delete p;p=NULL;1head28tailqp演示空指針第73頁，共88頁。這里 delete p 是釋放 p 結(jié)點(diǎn)所占用的內(nèi)存空間的語句。如果 mm 不是 1 而是 3，程序會(huì)在 do-while 循環(huán)中，讓 x 加兩次 1，q 和 p 一起移動(dòng)兩次，p 指向 3#所在結(jié)點(diǎn)，q 指向 2# 所在結(jié)點(diǎn)，之后仍然用上述四條語句刪去 3# 所在的結(jié)點(diǎn)。1head28qp34q演示第74頁，共88頁。這個(gè)do-while循環(huán)的退出條件是 q= q-next。即當(dāng)只剩下一個(gè)結(jié)點(diǎn)時(shí)才退出循環(huán)。當(dāng)然猴王非其莫屬了。這時(shí)，讓頭指針 head 指向 q，head

42、 是全局變量，在主程序最后輸出猴王時(shí)要用 head-num。參考程序如下：7headq第75頁，共88頁。/*/* 程 序 名：7_22.cpp */* 作 者：wuwh */* 編制時(shí)間：2002年12月11日 */* 主要功能：猴子選大王 */*#include / 預(yù)編譯命令struct monkey/ 結(jié)構(gòu)聲明int num;/ 整型數(shù), 用于記錄猴子號(hào)monkey *next;/ monkey結(jié)構(gòu)指針;monkey *head, *tail;/ monkey結(jié)構(gòu)指針，全局變量第76頁，共88頁。void create(int nn)/ 被調(diào)用函數(shù) / 函數(shù)體開始 int i; / 整

43、型變量i，用于計(jì)數(shù)monkey *p,*q; / 聲明monkey結(jié)構(gòu)指針 / 為p分配內(nèi)存空間p=new monkey;p-num=1; / 初始化p結(jié)點(diǎn)num域?yàn)?p-next=NULL; / 初始化p結(jié)點(diǎn)next域?yàn)榭説ead=p; / 鏈表頭指針head賦值為pq=p;/ q賦值為p第77頁，共88頁。for(i=2;inum=i;/ 初始化p結(jié)點(diǎn)num域?yàn)閕，表 示猴子號(hào)q-next=p;/ 將p結(jié)點(diǎn)加到鏈表尾部q=p;/ 讓q指向鏈表尾部結(jié)點(diǎn)p-next=NULL;/ 鏈表尾部指向空/ 循環(huán)體結(jié)束tail = q;/ 鏈表尾tail-next=head;/ 鏈表尾部指向鏈表頭/ 函

44、數(shù)體結(jié)束第78頁，共88頁。/ 被調(diào)用函數(shù)select，mm表示結(jié)點(diǎn)刪除間隔void select(int mm)/ 函數(shù)體開始int x=0; / 聲明整型值x，并初始化為0monkey *p,*q; / 聲明結(jié)構(gòu)指針p，qq=tail;/ q賦值為tail，指向循環(huán)鏈表尾部 do/ 直到型循環(huán)，用于循環(huán)刪除指定間隔的結(jié)點(diǎn)/ 循環(huán)體開始p=q-next;/ p賦值為q相鄰的下一個(gè)結(jié)點(diǎn)x=x+1;/ x加1if(x % mm=0)/ x是否整除mm，/ 表示是否跳過指定間隔/ 輸出被刪掉的猴子號(hào)cout 被刪掉的猴子號(hào)為 num next=p-next;/ 刪除此結(jié)點(diǎn)delete p;/ 釋放空間p=NULL;/ p賦值為空else q=p;/ q指向相鄰的下一個(gè)結(jié)點(diǎn)pwhile(q!=q-next);/ 剩余結(jié)點(diǎn)數(shù)不為1，則繼續(xù)循環(huán)head = q;/ head指向結(jié)點(diǎn)q，q為鏈表中剩余的一個(gè)結(jié)點(diǎn)/ 函數(shù)體結(jié)束第79頁，共88頁。do/ 直到型循環(huán)，用于循環(huán)刪除指定間隔的結(jié)點(diǎn) p=q-next;/ p賦值為q相鄰的下一個(gè)結(jié)點(diǎn)