動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)教學(xué).ppt

第十二章 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),管理動(dòng)態(tài)變量 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 棧 stack 隊(duì)列 queue 鏈表linkage table 樹tree 圖 graph 程序設(shè)計(jì)實(shí)例 本章小結(jié) 作業(yè),考慮上一章的職工卡片問題，用計(jì)算機(jī)管理這些卡片, 要把卡片保存在計(jì)算機(jī)內(nèi)。 首先，用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)：一張卡片是一個(gè)結(jié)構(gòu)體，所有卡片自然用結(jié)構(gòu)體數(shù)組。 第三，操作問題： 若增加一個(gè)人，應(yīng)該在數(shù)組中加一個(gè)元素，會(huì)產(chǎn)生數(shù)組不夠大的可能。 若增加一張卡片在數(shù)組中間，應(yīng)該把加入位置以后的其它元素依次向后移動(dòng)。 若在中間刪除一張卡片，會(huì)在數(shù)組中間留下一個(gè)“洞”，應(yīng)該把“洞”以后的元素依次向前移動(dòng),使用數(shù)組帶來的問題是： 操作不方便； 數(shù)組尺寸不好確定。 第二，數(shù)組多大：為保存全部卡片，并且人數(shù)不固定，就應(yīng)該給一個(gè)足夠大的數(shù)組。 最好把這些卡片存儲(chǔ)成動(dòng)態(tài)的， 需要多大存儲(chǔ)量（有多少張卡片）就用多大。 中間加一張卡片時(shí)不要向后串別的卡片， 刪除一張卡片時(shí)不要留下“洞”。,如圖的鏈?zhǔn)浇Y(jié)構(gòu)可以滿足要求: 當(dāng)增加一張卡片時(shí)，只需要向計(jì)算機(jī)系統(tǒng)申請一塊空間，聯(lián)到鏈的適當(dāng)位置上。例如，要增加一張卡片 50 插入到 2 、3 之間，則只需要如下修改指針： 若刪除一節(jié)，只需要將其從鏈上摘下來即可。例刪除2節(jié)得 鏈上已經(jīng)沒有2節(jié)了，刪掉的節(jié)所占的存儲(chǔ)空間還可以還回計(jì)算機(jī)系統(tǒng)，以便作其它用途。,這就是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的鏈表。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)上的一項(xiàng)是一個(gè)動(dòng)態(tài)變量，指針是標(biāo)識(shí)動(dòng)態(tài)變量的有力手段。動(dòng)態(tài)變量與靜態(tài)變量的區(qū)別在于: 靜態(tài)變量是程序中由程序員“顯式”說明的變量。它有一個(gè)名字，在編譯時(shí)，編譯程序已經(jīng)給它分配存儲(chǔ)空間。這塊存儲(chǔ)空間用變量的名字來標(biāo)識(shí)。,動(dòng)態(tài)變量在程序中沒有“顯式”說明，它沒有名字 在編譯時(shí)編譯程序不知道有該變量，不給（也不可能給）它分配空間。 動(dòng)態(tài)變量是在程序運(yùn)行時(shí) 隨程序存儲(chǔ)數(shù)據(jù)的需要，申請空間函數(shù)（例如malloc，當(dāng)然也是由程序員安排的）隨機(jī)的動(dòng)態(tài)的申請來的空間。它沒有名字，一般動(dòng)態(tài)變量都由指針標(biāo)識(shí)。 當(dāng)使用完畢后，由釋放空間函數(shù)（例如free）釋放，還回計(jì)算機(jī)存儲(chǔ)管理系統(tǒng)，以備它用。,注意：這里所說的靜態(tài)變量不是C語言中由靜態(tài)存儲(chǔ)類別static聲明的變量；動(dòng)態(tài)變量也不是C語言中由自動(dòng)存儲(chǔ)類別auto聲明的變量。而是一般程序設(shè)計(jì)概念中的靜態(tài)變量、動(dòng)態(tài)變量,管理動(dòng)態(tài)變量,動(dòng)態(tài)變量在程序運(yùn)行時(shí)，隨程序存儲(chǔ)數(shù)據(jù)的需要，向計(jì)算機(jī)系統(tǒng)申請；使用完后還回計(jì)算機(jī)系統(tǒng)。 本節(jié)介紹 申請計(jì)算機(jī)存儲(chǔ)空間函數(shù)malloc 釋放存儲(chǔ)空間函數(shù)free,內(nèi)存 程序運(yùn)行時(shí)，涉及用戶程序的內(nèi)存存儲(chǔ)結(jié)構(gòu)如右圖所示，首先是目標(biāo)代碼區(qū)；然后是靜態(tài)存儲(chǔ)區(qū)，用于存放那些可用絕對(duì)地址標(biāo)識(shí)的，主要是具有靜態(tài)存儲(chǔ)類別的數(shù)據(jù)和變量；接著是目標(biāo)代碼運(yùn)行時(shí)用到的庫程序代碼區(qū)；最后剩余空間是棧區(qū)和堆區(qū)，棧區(qū)和堆區(qū)從剩余空間的兩端，動(dòng)態(tài)的向中間增長。棧區(qū)用來存儲(chǔ)程序中聲明的函數(shù)的局部變量等具有自動(dòng)存儲(chǔ)類別的數(shù)據(jù)和變量；堆區(qū)用來存儲(chǔ)經(jīng)過動(dòng)態(tài)申請空間函數(shù)申請的變量。,sizeof 運(yùn)算符 單目運(yùn)算符 sizeof 的 操作數(shù)是類型。 運(yùn)算結(jié)果是求得相應(yīng)類型的尺寸，即存儲(chǔ)相應(yīng)類型數(shù)據(jù)所需要的字節(jié)數(shù)。 sizeof(int) /* 結(jié)果是2 */ sizeof(char) /* 結(jié)果是1 */ sizeof(struct date) /* 若 struct date 是第十一章定義的日期類型，結(jié)果是6 */,malloc 函數(shù): 原型 void *malloc(unsigned long size); 功能 申請足夠大內(nèi)存區(qū)域用來存儲(chǔ)長度為size的數(shù)據(jù)對(duì)象，返回該區(qū)域的首指針，并保證該區(qū)域符合任何數(shù)據(jù)類型對(duì)存儲(chǔ)區(qū)域開始地址和對(duì)齊的要求。 返回指針是void類型的，調(diào)用者必須使用顯示強(qiáng)制類型轉(zhuǎn)換，把該指針轉(zhuǎn)換成所需要類型的指針。,例: float *p ; p = (float*)malloc( sizeof(float) ); struct date *pdate; pdate=(struct date*)malloc(sizeof(struct date);,free函數(shù) 動(dòng)態(tài)申請的內(nèi)存如果不再使用，應(yīng)當(dāng)適時(shí)釋放這樣可以提高程序運(yùn)行效率。free函數(shù)用來釋放經(jīng)過malloc申請的動(dòng)態(tài)空間。free的函數(shù) 原型 void free ( void *ptr ) ; 功能 釋放由malloc申請的內(nèi)存區(qū)域。free的參數(shù)ptr是一個(gè)指針，指向以前由malloc申請的一個(gè)內(nèi)存區(qū)域。,例 申請 float *p ; p = (float*)malloc( sizeof(float) ); struct date *pdate; pdate=(struct date*)malloc(sizeof(struct date); 釋放 free(p); free(pdate);,free(ptr) /* 釋放ptr所指向由malloc申請的內(nèi)存空間 */ 一塊存儲(chǔ)區(qū)域一經(jīng)釋放，便不能再使用。使用free特別注意，操作不當(dāng)會(huì)產(chǎn)生不可預(yù)料的結(jié)果。如下情況下使用free都會(huì)造成災(zāi)難性后果。 ptr無值； ptr的值為NULL； ptr所指向的空間不是經(jīng)過malloc申請來的； 對(duì)一次申請的存儲(chǔ)區(qū)進(jìn)行多次釋放（實(shí)際可能是ptr無值或值為NULL）。,實(shí)用問題: 若指針變量指向的用malloc申請來的動(dòng)態(tài)變量，是孤立的不能與其它變量相聯(lián)系，顯然作用不大。 引進(jìn)動(dòng)態(tài)變量的目的是構(gòu)造動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。 例如象本章開始介紹的那樣，構(gòu)造一個(gè)鏈表等。 這就要求一個(gè)數(shù)據(jù)項(xiàng)上除基本的數(shù)據(jù)信息外，還應(yīng)包含與其它數(shù)據(jù)項(xiàng)相聯(lián)系的信息，也就是包含指針。 該結(jié)構(gòu)必須用結(jié)構(gòu)體類型描述，鏈表上一節(jié)的類型定義形式。,棧 stack,在第六章已經(jīng)用數(shù)組實(shí)現(xiàn)過棧和隊(duì)列，但是，數(shù)組有一定的局限性。如圖可以用單向鏈表實(shí)現(xiàn)棧，指針變量top指向棧頂。棧的操作有: 初始化：stackintial 壓棧：stackpush 彈棧：stackpop,設(shè)有聲明: typedef . items ; typedef struct stackcell items data ; struct stackcell *predocessor ; stackcelltype ; typedef stackcelltype *pstacktype ; pstacktype top ;,如下實(shí)現(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 ) *x = top-data ; p = top ; top = top-predecessor ; free(p); else printf( “棧下溢n” ); ,看一下這三個(gè)操作: 初始化后(調(diào)用stackinitail)得。 調(diào)用一次 stackpush(1) 得。 再調(diào)用一次stackpush(2)得 。 調(diào)用一次stackpop(&b)得 。,2,隊(duì)列,如圖可用單向鏈表實(shí)現(xiàn)隊(duì)列，現(xiàn)在要用兩個(gè)指針變量，一個(gè)指向隊(duì)頭（front），一個(gè)指向隊(duì)尾（rear）。隊(duì)列的操作有 初始化（ queueinitial ） 進(jìn)隊(duì)排在隊(duì)尾（inqueue） 出隊(duì)從隊(duì)頭刪一項(xiàng)（outqueue）,設(shè)有如下說明: typedef . items ; typedef struct queue items data struct queue *next ; queuetype ; typedef queuetype *pqueuetype ; pqueuetype front,rear ; 操作： void queueinital(void) front = NULL ; rear = NULL ; ,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 ; ,void outgueue ( item *x ) pqueuetype p; if ( front=NULL ) printf( “隊(duì)空n” ); else *x = front- data ; p = front ; front = front- next; if ( front=NULL ) rear = NULL ; free( p ) ; ,看一下這三個(gè)操作: 1. 調(diào)用初始化后（調(diào)用一次 queueinitail） 得； 2. 調(diào)用一次ingueue(1)得； 再調(diào)用一次ingueue(2)得； 再調(diào)用一次 ingueue(3)得 ; 3. 調(diào)用一次 outgueue( 再調(diào)用一次 outgueue(&a) 得 。,1,2,3,NULL,NULL,鏈表linkage table,實(shí)際上前邊講的棧，隊(duì)列都是單向鏈表，但是棧和隊(duì)列只是單向鏈表的兩種特殊應(yīng)用操作只在頭尾進(jìn)行。下邊介紹單向鏈表的一般操作: 創(chuàng)建單向鏈表: 創(chuàng)建單向鏈表，是指用一項(xiàng)一項(xiàng)的數(shù)據(jù)逐步建立、形成一個(gè)鏈表?？梢苑殖上蜴滎^加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。 創(chuàng)建單向鏈表可以分成向鏈頭加入數(shù)據(jù)和向鏈尾加入數(shù)據(jù)兩種方式。新項(xiàng)加入鏈頭就是壓棧的算法；新項(xiàng)加入鏈尾就是隊(duì)列中入隊(duì)的算法。只要反復(fù)調(diào)用那里的函數(shù)或?qū)⒑瘮?shù)體放在循環(huán)語句中即可，這里不贅述。,遍歷單向鏈表: 遍歷是指從頭到尾將鏈表上數(shù)據(jù)全部加工一遍?？捎萌缦伦蠖说乃惴ā５珜?shí)用中，經(jīng)常用如下右端 的算法來遍歷單向鏈表。,p = base ; p0 = NULL; while (p != NULL ) p = base ; 加工 p - while (p != NULL ) p = p- next; 加工 p - p0 = p ; p = p- next; ,在單向鏈表上檢索: 檢索是指在單向鏈表上查找關(guān)鍵字等于某給定值的節(jié)點(diǎn), 若找到則帶回相應(yīng)節(jié)點(diǎn)的指針；否則帶回NULL 。設(shè)關(guān)鍵字域域名為key ；欲檢索的關(guān)鍵字值為key0 . 如下算法實(shí)現(xiàn)檢索： p0 = NULL; p = base ; while (p != NULL ,向單向鏈表插入一項(xiàng): 設(shè)有下圖的鏈表，現(xiàn)在要把r所指示的數(shù)據(jù)項(xiàng)插入到 p0、p 所指兩項(xiàng)之間。操作是: r- next = p ; p0- next = r ; p0 = r /* 使 p0 仍為 p 的前一項(xiàng) */,p0:,p:,1,2,3,4,.,.,從單向鏈表上刪除一項(xiàng): 設(shè)有下圖的鏈表，現(xiàn)在要?jiǎng)h除p所指項(xiàng)。刪除算法是： q = p ; p = p- next ; p0- next = p ; free(q),p0:,1,2,4,.,.,p:,交換單向鏈表上兩項(xiàng): 設(shè)有如圖所示鏈表?，F(xiàn)在要把 p 所指的項(xiàng)與 q 所指的項(xiàng)交換 為了表示操作方便，我們把該鏈表分兩段畫出。,/*交換 p- next 、q- next */ g = p- next; /* 1 */ p- next = q- next; /* 2 */ q- next = g; /* 3 */ /*交換 p0- next 、q0- next */ p0- next = q; /* 4 */ q0- next = p; /* 5 */ /*交換 p 、q */ p = p0- next ; /* 6 */ q = q0- next ; /* 7 */,樹tree,兩叉樹，兩叉樹的每個(gè)數(shù)據(jù)項(xiàng)附帶兩個(gè)指針，分別指向它的兩個(gè)分支。兩叉樹的定義: 空是樹； 一個(gè)結(jié)點(diǎn)連接兩個(gè)不相交的樹,仍為樹； 所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。,( a + b / c ) * ( d e * f ),設(shè) ti 為二叉樹的一個(gè)結(jié)點(diǎn)，一般 ti 由兩部分組成： 基本數(shù)據(jù)部分-保存本結(jié)點(diǎn)上的基本數(shù)據(jù)； 指針部分連-接本結(jié)點(diǎn)以下的其它結(jié)點(diǎn)。 結(jié)點(diǎn) ti 的指針連接的結(jié)點(diǎn)稱為 ti 的子結(jié)點(diǎn)， 相應(yīng) ti 稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)。,ti的指針部分有兩個(gè)指針：左指針、右指針。 稱 ti 的左指針連接的部分為 ti 的左子樹， ti 的右指針連接的部分為 ti 的右子樹。 若左、右子樹均空，則稱 ti 為葉結(jié)點(diǎn)。,ti,為了檢索操作方便，一般把兩叉樹組織成兩叉檢索樹。兩叉檢索樹的定義是： 設(shè)樹中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分有一個(gè)數(shù)據(jù)項(xiàng) key 是有序的, 稱該數(shù)據(jù)項(xiàng)為關(guān)鍵字。 一個(gè)兩叉樹稱為檢索樹， 如果對(duì)每個(gè)結(jié)點(diǎn) ti ，它的左子樹中所有結(jié)點(diǎn)的 key 值都小于 ti 的 key 值； ti 的右子樹中所有結(jié)點(diǎn)的 key 值都大于 ti 的 key 值。,二叉檢索樹的操作有: 遍歷 檢索 插入一個(gè)結(jié)點(diǎn) 刪除一個(gè)結(jié)點(diǎn) 由于樹是遞歸定義的，所以樹的操作用遞歸算法十分簡潔。,設(shè)有說明部分: typedef . keytype ； typedef . datatype ； typedef struct tree keytype key ； datatype data ； struct tree *left ； struct tree *right ； treetype; typedef treetype * treepointer ； treepointer root ；,遍歷 遍歷二叉樹是指按一定規(guī)律走遍樹的每個(gè)結(jié)點(diǎn)，使每一結(jié)點(diǎn)被訪問一次，而且只被訪問一次。在訪問一個(gè)結(jié)點(diǎn)時(shí)，可以做任何信息加工工作。下例打印結(jié)點(diǎn)的data域，并設(shè)該域?yàn)閏har型的。 遍歷算法可分為前序，中序，后序遍歷三種。 前序遍歷：對(duì)任意一個(gè)結(jié)點(diǎn) ti 來講，先訪問及處理該結(jié)點(diǎn)的數(shù)據(jù)域；然后遍歷左子樹；最后遍歷右子樹。 中序遍歷：對(duì)任意一個(gè)結(jié)點(diǎn) ti 來講，先遍歷左子樹；然后訪問及處理該結(jié)點(diǎn)的數(shù)據(jù)域；最后遍歷右子樹。 后序遍歷：對(duì)任意一個(gè)結(jié)點(diǎn) ti 來講，先遍歷左子樹；然后遍歷右子樹；最后訪問及處理該結(jié)點(diǎn)的數(shù)據(jù)域。,【例12-1】設(shè)有下圖所示樹,這是由表達(dá)式 (a+b/c)*(d-e*f) 生成的樹，這棵樹反映了表達(dá)式的結(jié)構(gòu)，同時(shí)也反映了表達(dá)式的運(yùn)算次序。 前序遍歷過程是：得到表達(dá)式的波蘭表示式（運(yùn)算符在兩個(gè)運(yùn)算分量前）。 前序遍歷算法是： void preorder (treepointer p) if ( p!=NULL ) printf(“%c” , p- data ) ; preorder( p- left ) ; preorder( p- right ) ,a,/,b,c,-,d,*,e,f,中序遍歷過程是： 得到表達(dá)式的原形式，只是沒有括號(hào)。 中序遍歷算法是： void inorder (treepointer p) /*中序遍歷*/ if ( p!=NULL ) inorder( p- left ) ; printf(“%c” , p- data ) ; inorder( p- right ) ,a,/,b,c,-,d,*,e,f,后序遍歷過程是： 得到表達(dá)式的表達(dá)式的逆波蘭表示式（運(yùn)算符在兩個(gè)運(yùn)算分量之后）。 后序遍歷算法是： void postorder (treepointer p) /*后序遍歷*/ if ( p!=NULL ) postorder( p- left ) ; postorder( p- right ) printf(“%c” , p- data ) ; ,a,/,b,c,-,d,*,e,f,檢索 檢索是按給定關(guān)鍵字值 c 在樹上找一個(gè)結(jié)點(diǎn) ti ，且 ti 的關(guān)鍵字值 key 恰好等于 c 。若檢索到，函數(shù)將帶回相應(yīng)結(jié)點(diǎn)指針；否則若沒檢索到，函數(shù)將帶回 NULL 。下述檢索算法的前提條件是，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 ) ; ,插入一個(gè)結(jié)點(diǎn) 插入是指將一個(gè)數(shù)據(jù)項(xiàng)插入到樹中某一恰當(dāng)位置，使樹仍保持檢索樹的性質(zhì)。顯然，首先要按key值查出應(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 , ,由于 insert 的參數(shù) p 是指向指針的指針類型，在 insert 內(nèi) p 指向指針類型的實(shí)在參數(shù)。所以在執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree) 時(shí)，將使實(shí)在參數(shù)指針變量指向新申請來的結(jié)點(diǎn)。,1) 若調(diào)用 insert 時(shí)，如圖 root 為空樹。 以 &root 作實(shí)在參數(shù)調(diào)用 insert , 即 insert(c,d,&root) insert 的形式參數(shù) p 指向 root ，而 root 值為 NULL。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree) 得: 再執(zhí)行后邊的幾個(gè)賦值語句, 得:,c ; d ,2) 若調(diào)用insert時(shí)，root非空，在中間某一個(gè)結(jié)點(diǎn)查到空指 針，如圖；設(shè)查到該結(jié)點(diǎn)后，應(yīng)該繼續(xù)向右查，以 &(*p)-right) 作實(shí)在參數(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í)行后邊的幾個(gè)賦值語句, 得:,c ; d ,刪除一結(jié)點(diǎn) 設(shè)欲刪除結(jié)點(diǎn)為 r，則可能有如下幾種情況。針對(duì)不同情況刪除算法不同. r 是葉結(jié)點(diǎn):簡單刪掉 r 結(jié)點(diǎn)，并把 r 的父結(jié)點(diǎn)連接處改成NULL 即可 。,r:,r 只有一個(gè)左子樹,r 只有一個(gè)子樹: 把 r 以下部分接入 r 的父結(jié)點(diǎn)連接 r 處。 然后刪掉r結(jié)點(diǎn) 。,r 只有一個(gè)右子樹,r 兩個(gè)方向都有子樹: 在 r 的左子樹上找到關(guān)鍵字 key 值最大的結(jié)點(diǎn) s，把 s 結(jié)點(diǎn)的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點(diǎn)上，然后刪除掉 s 結(jié)點(diǎn)。,10,r:,9,當(dāng)然也可以在r的右子樹上找到關(guān)鍵字key值最小的結(jié)點(diǎn)s，把s結(jié)點(diǎn)的數(shù)據(jù)data及關(guān)鍵字key復(fù)制到r結(jié)點(diǎn)上，然后刪除掉s結(jié)點(diǎn)。,s:,5,r:,6,使用在左子樹上找最大結(jié)點(diǎn)的方法，按如下步驟進(jìn)行: 沿 r 左子樹的右方向，向下找一個(gè)沒有 右子樹的結(jié)點(diǎn)s ，圖中結(jié)點(diǎn) (9) 。 把該結(jié)點(diǎn) s 的值復(fù)制到結(jié)點(diǎn)r（即欲刪除 的結(jié)點(diǎn)。 把 s 的左子樹連在 s 的父結(jié)點(diǎn)（圖中為 結(jié)點(diǎn)(5) ）的右鏈上，在圖中即連到(5) 結(jié)點(diǎn)的右鏈上。 刪除s結(jié)點(diǎn)，即圖中的(9)結(jié)點(diǎn)。,圖3的情況 r 兩個(gè)方向都有子樹: 在 r 的左子樹上找到關(guān)鍵字 key 值最大的結(jié)點(diǎn) s，把 s 結(jié)點(diǎn)的數(shù)據(jù) data及關(guān)鍵字 key 復(fù)制到 r 結(jié)點(diǎn) 上，然后刪除掉 s 結(jié)點(diǎn)。,10,r:,9,綜合上述三種情況，下述函數(shù)deletenode 完成刪除一個(gè)結(jié)點(diǎn)。deletenode的調(diào)用形式是： deletenode( valueofkey , &root ) 其中 value_of_key是欲刪除結(jié)點(diǎn)的關(guān)鍵字值； root是指針類型（treepointer）變量，指向樹根。這里 用指向指針的指針作參數(shù)。,treepointer del( treepointer * , treepointer * )；/* 處理第三種情況的函數(shù)的函數(shù)原型 */ void deletenode( keytype c , treepointer *p ) /* 刪除關(guān)鍵字值等于 c 的結(jié)點(diǎn) */ 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é)點(diǎn)的 key 值，被刪結(jié)點(diǎn)在右子樹上 */ deletenode( c , ,else r = *p ; if ( r-right = NULL ) *p = r- left /* 右子樹空，接左分支 */ else if ( r-left = NULL ) *p = r- right ; /* 左子樹空，接右分支 */ else r=del( ,root:,p:,deletenode( 4 , &root ),r 只有一個(gè)左子樹,treepointer del( treepointer *s, treepointer *p ) /* 處理第三種情況，僅第三種情況調(diào)用 */ treepointer r; if (*s)-right != NULL ) /* 右分支非空? */ r=del( / 把將釋放的變量指針帶回主程序 ,p:,s:,9,root:,圖G=(V，E)。其中, V=(v1 ,v2 , ,vn) 為圖G的結(jié)點(diǎn)集合 vi為圖G中結(jié)點(diǎn) E= (vi , vj ) |vi, vjV 是圖中邊的集合 (vi ,vj)表示連接結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的邊。,圖graph,(一) 鄰接表方法 設(shè)圖G有k個(gè)結(jié)點(diǎn)，使用一個(gè)k*k的int型矩陣g表示圖G, 矩陣g的第i行順序列出與結(jié)點(diǎn)i直接相連的結(jié)點(diǎn)編號(hào), 最后以“-1”結(jié)尾。則圖G表示成右圖的鄰接表。,(二) 鄰接矩陣方法 設(shè)圖G有k個(gè)結(jié)點(diǎn)，使用一個(gè)k*k的bool類型矩陣g表示圖G 矩陣元素 利用這種表示法，左圖的網(wǎng)表示成右圖 8*8 的 bool 矩陣。,(三) 鄰接鏈表方法 設(shè)圖G中有k個(gè)結(jié)點(diǎn)，使用一個(gè)有k個(gè)元素的一維指針數(shù)組G , 數(shù)組G的第i個(gè)元素對(duì)應(yīng)網(wǎng)中第i個(gè)結(jié)點(diǎn)。以它為鏈?zhǔn)? 把與結(jié)點(diǎn)i直接相連的結(jié)點(diǎn)鏈成一個(gè)鏈。圖G表示成右圖的鄰接鏈表 :,已知一個(gè)網(wǎng)g=(v,e)。其中, v=(v1 ,v2 , ,vn) 為網(wǎng)g的結(jié)點(diǎn)集合, vi為網(wǎng)中結(jié)點(diǎn)。 e= (vi , vj) 是網(wǎng)中邊的集合, (vi ,vj)表示連接結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的邊。 找路徑是指求從結(jié)點(diǎn)m到結(jié)點(diǎn)n的所有路徑。,例12-5 找路徑,解:這樣想該問題, 從m點(diǎn)出發(fā)沿所有可能的路向前走一步; 然后再站在新的點(diǎn)上，再向前走一步; . 如此重復(fù)，直到走到結(jié)點(diǎn)n為止。 在走的過程中，保證不走重復(fù)點(diǎn)，可以得到下圖的算法:,在該算法中，關(guān)鍵在于找出m點(diǎn)的所有后繼點(diǎn)。 (一) 鄰接鏈表方法,設(shè)有如下聲明： #define h 10 struct 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ù)原型：判斷 /點(diǎn)i是否已經(jīng)走過（在P中）,void route ( int m, int n, int r ) / 開始結(jié)點(diǎn)、終結(jié)結(jié)點(diǎn)、路跡數(shù)組p的尾 struct node *hh; int i; 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; ,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; j=f; j+) printf(“%4d“, pj ); printf(“n“); ,程序設(shè)計(jì)實(shí)例,一個(gè)排序算法 法雷序列 多項(xiàng)式加法,例12-2 排序算法,數(shù)組排序已經(jīng)很熟悉，而且有各種各樣的算法。下邊用逐步增加遞增子序列的方法實(shí)現(xiàn)鏈表排序。設(shè)有說明: typedef . datatype ; struct item datatype data ; int key ; struct item *next ; ; typedef struct item *pt,以base為鏈?zhǔn)椎逆湵砣缦聢D所示。該算法的思想是: 開始假設(shè)空序列是遞增的 若i個(gè)元素子序列已經(jīng)遞增，則加一個(gè)元素，把插入到序列中一個(gè)適當(dāng)位置使i+1個(gè)元素的子序列也遞增 直到i=n為止,考查程序運(yùn)行中各個(gè)參數(shù)、變量、鏈表的變化狀態(tài)。如圖所示： 設(shè)從base到p0之間的子鏈表已經(jīng)遞增，現(xiàn)在加入p所指示的節(jié)； 在basep0之間查找合適位置，設(shè)應(yīng)該把p所指的節(jié)插入到r0,r所之間； 把p獨(dú)立出來=q ， p指向p0： q = p ; p0-next = p-next ; p = p0 ; 把p（現(xiàn)在由q指示）插入到r0,r之間： q-next = r ; r0-next = q； 現(xiàn)在鏈表結(jié)構(gòu)是：,.,pt sort( pt base ) /* 鏈表排序，base 為鏈?zhǔn)?*/ pt p , p0 , r , r0 , q ; p0 = NULL ; p = base ; while ( p!=NULL ) /* 逐項(xiàng)處理，把p加入到子序列中，并保持“base-p”遞增 */ r = base ; /* 尋找位置 */ while ( ( r-key key ) /* sort */,對(duì)任意給定的自然數(shù) n ，把所有如下形式的不可約分?jǐn)?shù) 按遞增順序排列起來，稱該序列為 n 級(jí)法雷序列 Fn 。 例如F8 為: 編函數(shù)，對(duì)任意給定的正整數(shù)n ，求n級(jí)法雷序列，并帶回n級(jí)法雷序列鏈指針。,例12-3 法雷序列,分析： 法雷序列的每項(xiàng)是個(gè)分?jǐn)?shù)，不能用實(shí)數(shù)精確的表示，而且這些數(shù)的排列順序是不規(guī)則的。用下圖形式的鏈表來表示它。,顯然法雷序列的各項(xiàng)均在區(qū)間0/1,1/1之內(nèi)。生成法雷序列算法 先把一階法雷序列：0/1,1/1放入鏈表中； 然后順序分別以i=2,3, . ,n 作分母，對(duì)任意i以j=1,2, . , i-1作 分子，作成分?jǐn)?shù)j/i； 若j/i是不可約分?jǐn)?shù)，則該j/i必然是法雷序列的一項(xiàng)；把該j/i插入到鏈表的合適位置上，并使鏈表仍保持按遞增排序。,0/1 , 1/1 放入序列,讀入 n,把 j/i 放入序列,struct farlei_item int numerator , denominator ; struct farlei_item *next ; ; typedef struct farlei_item * farleipointer ; int gcd( int x , int y ) /* 求最大公約數(shù) */ if ( y=0 ) return x ; else return gcd( y , x % y ) ; ,/*構(gòu)造法雷序列,并返回序列頭指針*/ farleipointer farlei(int n) int i,j ; farleipointer fn , r , r0 , p ; if( nnumerator = 0 ; fn-denominator = 1 ; fn-next = (farle