C程序設(shè)計第12章PPT學(xué)習(xí)教案

1、會計學(xué)1C程序設(shè)計第程序設(shè)計第12章章n使用數(shù)組帶來的問題是：使用數(shù)組帶來的問題是：n操作不方便；操作不方便；n數(shù)組尺寸不好確定。數(shù)組尺寸不好確定。 第二，數(shù)組第二，數(shù)組多大：為保存全部卡片，并且人多大：為保存全部卡片，并且人數(shù)不固定，就應(yīng)該給一個足夠大數(shù)不固定，就應(yīng)該給一個足夠大的數(shù)組。的數(shù)組。n最好把這些卡片存儲成動態(tài)的，最好把這些卡片存儲成動態(tài)的，n需要多大存儲量（有多少張卡片）需要多大存儲量（有多少張卡片）就用多大。就用多大。n中間加一張卡片時不要向后串別中間加一張卡片時不要向后串別的卡片，的卡片，n刪除一張卡片時不要留下刪除一張卡片時不要留下“洞洞”。第1頁/共91頁 如圖的鏈?zhǔn)浇Y(jié)構(gòu)

2、可以滿足要求:n當(dāng)增加一張卡片時，只需要向計算機系統(tǒng)申請一塊空間，聯(lián)到鏈的適當(dāng)位置上。例如，要增加一張卡片 50 插入到 2 、3 之間，則只需要如下修改指針：n若刪除一節(jié)，只需要將其從鏈上摘下來即可。例刪除2節(jié)得鏈上已經(jīng)沒有2節(jié)了，刪掉的節(jié)所占的存儲空間還可以還回計算機系統(tǒng)，以便作其它用途。123 n.50 第2頁/共91頁n這就是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)中的這就是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)中的鏈表。動態(tài)數(shù)據(jù)結(jié)構(gòu)上的一項鏈表。動態(tài)數(shù)據(jù)結(jié)構(gòu)上的一項是一個動態(tài)變量，指針是標(biāo)識動是一個動態(tài)變量，指針是標(biāo)識動態(tài)變量的有力手段。動態(tài)變量與態(tài)變量的有力手段。動態(tài)變量與靜態(tài)變量的區(qū)別在于靜態(tài)變量的區(qū)別在于:n靜態(tài)變量是程序

3、中由程序員靜態(tài)變量是程序中由程序員“顯顯式式”說明的變量。它有一個名字，說明的變量。它有一個名字，在編譯時，編譯程序已經(jīng)給它分在編譯時，編譯程序已經(jīng)給它分配存儲空間。這塊存儲空間用變配存儲空間。這塊存儲空間用變量的名字來標(biāo)識。量的名字來標(biāo)識。第3頁/共91頁n動態(tài)變量在程序中沒有動態(tài)變量在程序中沒有“顯式顯式”說明，它沒有名字說明，它沒有名字n在編譯時編譯程序不知道有該變量，不給（也不可在編譯時編譯程序不知道有該變量，不給（也不可能給）它分配空間。能給）它分配空間。n動態(tài)變量是在程序運行時動態(tài)變量是在程序運行時n隨程序存儲數(shù)據(jù)的需要，申請空間隨程序存儲數(shù)據(jù)的需要，申請空間函數(shù)（例如函數(shù)（例如m

4、alloc，當(dāng)然也是由程，當(dāng)然也是由程序員安排的）隨機的動態(tài)的申請來序員安排的）隨機的動態(tài)的申請來的空間。它沒有名字，一般動態(tài)變的空間。它沒有名字，一般動態(tài)變量都由指針標(biāo)識。量都由指針標(biāo)識。n當(dāng)使用完畢后，由釋放空間函數(shù)當(dāng)使用完畢后，由釋放空間函數(shù)（例如（例如free）釋放，還回計算機存）釋放，還回計算機存儲管理系統(tǒng)，以備它用。儲管理系統(tǒng)，以備它用。第4頁/共91頁n注意：這里所說的靜態(tài)變量不是注意：這里所說的靜態(tài)變量不是C語言中由靜態(tài)存儲類別語言中由靜態(tài)存儲類別static聲聲明的變量；動態(tài)變量也不是明的變量；動態(tài)變量也不是C語語言中由自動存儲類別言中由自動存儲類別auto聲明的聲明的變量。

5、而是一般程序設(shè)計概念中變量。而是一般程序設(shè)計概念中的靜態(tài)變量、動態(tài)變量的靜態(tài)變量、動態(tài)變量第5頁/共91頁第6頁/共91頁目標(biāo)代碼空間靜態(tài)區(qū)空間庫代碼空間堆區(qū)空間棧區(qū)空間 內(nèi)存 程序運行時，涉及用戶程序的內(nèi)存存儲結(jié)構(gòu)如右圖所示，首先是目標(biāo)代碼區(qū)；然后是靜態(tài)存儲區(qū)，用于存放那些可用絕對地址標(biāo)識的，主要是具有靜態(tài)存儲類別的數(shù)據(jù)和變量；接著是目標(biāo)代碼運行時用到的庫程序代碼區(qū)；最后剩余空間是棧區(qū)和堆區(qū)，棧區(qū)和堆區(qū)從剩余空間的兩端，動態(tài)的向中間增長。棧區(qū)用來存儲程序中聲明的函數(shù)的局部變量等具有自動存儲類別的數(shù)據(jù)和變量；堆區(qū)用來存儲經(jīng)過動態(tài)申請空間函數(shù)申請的變量。第7頁/共91頁nsizeof 運算符運算

6、符n單目運算符單目運算符 sizeof 的的n操作數(shù)操作數(shù)是類型。是類型。n運算結(jié)果運算結(jié)果是求得相應(yīng)類型的尺寸，即存儲是求得相應(yīng)類型的尺寸，即存儲相應(yīng)類型數(shù)據(jù)所需要的字節(jié)數(shù)。相應(yīng)類型數(shù)據(jù)所需要的字節(jié)數(shù)。nsizeof(int) /* 結(jié)果是結(jié)果是2 */nsizeof(char) /* 結(jié)果是結(jié)果是1 */nsizeof(struct date) /* 若若 struct date 是第十一章定義的日期類型，是第十一章定義的日期類型，結(jié)果是結(jié)果是6 */第8頁/共91頁nmalloc 函數(shù)函數(shù):n原型原型 void *malloc(unsigned long size);n功能功能 申請足夠

7、大內(nèi)存區(qū)域用來存申請足夠大內(nèi)存區(qū)域用來存儲長度為儲長度為size的數(shù)據(jù)對象，返回的數(shù)據(jù)對象，返回該區(qū)域的首指針，并保證該區(qū)域該區(qū)域的首指針，并保證該區(qū)域符合任何數(shù)據(jù)類型對存儲區(qū)域開符合任何數(shù)據(jù)類型對存儲區(qū)域開始地址和對齊的要求。始地址和對齊的要求。 返回指針是返回指針是void類型的，調(diào)類型的，調(diào)用者必須使用顯示強制類型轉(zhuǎn)換，用者必須使用顯示強制類型轉(zhuǎn)換，把該指針轉(zhuǎn)換成所需要類型的指把該指針轉(zhuǎn)換成所需要類型的指針。針。第9頁/共91頁n例例:float *p ;p = (float*)malloc( sizeof(float) );struct date *pdate;pdate=(struc

8、t date*)malloc(sizeof(struct date);第10頁/共91頁nfree函數(shù)函數(shù)n動態(tài)申請的內(nèi)存如果不再使用，動態(tài)申請的內(nèi)存如果不再使用，應(yīng)當(dāng)適時釋放這樣可以提高程序應(yīng)當(dāng)適時釋放這樣可以提高程序運行效率。運行效率。free函數(shù)用來釋放經(jīng)過函數(shù)用來釋放經(jīng)過malloc申請的動態(tài)空間。申請的動態(tài)空間。free的函的函數(shù)數(shù)n原型原型 void free ( void *ptr ) ;n功能功能釋放由釋放由malloc申請的內(nèi)存區(qū)域。申請的內(nèi)存區(qū)域。free的參數(shù)的參數(shù)ptr是一個指針，指向是一個指針，指向以前由以前由malloc申請的一個內(nèi)存區(qū)申請的一個內(nèi)存區(qū)域。域。第11

9、頁/共91頁n例例n申請申請float *p ;p = (float*)malloc( sizeof(float) );struct date *pdate;pdate=(struct date*)malloc(sizeof(struct date);n釋放釋放free(p);free(pdate);第12頁/共91頁nfree(ptr) /* 釋放釋放ptr所指向由所指向由malloc申請的內(nèi)存空間申請的內(nèi)存空間 */n一塊存儲區(qū)域一經(jīng)釋放，便不能再使用。使用一塊存儲區(qū)域一經(jīng)釋放，便不能再使用。使用free特別注意，操作不當(dāng)會產(chǎn)生不可預(yù)料的結(jié)果。如下特別注意，操作不當(dāng)會產(chǎn)生不可預(yù)料的結(jié)果。如

10、下情況下使用情況下使用free都會造成災(zāi)難性后果。都會造成災(zāi)難性后果。nptr無值；無值；nptr的值為的值為NULL；nptr所指向的空間不是經(jīng)過所指向的空間不是經(jīng)過malloc申申請來的；請來的；n對一次申請的存儲區(qū)進(jìn)行多次釋放對一次申請的存儲區(qū)進(jìn)行多次釋放（實際可能是（實際可能是ptr無值或值為無值或值為NULL）。）。第13頁/共91頁n實用問題實用問題:n若指針變量指向的用若指針變量指向的用malloc申請來的動態(tài)變量，是申請來的動態(tài)變量，是孤立的不能與其它變量相聯(lián)系，顯然作用不大。孤立的不能與其它變量相聯(lián)系，顯然作用不大。n引進(jìn)動態(tài)變量的目的是構(gòu)造動態(tài)數(shù)據(jù)結(jié)構(gòu)。引進(jìn)動態(tài)變量的目的是

11、構(gòu)造動態(tài)數(shù)據(jù)結(jié)構(gòu)。n例如象本章開始介紹的那樣，構(gòu)造一個鏈表等。例如象本章開始介紹的那樣，構(gòu)造一個鏈表等。n這就要求一個數(shù)據(jù)項上除基本的數(shù)據(jù)信息外，還應(yīng)這就要求一個數(shù)據(jù)項上除基本的數(shù)據(jù)信息外，還應(yīng)包含與其它數(shù)據(jù)項相聯(lián)系的信息，也就是包含指針。包含與其它數(shù)據(jù)項相聯(lián)系的信息，也就是包含指針。n該結(jié)構(gòu)必須用結(jié)構(gòu)體類型描述，鏈表上一節(jié)的類型該結(jié)構(gòu)必須用結(jié)構(gòu)體類型描述，鏈表上一節(jié)的類型定義形式。定義形式。第14頁/共91頁類型定義形式 struct t 基本數(shù)據(jù)部分； struct t *next ; 基本數(shù)據(jù)部分指針部分一個數(shù)據(jù)項 123 n.第15頁/共91頁棧棧 stackn在第六章已經(jīng)用數(shù)組實現(xiàn)過

12、棧和隊列，但是，數(shù)組有一定的局限在第六章已經(jīng)用數(shù)組實現(xiàn)過棧和隊列，但是，數(shù)組有一定的局限性。如圖可以用單向鏈表實現(xiàn)棧，指針變量性。如圖可以用單向鏈表實現(xiàn)棧，指針變量top指向棧頂。棧的操指向棧頂。棧的操作有作有: 初始化：初始化：stackintial 壓棧：壓棧：stackpush 彈棧：彈棧：stackpop第16頁/共91頁設(shè)有聲明設(shè)有聲明: typedef . items ; typedef struct stackcell items data ; struct stackcell *predocessor ; stackcelltype ; typedef stackcelltyp

13、e *pstacktype ; pstacktype top ;top:. .棧第17頁/共91頁如下實現(xiàn)棧的操作：如下實現(xiàn)棧的操作： void stackinitial(void) top = NULL ; void stackpush ( items x ) pstacktype p ; p = (pstacktype)malloc(sizeof(stackcelltype); p-data = x ; p-prodocessor = top ; top = p ; void stackpop ( items *x ) pstacktype p ; if ( top != NULL ) *

14、x = top-data ; p = top ; top = top-predecessor ; free(p); else printf( “棧下溢棧下溢n” ); 第18頁/共91頁看一下這三個操作看一下這三個操作:1.初始化后初始化后(調(diào)用調(diào)用stackinitail)得。得。2.調(diào)用一次調(diào)用一次 stackpush(1) 得。得。3.再調(diào)用一次再調(diào)用一次stackpush(2)得得 。4.調(diào)用一次調(diào)用一次stackpop(&b)得得 。top:1.2b:2第19頁/共91頁n如圖可用單向鏈表實現(xiàn)隊列，現(xiàn)在要用兩個指針變量，一如圖可用單向鏈表實現(xiàn)隊列，現(xiàn)在要用兩個指針變量，一個指向隊頭（

15、個指向隊頭（front），一個指向隊尾（），一個指向隊尾（rear）。隊列的操）。隊列的操作有作有 初始化（初始化（ queueinitial ） 進(jìn)隊進(jìn)隊排在隊尾（排在隊尾（inqueue） 出隊出隊從隊頭刪一項（從隊頭刪一項（outqueue）rear:front:. .第20頁/共91頁設(shè)有如下說明設(shè)有如下說明: typedef . items ; typedef struct queue items data struct queue *next ; queuetype ; typedef queuetype *pqueuetype ; pqueuetype front,rear ;操

16、作：操作： void queueinital(void) front = NULL ; rear = NULL ; 第21頁/共91頁void inqueue (item x) pqueuetype p; p = (pqueuetype)malloc(sizeof(queuetype); p- data = x ; p- next = NULL ; if ( rear=NULL ) rear = p ; front = p ; else rear- next = p ; rear = p ; 第22頁/共91頁void outgueue ( item *x ) pqueuetype p; if

17、 ( front=NULL ) printf( “隊空隊空n” ); else *x = front- data ; p = front ; front = front- next; if ( front=NULL ) rear = NULL ; free( p ) ; 第23頁/共91頁看一下這三個操作看一下這三個操作: 1. 調(diào)用初始化后（調(diào)用一次調(diào)用初始化后（調(diào)用一次 queueinitail） 得；得； 2. 調(diào)用一次調(diào)用一次ingueue(1)得；得； 再調(diào)用一次再調(diào)用一次ingueue(2)得；得； 再調(diào)用一次再調(diào)用一次 ingueue(3)得得 ;3. 調(diào)用一次調(diào)用一次 outg

18、ueue(&a) 得；得； 再調(diào)用一次再調(diào)用一次 outgueue(&b) 得得; 再調(diào)用一次再調(diào)用一次 outgueue(&a) 得得 。1a:rear:front:231 p:b:23NULLNULL第24頁/共91頁base:1.2N-1N.雙向鏈base:12N-1N.單向鏈第25頁/共91頁base:12N-1N.環(huán)形鏈base:12N-1N.雙向環(huán)形鏈第26頁/共91頁n創(chuàng)建單向鏈表創(chuàng)建單向鏈表: :第27頁/共91頁n遍歷單向鏈表遍歷單向鏈表:p = base ; p0 = NULL;while (p != NULL ) p = base ; 加工 p - while (p !=

19、 NULL ) p = p- next; 加工 p - p0 = p ; p = p- next; 第28頁/共91頁n在單向鏈表上檢索在單向鏈表上檢索: 檢索是指在單向鏈表上查找關(guān)鍵字等于某給定檢索是指在單向鏈表上查找關(guān)鍵字等于某給定值的節(jié)點值的節(jié)點, 若找到則帶回相應(yīng)節(jié)點的指針；否則若找到則帶回相應(yīng)節(jié)點的指針；否則帶回帶回NULL 。設(shè)關(guān)鍵字域域名為。設(shè)關(guān)鍵字域域名為key ；欲檢索的；欲檢索的關(guān)鍵字值為關(guān)鍵字值為key0 . 如下算法實現(xiàn)檢索：如下算法實現(xiàn)檢索： p0 = NULL; p = base ; while (p != NULL & p-key !=key0 ) p0 = p;

20、 p = p- next; 第29頁/共91頁n向單向鏈表插入一項向單向鏈表插入一項: 設(shè)有下圖的鏈表，現(xiàn)在要把設(shè)有下圖的鏈表，現(xiàn)在要把r所指示的數(shù)據(jù)項插所指示的數(shù)據(jù)項插入到入到 p0、p 所指兩項之間。操作是所指兩項之間。操作是: r- next = p ; p0- next = r ; p0 = r /* 使使 p0 仍為仍為 p 的前一項的前一項 */r:5p0: p: 1 2 3 4.第30頁/共91頁n從單向鏈表上刪除一項從單向鏈表上刪除一項: 設(shè)有下圖的鏈表，現(xiàn)在要刪除設(shè)有下圖的鏈表，現(xiàn)在要刪除p所指項。刪除所指項。刪除算法是：算法是： q = p ; p = p- next ;

21、p0- next = p ; free(q)p0:1234.p:q:第31頁/共91頁n交換單向鏈表上兩項交換單向鏈表上兩項: 設(shè)有如圖所示鏈表?，F(xiàn)在要把設(shè)有如圖所示鏈表。現(xiàn)在要把 p 所指的項與所指的項與 q 所指所指的項交換的項交換 為了表示操作方便，我們把該鏈表分兩段畫出。為了表示操作方便，我們把該鏈表分兩段畫出。p0p123.q0 q456.第32頁/共91頁p0:p:123.q0q:456. g:/*交換 p- next 、q- next */ g = p- next; /* 1 */ p- next = q- next; /* 2 */ q- next = g; /* 3 */ /

22、*交換 p0- next 、q0- next */ p0- next = q; /* 4 */ q0- next = p; /* 5 */*交換 p 、q */ p = p0- next ; /* 6 */ q = q0- next ; /* 7 */第33頁/共91頁n兩叉樹，兩叉樹的每個數(shù)據(jù)項附帶兩個指針，分別指向它的兩個兩叉樹，兩叉樹的每個數(shù)據(jù)項附帶兩個指針，分別指向它的兩個分支。兩叉樹的定義分支。兩叉樹的定義:n空是樹；空是樹；n一個結(jié)點連接兩個不相交的樹一個結(jié)點連接兩個不相交的樹,仍為樹；仍為樹； n所有結(jié)點具有相同的數(shù)據(jù)類型。所有結(jié)點具有相同的數(shù)據(jù)類型。*+-a/d*bcef( a

23、 + b / c ) * ( d e * f )第34頁/共91頁root: 設(shè) ti 為二叉樹的一個結(jié)點，一般 ti 由兩部分組成：l基本數(shù)據(jù)部分-保存本結(jié)點上的基本數(shù)據(jù)；l指針部分連-接本結(jié)點以下的其它結(jié)點。 結(jié)點 ti 的指針連接的結(jié)點稱為 ti 的子結(jié)點， 相應(yīng) ti 稱為其子結(jié)點的父結(jié)點。 ti的指針部分有兩個指針：左指針、右指針。 稱 ti 的左指針連接的部分為 ti 的左子樹， ti 的右指針連接的部分為 ti 的右子樹。 若左、右子樹均空，則稱 ti 為葉結(jié)點。ti第35頁/共91頁78563124ti:n為了檢索操作方便，一般把兩叉樹組織成兩叉檢為了檢索操作方便，一般把兩叉樹

24、組織成兩叉檢索樹。兩叉檢索樹的定義是：索樹。兩叉檢索樹的定義是：n設(shè)樹中每個結(jié)點的數(shù)據(jù)部分有一個設(shè)樹中每個結(jié)點的數(shù)據(jù)部分有一個數(shù)據(jù)項數(shù)據(jù)項 key 是有序的是有序的, 稱該數(shù)據(jù)項稱該數(shù)據(jù)項為關(guān)鍵字。為關(guān)鍵字。n一個兩叉樹稱為檢索樹，一個兩叉樹稱為檢索樹，n如果對每個結(jié)點如果對每個結(jié)點 ti ，它的左子樹中，它的左子樹中所有結(jié)點的所有結(jié)點的 key 值都小于值都小于 ti 的的 key 值；值；nti 的右子樹中所有結(jié)點的的右子樹中所有結(jié)點的 key 值都值都大于大于 ti 的的 key 值。值。第36頁/共91頁n二叉檢索樹的操作有二叉檢索樹的操作有:n遍歷遍歷n檢索檢索n插入一個結(jié)點插入一個

25、結(jié)點n刪除一個結(jié)點刪除一個結(jié)點 由于樹是遞歸定義的，所以樹的由于樹是遞歸定義的，所以樹的操作用遞歸算法十分簡潔。操作用遞歸算法十分簡潔。第37頁/共91頁 設(shè)有說明部分設(shè)有說明部分: typedef . keytype ； typedef . datatype ； typedef struct tree keytype key ； datatype data ； struct tree *left ； struct tree *right ； treetype; typedef treetype * treepointer ； treepointer root ；第38頁/共91頁n遍歷遍歷遍

26、歷二叉樹是指按一定規(guī)律走遍樹的每個結(jié)點，使每遍歷二叉樹是指按一定規(guī)律走遍樹的每個結(jié)點，使每一結(jié)點被訪問一次，而且只被訪問一次。在訪問一個一結(jié)點被訪問一次，而且只被訪問一次。在訪問一個結(jié)點時，可以做任何信息加工工作。下例打印結(jié)點的結(jié)點時，可以做任何信息加工工作。下例打印結(jié)點的data域，并設(shè)該域為域，并設(shè)該域為char型的。型的。n遍歷算法可分為前序，中序，后序遍歷三種。遍歷算法可分為前序，中序，后序遍歷三種。n前序遍歷前序遍歷：對任意一個結(jié)點：對任意一個結(jié)點 ti 來講，先訪問及處理來講，先訪問及處理該結(jié)點的數(shù)據(jù)域；然后遍歷左子樹；最后遍歷右子該結(jié)點的數(shù)據(jù)域；然后遍歷左子樹；最后遍歷右子樹。樹

27、。n中序遍歷中序遍歷：對任意一個結(jié)點：對任意一個結(jié)點 ti 來講，先遍歷左子樹；來講，先遍歷左子樹；然后訪問及處理該結(jié)點的數(shù)據(jù)域；最后遍歷右子樹。然后訪問及處理該結(jié)點的數(shù)據(jù)域；最后遍歷右子樹。n后序遍歷后序遍歷：對任意一個結(jié)點：對任意一個結(jié)點 ti 來講，先遍歷左子樹；來講，先遍歷左子樹；然后遍歷右子樹；最后訪問及處理該結(jié)點的數(shù)據(jù)域。然后遍歷右子樹；最后訪問及處理該結(jié)點的數(shù)據(jù)域。第39頁/共91頁 【例例12-1】設(shè)有下圖所示樹設(shè)有下圖所示樹,這是由表達(dá)式這是由表達(dá)式 (a+b/c)*(d-e*f) 生成生成的樹，這棵樹反映了表達(dá)式的結(jié)構(gòu)，同時也反映了表達(dá)式的運的樹，這棵樹反映了表達(dá)式的結(jié)構(gòu)，

28、同時也反映了表達(dá)式的運算次序。算次序。l 前序遍歷過程是：得到表達(dá)式的波蘭表示式（運算符在兩前序遍歷過程是：得到表達(dá)式的波蘭表示式（運算符在兩個運算分量前）。個運算分量前）。l前序遍歷算法是：前序遍歷算法是： void preorder (treepointer p) if ( p!=NULL ) printf(“%c” , p- data ) ; preorder( p- left ) ; preorder( p- right ) *+-a/d*bcefa/bc-d*ef第40頁/共91頁l中序遍歷過程是：中序遍歷過程是：得到表達(dá)式的原形式，只是沒有括號。得到表達(dá)式的原形式，只是沒有括號。中

29、序遍歷算法是：中序遍歷算法是： void inorder (treepointer p) /*中序遍歷中序遍歷*/ if ( p!=NULL ) inorder( p- left ) ; printf(“%c” , p- data ) ; inorder( p- right ) *+-a/d*bcefa/bc-d*ef第41頁/共91頁l后序遍歷過程是：后序遍歷過程是：得到表達(dá)式的表達(dá)式的逆波蘭表示式（運算符在兩個運算分量得到表達(dá)式的表達(dá)式的逆波蘭表示式（運算符在兩個運算分量之后）。之后）。后序遍歷算法是：后序遍歷算法是： void postorder (treepointer p) /*后序

30、遍歷后序遍歷*/ if ( p!=NULL ) postorder( p- left ) ; postorder( p- right ) printf(“%c” , p- data ) ; *+-a/d*bcefa/bc-d*ef第42頁/共91頁n檢索檢索檢索是按給定關(guān)鍵字值檢索是按給定關(guān)鍵字值 c 在樹上找一個結(jié)點在樹上找一個結(jié)點 ti ，且，且 ti 的的關(guān)鍵字值關(guān)鍵字值 key 恰好等于恰好等于 c 。若檢索到，函數(shù)將帶回相應(yīng)。若檢索到，函數(shù)將帶回相應(yīng)結(jié)點指針；否則若沒檢索到，函數(shù)將帶回結(jié)點指針；否則若沒檢索到，函數(shù)將帶回 NULL 。下述檢。下述檢索算法的前提條件是，索算法的前提條件

31、是，p 是檢索樹。是檢索樹。 treepointer search( typekey c , treepointer p ) if ( ( p- key = c ) | ( p = NULL ) ) return p ; else if ( c key ) return search( c , p- left ) ; else return search( c , p- right ) ; 第43頁/共91頁n插入一個結(jié)點插入一個結(jié)點插入是指將一個數(shù)據(jù)項插入到樹中某一恰當(dāng)位置，使樹插入是指將一個數(shù)據(jù)項插入到樹中某一恰當(dāng)位置，使樹仍保持檢索樹的性質(zhì)。顯然，首先要按仍保持檢索樹的性質(zhì)。顯然，首先要

32、按key值查出應(yīng)該值查出應(yīng)該插入的位置，然后再插入。插入的位置，然后再插入。 void insert( keytype c , datatype d , treepointer *p ) if ( *p = NULL ) *p = (treepointer)malloc(sizeof(struct tree); (*p) - key = c ; (*p) - data = d ; (*p) - left = NULL ; (*p) - right = NULL ; else if ( c key ) insert( c , d , &(*p)-left) ) ; else insert( c

33、, d , &(*p)-right) ) ; 第44頁/共91頁由于 insert 的參數(shù) p 是指向指針的指針類型，在 insert 內(nèi) p 指向指針類型的實在參數(shù)。所以在執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)時，將使實在參數(shù)指針變量指向新申請來的結(jié)點。第45頁/共91頁 1) 若調(diào)用 insert 時，如圖 root 為空樹。 以 &root 作實在參數(shù)調(diào)用 insert , 即 insert(c,d,&root) insert 的形式參數(shù) p 指向 root ，而 root 值為 NULL。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepoint

34、er)malloc(sizeof(struct tree) 得: 再執(zhí)行后邊的幾個賦值語句, 得: root: c ; d p:第46頁/共91頁 2) 若調(diào)用insert時，root非空，在中間某一個結(jié)點查到空指 針，如圖；設(shè)查到該結(jié)點后，應(yīng)該繼續(xù)向右查，以 &(*p)-right)作實在參數(shù)遞歸調(diào)用insert，即執(zhí)行 insert(c,d, &(*p)-right) )insert 的形式參數(shù) p 指向本步的 (*p)- right ，而 (*p)- right 值為 NULL。轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)再執(zhí)行后

35、邊的幾個賦值語句, 得: c ; d . p:第47頁/共91頁n刪除一結(jié)點設(shè)欲刪除結(jié)點為 r，則可能有如下幾種情況。針對不同情況刪除算法不同.r 是葉結(jié)點:簡單刪掉 r 結(jié)點，并把 r 的父結(jié)點連接處改成NULL 即可 。 42513r:第48頁/共91頁r 只有一個左子樹78563124r:78564231r:r 只有一個子樹: 把 r 以下部分接入 r 的父結(jié)點連接 r 處。然后刪掉r結(jié)點 。r 只有一個右子樹第49頁/共91頁r 兩個方向都有子樹: 在 r 的左子樹上找到關(guān)鍵字 key 值最大的結(jié)點 s，把 s 結(jié)點的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點上，然后刪除掉 s

36、結(jié)點。 9s:10r:4514151213312118679第50頁/共91頁當(dāng)然也可以在r的右子樹上找到關(guān)鍵字key值最小的結(jié)點s，把s結(jié)點的數(shù)據(jù)data及關(guān)鍵字key復(fù)制到r結(jié)點上，然后刪除掉s結(jié)點。8s:5r:410131411123129766第51頁/共91頁使用在左子樹上找最大結(jié)點的方法，按如下步驟進(jìn)行:沿 r 左子樹的右方向，向下找一個沒有右子樹的結(jié)點s ，圖中結(jié)點 (9) 。把該結(jié)點 s 的值復(fù)制到結(jié)點r（即欲刪除的結(jié)點。把 s 的左子樹連在 s 的父結(jié)點（圖中為結(jié)點(5) ）的右鏈上，在圖中即連到(5) 結(jié)點的右鏈上。刪除s結(jié)點，即圖中的(9)結(jié)點。 圖3的情況 r 兩個方向

37、都有子樹: 在 r 的左子樹上找到關(guān)鍵字 key 值最大的結(jié)點 s，把 s 結(jié)點的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點 上，然后刪除掉 s 結(jié)點。 9s:10r:4514151213312118679第52頁/共91頁綜合上述三種情況，下述函數(shù)deletenode 完成刪除一個結(jié)點。deletenode的調(diào)用形式是： deletenode( valueofkey , &root )其中l(wèi)value_of_key是欲刪除結(jié)點的關(guān)鍵字值；lroot是指針類型（treepointer）變量，指向樹根。這里用指向指針的指針作參數(shù)。第53頁/共91頁treepointer del( tree

38、pointer * , treepointer * )；/* 處理第三種處理第三種情況的函數(shù)的函數(shù)原型情況的函數(shù)的函數(shù)原型 */void deletenode( keytype c , treepointer *p ) /* 刪除關(guān)鍵字刪除關(guān)鍵字值等于值等于 c 的結(jié)點的結(jié)點 */ treepointer r; if ( *p = NULL ) printf( “not found:%dn” , c ); else if ( c key ) /* c left) ) ; else if ( c (*p) - key ) /* c 當(dāng)前結(jié)點的當(dāng)前結(jié)點的 key 值，被刪結(jié)點在右子樹上值，被刪結(jié)點

39、在右子樹上 */ deletenode( c , &(*p) - right ) ) ; 第54頁/共91頁 else r = *p ; if ( r-right = NULL ) *p = r- left /* 右子樹空，接左右子樹空，接左分支分支 */ else if ( r-left = NULL ) *p = r- right ; /* 左子樹空，接右左子樹空，接右分支分支 */ else r=del( &(r-left),p ) ; /* 左右均非空左右均非空 */ free( r ) ; /* 釋放釋放 r */ ;第55頁/共91頁45627138root:p:deletenod

40、e( 4 , &root )r:r 只有一個左子樹第56頁/共91頁treepointer del( treepointer *s, treepointer *p ) /* 處理第三種情況，僅第三種情況調(diào)用處理第三種情況，僅第三種情況調(diào)用 */ treepointer r;if (*s)-right != NULL ) /* 右分支非空右分支非空? */ r=del( &(*s)-right),p ) /右分支非空右分支非空, 在右方向以下繼續(xù)查找在右方向以下繼續(xù)查找 else /* 找到右分支為空的結(jié)點找到右分支為空的結(jié)點 *s */ (*p)-key =(*s)- key ; /* 復(fù)制復(fù)

41、制 *s的關(guān)鍵字、數(shù)據(jù)到的關(guān)鍵字、數(shù)據(jù)到 *p結(jié)點結(jié)點 */ (*p)-data =(*s)- data ; r = *s ; /* r記載該記載該 *s結(jié)點，為結(jié)點，為free做準(zhǔn)備做準(zhǔn)備 */ *s =(*s)- left ；/* 刪除刪除 *s所指結(jié)點。由于所指結(jié)點。由于s參數(shù)是指向指針的變量參數(shù)是指向指針的變量 */ /* 本語句把本語句把 *s 左分支接到左分支接到 *s 的父結(jié)點上，的父結(jié)點上，*/ /* 從而在樹上摘下了從而在樹上摘下了 *s 所指向的結(jié)點。所指向的結(jié)點。*/ return r; / 把將釋放的變量指針帶回主程序把將釋放的變量指針帶回主程序第57頁/共91頁123

42、459768101112131415p:s:9r:root:第58頁/共91頁圖圖G=(V，E)。其中。其中,lV=(v1 ,v2 , ,vn) 為圖為圖G的結(jié)點集的結(jié)點集合合 lvi為圖為圖G中結(jié)點中結(jié)點lE= (vi , vj ) |vi, vjV 是圖中邊的是圖中邊的集合集合l(vi ,vj)表示連接結(jié)點表示連接結(jié)點vi到結(jié)點到結(jié)點vj的邊。的邊。04316752第59頁/共91頁(一一) 鄰接表方法鄰接表方法 設(shè)設(shè)圖圖G有有k個結(jié)點，使用一個個結(jié)點，使用一個k*k的的int型矩陣型矩陣g表示表示圖圖G, 矩陣矩陣g的第的第i行順序列出與結(jié)點行順序列出與結(jié)點i直接相連的結(jié)點編號直接相連的

43、結(jié)點編號, 最后以最后以“-1”結(jié)尾。則結(jié)尾。則圖圖G表示成右圖的鄰接表。表示成右圖的鄰接表。04316752012-11034-12045-1314-1412367-15267-1645-1745-1第60頁/共91頁(二二) 鄰接矩陣方法鄰接矩陣方法 設(shè)設(shè)圖圖G有有k個結(jié)點，使用一個個結(jié)點，使用一個k*k的的bool類型矩陣類型矩陣g表示表示圖圖G 矩陣元素矩陣元素 利用這種表示法，左圖的網(wǎng)表示成右圖利用這種表示法，左圖的網(wǎng)表示成右圖 8*8 的的 bool 矩陣。矩陣。gij,=true i j false i j 表示從結(jié)點到結(jié)點有直接路；表示從結(jié)點到結(jié)點沒有直接路；012345670

44、tt1ttt2ttt3tt4ttttt5ttt6tt7tt04316752第61頁/共91頁 (三三) 鄰接鏈表方法鄰接鏈表方法 設(shè)圖設(shè)圖G中有中有k個結(jié)點，使用一個有個結(jié)點，使用一個有k個元素的一維指針數(shù)組個元素的一維指針數(shù)組G , 數(shù)組數(shù)組G的第的第i個元素對應(yīng)網(wǎng)中第個元素對應(yīng)網(wǎng)中第i個結(jié)點。以它為鏈?zhǔn)讉€結(jié)點。以它為鏈?zhǔn)? 把與結(jié)點把與結(jié)點i直接相連的結(jié)點鏈成一個鏈。圖直接相連的結(jié)點鏈成一個鏈。圖G表示成右圖的鄰接鏈表表示成右圖的鄰接鏈表 :04316752 4 5 . 1 2 . 1 4 0 3 4 . 0 4 5 . 2 6 7 . 1 2 3 6 7 . 4 5 . 7 6 5 4

45、3 2 1 0第62頁/共91頁已知一個網(wǎng)已知一個網(wǎng)g=(v,e)。其中。其中,l v=(v1 ,v2 , ,vn) 為網(wǎng)為網(wǎng)g的結(jié)點集合的結(jié)點集合, l vi為網(wǎng)中結(jié)點。為網(wǎng)中結(jié)點。l e= (vi , vj) 是網(wǎng)中邊的集合是網(wǎng)中邊的集合,l (vi ,vj)表示連接結(jié)點表示連接結(jié)點vi到結(jié)點到結(jié)點vj的邊。的邊。找路徑是指求從結(jié)點找路徑是指求從結(jié)點m到結(jié)點到結(jié)點n的所有路徑。的所有路徑。04316752第63頁/共91頁解解:這樣想該問題這樣想該問題, 1.從從m點出發(fā)沿所有可能的路向前走一步點出發(fā)沿所有可能的路向前走一步; 2.然后再站在新的點上，再向前走一步然后再站在新的點上，再向前

46、走一步; . 如此重復(fù)，直到走到結(jié)點如此重復(fù)，直到走到結(jié)點n為止。為止。 在走的過程中，保證不走重復(fù)點，可以得到下圖的算法在走的過程中，保證不走重復(fù)點，可以得到下圖的算法:m=n輸出p0rm點的所有后繼結(jié)點 iip0rpr = mroute(i,n,r+1)route m:開始點；n:終結(jié)點； r:路跡數(shù)組p尾標(biāo)結(jié)束第64頁/共91頁在該算法中，關(guān)鍵在于找出在該算法中，關(guān)鍵在于找出m點的所有后繼點。點的所有后繼點。 (一一) 鄰接鏈表方法鄰接鏈表方法 04316752 4 5 1 2 1 4 0 3 4 0 4 5 2 6 7 1 2 3 6 7 4 5 7 6 5 4 3 2 1 0第65頁

47、/共91頁設(shè)有如下聲明：#define h 10struct node int no; struct node *link; ;int ph ; /* 路跡數(shù)組 */struct node *gh ; /* 網(wǎng)的鄰接鏈表 */void printp( int,int )； / 函數(shù)原型：輸出bool iinp( int,int,int ) ; / 函數(shù)原型：判斷 /點i是否已經(jīng)走過（在P中）第66頁/共91頁void route ( int m, int n, int r ) / 開始結(jié)點、終結(jié)結(jié)點、路跡數(shù)組開始結(jié)點、終結(jié)結(jié)點、路跡數(shù)組p的尾的尾 struct node *hh; int i;

48、 pr=m; if ( m=n ) printp(0,r); else hh = gm; while ( hh!=NULL ) i = hh-no; if ( !iinp(i,0,r) ) route(i,n,r+1); hh = hh-link; 第67頁/共91頁bool iinp( int ii,int u,int v ) int j; for ( j=u; j=v; j+ ) if ( ii=pj ) return true; return false ;void printp( int e,int f ) int j; for (j=e; jnext結(jié)束return base使bas

49、ep遞增尋找p應(yīng)該插入的位置r0,rp插入到r0、r之間結(jié)束第72頁/共91頁p插入到r0、r之間結(jié)束defrp把p獨立出來=q ;p指向p0插入到r0,r之間:q-next = r ; r0-next = q插入到鏈頭:q-next = base ; base = qr = base尋找位置r = base r-keykey r!=pr0 = r;r = r-next 結(jié)束def第73頁/共91頁考查程序運行中各個參數(shù)、變量、鏈表的變化狀態(tài)。如圖所示：考查程序運行中各個參數(shù)、變量、鏈表的變化狀態(tài)。如圖所示：設(shè)從設(shè)從base到到p0之間的子鏈表已經(jīng)遞增，現(xiàn)在加入之間的子鏈表已經(jīng)遞增，現(xiàn)在加入p

50、所指示的節(jié)；所指示的節(jié)；在在basep0之間查找合適位置，設(shè)應(yīng)該把之間查找合適位置，設(shè)應(yīng)該把p所指的節(jié)插入到所指的節(jié)插入到r0,r所之間；所之間；把把p獨立出來獨立出來=q ， p指向指向p0： q = p ; p0-next = p-next ; p = p0 ;把把p（現(xiàn)在由（現(xiàn)在由q指示）插入到指示）插入到r0,r之間：之間： q-next = r ; r0-next = q；現(xiàn)在鏈表結(jié)構(gòu)是：現(xiàn)在鏈表結(jié)構(gòu)是：datakeydatakey.datakeydatakeybase:datakeydatakeydatakeydatakeyr0:r:p:p0:q:第74頁/共91頁pt sort(

51、 pt base ) /* 鏈表排序，鏈表排序，base 為鏈?zhǔn)诪殒準(zhǔn)?*/ pt p , p0 , r , r0 , q ; p0 = NULL ; p = base ; while ( p!=NULL ) /* 逐項處理，把逐項處理，把p加入到子序列中，并保持加入到子序列中，并保持“base-p”遞增遞增 */ r = base ; /* 尋找位置尋找位置 */ while ( ( r-key key ) & ( r!=p ) ) r0 = r ; r = r- next ; if (r!=p) /* p插入到插入到r0、r之間之間 */ /* 若若 r=p ，在鏈尾，則不用插入，在鏈尾，

52、則不用插入 */ q = p ; /* 把把 p 獨立出來，令獨立出來，令 q 指向它指向它 */ p0-next = p-next ; p = p0 ; if ( r = base ) /* 插入插入 */ /* 插在鏈?zhǔn)撞逶阪準(zhǔn)?*/ q-next = base ; base = q ; else /* 插在鏈中插在鏈中r0 、r之間之間 */ q-next = r ; r0 - next = q ; p0 = p ; /* 前進(jìn)一項前進(jìn)一項 */ p = p-next ; return base ; /* sort */ 第75頁/共91頁 對任意給定的自然數(shù)對任意給定的自然數(shù) n ，把

53、所有如下形式的不可約分?jǐn)?shù)，把所有如下形式的不可約分?jǐn)?shù) 按遞增順序排列起來，稱該序列為按遞增順序排列起來，稱該序列為 n 級法雷序列級法雷序列 Fn 。 例如例如F8 為為: 編函數(shù)，對任意給定的正整數(shù)編函數(shù)，對任意給定的正整數(shù)n ，求，求n級法雷序列，并帶回級法雷序列，并帶回n級法雷序列鏈指針。級法雷序列鏈指針。 ( 0in ; 0ji )ji=0 1 1 1 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 5 6 7 1,1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1例例12-3 法雷序列法雷序列第76頁/共91頁分析：分析： 法雷序列

54、的每項是個分?jǐn)?shù)，不能用實數(shù)精確的表示，而且這法雷序列的每項是個分?jǐn)?shù)，不能用實數(shù)精確的表示，而且這些數(shù)的排列順序是不規(guī)則的。用下圖形式的鏈表來表示它。些數(shù)的排列順序是不規(guī)則的。用下圖形式的鏈表來表示它。 分子分母分子分母分子分母分子分母.第77頁/共91頁顯然法雷序列的各項均在區(qū)間0/1,1/1之內(nèi)。生成法雷序列算法l先把一階法雷序列：0/1,1/1放入鏈表中；l然后順序分別以i=2,3, . ,n 作分母，對任意i以j=1,2, . , i-1作 分子，作成分?jǐn)?shù)j/i；l若j/i是不可約分?jǐn)?shù)，則該j/i必然是法雷序列的一項；把該j/i插入到鏈表的合適位置上，并使鏈表仍保持按遞增排序。0/1 ,

55、 1/1 放入序列讀入 n生成 n 階法雷序列鏈表結(jié)束 for(i=2; i=n; i+) for(j=1; ji; j+)把 j/i 放入序列j/i 不可約分把 j/i 插入到 r0,r 之間查 j/i 應(yīng)插入的位置 r0,r第78頁/共91頁 struct farlei_item int numerator , denominator ; struct farlei_item *next ;typedef struct farlei_item * farleipointer ;int gcd( int x , int y ) /* 求最大公約數(shù)求最大公約數(shù) */ if ( y=0 ) return x ; else return gcd( y , x % y ) ;第79頁/共91頁/*構(gòu)造法雷序列,并返回序列頭指針*/farleipointer farlei(int n) int i,j ; farleipointer fn , r , r0 , p ; if( n1 ) /如果nnumerator = 0 ; fn-denominator = 1 ; fn-next = (farleipointer) m