《《算法與數(shù)據(jù)結(jié)構(gòu)》第6章數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)ppt.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第6章數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)ppt.ppt（132頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu),第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),數(shù)據(jù)結(jié)構(gòu)是對(duì)程序中數(shù)據(jù)信息的結(jié)構(gòu)組織，供給定問(wèn)題求解算法的控制結(jié)構(gòu)來(lái)處理。 Niklaus wirth曾經(jīng)給出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的公式，得到了計(jì)算機(jī)科學(xué)界的普遍認(rèn)可。 在程序設(shè)計(jì)語(yǔ)言中如何表示數(shù)據(jù)和控制，很大程度上決定了如何使用這個(gè)語(yǔ)言來(lái)編寫程序；所以在程序設(shè)計(jì)語(yǔ)言中不僅提供了與程序控制流程有關(guān)的控制結(jié)構(gòu)，同時(shí)也提供了與程序中數(shù)據(jù)信息組織有關(guān)的數(shù)據(jù)結(jié)構(gòu)。 程序設(shè)計(jì)的主要任務(wù)就是在選取或組織適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，利用三種基本結(jié)構(gòu)（順序、選擇、重復(fù)）把逐級(jí)分解得到的一系列基本操作組織起來(lái)，形成用某種特定語(yǔ)言書寫的源程序。,數(shù)據(jù)

2、結(jié)構(gòu)的程序?qū)崿F(xiàn)(續(xù)),算法與數(shù)據(jù)結(jié)構(gòu)課程討論數(shù)據(jù)結(jié)構(gòu)的目的，就是為了在設(shè)計(jì)給定問(wèn)題的求解算法時(shí)，應(yīng)用這些數(shù)據(jù)結(jié)構(gòu)來(lái)組織程序中的數(shù)據(jù)；從而降低問(wèn)題的分析與設(shè)計(jì)難度，提高程序（或算法）的設(shè)計(jì)質(zhì)量，縮短設(shè)計(jì)周期。 這里就有一個(gè)在程序中如何實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的問(wèn)題。實(shí)現(xiàn)是使用的前提，只有在程序中實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)，才能在程序中利用數(shù)據(jù)結(jié)構(gòu)對(duì)給定問(wèn)題進(jìn)行有效地求解。 本章將從幾個(gè)不同的角度討論如何在程序中實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的問(wèn)題。,第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),6.1 基本的實(shí)現(xiàn)策略 6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,基本的實(shí)現(xiàn)策略,程序設(shè)計(jì)語(yǔ)言中提供了

3、與程序中數(shù)據(jù)信息組織有關(guān)的數(shù)據(jù)結(jié)構(gòu)，但沒有也不可能提供所有的數(shù)據(jù)結(jié)構(gòu)。 一方面，受科學(xué)技術(shù)和生產(chǎn)力發(fā)展水平的限制，人類認(rèn)知世界具有歷史局限性；人們不可能在某一天完成對(duì)現(xiàn)實(shí)世界的認(rèn)知過(guò)程，同樣也不可能在某一天說(shuō)對(duì)數(shù)據(jù)結(jié)構(gòu)的認(rèn)知過(guò)程已經(jīng)完結(jié)，這種認(rèn)知過(guò)程是一個(gè)漸進(jìn)式不斷深化和逐步完善的過(guò)程。 另一方面，受計(jì)算機(jī)科學(xué)發(fā)展和計(jì)算機(jī)系統(tǒng)本身的限制，人們不可能研制出一種設(shè)施包羅萬(wàn)象、功能應(yīng)有盡有的計(jì)算機(jī)語(yǔ)言和語(yǔ)言翻譯系統(tǒng)。 因此，程序設(shè)計(jì)語(yǔ)言中只可能提供一些基本的和常用的數(shù)據(jù)結(jié)構(gòu)設(shè)施，并提供一些構(gòu)造求解現(xiàn)實(shí)世界中問(wèn)題所需數(shù)據(jù)結(jié)構(gòu)的基本設(shè)施和方法手段。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的程序

4、實(shí)現(xiàn) 6.1.2 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.3 數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)綄?shí)現(xiàn) 6.1.4 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實(shí)現(xiàn),簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)了，并作為數(shù)據(jù)類型提供給程序設(shè)計(jì)人員。 諸如整型數(shù)據(jù)、實(shí)型數(shù)據(jù)、布爾型數(shù)據(jù)和字符型數(shù)據(jù)等等。 程序設(shè)計(jì)人員只要在程序中用相應(yīng)的類型標(biāo)識(shí)符直接說(shuō)明程序中數(shù)據(jù)變量的類型就可以直接使用了，如C語(yǔ)言中的int，unsigned int，long int，short int，unsigned short int，char，float和double等。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.2 構(gòu)造型數(shù)據(jù)結(jié)

5、構(gòu)的程序?qū)崿F(xiàn) 6.1.3 數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)綄?shí)現(xiàn) 6.1.4 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實(shí)現(xiàn),構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),還有一些簡(jiǎn)單類型和構(gòu)造類型，也是在程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。如枚舉型、子界型、日期型、集合、數(shù)組、字符串、記錄、文件等。 程序設(shè)計(jì)語(yǔ)言中提供了程序設(shè)計(jì)人員在程序中說(shuō)明這些數(shù)據(jù)類型的方法，程序設(shè)計(jì)人員只要在程序中的適當(dāng)位置按照相應(yīng)的格式和要求對(duì)程序中的數(shù)據(jù)進(jìn)行說(shuō)明就可以使用了。如C語(yǔ)言中的枚舉、數(shù)組、字符串、結(jié)構(gòu)體、共同體、文件等。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.2 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.3 數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)綄?shí)現(xiàn) 6.1.4 數(shù)據(jù)結(jié)構(gòu)的

6、數(shù)組實(shí)現(xiàn),數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)綄?shí)現(xiàn),其它的數(shù)據(jù)結(jié)構(gòu)，如鏈表、循環(huán)鏈表、棧、隊(duì)列、廣義表、樹、二叉樹、圖、網(wǎng)和堆等，在程序設(shè)計(jì)語(yǔ)言中一般都沒有提供其相應(yīng)的數(shù)據(jù)類型，程序設(shè)計(jì)人員不能夠在程序中用類型說(shuō)明的辦法直接引入。 然而，許多程序設(shè)計(jì)語(yǔ)言都提供有指針類型，程序設(shè)計(jì)人員可以利用指針類型在程序中動(dòng)態(tài)建立所需要的某種數(shù)據(jù)結(jié)構(gòu)。 一般地，在建立某種數(shù)據(jù)結(jié)構(gòu)之前，先需要說(shuō)明其數(shù)據(jù)元素的結(jié)點(diǎn)類型，如說(shuō)明成記錄、結(jié)構(gòu)體等，再用指針變量動(dòng)態(tài)建立起相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以供求解問(wèn)題的程序使用或處理。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.2 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 6.1.3 數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)?/p>

7、實(shí)現(xiàn) 6.1.4 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實(shí)現(xiàn),數(shù)據(jù)結(jié)構(gòu)的數(shù)組實(shí)現(xiàn),如果在程序設(shè)計(jì)語(yǔ)言中沒有提供指針變量，就不能動(dòng)態(tài)實(shí)現(xiàn)程序中需要的數(shù)據(jù)結(jié)構(gòu)；還有一些數(shù)據(jù)結(jié)構(gòu)，不宜借助指針來(lái)實(shí)現(xiàn)，如順序表、順序棧、順序隊(duì)列等。對(duì)于這兩種情況，程序設(shè)計(jì)人員都可以在程序中利用數(shù)組模擬實(shí)現(xiàn)程序中需要的一些數(shù)據(jù)結(jié)構(gòu)。 數(shù)組是每一種高級(jí)程序設(shè)計(jì)語(yǔ)言都提供了的數(shù)據(jù)結(jié)構(gòu)?？梢岳靡痪S數(shù)組模擬實(shí)現(xiàn)順序表、順序棧、順序隊(duì)列?？梢岳枚S數(shù)組模擬實(shí)現(xiàn)鏈表或循環(huán)鏈表，其中一列描寫一個(gè)數(shù)據(jù)元素（或結(jié)點(diǎn)）；若構(gòu)成數(shù)據(jù)元素各字段類型不一致，也可改用兩個(gè)或多個(gè)一維數(shù)組來(lái)模擬實(shí)現(xiàn)之?？捎萌齻€(gè)一維數(shù)組來(lái)模擬實(shí)現(xiàn)二叉樹，其中一個(gè)數(shù)組存放數(shù)據(jù)域的值，兩個(gè)數(shù)

8、組分別作為左右鏈域。樹可通過(guò)左孩子右兄弟表示法轉(zhuǎn)化為二叉樹用數(shù)組表示，而圖和網(wǎng)的鄰接矩陣表示法本身就是用二維數(shù)組表示的方法。,第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),6.1 基本的實(shí)現(xiàn)策略 6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn),所謂動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（dynamic data structure）是指可以隨著程序的執(zhí)行而動(dòng)態(tài)地改變大小程形狀的一類數(shù)據(jù)結(jié)構(gòu)，如鏈表、樹和圖等。動(dòng)態(tài)結(jié)構(gòu)的數(shù)據(jù)，在編譯時(shí)無(wú)法預(yù)先規(guī)定它們所需要分配的存儲(chǔ)空間大小，只有在運(yùn)行時(shí)進(jìn)行動(dòng)態(tài)存儲(chǔ)分配，與之相對(duì)應(yīng)的是靜態(tài)數(shù)據(jù)結(jié)構(gòu)（static data structure

9、），數(shù)據(jù)所需存儲(chǔ)空間是一個(gè)固定的有限區(qū)域，可在程序說(shuō)明中顯式規(guī)定，在編譯時(shí)靜態(tài)進(jìn)行存儲(chǔ)分配。 凡是可以用指針動(dòng)態(tài)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，都可以利用數(shù)組靜態(tài)地模擬實(shí)現(xiàn)。有時(shí)也把這種利用數(shù)組靜態(tài)模擬實(shí)現(xiàn)了的動(dòng)態(tài)結(jié)構(gòu)稱之為半靜態(tài)數(shù)據(jù)結(jié)構(gòu)（semi-static data structure）。當(dāng)然，半動(dòng)態(tài)結(jié)構(gòu)中也包含可變數(shù)組和變長(zhǎng)記錄等部分采用靜態(tài)分配、部分采用動(dòng)態(tài)分配的數(shù)據(jù)結(jié)構(gòu)。,6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實(shí)現(xiàn),靜態(tài)鏈表,在利用提供指針類型的高級(jí)程序設(shè)計(jì)語(yǔ)言編寫程序時(shí)，鏈表的實(shí)現(xiàn)是

10、很簡(jiǎn)單和很自然的。如果語(yǔ)言中沒有提供指針類型，可以用數(shù)組來(lái)模擬實(shí)現(xiàn)鏈表結(jié)構(gòu)，并稱之為靜態(tài)鏈表（static linked list），用以記錄類型作為基類型的數(shù)組來(lái)模擬實(shí)現(xiàn)靜態(tài)鏈表。 模擬實(shí)現(xiàn)靜態(tài)鏈表的數(shù)組可如下定義： #define maxsize 100 typedef struct elementype data; /*數(shù)據(jù)域?yàn)樵仡愋?/ int next; /*指針域?yàn)檎?/ snode; /*snode為結(jié)點(diǎn)類型標(biāo)識(shí)符*/ snode smaxsize; /*s為基類型是snode的一維數(shù)組，即記錄數(shù)組*/,靜態(tài)鏈表（續(xù)）,注意這里的next域說(shuō)明與單鏈表中的說(shuō)明不同，在單鏈表中

11、是指向結(jié)構(gòu)體的指針類型，值為結(jié)點(diǎn)的實(shí)際地址；在靜態(tài)鏈表中是int類型，值為結(jié)點(diǎn)在s數(shù)組中的下標(biāo)值，指針值為空時(shí)用-1表示。 對(duì)于靜態(tài)鏈表實(shí)現(xiàn)線性表的各種運(yùn)算操作與動(dòng)態(tài)的單鏈表上的實(shí)現(xiàn)基本相同，所不同的是在存儲(chǔ)區(qū)的管理上有差別。 單鏈表上的運(yùn)算操作實(shí)現(xiàn)不要考慮存儲(chǔ)區(qū)的管理問(wèn)題，是通過(guò)malloc函數(shù)獲得結(jié)點(diǎn)空間并利用free函數(shù)釋放結(jié)點(diǎn)空間，存儲(chǔ)區(qū)的管理交由系統(tǒng)完成； 而靜態(tài)鏈表的存儲(chǔ)區(qū)就是這個(gè)記錄數(shù)組s，獲得結(jié)點(diǎn)空間和釋放結(jié)點(diǎn)空間都對(duì)數(shù)組s進(jìn)行，必須在程序中設(shè)計(jì)相應(yīng)的管理程序段。,靜態(tài)鏈表及其存儲(chǔ)區(qū)管理舉例,6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示

12、法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實(shí)現(xiàn),二叉樹的靜態(tài)二叉鏈表表示法,對(duì)于沒有提供指針類型的高級(jí)程序設(shè)計(jì)語(yǔ)言，程序中要用到二叉樹結(jié)構(gòu)組織數(shù)據(jù)信息，可用靜態(tài)二叉鏈表（static binary linked list）表示法實(shí)現(xiàn)二叉樹結(jié)構(gòu)。和靜態(tài)鏈表類似，靜態(tài)二叉鏈表的存儲(chǔ)區(qū)管理也是利用以結(jié)點(diǎn)類型作為基類型的一維數(shù)組實(shí)現(xiàn)；獲得結(jié)點(diǎn)空間的函數(shù)malloc和釋放結(jié)點(diǎn)空間的free函數(shù)的實(shí)現(xiàn)也是類似的。 用靜態(tài)二叉鏈表表示二叉樹的類型定義如下： #define maxsize 100 typedef struct /*定義結(jié)點(diǎn)類型為結(jié)構(gòu)體*/ elementype dat

13、a; /*數(shù)據(jù)域?yàn)樵仡愋?/ int lchild,rchild; /*定義左右孩子域?yàn)檎?/ sbinarytree; sbinarytree stmaxsize;,二叉樹的靜態(tài)二叉鏈表表示法,和靜態(tài)鏈表一樣，靜態(tài)二叉鏈表的左孩子域和右孩子域也都是int類型，其值為數(shù)組中的下標(biāo)值。 靜態(tài)二叉鏈表的存儲(chǔ)區(qū)管理是利用右孩子域形成的靜態(tài)鏈棧av，用-1表示指針為NULL的情況。 除了在插入結(jié)點(diǎn)時(shí)獲取一個(gè)結(jié)點(diǎn)空間以及在刪除時(shí)釋放一個(gè)結(jié)點(diǎn)空間的存儲(chǔ)區(qū)管理是要在程序中完成之外，用靜態(tài)二叉鏈表表示的二叉樹的各種運(yùn)算操作與用二叉鏈表表示的二叉樹的相應(yīng)運(yùn)算操作一致。,二叉樹的靜態(tài)二叉鏈表表示法舉例,6.2

14、 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實(shí)現(xiàn),樹和森林的雙親表示法舉例,在前面我們介紹了樹和森林的兩種存儲(chǔ)表示方法，即孩子鏈表表示法和左孩子右兄弟表示法；這兩種表示方法，都可以通過(guò)靜態(tài)鏈表和靜態(tài)二叉鏈表來(lái)實(shí)現(xiàn)。 樹和森林還有一種存儲(chǔ)表示方法，就是雙親表示法。因?yàn)闃浜蜕种械拿恳粋€(gè)結(jié)點(diǎn)，其雙親結(jié)點(diǎn)是惟一的；利用這一性質(zhì)，在存儲(chǔ)結(jié)點(diǎn)信息時(shí)為每個(gè)結(jié)點(diǎn)增加一個(gè)指向其雙親的指針parent，就可以惟一地表示樹或森林。 若用靜態(tài)鏈表實(shí)現(xiàn)樹和森林的雙親表示法，其類型定義如下： #define maxsi

15、ze 100 typedef struct elementype data; int parent; sptnode; sptnode ptmaxsize;,樹和森林的雙親表示法,6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實(shí)現(xiàn),哈夫曼算法的靜態(tài)實(shí)現(xiàn),由于哈夫曼樹中沒有度為1的結(jié)點(diǎn)，一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹有2n-1個(gè)結(jié)點(diǎn)，所以可用大小為2n-1個(gè)元素的數(shù)組構(gòu)造靜態(tài)鏈表來(lái)存儲(chǔ)哈夫曼樹，一個(gè)數(shù)組元素中存放一個(gè)結(jié)點(diǎn)。 結(jié)點(diǎn)的結(jié)構(gòu)可以這樣來(lái)考慮，由于每個(gè)葉子結(jié)點(diǎn)都有一個(gè)權(quán)重值，構(gòu)造哈夫曼樹

16、的過(guò)程中每個(gè)分枝結(jié)點(diǎn)的權(quán)重值等于兩個(gè)孩子結(jié)點(diǎn)權(quán)重值的和，所以應(yīng)該有一個(gè)權(quán)重域和指向左右孩子的兩個(gè)指針域； 另外在建成哈夫曼樹之后，為了求得每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼，需要走一條從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，而譯碼的過(guò)程是從根結(jié)點(diǎn)出發(fā)到葉子結(jié)點(diǎn)的不斷匹配的過(guò)程，所以既需要知道孩子結(jié)點(diǎn)的信息，也需要知道雙親結(jié)點(diǎn)的信息，應(yīng)該再有一個(gè)指向雙親結(jié)點(diǎn)的指針域。 由此可知每個(gè)結(jié)點(diǎn)至少應(yīng)該有一個(gè)權(quán)重域weight和三個(gè)指針域parent、lchild和rchild，也就是說(shuō)要用靜態(tài)三叉鏈表來(lái)表示哈夫曼樹。,哈夫曼樹及其靜態(tài)三叉鏈表存儲(chǔ)表示示例,哈夫曼算法的靜態(tài)實(shí)現(xiàn)(續(xù)),由于在實(shí)際構(gòu)造哈夫曼樹時(shí)，是由葉子結(jié)點(diǎn)的權(quán)值

17、逐級(jí)構(gòu)造最后生成樹根，且在構(gòu)造過(guò)程中僅與葉子結(jié)點(diǎn)的權(quán)值有關(guān)而與葉子結(jié)點(diǎn)的數(shù)據(jù)域值無(wú)關(guān)； 所以構(gòu)造算法的實(shí)現(xiàn)中可以不考慮葉子結(jié)點(diǎn)的數(shù)據(jù)域值，并且在靜態(tài)三叉鏈表中從葉子結(jié)點(diǎn)開始存放，然后不斷地把兩棵權(quán)值最小的子樹合并成為一棵權(quán)值為其和的較大的子樹，逐步生成各內(nèi)部結(jié)點(diǎn)直到樹根。 哈夫曼樹的類型定義如下： #define maxvalue 10000 #define maxnodenumber 100 typedef struct int weight; int parent,lchild,rchild; htnode; /*定義結(jié)點(diǎn)類型標(biāo)識(shí)符*/ type htnode *huffmantree;

18、/*定義哈夫曼樹類型*/ htnode htmaxnodenumber;,建立哈夫曼樹的算法的描述,在以上類型定義的基礎(chǔ)上，對(duì)于給定的一組權(quán)重值，建立其哈夫曼樹的算法可描述如下： huffmantree crthuffmantree(int n) int i,j,m1,m2,k1,k2; for(i=0;i2*n-1;i+) hti.weight=0; /*權(quán)重初始化為0*/ hti.parent= -1; hti.lchild= -1; hti.rchild= -1; for(i=0;in;i+) scanf(“%d”,建立哈夫曼樹的算法的描述(續(xù)),for(i=0;in-1;i+) m1=

19、maxvalue; m2=maxvalue; k1=0; k2=0; for(j=0;jn+i;j+) if(htj.parent=-,建立哈夫曼樹的算法的描述(續(xù)),htk1.parent=n+i; htk2.parent=n+i; htn+i.weight=htk1.weight +htk2.weight; htn+i.lchild=k1; htn+i.rchild=k2; return ht; /*crthuffmantree end */ 注意，在建立哈夫曼樹的算法描述中，有效地利用了每個(gè)結(jié)點(diǎn)的雙親域parent的值是否為-1來(lái)區(qū)分該結(jié)點(diǎn)是否是哈夫曼森林中一棵樹的根結(jié)點(diǎn)；每次是在根結(jié)點(diǎn)

20、中找出兩個(gè)權(quán)重值weight最小的樹作為左右子樹構(gòu)造一棵更大的樹。,求哈夫曼編碼的方法,求哈夫曼編碼的方法是，在已建好的哈夫曼樹中從每個(gè)葉子結(jié)點(diǎn)開始沿雙親鏈域回退到根結(jié)點(diǎn)，每回退一步走過(guò)哈夫曼樹的一個(gè)分枝得到一位哈夫曼編碼值；由于每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)的路徑上各分枝代碼所組成的0、1序列，所以先得到的分枝代碼為所求編碼的低位碼而后得到的為高位碼。 對(duì)于每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼可以考慮用一個(gè)一維數(shù)組bit從后向前依次保存所求得的各位編碼值，并用start記住編碼在數(shù)組bit中的開始位置。由此可做如下的類型定義： #define maxbit 10 typedef str

21、uct int bitmaxbit; int start; hcodetype; /*定義哈夫曼編碼類型*/,求哈夫曼編碼的算法描述,從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)逆向求每個(gè)葉子結(jié)點(diǎn)所代表值的哈夫曼編碼的算法可描述如下： void gethuffmancode(htnode ht,int n) int i,j,c,p; hcodetype cdn; for(i=0;in;i+) c=i; j=maxbit+1; do j-; p=htc.parent; if(htp.lchild=c) /*如果c是p的左孩子*/ cdi.bitj=0; else cdi.bitj=1; c=p; while(p!= -1

22、);,求哈夫曼編碼的算法描述(續(xù)),cdi.start=j; for(i=0;in;i+) for(j=cdi.start;jmaxbit;j+) printf(“%d”,cdi.bitj); printf(“n”); /*gethuffmancode end*/,求哈夫曼編碼的算法舉例,例如，已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)六種字符，其使用各字符的頻度分別為（0.05，0.20，0.12，0.07，0.47，0.09）。若要為這六種字符設(shè)計(jì)哈夫曼編碼，可設(shè)權(quán)w=(5，20，12，7，47，9)，n=6，2n-1=11；按上述crthuffmantree算法構(gòu)造的哈夫曼樹如下左圖所示。按get

23、huffmancode算法求得的哈夫曼編碼在cd數(shù)組中的狀態(tài)如下右圖所示。,求哈夫曼編碼的算法舉例(續(xù)),其存儲(chǔ)結(jié)構(gòu)的靜態(tài)三叉鏈表ht的初始狀態(tài)如下左圖所示，最終狀態(tài)如下右圖所示。,第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),6.1 基本的實(shí)現(xiàn)策略 6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,6.3 大批量數(shù)據(jù)的組織策略,6.3.1 文件的組織 6.3.2 數(shù)據(jù)庫(kù)技術(shù),1.文件的基本概念,文件的概念和線性表類似，是由大量性質(zhì)相同的記錄組成的集合；二者的區(qū)別在于線性表是把記錄全部組織在內(nèi)存儲(chǔ)器中，而文件則是把大量記錄都組織在外存儲(chǔ)器中。 按照記錄的類型，可以把文

24、件分為操作系統(tǒng)文件和數(shù)據(jù)庫(kù)文件兩大類。 操作系統(tǒng)文件中的記錄只是一個(gè)字符序列，無(wú)結(jié)構(gòu)，無(wú)解釋，僅是為了加工，存取的方便劃分的字符組。 而數(shù)據(jù)庫(kù)文件中的記錄是有結(jié)構(gòu)的，可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，是存取文件中數(shù)據(jù)的基本單位；數(shù)據(jù)項(xiàng)是不可再分的最基本單位，也是文件中可使用數(shù)據(jù)的最小單位。,文件的基本概念（續(xù)）,按照記錄的長(zhǎng)度特性，可以把文件分為定長(zhǎng)記錄文件和不定長(zhǎng)記錄文件。 定長(zhǎng)記錄文件中每個(gè)記錄含有的信息長(zhǎng)度相同， 不定長(zhǎng)記錄文件中每個(gè)記錄含有的信息長(zhǎng)度不等。 按照記錄中關(guān)鍵字的多少，可以把文件分為單關(guān)鍵字文件和多關(guān)鍵字文件。 單關(guān)鍵字文件中的記錄只有一個(gè)惟一標(biāo)識(shí)記錄的主關(guān)鍵字； 多關(guān)鍵字文件中

25、的記錄除了主關(guān)鍵字外，還含有一個(gè)或多個(gè)次關(guān)鍵字，記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)稱作記錄的屬性。,文件的基本概念（續(xù)）,記錄有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之分。 邏輯結(jié)構(gòu)是指記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和存取方式；用戶讀寫一個(gè)記錄是指邏輯記錄。 記錄的物理結(jié)構(gòu)是數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織方式。一個(gè)物理記錄是指計(jì)算機(jī)用一條I/O命令進(jìn)行讀寫的基本數(shù)據(jù)單位，對(duì)于固定的設(shè)備和操作系統(tǒng)，它的大小基本上是固定不變的； 而邏輯記錄的大小是根據(jù)使用的需要確定的。 一個(gè)物理記錄可以存放一個(gè)或多個(gè)邏輯記錄，多個(gè)物理記錄可以表示一個(gè)邏輯記錄。用戶讀寫的是邏輯記錄，查找其對(duì)應(yīng)的

26、物理記錄是操作系統(tǒng)的職責(zé)。,文件的基本概念（續(xù)）,文件的操作有三類，檢索、修改和排序。 檢索的方式有三種： 順序檢索，按記錄的相對(duì)位置檢索下一個(gè)邏輯記錄； 按記錄號(hào)檢索，根據(jù)記錄存入文件時(shí)的順序編號(hào)，檢索第i個(gè)邏輯記錄； 按關(guān)鍵字檢索，檢索關(guān)鍵字值與給定值相關(guān)的一個(gè)或多個(gè)邏輯記錄，在數(shù)據(jù)庫(kù)文件中又可按給定關(guān)鍵字值、給定關(guān)鍵字的范圍、給定關(guān)鍵字的某個(gè)函數(shù)以及組合條件等方式進(jìn)行檢索。 修改操作包括插入、刪除和更新一個(gè)記錄這三種操作。 排序操作則是為了檢索方便高效對(duì)文件中記錄的重新有序整理。,文件的基本概念（續(xù)）,文件的操作可以有實(shí)時(shí)和批處理兩種不同的方式。 實(shí)時(shí)處理通常對(duì)應(yīng)答時(shí)間要求嚴(yán)格，應(yīng)在接收

27、詢問(wèn)后立即完成相應(yīng)的操作； 而批處理則不同，可以根據(jù)需要對(duì)積累一段時(shí)間的記錄進(jìn)行成批處理。 文件在存儲(chǔ)介質(zhì)上的組織方式（即物理結(jié)構(gòu)）有順序組織、隨機(jī)組織和鏈?zhǔn)浇M織等基本方式，具體選用哪種方式應(yīng)結(jié)合存儲(chǔ)介質(zhì)類型（磁盤、磁帶等）、記錄類型、記錄大小、關(guān)鍵字?jǐn)?shù)目以及對(duì)文件進(jìn)行何種操作等各種因素綜合考慮。,2.順序文件,順序文件（sequential file）是把記錄按建立文件時(shí)的邏輯順序依次存放在外存儲(chǔ)器中，文件中的物理記錄順序和邏輯記錄順序一致。 若次序相繼的兩個(gè)物理記錄在存儲(chǔ)器上的存儲(chǔ)位置是相鄰的，則又稱為連續(xù)文件； 若物理記錄之間的次序由指針鏈接，則稱為串聯(lián)文件。 順序文件的存取方式是根據(jù)記

28、錄號(hào)或記錄的相對(duì)位置進(jìn)行的，其特點(diǎn)是： 存取第i個(gè)記錄必須先搜索在它之前的i-1個(gè)記錄； 插入的新記錄只能加在文件的未尾； 若要更新文件中的某個(gè)記錄，必須在整個(gè)文件的復(fù)制過(guò)程中進(jìn)行。,順序文件（續(xù)）,由于順序文件的優(yōu)點(diǎn)是連續(xù)存取速度快，因此主要用于順序存取和批量修改的情況。 若對(duì)應(yīng)答時(shí)間要求不嚴(yán)時(shí)亦可進(jìn)行直接存取。 在對(duì)順序文件作修改時(shí)，可對(duì)原文件中的記錄復(fù)制一遍，并在復(fù)制的過(guò)程中插入新的記錄、跳過(guò)待刪除的記錄、或用修改過(guò)的新記錄代替原記錄。 為了修改方便起見，要求待修改文件按關(guān)鍵字有序（對(duì)非數(shù)據(jù)庫(kù)文件可將邏輯記錄號(hào)作為關(guān)鍵字）。,順序文件（續(xù)）,磁帶是一種典型的順序存取設(shè)備，存儲(chǔ)在磁帶上的文

29、件就是順序文件。然而現(xiàn)在很少使用磁帶，較多使用的是磁盤上的順序文件。對(duì)磁盤上的順序文件進(jìn)行修改時(shí)，若不增加記錄的長(zhǎng)度，也可在原文件上直接修改而不必復(fù)制文件。 對(duì)順序文件進(jìn)行順序檢索的方法類似于靜態(tài)表的順序檢索，其平均檢索長(zhǎng)度為(n+1)/2，其中n為文件中所含物理記錄的數(shù)目（內(nèi)存檢索時(shí)間可以忽略不計(jì)）。也可以對(duì)磁盤文件進(jìn)行分塊檢索或二分法檢索。但當(dāng)文件很大時(shí)，二分法檢索將會(huì)引起磁頭在存儲(chǔ)文件的多個(gè)柱面之間來(lái)回移動(dòng)而增加檢索時(shí)間。,3.索引文件,除了主文件（即數(shù)據(jù)文件）之外，再建立一張索引表來(lái)指示邏輯記錄和物理記錄之間的一一對(duì)應(yīng)關(guān)系；索引表中的每一項(xiàng)稱作索引項(xiàng)，由記錄的關(guān)鍵字和記錄的存放地址構(gòu)成

30、；把索引表和主文件總稱為索引文件（indexed file）。 索引表通常是按關(guān)鍵字的升序排列。若主文件也按關(guān)鍵字升序排列，則構(gòu)成的索引文件稱作索引順序文件； 若主文件是無(wú)序的，則稱所構(gòu)造的索引文件為索引非順序文件。,索引文件（續(xù)）,索引文件只適用于直接存取的外存儲(chǔ)器（如磁盤）。索引文件的存儲(chǔ)分索引區(qū)和數(shù)據(jù)區(qū)來(lái)進(jìn)行，索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。 在輸入記錄建立數(shù)據(jù)區(qū)的同時(shí)建立索引表，表中的索引項(xiàng)按記錄輸入的先后次序排列；待全部記錄輸入完畢后再對(duì)索引表按關(guān)鍵字排序，排序后的索引表和主文件一起構(gòu)成了索引文件。,索引非順序文件舉例,索引文件（續(xù)）,索引文件的檢索，應(yīng)先在索引表中檢索。若在索引

31、表中找到關(guān)鍵字值等于給定值的索引項(xiàng)，則按索引項(xiàng)指示從外部存儲(chǔ)器讀取該記錄；否則說(shuō)明待檢索記錄不存在無(wú)需訪問(wèn)外存儲(chǔ)器。 相對(duì)于記錄而言索引項(xiàng)長(zhǎng)度較小，即由索引項(xiàng)構(gòu)成的索引表所占空間較小，通?？梢淮巫x入內(nèi)存。然而當(dāng)主文件中記錄數(shù)目很大時(shí)，索引表仍可能超出一個(gè)物理塊的容量，這樣對(duì)索引表的檢索就可能需要多次訪問(wèn)外存儲(chǔ)器。 為此，可對(duì)索引表再次建立二級(jí)索引；檢索時(shí)先在二級(jí)索引中找，再檢索索引表，然后讀取記錄。 索引表和二級(jí)索引表都是有序表，在內(nèi)存儲(chǔ)器中可用檢索效率較高的方法如二分法檢索方法進(jìn)行檢索。,4.ISAM文件,ISAM（indexed sequential access method）即索引順序

32、存取方法，是一種專為磁盤存取設(shè)計(jì)的文件組織方式。 由于磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，所以可以對(duì)磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級(jí)索引。 文件的記錄在同一盤組上存放時(shí)，應(yīng)先集中放在一個(gè)柱面上，然后再順序存放在相鄰柱面上；對(duì)同一柱面，則應(yīng)按盤面的次序順序存放。,ISAM文件結(jié)構(gòu)舉例,ISAM文件（續(xù)）,在一個(gè)磁盤組上的ISAM文件，每個(gè)柱面建立一個(gè)磁道索引，每個(gè)磁道索引項(xiàng)由基本索引項(xiàng)和溢出索引項(xiàng)兩部分組成，每一部分都包括關(guān)鍵字和指針兩個(gè)域，前者表示該磁道中最大關(guān)鍵字，后者指示該磁道中第一個(gè)記錄的位置。 柱面索引的每一個(gè)索引項(xiàng)也由關(guān)鍵字和指針兩部分組成，前者表示該柱面中的最大關(guān)鍵

33、字，后者指示該柱面上的磁道索引位置。 柱面索引存放在某個(gè)柱面上，若柱面索引較大占多個(gè)磁道時(shí)，則可建立柱面索引的一個(gè)主索引。,ISAM文件（續(xù)）,在ISAM文件上檢索記錄時(shí)，先從主索引出發(fā)找到相應(yīng)的柱面索引，再?gòu)闹嫠饕业接涗浰谥娴拇诺浪饕?，最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直至找到為止；反之，若找遍磁道而不存在此記錄，則表明文件中無(wú)此記錄。 在前例中為每個(gè)柱面開辟了一個(gè)溢出區(qū)，并在磁道索引項(xiàng)中有溢出索引項(xiàng)（后面兩個(gè)域），這是為插入記錄所設(shè)置的。,ISAM文件（續(xù)）,由于ISAM文件中記錄是按關(guān)鍵字順序存放的，在插入一個(gè)記錄時(shí)需要向后移動(dòng)記錄，

34、并將同一磁道上的最后一個(gè)記錄移至溢出區(qū)，同時(shí)修改磁道索引項(xiàng)。除了為每個(gè)柱面設(shè)置一個(gè)溢出區(qū)的方法外，還可只集中設(shè)置一個(gè)大的公共溢出區(qū)；也可以既為每個(gè)柱面設(shè)置溢出區(qū)，同時(shí)也設(shè)置了一個(gè)公共溢出區(qū)，在柱面溢出區(qū)滿后再使用公共溢出區(qū)。 ISAM文件中刪除記錄比較簡(jiǎn)單，只需作刪除標(biāo)記而不用移動(dòng)記錄或改變指針。當(dāng)然應(yīng)該周期性地把記錄讀入內(nèi)存重排整理ISAM文件，以盡量填滿基本區(qū)而空出溢出區(qū)。,5.VSAM文件,VSAM（virtual storage access method）即虛擬存儲(chǔ)存取方法。它利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，使用戶只需考慮控制區(qū)間等邏輯存儲(chǔ)單位，而無(wú)需考慮其物理位置以及何時(shí)對(duì)外存儲(chǔ)

35、器進(jìn)行讀寫操作，給用戶使用文件提供了方便。 VSAM文件的結(jié)構(gòu)由索引集、順序集和數(shù)據(jù)集三部分組成。 數(shù)據(jù)集存放文件的所有記錄， 順序集和索引集構(gòu)成一棵B+樹是文件的索引部分。數(shù)據(jù)集中的一個(gè)結(jié)點(diǎn)稱為控制區(qū)間（control interval），它由一組連續(xù)的存儲(chǔ)單元組成，是讀寫操作的基本單位。,VSAM文件的結(jié)構(gòu)舉例,VSAM文件（續(xù)）,同一文件上的控制區(qū)間大小相同，含有一個(gè)或多個(gè)按關(guān)鍵字升序排列的記錄。 順序集中的一個(gè)結(jié)點(diǎn)，存放著若干相鄰控制區(qū)間的索引項(xiàng)，每個(gè)索引項(xiàng)由控制區(qū)間中的最大關(guān)鍵字和指向該控制區(qū)間的指針組成。 順序集中的一個(gè)結(jié)點(diǎn)連同其下層所有控制區(qū)間形成的整體稱作控制區(qū)域（contro

36、l range）。 順序集中的結(jié)點(diǎn)之間用指針相鏈接；在它們上層的結(jié)點(diǎn)又以它們?yōu)榛A(chǔ)形成索引，并逐級(jí)向上建立索引，形成B+樹的非終端結(jié)點(diǎn)。,VSAM文件（續(xù)）,對(duì)VSAM文件中記錄的檢索，既可以從最高層的索引逐層往下按關(guān)鍵字進(jìn)行查找，又可以在順序集中沿著指針鏈順序查找。 VSAM文件沒有專門的溢出區(qū)，但可利用控制區(qū)間中的空隙或控制區(qū)域中空的控制區(qū)間來(lái)插入記錄（即在B+樹上插入記錄）。 在控制區(qū)間中插入記錄時(shí)，為了保證區(qū)間內(nèi)記錄按關(guān)鍵字有序需要移動(dòng)記錄；而當(dāng)區(qū)間中記錄已滿時(shí)，為了插入記錄需要將區(qū)間分裂。 在VSAM文件中刪除記錄時(shí)，也是需要移動(dòng)記錄的。,VSAM文件（續(xù)）,VSAM文件占有較多的存

37、儲(chǔ)空間，存儲(chǔ)空間的利用率一般也只能保持在75%左右。 然而它具有許多優(yōu)點(diǎn)，如動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，無(wú)需像ISAM文件那樣定期重排文件，并能較快地執(zhí)行插入操作和保持較高的檢索效率。 VSAM文件通常作為組織大型索引順序文件的標(biāo)準(zhǔn)形式。,6.散列文件,散列文件（Hash file）也稱作直接存取文件，它是利用哈希方法組織的數(shù)據(jù)文件；即根據(jù)某個(gè)哈希函數(shù)和一定的沖突消解策略而得到的存放在外存儲(chǔ)器上的散列表。 與哈希表不同的是，磁盤上的文件記錄通常是成組存放的。 若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，在散列文件中這個(gè)存儲(chǔ)單位稱作桶。 一個(gè)桶能存放的邏輯記錄的總數(shù)稱作桶的容量。假如桶的容量為m，即m個(gè)同義詞的記

38、錄可以存放在同一地址的桶中，當(dāng)?shù)趍+1個(gè)同義詞記錄出現(xiàn)時(shí)則發(fā)生溢出。處理溢出也可采用哈希表中的各種處理沖突的方法，但對(duì)散列文件主要是采用鏈地址法消解沖突。,散列文件（續(xù)）,當(dāng)發(fā)生溢出時(shí)，需要將第m+1個(gè)同義詞存放到另一個(gè)桶中，通常稱作“溢出桶”；相應(yīng)地把存放前m個(gè)同義詞的桶稱作“基桶”。 溢出桶可以有多個(gè)，它們和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒有檢索到待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸腥z索； 因此，同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好是在同一柱面上。,散列文件舉例,例如，某文件有20個(gè)記錄，其關(guān)鍵字分別為28、19、13、93、89、25、14、55

39、、69、8、9、16、21、33、81、62、11、71、34、35。用除留余數(shù)法選定哈希函數(shù)H(key)= key%7，用鏈地址法消解地址沖突。桶的容量m=3，基桶個(gè)數(shù)b=7，由此得到的散列文件如下圖所示。,散列文件（續(xù)）,在散列文件中檢索時(shí)： 先根據(jù)給定的關(guān)鍵字值k求得哈希地址，即基桶號(hào)； 然后將基桶的記錄讀入內(nèi)存進(jìn)行順序檢索，若找到關(guān)鍵字值為k的記錄則檢索成功； 若基桶中雖無(wú)關(guān)鍵字值為k的記錄但指針域非空，需要把溢出桶中的記錄讀入內(nèi)存繼續(xù)檢索，直到檢索成功或檢索不成功。 檢索不成功的情況為基桶沒有填滿記錄，或雖填滿但指針域?yàn)榭眨o(wú)溢出桶），或雖有溢出桶但仍未找到關(guān)鍵字為k的記錄。,散列文

40、件（續(xù)）,在散列文件中，裝填因子為 ，其中n為文件中的記錄數(shù)，b為桶數(shù)，m為桶的容量；而存取桶數(shù)的期望值為 。如上例， 。在散列文件中，刪除記錄時(shí)僅需對(duì)被刪記錄作一刪除標(biāo)記即可。 總之，散列文件的優(yōu)點(diǎn)是插入和刪除方便，存取速度比索引文件要快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。其缺點(diǎn)是不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問(wèn)方式只有簡(jiǎn)單詢問(wèn)；在經(jīng)過(guò)多次的插入和刪除之后，也可能造成溢出桶滿而基桶內(nèi)多數(shù)為被刪除記錄的不合理文件結(jié)構(gòu)，亦需對(duì)文件進(jìn)行重新整理。,7.多關(guān)鍵字文件,多關(guān)鍵字文件（multiple key file）的特點(diǎn)是，在對(duì)文件進(jìn)行檢索操作時(shí)不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問(wèn)，還經(jīng)常需要對(duì)次關(guān)

41、鍵字進(jìn)行其它類型的詢問(wèn)檢索。 因此，對(duì)多關(guān)鍵字文件還需要建立一系列的次關(guān)鍵字索引。次關(guān)鍵字索引和主關(guān)鍵字索引所不同的是，每個(gè)索引項(xiàng)應(yīng)包含次關(guān)鍵字和具有同一次關(guān)鍵字的多個(gè)記錄的主關(guān)鍵字或物理記錄號(hào)。 多重表文件和倒排文件是常見的兩種多關(guān)鍵字文件組織方法。,多關(guān)鍵字文件（續(xù)）,多重表文件（multilist file）的特點(diǎn)是，記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，并建立主關(guān)鍵字索引（稱為主索引）；對(duì)每一個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。 主索引為非稠密索引，一組記錄建立一個(gè)索引項(xiàng)；次索引為稠密索引，每個(gè)記錄建立一個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)包括次關(guān)鍵字、

42、頭指針和鏈表長(zhǎng)度。,多關(guān)鍵字文件舉例,例如，下圖所示為一個(gè)多重表文件。其中工號(hào)為主關(guān)鍵字，記錄按工號(hào)順序鏈接。,多關(guān)鍵字文件舉例（續(xù)）,對(duì)工號(hào)非稠密索引分成三個(gè)子鏈表，其索引如下圖(b)所示，索引項(xiàng)中的主關(guān)鍵字為各組中關(guān)鍵字的最大值。職稱和專業(yè)是兩個(gè)次關(guān)鍵字項(xiàng)，其索引分別如下圖(c)和(d)所示，具有相同次關(guān)鍵字值的記錄鏈接在同一鏈表中。,多關(guān)鍵字文件（續(xù)）,有了這些次關(guān)鍵字索引，根據(jù)關(guān)鍵字值找到鏈表頭指針，然后從頭指針出發(fā)可列出鏈表中所有記錄。比如查詢數(shù)學(xué)專業(yè)的教授，可以專業(yè)索引表中找到“數(shù)學(xué)”的頭指針和表長(zhǎng)，逐一讀取記錄查看哪些記錄的職稱為教授即可。此查詢也可從職稱索引入手進(jìn)行。當(dāng)然，較好

43、的方法是先讀長(zhǎng)度較短的鏈表中的記錄。 在多重表文件中插入一個(gè)記錄是容易的，只要修改指針將記錄插在鏈表的頭指針之后即可。然而要?jiǎng)h去一個(gè)記錄卻很繁瑣 ，需要在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。,多關(guān)鍵字文件（續(xù)）,倒排文件（inverted file）和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。倒排文件的次關(guān)鍵字索引稱為倒排表，在倒排表的索引項(xiàng)中沒有頭指針和鏈長(zhǎng)度，而是直接用一個(gè)項(xiàng)存放具有同一關(guān)鍵字的所有記錄的物理記錄號(hào)或主關(guān)鍵字值。值得注意的是，倒排表中具有同一次關(guān)鍵字的記錄號(hào)是有序排列的。上例的倒排表如下圖所示：,多關(guān)鍵字文件（續(xù)）,倒排表作索引的好處在于檢索記錄較快。特別是對(duì)某些詢問(wèn)，不用讀

44、取記錄就可得到答案。例如上例查詢數(shù)學(xué)專業(yè)教授，只要將“數(shù)學(xué)”索引中的記錄號(hào)和“教授”索引中的記錄號(hào)求集合的交集運(yùn)算就可以了，即2，5，92，6=2就得到記錄號(hào)為2者便是數(shù)學(xué)教授。 在插入和刪除記錄時(shí)，倒排表也要進(jìn)行相應(yīng)修改；需要移動(dòng)索引項(xiàng)中記錄號(hào)以保持其有序排列。若數(shù)據(jù)文件是索引順序文件（如ISAM文件），倒排表中應(yīng)存放記錄的主關(guān)鍵字而不是物理記錄號(hào)。 倒排文件的缺點(diǎn)是維護(hù)困難。同一倒排表中各項(xiàng)長(zhǎng)度不同，不同倒排表的長(zhǎng)度也不同，這些都給倒排文件的維護(hù)帶來(lái)一定的困難。,6.3 大批量數(shù)據(jù)的組織策略,6.3.1 文件的組織 6.3.2 數(shù)據(jù)庫(kù)技術(shù),文件系統(tǒng)的缺陷,利用文件組織大批量數(shù)據(jù)是數(shù)據(jù)組織中

45、行之有效的方法，然而，文件系統(tǒng)也存在著一些明顯的缺陷。如： 數(shù)據(jù)冗余大。因?yàn)槊總€(gè)文件都是為特定用途設(shè)計(jì)的，因此會(huì)造成同樣的數(shù)據(jù)在多個(gè)文件中的重復(fù)存儲(chǔ)。 數(shù)據(jù)的不一致性，這往往是由于數(shù)據(jù)冗余所造成的；在數(shù)據(jù)更新時(shí)，稍有不慎就會(huì)造成同一數(shù)據(jù)在不同文件中的不一致。 程序和數(shù)據(jù)之間的獨(dú)立性差。應(yīng)用程序依賴于文件的存儲(chǔ)結(jié)構(gòu)，使得在對(duì)文件的存儲(chǔ)結(jié)構(gòu)進(jìn)行修改時(shí)，必須修改應(yīng)用程序。 數(shù)據(jù)聯(lián)系弱。文件與文件之間是獨(dú)立的，文件之間的聯(lián)系必須通過(guò)程序來(lái)構(gòu)造。因此，文件系統(tǒng)是一個(gè)不具有彈性的無(wú)結(jié)構(gòu)的數(shù)據(jù)集合，難以反應(yīng)客觀世界中事物之間的聯(lián)系。,數(shù)據(jù)庫(kù)技術(shù)誕生,為了克服上述文件系統(tǒng)的不足，20世紀(jì)60年代后期開始誕生了

46、解決大批量數(shù)據(jù)組織和管理的數(shù)據(jù)庫(kù)技術(shù)。數(shù)據(jù)庫(kù)技術(shù)誕生的標(biāo)志性事件是： 1968年研制成功，1969年形成產(chǎn)品的美國(guó)IBM公司的數(shù)據(jù)庫(kù)管理系統(tǒng)IMS（information management system）的問(wèn)世，該系統(tǒng)支持的是層次數(shù)據(jù)模型。 美國(guó)數(shù)據(jù)系統(tǒng)語(yǔ)言協(xié)會(huì)CODASYL（conference on data system language）下屬的數(shù)據(jù)庫(kù)任務(wù)組DBTG（database task group）對(duì)數(shù)據(jù)庫(kù)方法進(jìn)行了系統(tǒng)的研究，在20世紀(jì)60年代末期和70年代初期發(fā)表了若干個(gè)報(bào)告（稱為DBTG報(bào)告），該報(bào)告建立了數(shù)據(jù)庫(kù)的許多概念、方法和技術(shù)。DBTG所提議的方法是基于網(wǎng)狀數(shù)據(jù)

47、模型的。 從1970年起，IBM的研究員E.F.Codd發(fā)表了一系列的論文，提出了數(shù)據(jù)庫(kù)的關(guān)系模型，開創(chuàng)了數(shù)據(jù)庫(kù)關(guān)系方法和關(guān)系數(shù)據(jù)理論的研究，為關(guān)系數(shù)據(jù)庫(kù)的發(fā)展和理論研究奠定了基礎(chǔ)。,數(shù)據(jù)庫(kù)技術(shù),數(shù)據(jù)庫(kù)技術(shù)發(fā)展到現(xiàn)在，已經(jīng)是一門非常成熟的技術(shù)，作為算法與數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)課程。 概括地講，數(shù)據(jù)庫(kù)具有如下基本特征： 數(shù)據(jù)庫(kù)是相互關(guān)聯(lián)的數(shù)據(jù)的集合。 數(shù)據(jù)庫(kù)用綜合的方法組織數(shù)據(jù)，并保證盡可能高的訪問(wèn)效率。 數(shù)據(jù)庫(kù)具有較小的數(shù)據(jù)冗余，可供多個(gè)用戶共享。 數(shù)據(jù)庫(kù)具有較高的數(shù)據(jù)獨(dú)立性。 數(shù)據(jù)庫(kù)具有安全控制機(jī)制，能夠保證數(shù)據(jù)的安全性和可靠性。 數(shù)據(jù)庫(kù)允許并發(fā)使用，能有效和及時(shí)地處理數(shù)據(jù)，并能保證數(shù)據(jù)的一致性

48、和完整性。,層次數(shù)據(jù)庫(kù),層次數(shù)據(jù)庫(kù)和網(wǎng)狀數(shù)據(jù)庫(kù)可以看作是第一代數(shù)據(jù)庫(kù)系統(tǒng)。 層次數(shù)據(jù)庫(kù)是建立在層次數(shù)據(jù)模型的基礎(chǔ)上的數(shù)據(jù)庫(kù)，層次數(shù)據(jù)模型以樹結(jié)構(gòu)來(lái)表示實(shí)體之間的聯(lián)系。 樹中的結(jié)點(diǎn)表示實(shí)體集（文件或記錄型），連線表示兩個(gè)實(shí)體之間的聯(lián)系，且這種聯(lián)系只能是一對(duì)多的。 對(duì)于多對(duì)多的聯(lián)系不能直接用層次模型表示，需要分解成兩個(gè)層次型。 層次數(shù)據(jù)庫(kù)的典型代表是IBM公司1969年誕生的IMS。,網(wǎng)狀數(shù)據(jù)庫(kù),網(wǎng)狀數(shù)據(jù)庫(kù)是建立在網(wǎng)狀數(shù)據(jù)模型的基礎(chǔ)上的數(shù)據(jù)庫(kù)，網(wǎng)狀數(shù)據(jù)模型以圖結(jié)構(gòu)來(lái)表示實(shí)體之間的聯(lián)系，這種聯(lián)系是一種多對(duì)多的聯(lián)系。 然而，多對(duì)多的聯(lián)系實(shí)現(xiàn)起來(lái)太復(fù)雜了，所以在一些實(shí)際的支持網(wǎng)狀數(shù)據(jù)模型的數(shù)據(jù)庫(kù)管理系統(tǒng)

49、上，對(duì)多對(duì)多聯(lián)系還是做了限制。如網(wǎng)狀模型的典型代表CODASYL系統(tǒng)就僅支持一對(duì)多的聯(lián)系，它按系（set）組織數(shù)據(jù)。系可理解為命了名的聯(lián)系，由一個(gè)雙親記錄和一個(gè)或多個(gè)子記錄型組成。,關(guān)系數(shù)據(jù)庫(kù),關(guān)系數(shù)據(jù)庫(kù)可以看作是第二代數(shù)據(jù)庫(kù)系統(tǒng)。 關(guān)系數(shù)據(jù)庫(kù)是建立在關(guān)系數(shù)據(jù)模型基礎(chǔ)之上的數(shù)據(jù)庫(kù)，關(guān)系數(shù)據(jù)模型用關(guān)系（即二維表格數(shù)據(jù)）表示實(shí)體之間的聯(lián)系。 通俗地講，關(guān)系就是二維表格；表格中的每一行稱作一個(gè)元組，相當(dāng)于一個(gè)記錄值；每一列是一個(gè)屬性值集，列可以命名，稱作屬性名。 由此可以說(shuō)，關(guān)系是元組的集合，如果表格有n列，則稱該關(guān)系為n元關(guān)系。,關(guān)系模型中的操作,關(guān)系模型中的操作有： 傳統(tǒng)的集合運(yùn)算：交、并、差和

50、廣義笛卡積等； 專門的關(guān)系運(yùn)算：選擇、投影、連接和除等； 有關(guān)的數(shù)據(jù)操作：查詢、插入、刪除和修改等。,對(duì)數(shù)據(jù)庫(kù)技術(shù)的研究,對(duì)數(shù)據(jù)庫(kù)技術(shù)的研究是從以下三個(gè)方面進(jìn)行的： 數(shù)據(jù)模型。數(shù)據(jù)模型的研究是數(shù)據(jù)庫(kù)系統(tǒng)的基礎(chǔ)研究，重點(diǎn)研究如何構(gòu)造數(shù)據(jù)模型，如何表示數(shù)據(jù)及其聯(lián)系。現(xiàn)在的重點(diǎn)研究課題是面向?qū)ο竽Ｐ汀?應(yīng)用領(lǐng)域。數(shù)據(jù)庫(kù)技術(shù)的最初應(yīng)用主要是信息管理領(lǐng)域，事實(shí)上，只要有大量數(shù)據(jù)要管理或者需要大批量數(shù)據(jù)支持的工作，都可以使用數(shù)據(jù)庫(kù)。 計(jì)算機(jī)技術(shù)。計(jì)算機(jī)技術(shù)的發(fā)展促進(jìn)了數(shù)據(jù)庫(kù)技術(shù)的發(fā)展。通過(guò)將計(jì)算機(jī)技術(shù)的一些研究領(lǐng)域與數(shù)據(jù)庫(kù)技術(shù)相結(jié)合，產(chǎn)生了許多新的數(shù)據(jù)庫(kù)系統(tǒng)。,第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),6.1 基本的實(shí)

51、現(xiàn)策略 6.2 動(dòng)態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,6.4.1 Josephus問(wèn)題 6.4.2 教務(wù)管理與二分圖 6.4.3 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織,Josephus問(wèn)題,Josephus問(wèn)題是由古羅馬著名史學(xué)家Josephus所提出的問(wèn)題演變而來(lái)的。Josephus問(wèn)題的提法很多，如“猴子選大王問(wèn)題”、“旅行社獎(jiǎng)游客問(wèn)題”等，就其數(shù)學(xué)本質(zhì)而言是相同的問(wèn)題。Josephus問(wèn)題的一般描述如下： 設(shè)有n個(gè)人圍坐一圈并由1到n編號(hào)。從某個(gè)人（例如編號(hào)為k的人）開始報(bào)數(shù)，數(shù)到m的人出列；接著從出列的下一個(gè)人開始

52、重新1到m報(bào)數(shù)，數(shù)到m的人又出列；如此反復(fù)地報(bào)數(shù)和出列，直到最后一個(gè)人出列為止。試設(shè)計(jì)確定這n個(gè)人出列序列的程序。,Josephus問(wèn)題（續(xù)）,由問(wèn)題描述可以很自然地聯(lián)想到循環(huán)鏈表，用循環(huán)鏈表對(duì)Josephus問(wèn)題建模，可以做到程序世界和問(wèn)題世界的完全一致性，符合面向?qū)ο蟮某绦蛟O(shè)計(jì)思想。 考慮到反復(fù)報(bào)數(shù)的過(guò)程，可選用不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，以避免報(bào)數(shù)過(guò)程中識(shí)別頭結(jié)點(diǎn)的麻煩。 由此，程序中可以先構(gòu)建一個(gè)具有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后從約定的結(jié)點(diǎn)開始1到m計(jì)數(shù)，計(jì)到m時(shí)從鏈表中刪除對(duì)應(yīng)結(jié)點(diǎn)；接著從被刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)起計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除后結(jié)束。,Josephus問(wèn)題舉例,例如，若

53、n8，m=3，k=1時(shí)，出列的序列為3，6，1，5，2，8，4，7。如下圖給出了問(wèn)題求解過(guò)程示意圖，圖中的箭頭表示當(dāng)前報(bào)數(shù)的位置，虛線框中為要出列者的序號(hào)，實(shí)黑框中為已出列者的序號(hào)，空白框中為未出列者的序號(hào)。,Josephus問(wèn)題算法描述,用C語(yǔ)言編寫利用單循環(huán)鏈表求解Josephus問(wèn)題程序如下： #include “stdio.h” #include “malloc.h” typedef struct node int num; struct node *next; linklist; linklist *creat(head,n) linklist *head; int n; linkl

54、ist *s,*p; int i; s=(linklist*)malloc(sizeof(linklist); head=s;,Josephus問(wèn)題算法描述（續(xù)）,s-num=1; p=s; for(i=2;inum=i; p-next=s; p=s; p-next=head; return head; /*creat*/,Josephus問(wèn)題算法描述（續(xù)）,linklist *select(head,m) linklist *head; int m; linklist *p,*q; int i,t; p=head; t=1; q=p; do p=q-next; t=t+1;,Josephus

55、問(wèn)題算法描述（續(xù)）,if(t%m= =0) printf(“%4d”,p-num); q-next=p-next; free(p); else q=p; while(q=p); head=p; return(head); /*select*/,Josephus問(wèn)題算法描述（續(xù)）,main() int n,m; linklist *head; printf(“input the total numbern”); scanf(“%d”, /*main */,Josephus問(wèn)題算法描述（續(xù)）,求解Josephus問(wèn)題，也可以考慮用靜態(tài)循環(huán)鏈表組織數(shù)據(jù)。由于數(shù)組下標(biāo)與n個(gè)人的編號(hào)可以一致起來(lái)（不用下

56、標(biāo)0），故僅用一維數(shù)組即可，其中數(shù)組元素作為靜態(tài)指針指向下一個(gè)人，這種實(shí)現(xiàn)方法稱作環(huán)形數(shù)組實(shí)現(xiàn)方法，程序如下： #include “stdio.h” #include “malloc.h” void Josephus(n,m,k) int m,n,k; int R; int i,j; for(i=1;in;i+) Ri=i+1;,Josephus問(wèn)題算法描述（續(xù)）,Rn=1; if(k=1) j=n; else j=k-1; /*初始化報(bào)數(shù)變量j*/ while(Rj!=j) for(i=1;i=m;i+) /*由1到m報(bào)數(shù)*/ J=Rj; printf(“%dn”,Rj);/*出列*/ Rj

57、=RRj; /*刪除第j個(gè)結(jié)點(diǎn)*/ printf(“%dn”,Rj); /*最后一個(gè)出列者*/ /*Josephus end*/,Josephus問(wèn)題算法描述（續(xù)）,void main() int n,m,k; printf(“Josephus問(wèn)題求解：”); scanf(“%d%d%d”, /*main end*/,6.4 數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用,6.4.1 Josephus問(wèn)題 6.4.2 教務(wù)管理與二分圖 6.4.3 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織,二分圖,設(shè)G=(V，E)是一個(gè)無(wú)向圖，其中V=v1，v2，vn，E e1，e2，en 。如果頂點(diǎn)集合V可以分割成為兩個(gè)互不相交的子集X和Y，使

58、圖中每條邊ei=(vi，vj)都具這樣的性質(zhì)：其一個(gè)端點(diǎn)vi是X中的頂點(diǎn)（即viX）而另一個(gè)端點(diǎn)vj是Y中的頂點(diǎn)（即vjY），則稱圖G是一個(gè)二分圖（bipartite graph）。,教務(wù)管理與二分圖,在高等學(xué)校的教務(wù)管理中，處理學(xué)生選課是一項(xiàng)日常工作。每個(gè)學(xué)生可同時(shí)選修多門課程，每門課程也允許多個(gè)學(xué)生同時(shí)選修。這種學(xué)生與課程之間的關(guān)系可以用二分圖表示為如右圖所示，圖中的頂點(diǎn)由學(xué)生和課程組成，邊（s，c）表示學(xué)生s選修課程c。,教務(wù)管理與二分圖（續(xù)）,教務(wù)員經(jīng)常需要做如下一些管理工作： 登記學(xué)生選修的課程； 撤銷學(xué)生的修課登記； 查看某個(gè)學(xué)生選修哪些課程； 查看某個(gè)課程有哪些學(xué)生選修。 這些管

59、理工作即是對(duì)二分圖做相應(yīng)的插入、刪除和檢索操作。 在現(xiàn)實(shí)社會(huì)中，諸如商店與商品、商店與顧客、技術(shù)人員與技術(shù)職稱、教師與課程等許多管理問(wèn)題都和學(xué)生與課程問(wèn)題類似，都可以用二分圖來(lái)表示。二分圖是數(shù)據(jù)庫(kù)等應(yīng)用系統(tǒng)的重要的數(shù)據(jù)結(jié)構(gòu)。,教務(wù)管理與二分圖（續(xù)）,由于二分圖中頂點(diǎn)集合V分割成為兩個(gè)互不相交的子集X和Y，同一子集中（X中或Y中）的頂點(diǎn)無(wú)邊相連，這就使得二分圖的鄰接矩陣呈現(xiàn)為一個(gè)對(duì)稱分塊矩陣： 即二分圖可以用特殊的存儲(chǔ)結(jié)構(gòu)矩陣B陣來(lái)表示。 顯然，用矩陣B表示二分圖比鄰接矩陣A節(jié)省存儲(chǔ)空間。然而矩陣B也可能是一個(gè)稀疏矩陣，可針對(duì)具體情況作進(jìn)一步的壓縮存儲(chǔ)處理，,教務(wù)管理與二分圖舉例,例如，前例中圖

60、的二分圖SCG的鄰接矩陣如下圖(a)所示，為一對(duì)稱分塊矩陣；其特殊存儲(chǔ)表示即矩陣B如下圖 (b)所示。,教務(wù)管理與二分圖（續(xù)）,教務(wù)管理中的另一項(xiàng)重要的日常工作是安排教師教學(xué)工作。在一般情況下，每位教師通?？梢詣偃味嚅T課程的教學(xué)，而在一個(gè)學(xué)期內(nèi)只講授他所勝任的一門課程；反之，在一個(gè)學(xué)期內(nèi)一門課程只需一位教師主講。這就需要對(duì)教師和課程作合理安排，我們可以用一個(gè)二分圖來(lái)表示教師與課程之間的這種關(guān)系，教師和課程都是圖中的頂點(diǎn)，邊（t，c）表示教師t勝任課程c，右圖給出了五位教師和五門課程之間關(guān)系的二分圖。,教務(wù)管理與二分圖（續(xù)）,為每位教師安排一門課程，相當(dāng)于為每個(gè)教師頂點(diǎn)選擇一條和課程頂點(diǎn)相關(guān)聯(lián)的

61、邊，使任何兩個(gè)教師頂點(diǎn)不和同一課程頂點(diǎn)相鄰接。這種安排課程給每位教師的問(wèn)題，實(shí)際上是圖的匹配問(wèn)題。圖匹配問(wèn)題的一般描述如下： 給定一個(gè)圖G=(V，E)，若邊集合E的一個(gè)子集M中任意兩條邊都不依附圖中的同一個(gè)頂點(diǎn)，稱M是圖G的一個(gè)匹配（matching）；G的邊數(shù)最多的匹配稱作G的最大匹配（maximal matching）。如果在圖G的一個(gè)匹配中，圖中每個(gè)頂點(diǎn)都是該匹配中某條邊的端點(diǎn)，則稱該匹配為圖G的完全匹配（complete matching）。圖G的任何一個(gè)完全匹配，一定都是圖G的最大匹配。,二分圖TCG的匹配和最大匹配示例,下圖(a)和(b)的實(shí)線邊分別給出了前例中二分圖TCG的一個(gè)匹

62、配和一個(gè)最大匹配的示例。,二分圖TCG的匹配和最大匹配,為了求出一個(gè)圖的最大匹配，顯而易見的辦法是列舉出該圖的全部匹配，然后選出邊數(shù)最多的一個(gè)匹配。然而，這種方法的時(shí)間復(fù)雜度是邊數(shù)的指數(shù)階函數(shù)。因此，需要一種更有效的匹配算法。 下面介紹一種利用增廣路徑求最大匹配的有效算法。 設(shè)M是圖G的一個(gè)匹配，我們將M中的邊所關(guān)聯(lián)的頂點(diǎn)稱為已匹配頂點(diǎn)，其余頂點(diǎn)稱為未匹配頂點(diǎn)。若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且在P上屬于M的邊和不屬于M 的邊交替出現(xiàn)，則稱P為一條關(guān)于M的增廣路徑（augmenting path）。,二分圖TCG的匹配和最大匹配（續(xù)）,由利用增廣路徑求最大匹配的有效算法的定義可有如

63、下結(jié)論： 一條關(guān)于M的增廣路徑的長(zhǎng)度必為奇數(shù)，且路徑上的第一條邊和最后一條邊都不屬于M。 對(duì)于一條關(guān)于M的增廣路徑P，由對(duì)稱差集運(yùn)算MP可以得到一個(gè)比M更大的匹配。即這個(gè)更大的匹配包括所有在M中但不在P中和在P中但不在M 中的邊的集合構(gòu)成。 M為G的一個(gè)最大匹配，當(dāng)且僅當(dāng)不存在關(guān)于M的增廣路徑。 結(jié)論和是顯而易見的。 對(duì)于結(jié)論，當(dāng)存在一條關(guān)于M的增廣路徑時(shí)，由結(jié)論知M不是最大匹配；反之，當(dāng)M不是最大匹配時(shí)，一定可以找到一條關(guān)于M的增廣路徑。,二分圖TCG的匹配和最大匹配（續(xù)）,事實(shí)上，設(shè)N是一個(gè)比M更大的匹配，并令=(V，MN)；因?yàn)镸和N都是G的一個(gè)匹配，所以V中的頂點(diǎn)最多和M中的一條邊相關(guān)

64、聯(lián)，也最多和N 中的一條邊相關(guān)聯(lián)；于是的每個(gè)連通分量都是由M和N中的邊交替組成的一條簡(jiǎn)單路徑或環(huán)，每個(gè)環(huán)中所含M和N的邊數(shù)相等，而每條簡(jiǎn)單路徑是一條關(guān)于M的增廣路徑或關(guān)于N的增廣路徑，由于中的邊MN所含N的邊數(shù)較M多，所以中必含一條關(guān)于M的增廣路徑。 由此，求圖G=(V，E)的最大匹配M的算法可描述如下： 置M為空集； 找出一條關(guān)于M的增廣路徑P，并用MP代替M； 重復(fù)步驟直至不存在關(guān)于M的增廣路徑，此時(shí)得到的匹配M即為G的最大匹配。,二分圖TCG的匹配和最大匹配（續(xù)）,在上述算法中，關(guān)鍵問(wèn)題是如何根據(jù)已有匹配M找出G中關(guān)于M 的一條增廣路徑。為簡(jiǎn)化起見，我們只討論G是二分圖的情形。 設(shè)M是G

65、的一個(gè)匹配，用類似于圖的廣度優(yōu)先搜索過(guò)程構(gòu)造一棵樹。設(shè)層號(hào)為i，當(dāng)i=0時(shí)取G的一個(gè)未匹配頂點(diǎn)作為樹根；當(dāng)i為奇數(shù)時(shí)，將那些與第i-1層中一個(gè)頂點(diǎn)相關(guān)聯(lián)但不屬于M的邊，連同該邊相關(guān)聯(lián)的另一個(gè)頂點(diǎn)一起添加到樹上；當(dāng)i為偶數(shù)時(shí)，則是添加那些與第i-1層中一個(gè)頂點(diǎn)相關(guān)聯(lián)且屬于M的邊以及該邊所關(guān)聯(lián)的另一個(gè)頂點(diǎn)。 如果在上述樹的構(gòu)造過(guò)程中，發(fā)現(xiàn)一個(gè)未匹配頂點(diǎn)v被作為樹的奇數(shù)層頂點(diǎn)，則從樹根到頂點(diǎn)v的路徑就是一條關(guān)于M的增廣路徑；如果在樹的構(gòu)造過(guò)程中既沒有找到增廣路徑，又無(wú)法按要求往樹上添加新的邊和頂點(diǎn)，則可在剩余頂點(diǎn)中再取一個(gè)未匹配頂點(diǎn)作樹根構(gòu)造新的一棵樹。這個(gè)過(guò)程一直進(jìn)行下去，如果不存在其它未匹配頂點(diǎn)，即最終仍未得到任何增廣路徑，就說(shuō)明M已為一個(gè)最大匹配了。,二分圖TCG的匹配和最大匹配舉例,例如，對(duì)前例圖 (a)中實(shí)線邊（圖TCG的匹配M）： 按上述方法取未匹配頂點(diǎn)t5作為樹根，頂點(diǎn)c1是樹上惟一的第一層中的頂點(diǎn)，未匹配邊（t5，c1）是樹上的一條邊； 頂點(diǎn)t2處于樹的第二層，邊（c1，t2）屬于M且關(guān)聯(lián)于c1是樹上的又一條邊； 與t2相關(guān)聯(lián)但不屬于M的邊有（t2，c4）和（t2，c5）添加到樹中，同時(shí)頂點(diǎn)c4和c5添加到樹中作為第三層； 由于c5是未匹配頂點(diǎn)， 所以到此找到了一條增廣路徑P：t5c1t2c5。