動態(tài)數(shù)據(jù)結(jié)構教學.ppt

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