清華大學C語言教學共16個第12個PPT學習教案

1、會計學1 清華大學清華大學C語言教學共語言教學共16個第個第12個個 2 鏈表插入結(jié)點 原則： 1、插入操作不應破壞原鏈接關系 2、插入的結(jié)點應該在它該在的位置。應該有 一個插入位置的查找子過程。 第1頁/共45頁 3 head 先看下面一個簡單的例子：已有一個如圖所示的鏈表 。它是按結(jié)點中的整數(shù)域從小到大排序的。現(xiàn)在要 插入一個結(jié)點，該節(jié)點中的數(shù)為10。 待插入結(jié)點此結(jié)點已插入鏈表 第2頁/共45頁 4 / 結(jié)構(gòu)7.c #include / 預編譯命令 #include / 內(nèi)存空間分配 #define null 0/ 定義空指針常量 #define LEN sizeof(struct nu

2、mST)/ 定義常量，表示結(jié)構(gòu)長度 struct numST/ 結(jié)構(gòu)聲明 int num;/ 整型數(shù) struct numST *next;/ numST結(jié)構(gòu)指針 ; 參考程序 第3頁/共45頁 5 / 被調(diào)用函數(shù)insert()，兩個形參分別表示鏈表和待插入的結(jié)點 void insert (struct numST *phead, struct numST *p) / 函數(shù)體開始 struct numST *q,*r;/ 定義結(jié)構(gòu)指針q,r if (*phead)=null)/ 第一種情況，鏈表為空 *phead = p;/ 鏈表頭指向p return;/ 完成插入操作，返回 else/ 鏈

3、表不為空 / 第二種情況，p結(jié)點num值小于鏈表頭結(jié)點的num值 if ( (*phead)-num p-num ) / 將p結(jié)點插到鏈表頭部 p-next = *phead;/ 將p的next指針指向鏈表頭(*phead) *phead = p;/ 將鏈表頭賦值為p return;/ 返回 第4頁/共45頁 6 / 第三種情況，循環(huán)查找正確位置 r = *phead;/ r賦值為鏈表頭 q = (*phead)-next;/ q賦值為鏈表的下一個結(jié)點 while (q!=null) / 利用循環(huán)查找正確位置 / 判斷當前結(jié)點num是否小于p結(jié)點的num if (q-num num) r =

4、q;/ r賦值為q，即指向q所指的結(jié)點 q = q-next;/ q指向鏈表中相鄰的下一個結(jié)點 else/ 找到了正確的位置 break; / 退出循環(huán) / 將p結(jié)點插入正確的位置 r-next = p; p-next = q; 第5頁/共45頁 7 / 被調(diào)用函數(shù)，形參為ST結(jié)構(gòu)指針，用于輸出鏈表內(nèi)容 void print(struct numST *head) int k=0;/ 整型變量，用于計數(shù) struct numST * r; / 聲明r為ST結(jié)構(gòu)指針 r=head;/ r賦值為head，即指向鏈表頭 while(r != null)/ 當型循環(huán)，鏈表指針不為空則繼續(xù) / 循環(huán)體開

5、始 k=k+1;/ 計數(shù)加1 printf(%d %dn,k,r-num); r=r-next;/ 取鏈表中相鄰的下一個結(jié)點 / 循環(huán)體結(jié)束 第6頁/共45頁 8 void main()/ 主函數(shù)開始 / 函數(shù)體開始 struct numST *head, *p;/ ST型結(jié)構(gòu)指針 head = null;/ 初始化head為null / 分配3個ST結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表 head = (struct numST *) malloc(LEN); head-next = (struct numST *) malloc(LEN); head-next-next = (struct numS

6、T *) malloc(LEN); / 為鏈表中的3個結(jié)點中的num賦值為5、10和15 head-num = 5; head-next-num = 10; head-next-next-num = 15; head-next-next-next = null; / 鏈表尾賦值為空 / 構(gòu)造一個結(jié)點p，用于插入鏈表 p = (struct numST *) malloc(LEN); p-num = 12; p-next = null; insert(/ 調(diào)用insert函數(shù)將結(jié)點p插入鏈表 print(head);/ 調(diào)用print函數(shù)，輸出鏈表內(nèi)容 / 主函數(shù)結(jié)束 第7頁/共45頁 9 1、

7、定義兩個ST型結(jié)構(gòu)指針*head，*p，并讓head=null ； 2、分配3個ST結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表 （1）head=(struct numST*) malloc(LEN); （2）head-next=(struct numST*) malloc(LEN); （3）head-next-next=(struct numST*) malloc(LEN); 先看主函數(shù) head 這3個ST結(jié)構(gòu)的內(nèi)存空間如上圖所示。 head-next head-next-next 第8頁/共45頁 10 下面用賦值語句往這3個空間中放num數(shù)據(jù)。最后的 一個結(jié)點為隊尾，在其指針域存放null。 （4）h

8、ead-num=5; （5）head-next-num=10; （6）head-next-next-num=15; （7）head-next-next-next=null; 做了這4條之后形成了一條鏈表如下： head 該鏈表的頭結(jié)點由head所指向。 第9頁/共45頁 11 3、構(gòu)造一個結(jié)點p，在p結(jié)點的數(shù)據(jù)域放12，再插入 鏈表 （1）p=(struct numST*) malloc(LEN); （2）p-num=12; （3）p-next=null; 4、調(diào)用insert函數(shù)來插入p結(jié)點。 語句為 insert( 意思是以將p插入到以head為隊頭的鏈表中。但這里 在調(diào)用時，不是用hea

9、d作為實參，而是用 被調(diào)用函數(shù)為 void insert(struct munST *phead, struct numST*p); headp 實際參數(shù) 形式參數(shù) pphead 第11頁/共45頁 13 當著實際參數(shù)head賦給了形式參數(shù)phead之后，phead就 指向了已經(jīng)存在了的鏈表，見下圖。 phead 這時原來的主程序中的頭指針就不再起作用了。而是 phead起作用。假如現(xiàn)在p中的結(jié)點數(shù)據(jù)為4小于5，應 該將p插入到phead所指向的結(jié)點前，如下圖 head 第12頁/共45頁 14 head phead 被調(diào)用函數(shù)無法改變head，這時head不再是頭結(jié)點的指 針了。如果被調(diào)用函

10、數(shù)返回head，主函數(shù)只能表示 head為頭指針的三個結(jié)點，新插入的結(jié)點并沒有包含 進去。要想將新的插入到最前面的結(jié)點包含進去，就 必須用傳址調(diào)用。 phead 第13頁/共45頁 15 （2）如果是傳址調(diào)用 主程序中的調(diào)用語句為 insert( 被調(diào)用函數(shù)為 void insert(struct munST *phead, struct numST*p); 先看 struct numST *phead 是說定義（*phead）為指向numST結(jié)構(gòu)的指針。 *phead是指向numST結(jié)構(gòu)的指針,phead又是指向 *phead這個指針的指針。phead= / 將表頭指針指向p結(jié)點 retur

11、n; / 返回主程序 在主程序中必然頭指針head指向p結(jié)點。 第17頁/共45頁 19 第二種情況： p結(jié)點的num值小于鏈表頭結(jié)點的num值，即 (*phead)-nump-num。這時要將p結(jié)點插入到頭結(jié)點 的前面，要執(zhí)行如下三條語句 p-next=*phead; / 在p結(jié)點的指針域賦以頭結(jié)點的地址值 *phead=p; / 將頭結(jié)點指針phead指向p結(jié)點 return; / 返回主程序 這種情況如下圖 *phead *phead pnull 第18頁/共45頁 20 第三種情況： 前兩種情況，無論遇到哪一種，都會返回主程序。只要不返回就 是這第三種情況，即p結(jié)點的num大于頭指針所

12、指向的結(jié)點的num 值。這時肯定地說p結(jié)點要插入到頭結(jié)點之后，究竟要插到哪里 需要找到應該插入的位置。我們設指針r和指針q，分別指向相鄰 的兩個結(jié)點，r在前q在后，當著滿足 r-num num num 時，p就插在r與q之間。我們看圖 head p qr null qr 第19頁/共45頁 21 一開始讓 r=*phead，讓 q=*phead-next (1) 當指針q為空指針時，說明原鏈表中只有一個結(jié)點， 即r指向的結(jié)點，這時只要將p結(jié)點接在r之后即可。執(zhí) 行 r-next=p; p-next=q; (2) 如果q!=null，說明起碼有兩個結(jié)點在鏈表中，接著 要判p結(jié)點的num值是否大于

13、q結(jié)點的num值。如果是 大，則說明p應插在q之后而不是之前，這時讓r和q 指針同時后移一步，即 r=q; q=q-next; 第20頁/共45頁 22 執(zhí)行(2) 在q!=null的情況下，如果p-numnum了，說明這 時找到了正確的插入位置，退出while循環(huán)，將p結(jié)點 插入到r后，q前即可。使用的語句為 在下面我們畫出該算法的結(jié)構(gòu)框圖 r-next=p; p-next=q; 第21頁/共45頁 23 (*phead)=null T F T F (*phead)-nump-num 第第 2 種情況：種情況： p 結(jié)點中的數(shù)據(jù)小于頭結(jié)點中的數(shù)據(jù)。 將結(jié)點中的數(shù)據(jù)小于頭結(jié)點中的數(shù)據(jù)。 將 p

14、 結(jié)點插入到表頭前，然后返回主函數(shù)。即結(jié)點插入到表頭前，然后返回主函數(shù)。即 p-next=*phead; *phead=p; return; 第第 3 種情況：種情況： p 結(jié)點中的數(shù)據(jù)大于等于頭結(jié)點中的數(shù)據(jù)。定義兩個指針結(jié)點中的數(shù)據(jù)大于等于頭結(jié)點中的數(shù)據(jù)。定義兩個指針 r 和和 q，讓，讓 r 指向表頭，讓指向表頭，讓 q 指向相鄰的下一個結(jié)點，即指向相鄰的下一個結(jié)點，即 r=*phead; q= (*phead)-next; 進入循環(huán)進入循環(huán)查找查找該該插入的位置。插入的位置。 第第 1 種情種情 況： 鏈表為況： 鏈表為 空。 讓鏈表空。 讓鏈表 頭頭 *phead 指向指向 p 結(jié)結(jié)

15、點， 之后返點， 之后返 回主函數(shù)?；刂骱瘮?shù)。 即即 *phead=p; return; T F q-numnum while(q!=null) 當當 q 指向不空指向不空 p 結(jié)點中的數(shù)據(jù)大于結(jié)點中的數(shù)據(jù)大于 q 結(jié)點中結(jié)點中 的數(shù)據(jù)。讓的數(shù)據(jù)。讓 r 與與 q 同時后移一同時后移一 步步 r=q; q=q-next; p 結(jié)點中的數(shù)據(jù)小結(jié)點中的數(shù)據(jù)小 于等于于等于 q 結(jié)點中結(jié)點中 的數(shù)據(jù)。 找到了正的數(shù)據(jù)。 找到了正 確的插入位置， 退確的插入位置， 退 出循環(huán)。出循環(huán)。 找到了找到了 p 結(jié)點正確的插入位置。包括兩種情況（結(jié)點正確的插入位置。包括兩種情況（1）q 指指 向空，向空， r

16、 指向隊尾結(jié)點； （指向隊尾結(jié)點； （2） r-numnumnum。 這兩種情況都需將這兩種情況都需將 p 插入到插入到 r 后后 q 前，即前，即 r-next=p; p-next=q; 第22頁/共45頁 24 作業(yè) 1、按下表順序輸入某班的一個學習小組的成員表 希望你將學習小組形成一個鏈表，每人一個結(jié)點。結(jié) 點中有四個成員：姓名、出生年、出生月、指針。在 鏈表中生日大者在前，小者在后。 建成鏈表后輸出該鏈表。 第23頁/共45頁 25 2、一年后錢亮同學調(diào)至其它學習小組，希望你編程從 原鏈表中刪除錢亮所在結(jié)點，之后輸出該鏈表。 提示：原鏈表如下： head 查找待刪除的結(jié)點的位置，要從鏈

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

18、將孫參所在結(jié)點指向錢亮的指針，不再指向 錢亮，而指向武陸 第25頁/共45頁 27 二 叉 樹 第26頁/共45頁 28 鏈表結(jié)構(gòu)是利用結(jié)構(gòu)中的指針域?qū)⒚總€結(jié)點鏈接起來， 形似鏈條，屬于線性結(jié)構(gòu)數(shù)據(jù)。 下面介紹一種非線性結(jié)構(gòu)的東西，二叉樹。 先看下例： 結(jié)點1 結(jié)點2 結(jié)點4 結(jié)點6 結(jié)點7 結(jié)點5結(jié)點3 root 第27頁/共45頁 29 在圖中 （1）外形象一棵倒立的樹 （2）最上層有一個“根結(jié)點”，指針root指向根結(jié)點。 （3）每個結(jié)點都是一個結(jié)構(gòu)，一個成員是整型數(shù)據(jù)，兩 個成員是指針，分為左指針L和右指針R。 （4）根結(jié)點的左指針指向左子樹；右指針指向右子樹。 （5）左子樹或右子樹本

19、身又是一棵二叉樹，又有它們自 己的左子樹和右子樹， 這是遞歸定義的，因此，在處理時?？捎眠f歸算法。 第28頁/共45頁 30 二叉樹的遍歷 樹的遍歷是指訪遍樹中的所有結(jié)點。 對比看遍歷一個單鏈表，從表頭開始按一個方 向從頭到尾就可遍歷所有結(jié)點。對二叉樹來 說就沒有這樣簡單了，因為對樹或是對子樹 都存在根（或子樹的根）和左子樹、右子樹 ，先遍歷誰？由之產(chǎn)生了三種不同的方法： 第29頁/共45頁 31 1、前序法： 1.1 先訪問根結(jié)點； 1.2 遍歷左子樹； 1.3 遍歷右子樹； 2、中序法： 2.1 遍歷左子樹； 2.2 訪問根； 2.3 遍歷右子樹； 3、后序法 3.1 遍歷左子樹； 3.2

20、 遍歷右子樹； 3.3 訪問根； 第30頁/共45頁 32 我們就以中序法為例研究如何遍歷二叉樹。仍然采用 遞歸算法。令指針p指向二叉樹的根結(jié)點 定義樹的結(jié)構(gòu) struct TREE int data; struct TREE *L, *R; ; 定義p為TREE結(jié)構(gòu)的指針 struct TREE *p; 讓LNR(P)為對以p為根的樹作中序遍歷的子函數(shù)。可 得出如下圖所示的遞歸算法與或結(jié)點圖 第31頁/共45頁 33 A LNR(p)中序遍歷p結(jié)中序遍歷p結(jié) 點為根的二叉樹點為根的二叉樹 B 什么都不做什么都不做 C p!=null p=null D LNR(p-L) 中序遍歷p的左子樹中序

21、遍歷p的左子樹 E 訪問p結(jié)點訪問p結(jié)點 F LNR(p-R) 中序遍歷p的右子樹中序遍歷p的右子樹 圖2圖2 第32頁/共45頁 34 該圖說明如下： 1、A結(jié)點表示中序遍歷p結(jié)點為根的二叉樹，函數(shù)為 LNR(p)。該結(jié)點為“或”結(jié)點，有兩個分支。當p為 空時，A取B結(jié)點，什么都不做；當p不空時，說明 樹存在（起碼有一個根），有結(jié)點C。 2、C結(jié)點為一個“與”結(jié)點，要依次做相關聯(lián)的三件 事情： 2.1 D結(jié)點：中序遍歷p的左子樹，函數(shù)為LNR(p- L); 2.2 E結(jié)點：直接可解結(jié)點，訪問p結(jié)點（比如輸出p 結(jié)點數(shù)據(jù)域中的值）。 2.3 F結(jié)點：中序遍歷p的右子樹，函數(shù)為LNR(p-R)

22、第33頁/共45頁 35 3、比較LNR(p)與LNR(p-L)及LNR(p-R)可以看出， 都是同一個函數(shù)形式，只不過代入了不同的參數(shù)， 從層次和隸屬關系看，p是父結(jié)點的指針，而p-L和 p-R是子結(jié)點的指針，p-L是左子樹的根，p-R是 右子樹的根。 下面請大家做一個練習，依圖2畫“與或”圖將圖1所 示的二叉樹用中序遍歷，將所訪問到的結(jié)點數(shù)據(jù)輸 出。如圖3 第34頁/共45頁 36 訪問結(jié)點4訪問結(jié)點4 輸出：6輸出：6 LNR(p-L) 指向結(jié)點2指向結(jié)點2 LNR(p-R) 指向結(jié)點6指向結(jié)點6 LNR(p) p=root p!=null p-R!=null null nullnull

23、 !=null !=null !=null!=null null p-L!=null 什么都不做 訪問結(jié)點1： 輸出3 第35頁/共45頁 37 二叉樹的建立 建立二叉樹的過程是一個“插入”過程，下面我們用 一個例子來講解這一過程。 我們想建立這樣一棵二叉樹，樹中的每一個結(jié)點有一 個整數(shù)數(shù)據(jù)名為data，有兩個指針：左指針L，右指 針R，分別指向這個結(jié)點的左子樹和右子樹，顯然可 以用如下名為TREE的結(jié)構(gòu)來描述這種結(jié)點： struct TREE int data; struct TREE *L, *R; 第36頁/共45頁 38 對二叉樹最重要的是根，它起定位的作用，因此，首先 建立的是根結(jié)點

24、。也就是說，如果從鍵盤輸入數(shù)據(jù)來 建立二叉樹，第一個數(shù)據(jù)就是這棵樹的根的數(shù)據(jù)，之 后再輸入的數(shù)據(jù)，每一個都要與根中的數(shù)據(jù)作比較， 以便確定該數(shù)據(jù)所在接點的插入位置。假定我們這里 依然用圖1的中序遍歷的方式。即如果待插入結(jié)點的 數(shù)據(jù)比根結(jié)點的數(shù)據(jù)小，則將其插至左子樹，否則插 入右子樹。 定義一個遞歸函數(shù) void insert(struct TREE *proot, struct TREE *p) 其中，指針p指向含有待插入數(shù)據(jù)的結(jié)點。 proot為樹的根指針的地址。 insert函數(shù)棵理解為將p結(jié)點插入到*proot所指向的 樹中。 第37頁/共45頁 39 insert(proot, p)可

25、用下列與或結(jié)點圖來描述 insert(proot,p) 將結(jié)點p插入根結(jié)點將結(jié)點p插入根結(jié)點 *proot=p; return;*proot=p; return; 返回返回 C 根結(jié)點不空，根結(jié)點不空， 樹已存在樹已存在 根結(jié)點為空根結(jié)點為空 *proot=null p-datadata insert( 將p結(jié)點插入右子樹將p結(jié)點插入右子樹 圖3圖3 p-data (*proot)-data insert( 將p結(jié)點插入左子樹將p結(jié)點插入左子樹 第38頁/共45頁 40 注意在上圖中proot是被調(diào)用函數(shù)的形參。從前面對它的 定義看，proot是指針的指針，實際上是指向二叉樹根 結(jié)點的指針的指

26、針，或者說是指向二叉樹根結(jié)點的指 針的地址。如下圖。因此，在主程序調(diào)用insert函數(shù) 時， 根結(jié)點 proot 實參 / 整型數(shù) struct TREE *L,*R;/ TREE結(jié)構(gòu)指針 ; 第40頁/共45頁 42 / 被調(diào)用函數(shù)insert，將結(jié)點插入二叉樹 void insert (struct TREE *proot, struct TREE* p) / 函數(shù)體開始 if (*proot=null)/ 如果根結(jié)點為空 *proot = p;/ 將結(jié)點p插入根結(jié)點 return;/ 返回 else/ 根結(jié)點不為空 / 如果p結(jié)點數(shù)據(jù)小于等于根結(jié)點數(shù)據(jù) if (p-data data) insert( / 插入左