《《算法與數(shù)據(jù)結(jié)構(gòu)》第6章數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第6章數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn)ppt.ppt（132頁珍藏版）》請?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)是對程序中數(shù)據(jù)信息的結(jié)構(gòu)組織，供給定問題求解算法的控制結(jié)構(gòu)來處理。 Niklaus wirth曾經(jīng)給出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的公式，得到了計(jì)算機(jī)科學(xué)界的普遍認(rèn)可。 在程序設(shè)計(jì)語言中如何表示數(shù)據(jù)和控制，很大程度上決定了如何使用這個語言來編寫程序；所以在程序設(shè)計(jì)語言中不僅提供了與程序控制流程有關(guān)的控制結(jié)構(gòu)，同時也提供了與程序中數(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ù)）把逐級分解得到的一系列基本操作組織起來，形成用某種特定語言書寫的源程序。,數(shù)據(jù)

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

3、與程序中數(shù)據(jù)信息組織有關(guān)的數(shù)據(jù)結(jié)構(gòu)，但沒有也不可能提供所有的數(shù)據(jù)結(jié)構(gòu)。 一方面，受科學(xué)技術(shù)和生產(chǎn)力發(fā)展水平的限制，人類認(rèn)知世界具有歷史局限性；人們不可能在某一天完成對現(xiàn)實(shí)世界的認(rèn)知過程，同樣也不可能在某一天說對數(shù)據(jù)結(jié)構(gòu)的認(rèn)知過程已經(jīng)完結(jié)，這種認(rèn)知過程是一個漸進(jìn)式不斷深化和逐步完善的過程。 另一方面，受計(jì)算機(jī)科學(xué)發(fā)展和計(jì)算機(jī)系統(tǒng)本身的限制，人們不可能研制出一種設(shè)施包羅萬象、功能應(yīng)有盡有的計(jì)算機(jī)語言和語言翻譯系統(tǒng)。 因此，程序設(shè)計(jì)語言中只可能提供一些基本的和常用的數(shù)據(jù)結(jié)構(gòu)設(shè)施，并提供一些構(gòu)造求解現(xiàn)實(shí)世界中問題所需數(shù)據(jù)結(jié)構(gòu)的基本設(shè)施和方法手段。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡單數(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),簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),簡單的數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計(jì)語言中已經(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ù)據(jù)變量的類型就可以直接使用了，如C語言中的int，unsigned int，long int，short int，unsigned short int，char，float和double等。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡單數(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),還有一些簡單類型和構(gòu)造類型，也是在程序設(shè)計(jì)語言中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。如枚舉型、子界型、日期型、集合、數(shù)組、字符串、記錄、文件等。 程序設(shè)計(jì)語言中提供了程序設(shè)計(jì)人員在程序中說明這些數(shù)據(jù)類型的方法，程序設(shè)計(jì)人員只要在程序中的適當(dāng)位置按照相應(yīng)的格式和要求對程序中的數(shù)據(jù)進(jìn)行說明就可以使用了。如C語言中的枚舉、數(shù)組、字符串、結(jié)構(gòu)體、共同體、文件等。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡單數(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īng)的數(shù)據(jù)類型，程序設(shè)計(jì)人員不能夠在程序中用類型說明的辦法直接引入。 然而，許多程序設(shè)計(jì)語言都提供有指針類型，程序設(shè)計(jì)人員可以利用指針類型在程序中動態(tài)建立所需要的某種數(shù)據(jù)結(jié)構(gòu)。 一般地，在建立某種數(shù)據(jù)結(jié)構(gòu)之前，先需要說明其數(shù)據(jù)元素的結(jié)點(diǎn)類型，如說明成記錄、結(jié)構(gòu)體等，再用指針變量動態(tài)建立起相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以供求解問題的程序使用或處理。,6.1 基本的實(shí)現(xiàn)策略,6.1.1 簡單數(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ì)語言中沒有提供指針變量，就不能動態(tài)實(shí)現(xiàn)程序中需要的數(shù)據(jù)結(jié)構(gòu)；還有一些數(shù)據(jù)結(jié)構(gòu)，不宜借助指針來實(shí)現(xiàn)，如順序表、順序棧、順序隊(duì)列等。對于這兩種情況，程序設(shè)計(jì)人員都可以在程序中利用數(shù)組模擬實(shí)現(xiàn)程序中需要的一些數(shù)據(jù)結(jié)構(gòu)。 數(shù)組是每一種高級程序設(shè)計(jì)語言都提供了的數(shù)據(jù)結(jié)構(gòu)?？梢岳靡痪S數(shù)組模擬實(shí)現(xiàn)順序表、順序棧、順序隊(duì)列。可以利用二維數(shù)組模擬實(shí)現(xiàn)鏈表或循環(huán)鏈表，其中一列描寫一個數(shù)據(jù)元素（或結(jié)點(diǎn)）；若構(gòu)成數(shù)據(jù)元素各字段類型不一致，也可改用兩個或多個一維數(shù)組來模擬實(shí)現(xiàn)之?？捎萌齻€一維數(shù)組來模擬實(shí)現(xiàn)二叉樹，其中一個數(shù)組存放數(shù)據(jù)域的值，兩個數(shù)

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

9、），數(shù)據(jù)所需存儲空間是一個固定的有限區(qū)域，可在程序說明中顯式規(guī)定，在編譯時靜態(tài)進(jìn)行存儲分配。 凡是可以用指針動態(tài)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，都可以利用數(shù)組靜態(tài)地模擬實(shí)現(xiàn)。有時也把這種利用數(shù)組靜態(tài)模擬實(shí)現(xiàn)了的動態(tài)結(jié)構(gòu)稱之為半靜態(tài)數(shù)據(jù)結(jié)構(gòu)（semi-static data structure）。當(dāng)然，半動態(tài)結(jié)構(gòu)中也包含可變數(shù)組和變長記錄等部分采用靜態(tài)分配、部分采用動態(tài)分配的數(shù)據(jù)結(jié)構(gòu)。,6.2 動態(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è)計(jì)語言編寫程序時，鏈表的實(shí)現(xiàn)是

10、很簡單和很自然的。如果語言中沒有提供指針類型，可以用數(shù)組來模擬實(shí)現(xiàn)鏈表結(jié)構(gòu)，并稱之為靜態(tài)鏈表（static linked list），用以記錄類型作為基類型的數(shù)組來模擬實(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)識符*/ snode smaxsize; /*s為基類型是snode的一維數(shù)組，即記錄數(shù)組*/,靜態(tài)鏈表（續(xù)）,注意這里的next域說明與單鏈表

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

12、二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實(shí)現(xiàn),二叉樹的靜態(tài)二叉鏈表表示法,對于沒有提供指針類型的高級程序設(shè)計(jì)語言，程序中要用到二叉樹結(jié)構(gòu)組織數(shù)據(jù)信息，可用靜態(tài)二叉鏈表（static binary linked list）表示法實(shí)現(xiàn)二叉樹結(jié)構(gòu)。和靜態(tài)鏈表類似，靜態(tài)二叉鏈表的存儲區(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)體*/

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

14、叉樹的靜態(tài)二叉鏈表表示法舉例,6.2 動態(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)鏈表和靜態(tài)二叉鏈表來實(shí)現(xiàn)。 樹和森林還有一種存儲表示方法，就是雙親表示法。因?yàn)闃浜蜕种械拿恳粋€結(jié)點(diǎn)，其雙親結(jié)點(diǎn)是惟一的；利用這一性質(zhì)，在存儲結(jié)點(diǎn)信息時為每個結(jié)點(diǎn)增加一個指向其雙親的指針parent，就可以惟一地表示樹或森林。 若用靜態(tài)鏈表實(shí)現(xiàn)樹和森林的雙親表示法，其類型定

15、義如下： #define maxsize 100 typedef struct elementype data; int parent; sptnode; sptnode ptmaxsize;,樹和森林的雙親表示法,6.2 動態(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個葉子結(jié)點(diǎn)的哈夫曼樹有2n-1個結(jié)點(diǎn)，所以可用大小為2n-1個元素的數(shù)組構(gòu)造靜態(tài)鏈表來存儲哈夫曼樹，一個數(shù)組元素中存放一個結(jié)點(diǎn)。 結(jié)點(diǎn)的結(jié)構(gòu)可以這樣來考

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

17、續(xù)),由于在實(shí)際構(gòu)造哈夫曼樹時，是由葉子結(jié)點(diǎn)的權(quán)值逐級構(gòu)造最后生成樹根，且在構(gòu)造過程中僅與葉子結(jié)點(diǎn)的權(quán)值有關(guān)而與葉子結(jié)點(diǎn)的數(shù)據(jù)域值無關(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)

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

19、 scanf(“%d”,,建立哈夫曼樹的算法的描述(續(xù)),for(i=0;i

20、意，在建立哈夫曼樹的算法描述中，有效地利用了每個結(jié)點(diǎn)的雙親域parent的值是否為-1來區(qū)分該結(jié)點(diǎn)是否是哈夫曼森林中一棵樹的根結(jié)點(diǎn)；每次是在根結(jié)點(diǎn)中找出兩個權(quán)重值weight最小的樹作為左右子樹構(gòu)造一棵更大的樹。,求哈夫曼編碼的方法,求哈夫曼編碼的方法是，在已建好的哈夫曼樹中從每個葉子結(jié)點(diǎn)開始沿雙親鏈域回退到根結(jié)點(diǎn)，每回退一步走過哈夫曼樹的一個分枝得到一位哈夫曼編碼值；由于每個葉子結(jié)點(diǎn)的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)的路徑上各分枝代碼所組成的0、1序列，所以先得到的分枝代碼為所求編碼的低位碼而后得到的為高位碼。 對于每個葉子結(jié)點(diǎn)的哈夫曼編碼可以考慮用一個一維數(shù)組bit從后向前依次保存所求得

21、的各位編碼值，并用start記住編碼在數(shù)組bit中的開始位置。由此可做如下的類型定義： #define maxbit 10 typedef struct int bitmaxbit; int start; hcodetype; /*定義哈夫曼編碼類型*/,求哈夫曼編碼的算法描述,從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)逆向求每個葉子結(jié)點(diǎn)所代表值的哈夫曼編碼的算法可描述如下： void gethuffmancode(htnode ht,int n) int i,j,c,p; hcodetype cdn; for(i=0;i

22、rent; if(htp.lchild==c) /*如果c是p的左孩子*/ cdi.bitj=0; else cdi.bitj=1; c=p; while(p!= -1);,求哈夫曼編碼的算法描述(續(xù)),cdi.start=j; for(i=0;i

23、5，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)造的哈夫曼樹如下左圖所示。按gethuffmancode算法求得的哈夫曼編碼在cd數(shù)組中的狀態(tài)如下右圖所示。,求哈夫曼編碼的算法舉例(續(xù)),其存儲結(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 動態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應(yīng)用,6.3 大批量數(shù)據(jù)的組織策略,6.3.1

24、文件的組織 6.3.2 數(shù)據(jù)庫技術(shù),1.文件的基本概念,文件的概念和線性表類似，是由大量性質(zhì)相同的記錄組成的集合；二者的區(qū)別在于線性表是把記錄全部組織在內(nèi)存儲器中，而文件則是把大量記錄都組織在外存儲器中。 按照記錄的類型，可以把文件分為操作系統(tǒng)文件和數(shù)據(jù)庫文件兩大類。 操作系統(tǒng)文件中的記錄只是一個字符序列，無結(jié)構(gòu)，無解釋，僅是為了加工，存取的方便劃分的字符組。 而數(shù)據(jù)庫文件中的記錄是有結(jié)構(gòu)的，可以由一個或多個數(shù)據(jù)項(xiàng)組成，是存取文件中數(shù)據(jù)的基本單位；數(shù)據(jù)項(xiàng)是不可再分的最基本單位，也是文件中可使用數(shù)據(jù)的最小單位。,文件的基本概念（續(xù)）,按照記錄的長度特性，可以把文件分為定長記錄文件和不定長記錄文件

25、。 定長記錄文件中每個記錄含有的信息長度相同， 不定長記錄文件中每個記錄含有的信息長度不等。 按照記錄中關(guān)鍵字的多少，可以把文件分為單關(guān)鍵字文件和多關(guān)鍵字文件。 單關(guān)鍵字文件中的記錄只有一個惟一標(biāo)識記錄的主關(guān)鍵字； 多關(guān)鍵字文件中的記錄除了主關(guān)鍵字外，還含有一個或多個次關(guān)鍵字，記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)稱作記錄的屬性。,文件的基本概念（續(xù)）,記錄有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之分。 邏輯結(jié)構(gòu)是指記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方式；用戶讀寫一個記錄是指邏輯記錄。 記錄的物理結(jié)構(gòu)是數(shù)據(jù)在物理存儲器上存儲的方式，是數(shù)據(jù)的物理表示和組織方式。一個物理記錄是指計(jì)算機(jī)用一條I/O命令

26、進(jìn)行讀寫的基本數(shù)據(jù)單位，對于固定的設(shè)備和操作系統(tǒng)，它的大小基本上是固定不變的； 而邏輯記錄的大小是根據(jù)使用的需要確定的。 一個物理記錄可以存放一個或多個邏輯記錄，多個物理記錄可以表示一個邏輯記錄。用戶讀寫的是邏輯記錄，查找其對應(yīng)的物理記錄是操作系統(tǒng)的職責(zé)。,文件的基本概念（續(xù)）,文件的操作有三類，檢索、修改和排序。 檢索的方式有三種： 順序檢索，按記錄的相對位置檢索下一個邏輯記錄； 按記錄號檢索，根據(jù)記錄存入文件時的順序編號，檢索第i個邏輯記錄； 按關(guān)鍵字檢索，檢索關(guān)鍵字值與給定值相關(guān)的一個或多個邏輯記錄，在數(shù)據(jù)庫文件中又可按給定關(guān)鍵字值、給定關(guān)鍵字的范圍、給定關(guān)鍵字的某個函數(shù)以及組合條件等方

27、式進(jìn)行檢索。 修改操作包括插入、刪除和更新一個記錄這三種操作。 排序操作則是為了檢索方便高效對文件中記錄的重新有序整理。,文件的基本概念（續(xù)）,文件的操作可以有實(shí)時和批處理兩種不同的方式。 實(shí)時處理通常對應(yīng)答時間要求嚴(yán)格，應(yīng)在接收詢問后立即完成相應(yīng)的操作； 而批處理則不同，可以根據(jù)需要對積累一段時間的記錄進(jìn)行成批處理。 文件在存儲介質(zhì)上的組織方式（即物理結(jié)構(gòu)）有順序組織、隨機(jī)組織和鏈?zhǔn)浇M織等基本方式，具體選用哪種方式應(yīng)結(jié)合存儲介質(zhì)類型（磁盤、磁帶等）、記錄類型、記錄大小、關(guān)鍵字?jǐn)?shù)目以及對文件進(jìn)行何種操作等各種因素綜合考慮。,2.順序文件,順序文件（sequential file）是把記錄按建立

28、文件時的邏輯順序依次存放在外存儲器中，文件中的物理記錄順序和邏輯記錄順序一致。 若次序相繼的兩個物理記錄在存儲器上的存儲位置是相鄰的，則又稱為連續(xù)文件； 若物理記錄之間的次序由指針鏈接，則稱為串聯(lián)文件。 順序文件的存取方式是根據(jù)記錄號或記錄的相對位置進(jìn)行的，其特點(diǎn)是： 存取第i個記錄必須先搜索在它之前的i-1個記錄； 插入的新記錄只能加在文件的未尾； 若要更新文件中的某個記錄，必須在整個文件的復(fù)制過程中進(jìn)行。,順序文件（續(xù)）,由于順序文件的優(yōu)點(diǎn)是連續(xù)存取速度快，因此主要用于順序存取和批量修改的情況。 若對應(yīng)答時間要求不嚴(yán)時亦可進(jìn)行直接存取。 在對順序文件作修改時，可對原文件中的記錄復(fù)制一遍，并

29、在復(fù)制的過程中插入新的記錄、跳過待刪除的記錄、或用修改過的新記錄代替原記錄。 為了修改方便起見，要求待修改文件按關(guān)鍵字有序（對非數(shù)據(jù)庫文件可將邏輯記錄號作為關(guān)鍵字）。,順序文件（續(xù)）,磁帶是一種典型的順序存取設(shè)備，存儲在磁帶上的文件就是順序文件。然而現(xiàn)在很少使用磁帶，較多使用的是磁盤上的順序文件。對磁盤上的順序文件進(jìn)行修改時，若不增加記錄的長度，也可在原文件上直接修改而不必復(fù)制文件。 對順序文件進(jìn)行順序檢索的方法類似于靜態(tài)表的順序檢索，其平均檢索長度為(n+1)/2，其中n為文件中所含物理記錄的數(shù)目（內(nèi)存檢索時間可以忽略不計(jì)）。也可以對磁盤文件進(jìn)行分塊檢索或二分法檢索。但當(dāng)文件很大時，二分法檢

30、索將會引起磁頭在存儲文件的多個柱面之間來回移動而增加檢索時間。,3.索引文件,除了主文件（即數(shù)據(jù)文件）之外，再建立一張索引表來指示邏輯記錄和物理記錄之間的一一對應(yīng)關(guān)系；索引表中的每一項(xiàng)稱作索引項(xiàng)，由記錄的關(guān)鍵字和記錄的存放地址構(gòu)成；把索引表和主文件總稱為索引文件（indexed file）。 索引表通常是按關(guān)鍵字的升序排列。若主文件也按關(guān)鍵字升序排列，則構(gòu)成的索引文件稱作索引順序文件； 若主文件是無序的，則稱所構(gòu)造的索引文件為索引非順序文件。,索引文件（續(xù)）,索引文件只適用于直接存取的外存儲器（如磁盤）。索引文件的存儲分索引區(qū)和數(shù)據(jù)區(qū)來進(jìn)行，索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。 在輸入記錄建立

31、數(shù)據(jù)區(qū)的同時建立索引表，表中的索引項(xiàng)按記錄輸入的先后次序排列；待全部記錄輸入完畢后再對索引表按關(guān)鍵字排序，排序后的索引表和主文件一起構(gòu)成了索引文件。,索引非順序文件舉例,索引文件（續(xù)）,索引文件的檢索，應(yīng)先在索引表中檢索。若在索引表中找到關(guān)鍵字值等于給定值的索引項(xiàng)，則按索引項(xiàng)指示從外部存儲器讀取該記錄；否則說明待檢索記錄不存在無需訪問外存儲器。 相對于記錄而言索引項(xiàng)長度較小，即由索引項(xiàng)構(gòu)成的索引表所占空間較小，通?？梢淮巫x入內(nèi)存。然而當(dāng)主文件中記錄數(shù)目很大時，索引表仍可能超出一個物理塊的容量，這樣對索引表的檢索就可能需要多次訪問外存儲器。 為此，可對索引表再次建立二級索引；檢索時先在二級索引中

32、找，再檢索索引表，然后讀取記錄。 索引表和二級索引表都是有序表，在內(nèi)存儲器中可用檢索效率較高的方法如二分法檢索方法進(jìn)行檢索。,4.ISAM文件,ISAM（indexed sequential access method）即索引順序存取方法，是一種專為磁盤存取設(shè)計(jì)的文件組織方式。 由于磁盤是以盤組、柱面和磁道三級地址存取的設(shè)備，所以可以對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。 文件的記錄在同一盤組上存放時，應(yīng)先集中放在一個柱面上，然后再順序存放在相鄰柱面上；對同一柱面，則應(yīng)按盤面的次序順序存放。,ISAM文件結(jié)構(gòu)舉例,ISAM文件（續(xù)）,在一個磁盤組上的ISAM文件，每個柱面建立一個磁道

33、索引，每個磁道索引項(xiàng)由基本索引項(xiàng)和溢出索引項(xiàng)兩部分組成，每一部分都包括關(guān)鍵字和指針兩個域，前者表示該磁道中最大關(guān)鍵字，后者指示該磁道中第一個記錄的位置。 柱面索引的每一個索引項(xiàng)也由關(guān)鍵字和指針兩部分組成，前者表示該柱面中的最大關(guān)鍵字，后者指示該柱面上的磁道索引位置。 柱面索引存放在某個柱面上，若柱面索引較大占多個磁道時，則可建立柱面索引的一個主索引。,ISAM文件（續(xù)）,在ISAM文件上檢索記錄時，先從主索引出發(fā)找到相應(yīng)的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直至找到為止；反之，若找遍磁道而不存在此記錄

34、，則表明文件中無此記錄。 在前例中為每個柱面開辟了一個溢出區(qū)，并在磁道索引項(xiàng)中有溢出索引項(xiàng)（后面兩個域），這是為插入記錄所設(shè)置的。,ISAM文件（續(xù)）,由于ISAM文件中記錄是按關(guān)鍵字順序存放的，在插入一個記錄時需要向后移動記錄，并將同一磁道上的最后一個記錄移至溢出區(qū)，同時修改磁道索引項(xiàng)。除了為每個柱面設(shè)置一個溢出區(qū)的方法外，還可只集中設(shè)置一個大的公共溢出區(qū)；也可以既為每個柱面設(shè)置溢出區(qū)，同時也設(shè)置了一個公共溢出區(qū)，在柱面溢出區(qū)滿后再使用公共溢出區(qū)。 ISAM文件中刪除記錄比較簡單，只需作刪除標(biāo)記而不用移動記錄或改變指針。當(dāng)然應(yīng)該周期性地把記錄讀入內(nèi)存重排整理ISAM文件，以盡量填滿基本區(qū)而空

35、出溢出區(qū)。,5.VSAM文件,VSAM（virtual storage access method）即虛擬存儲存取方法。它利用了操作系統(tǒng)的虛擬存儲器的功能，使用戶只需考慮控制區(qū)間等邏輯存儲單位，而無需考慮其物理位置以及何時對外存儲器進(jìn)行讀寫操作，給用戶使用文件提供了方便。 VSAM文件的結(jié)構(gòu)由索引集、順序集和數(shù)據(jù)集三部分組成。 數(shù)據(jù)集存放文件的所有記錄， 順序集和索引集構(gòu)成一棵B+樹是文件的索引部分。數(shù)據(jù)集中的一個結(jié)點(diǎn)稱為控制區(qū)間（control interval），它由一組連續(xù)的存儲單元組成，是讀寫操作的基本單位。,VSAM文件的結(jié)構(gòu)舉例,VSAM文件（續(xù)）,同一文件上的控制區(qū)間大小相同，含

36、有一個或多個按關(guān)鍵字升序排列的記錄。 順序集中的一個結(jié)點(diǎn)，存放著若干相鄰控制區(qū)間的索引項(xiàng)，每個索引項(xiàng)由控制區(qū)間中的最大關(guān)鍵字和指向該控制區(qū)間的指針組成。 順序集中的一個結(jié)點(diǎn)連同其下層所有控制區(qū)間形成的整體稱作控制區(qū)域（control range）。 順序集中的結(jié)點(diǎn)之間用指針相鏈接；在它們上層的結(jié)點(diǎn)又以它們?yōu)榛A(chǔ)形成索引，并逐級向上建立索引，形成B+樹的非終端結(jié)點(diǎn)。,VSAM文件（續(xù)）,對VSAM文件中記錄的檢索，既可以從最高層的索引逐層往下按關(guān)鍵字進(jìn)行查找，又可以在順序集中沿著指針鏈順序查找。 VSAM文件沒有專門的溢出區(qū)，但可利用控制區(qū)間中的空隙或控制區(qū)域中空的控制區(qū)間來插入記錄（即在B+樹

37、上插入記錄）。 在控制區(qū)間中插入記錄時，為了保證區(qū)間內(nèi)記錄按關(guān)鍵字有序需要移動記錄；而當(dāng)區(qū)間中記錄已滿時，為了插入記錄需要將區(qū)間分裂。 在VSAM文件中刪除記錄時，也是需要移動記錄的。,VSAM文件（續(xù)）,VSAM文件占有較多的存儲空間，存儲空間的利用率一般也只能保持在75%左右。 然而它具有許多優(yōu)點(diǎn)，如動態(tài)地分配和釋放存儲空間，無需像ISAM文件那樣定期重排文件，并能較快地執(zhí)行插入操作和保持較高的檢索效率。 VSAM文件通常作為組織大型索引順序文件的標(biāo)準(zhǔn)形式。,6.散列文件,散列文件（Hash file）也稱作直接存取文件，它是利用哈希方法組織的數(shù)據(jù)文件；即根據(jù)某個哈希函數(shù)和一定的沖突消解策

38、略而得到的存放在外存儲器上的散列表。 與哈希表不同的是，磁盤上的文件記錄通常是成組存放的。 若干個記錄組成一個存儲單位，在散列文件中這個存儲單位稱作桶。 一個桶能存放的邏輯記錄的總數(shù)稱作桶的容量。假如桶的容量為m，即m個同義詞的記錄可以存放在同一地址的桶中，當(dāng)?shù)趍+1個同義詞記錄出現(xiàn)時則發(fā)生溢出。處理溢出也可采用哈希表中的各種處理沖突的方法，但對散列文件主要是采用鏈地址法消解沖突。,散列文件（續(xù)）,當(dāng)發(fā)生溢出時，需要將第m+1個同義詞存放到另一個桶中，通常稱作“溢出桶”；相應(yīng)地把存放前m個同義詞的桶稱作“基桶”。 溢出桶可以有多個，它們和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒有檢索到

39、待查記錄時，就順指針?biāo)傅揭绯鐾爸腥z索； 因此，同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好是在同一柱面上。,散列文件舉例,例如，某文件有20個記錄，其關(guān)鍵字分別為28、19、13、93、89、25、14、55、69、8、9、16、21、33、81、62、11、71、34、35。用除留余數(shù)法選定哈希函數(shù)H(key)= key%7，用鏈地址法消解地址沖突。桶的容量m=3，基桶個數(shù)b=7，由此得到的散列文件如下圖所示。,散列文件（續(xù)）,在散列文件中檢索時： 先根據(jù)給定的關(guān)鍵字值k求得哈希地址，即基桶號； 然后將基桶的記錄讀入內(nèi)存進(jìn)行順序檢索，若找到關(guān)鍵字值為k的記錄則檢索成功；

40、 若基桶中雖無關(guān)鍵字值為k的記錄但指針域非空，需要把溢出桶中的記錄讀入內(nèi)存繼續(xù)檢索，直到檢索成功或檢索不成功。 檢索不成功的情況為基桶沒有填滿記錄，或雖填滿但指針域?yàn)榭眨o溢出桶），或雖有溢出桶但仍未找到關(guān)鍵字為k的記錄。,散列文件（續(xù)）,在散列文件中，裝填因子為 ，其中n為文件中的記錄數(shù)，b為桶數(shù)，m為桶的容量；而存取桶數(shù)的期望值為 。如上例， 。在散列文件中，刪除記錄時僅需對被刪記錄作一刪除標(biāo)記即可。 總之，散列文件的優(yōu)點(diǎn)是插入和刪除方便，存取速度比索引文件要快；不需要索引區(qū)，節(jié)省存儲空間。其缺點(diǎn)是不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式只有簡單詢問；在經(jīng)過

41、多次的插入和刪除之后，也可能造成溢出桶滿而基桶內(nèi)多數(shù)為被刪除記錄的不合理文件結(jié)構(gòu)，亦需對文件進(jìn)行重新整理。,7.多關(guān)鍵字文件,多關(guān)鍵字文件（multiple key file）的特點(diǎn)是，在對文件進(jìn)行檢索操作時不僅對主關(guān)鍵字進(jìn)行簡單詢問，還經(jīng)常需要對次關(guān)鍵字進(jìn)行其它類型的詢問檢索。 因此，對多關(guān)鍵字文件還需要建立一系列的次關(guān)鍵字索引。次關(guān)鍵字索引和主關(guān)鍵字索引所不同的是，每個索引項(xiàng)應(yīng)包含次關(guān)鍵字和具有同一次關(guān)鍵字的多個記錄的主關(guān)鍵字或物理記錄號。 多重表文件和倒排文件是常見的兩種多關(guān)鍵字文件組織方法。,多關(guān)鍵字文件（續(xù)）,多重表文件（multilist file）的特點(diǎn)是，記錄按主關(guān)鍵字的順序構(gòu)

42、成一個串聯(lián)文件，并建立主關(guān)鍵字索引（稱為主索引）；對每一個次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個鏈表。 主索引為非稠密索引，一組記錄建立一個索引項(xiàng)；次索引為稠密索引，每個記錄建立一個索引項(xiàng)，每個索引項(xiàng)包括次關(guān)鍵字、頭指針和鏈表長度。,多關(guān)鍵字文件舉例,例如，下圖所示為一個多重表文件。其中工號為主關(guān)鍵字，記錄按工號順序鏈接。,多關(guān)鍵字文件舉例（續(xù)）,對工號非稠密索引分成三個子鏈表，其索引如下圖(b)所示，索引項(xiàng)中的主關(guān)鍵字為各組中關(guān)鍵字的最大值。職稱和專業(yè)是兩個次關(guān)鍵字項(xiàng)，其索引分別如下圖(c)和(d)所示，具有相同次關(guān)鍵字值的記錄鏈接在同一鏈表中。,多關(guān)鍵

43、字文件（續(xù)）,有了這些次關(guān)鍵字索引，根據(jù)關(guān)鍵字值找到鏈表頭指針，然后從頭指針出發(fā)可列出鏈表中所有記錄。比如查詢數(shù)學(xué)專業(yè)的教授，可以專業(yè)索引表中找到“數(shù)學(xué)”的頭指針和表長，逐一讀取記錄查看哪些記錄的職稱為教授即可。此查詢也可從職稱索引入手進(jìn)行。當(dāng)然，較好的方法是先讀長度較短的鏈表中的記錄。 在多重表文件中插入一個記錄是容易的，只要修改指針將記錄插在鏈表的頭指針之后即可。然而要刪去一個記錄卻很繁瑣 ，需要在每個次關(guān)鍵字的鏈表中刪去該記錄。,多關(guān)鍵字文件（續(xù)）,倒排文件（inverted file）和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。倒排文件的次關(guān)鍵字索引稱為倒排表，在倒排表的索引項(xiàng)中沒有

44、頭指針和鏈長度，而是直接用一個項(xiàng)存放具有同一關(guān)鍵字的所有記錄的物理記錄號或主關(guān)鍵字值。值得注意的是，倒排表中具有同一次關(guān)鍵字的記錄號是有序排列的。上例的倒排表如下圖所示：,多關(guān)鍵字文件（續(xù)）,倒排表作索引的好處在于檢索記錄較快。特別是對某些詢問，不用讀取記錄就可得到答案。例如上例查詢數(shù)學(xué)專業(yè)教授，只要將“數(shù)學(xué)”索引中的記錄號和“教授”索引中的記錄號求集合的交集運(yùn)算就可以了，即2，5，92，6=2就得到記錄號為2者便是數(shù)學(xué)教授。 在插入和刪除記錄時，倒排表也要進(jìn)行相應(yīng)修改；需要移動索引項(xiàng)中記錄號以保持其有序排列。若數(shù)據(jù)文件是索引順序文件（如ISAM文件），倒排表中應(yīng)存放記錄的主關(guān)鍵字而不是物理記

45、錄號。 倒排文件的缺點(diǎn)是維護(hù)困難。同一倒排表中各項(xiàng)長度不同，不同倒排表的長度也不同，這些都給倒排文件的維護(hù)帶來一定的困難。,6.3 大批量數(shù)據(jù)的組織策略,6.3.1 文件的組織 6.3.2 數(shù)據(jù)庫技術(shù),文件系統(tǒng)的缺陷,利用文件組織大批量數(shù)據(jù)是數(shù)據(jù)組織中行之有效的方法，然而，文件系統(tǒng)也存在著一些明顯的缺陷。如： 數(shù)據(jù)冗余大。因?yàn)槊總€文件都是為特定用途設(shè)計(jì)的，因此會造成同樣的數(shù)據(jù)在多個文件中的重復(fù)存儲。 數(shù)據(jù)的不一致性，這往往是由于數(shù)據(jù)冗余所造成的；在數(shù)據(jù)更新時，稍有不慎就會造成同一數(shù)據(jù)在不同文件中的不一致。 程序和數(shù)據(jù)之間的獨(dú)立性差。應(yīng)用程序依賴于文件的存儲結(jié)構(gòu)，使得在對文件的存儲結(jié)構(gòu)進(jìn)行修改時

46、，必須修改應(yīng)用程序。 數(shù)據(jù)聯(lián)系弱。文件與文件之間是獨(dú)立的，文件之間的聯(lián)系必須通過程序來構(gòu)造。因此，文件系統(tǒng)是一個不具有彈性的無結(jié)構(gòu)的數(shù)據(jù)集合，難以反應(yīng)客觀世界中事物之間的聯(lián)系。,數(shù)據(jù)庫技術(shù)誕生,為了克服上述文件系統(tǒng)的不足，20世紀(jì)60年代后期開始誕生了解決大批量數(shù)據(jù)組織和管理的數(shù)據(jù)庫技術(shù)。數(shù)據(jù)庫技術(shù)誕生的標(biāo)志性事件是： 1968年研制成功，1969年形成產(chǎn)品的美國IBM公司的數(shù)據(jù)庫管理系統(tǒng)IMS（information management system）的問世，該系統(tǒng)支持的是層次數(shù)據(jù)模型。 美國數(shù)據(jù)系統(tǒng)語言協(xié)會CODASYL（conference on data system languag

47、e）下屬的數(shù)據(jù)庫任務(wù)組DBTG（database task group）對數(shù)據(jù)庫方法進(jìn)行了系統(tǒng)的研究，在20世紀(jì)60年代末期和70年代初期發(fā)表了若干個報(bào)告（稱為DBTG報(bào)告），該報(bào)告建立了數(shù)據(jù)庫的許多概念、方法和技術(shù)。DBTG所提議的方法是基于網(wǎng)狀數(shù)據(jù)模型的。 從1970年起，IBM的研究員E.F.Codd發(fā)表了一系列的論文，提出了數(shù)據(jù)庫的關(guān)系模型，開創(chuàng)了數(shù)據(jù)庫關(guān)系方法和關(guān)系數(shù)據(jù)理論的研究，為關(guān)系數(shù)據(jù)庫的發(fā)展和理論研究奠定了基礎(chǔ)。,數(shù)據(jù)庫技術(shù),數(shù)據(jù)庫技術(shù)發(fā)展到現(xiàn)在，已經(jīng)是一門非常成熟的技術(shù)，作為算法與數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)課程。 概括地講，數(shù)據(jù)庫具有如下基本特征： 數(shù)據(jù)庫是相互關(guān)聯(lián)的數(shù)據(jù)的集合。

48、數(shù)據(jù)庫用綜合的方法組織數(shù)據(jù)，并保證盡可能高的訪問效率。 數(shù)據(jù)庫具有較小的數(shù)據(jù)冗余，可供多個用戶共享。 數(shù)據(jù)庫具有較高的數(shù)據(jù)獨(dú)立性。 數(shù)據(jù)庫具有安全控制機(jī)制，能夠保證數(shù)據(jù)的安全性和可靠性。 數(shù)據(jù)庫允許并發(fā)使用，能有效和及時地處理數(shù)據(jù)，并能保證數(shù)據(jù)的一致性和完整性。,層次數(shù)據(jù)庫,層次數(shù)據(jù)庫和網(wǎng)狀數(shù)據(jù)庫可以看作是第一代數(shù)據(jù)庫系統(tǒng)。 層次數(shù)據(jù)庫是建立在層次數(shù)據(jù)模型的基礎(chǔ)上的數(shù)據(jù)庫，層次數(shù)據(jù)模型以樹結(jié)構(gòu)來表示實(shí)體之間的聯(lián)系。 樹中的結(jié)點(diǎn)表示實(shí)體集（文件或記錄型），連線表示兩個實(shí)體之間的聯(lián)系，且這種聯(lián)系只能是一對多的。 對于多對多的聯(lián)系不能直接用層次模型表示，需要分解成兩個層次型。 層次數(shù)據(jù)庫的典型代表

49、是IBM公司1969年誕生的IMS。,網(wǎng)狀數(shù)據(jù)庫,網(wǎng)狀數(shù)據(jù)庫是建立在網(wǎng)狀數(shù)據(jù)模型的基礎(chǔ)上的數(shù)據(jù)庫，網(wǎng)狀數(shù)據(jù)模型以圖結(jié)構(gòu)來表示實(shí)體之間的聯(lián)系，這種聯(lián)系是一種多對多的聯(lián)系。 然而，多對多的聯(lián)系實(shí)現(xiàn)起來太復(fù)雜了，所以在一些實(shí)際的支持網(wǎng)狀數(shù)據(jù)模型的數(shù)據(jù)庫管理系統(tǒng)上，對多對多聯(lián)系還是做了限制。如網(wǎng)狀模型的典型代表CODASYL系統(tǒng)就僅支持一對多的聯(lián)系，它按系（set）組織數(shù)據(jù)。系可理解為命了名的聯(lián)系，由一個雙親記錄和一個或多個子記錄型組成。,關(guān)系數(shù)據(jù)庫,關(guān)系數(shù)據(jù)庫可以看作是第二代數(shù)據(jù)庫系統(tǒng)。 關(guān)系數(shù)據(jù)庫是建立在關(guān)系數(shù)據(jù)模型基礎(chǔ)之上的數(shù)據(jù)庫，關(guān)系數(shù)據(jù)模型用關(guān)系（即二維表格數(shù)據(jù)）表示實(shí)體之間的聯(lián)系。 通俗地

50、講，關(guān)系就是二維表格；表格中的每一行稱作一個元組，相當(dāng)于一個記錄值；每一列是一個屬性值集，列可以命名，稱作屬性名。 由此可以說，關(guān)系是元組的集合，如果表格有n列，則稱該關(guān)系為n元關(guān)系。,關(guān)系模型中的操作,關(guān)系模型中的操作有： 傳統(tǒng)的集合運(yùn)算：交、并、差和廣義笛卡積等； 專門的關(guān)系運(yùn)算：選擇、投影、連接和除等； 有關(guān)的數(shù)據(jù)操作：查詢、插入、刪除和修改等。,對數(shù)據(jù)庫技術(shù)的研究,對數(shù)據(jù)庫技術(shù)的研究是從以下三個方面進(jìn)行的： 數(shù)據(jù)模型。數(shù)據(jù)模型的研究是數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)研究，重點(diǎn)研究如何構(gòu)造數(shù)據(jù)模型，如何表示數(shù)據(jù)及其聯(lián)系?，F(xiàn)在的重點(diǎn)研究課題是面向?qū)ο竽Ｐ汀?應(yīng)用領(lǐng)域。數(shù)據(jù)庫技術(shù)的最初應(yīng)用主要是信息管理領(lǐng)域

51、，事實(shí)上，只要有大量數(shù)據(jù)要管理或者需要大批量數(shù)據(jù)支持的工作，都可以使用數(shù)據(jù)庫。 計(jì)算機(jī)技術(shù)。計(jì)算機(jī)技術(shù)的發(fā)展促進(jìn)了數(shù)據(jù)庫技術(shù)的發(fā)展。通過將計(jì)算機(jī)技術(shù)的一些研究領(lǐng)域與數(shù)據(jù)庫技術(shù)相結(jié)合，產(chǎn)生了許多新的數(shù)據(jù)庫系統(tǒng)。,第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn),6.1 基本的實(shí)現(xiàn)策略 6.2 動態(tài)結(jié)構(gòu)的靜態(tài)實(shí)現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應(yīng)用,6.4 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應(yīng)用,6.4.1 Josephus問題 6.4.2 教務(wù)管理與二分圖 6.4.3 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織,Josephus問題,Josephus問題是由古羅馬著名史學(xué)家Josephus所提出的問題演變而來的。Jo

52、sephus問題的提法很多，如“猴子選大王問題”、“旅行社獎游客問題”等，就其數(shù)學(xué)本質(zhì)而言是相同的問題。Josephus問題的一般描述如下： 設(shè)有n個人圍坐一圈并由1到n編號。從某個人（例如編號為k的人）開始報(bào)數(shù)，數(shù)到m的人出列；接著從出列的下一個人開始重新1到m報(bào)數(shù)，數(shù)到m的人又出列；如此反復(fù)地報(bào)數(shù)和出列，直到最后一個人出列為止。試設(shè)計(jì)確定這n個人出列序列的程序。,Josephus問題（續(xù)）,由問題描述可以很自然地聯(lián)想到循環(huán)鏈表，用循環(huán)鏈表對Josephus問題建模，可以做到程序世界和問題世界的完全一致性，符合面向?qū)ο蟮某绦蛟O(shè)計(jì)思想。 考慮到反復(fù)報(bào)數(shù)的過程，可選用不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，以避

53、免報(bào)數(shù)過程中識別頭結(jié)點(diǎn)的麻煩。 由此，程序中可以先構(gòu)建一個具有n個結(jié)點(diǎn)的單循環(huán)鏈表，然后從約定的結(jié)點(diǎn)開始1到m計(jì)數(shù)，計(jì)到m時從鏈表中刪除對應(yīng)結(jié)點(diǎn)；接著從被刪除結(jié)點(diǎn)的下一個結(jié)點(diǎn)起計(jì)數(shù)，直到最后一個結(jié)點(diǎn)從鏈表中刪除后結(jié)束。,Josephus問題舉例,例如，若n8，m=3，k=1時，出列的序列為3，6，1，5，2，8，4，7。如下圖給出了問題求解過程示意圖，圖中的箭頭表示當(dāng)前報(bào)數(shù)的位置，虛線框中為要出列者的序號，實(shí)黑框中為已出列者的序號，空白框中為未出列者的序號。,Josephus問題算法描述,用C語言編寫利用單循環(huán)鏈表求解Josephus問題程序如下： #include “stdio.h” #in

54、clude “malloc.h” typedef struct node int num; struct node *next; linklist; linklist *creat(head,n) linklist *head; int n; linklist *s,*p; int i; s=(linklist*)malloc(sizeof(linklist)); head=s;,Josephus問題算法描述（續(xù)）,s-num=1; p=s; for(i=2;inum=i; p-next=s; p=s; p-next=head; return head;

55、/*creat*/,Josephus問題算法描述（續(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問題算法描述（續(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*/,Jo

56、sephus問題算法描述（續(xù)）,main() int n,m; linklist *head; printf(“input the total numbern”); scanf(“%d”, /*main */,Josephus問題算法描述（續(xù)）,求解Josephus問題，也可以考慮用靜態(tài)循環(huán)鏈表組織數(shù)據(jù)。由于數(shù)組下標(biāo)與n個人的編號可以一致起來（不用下標(biāo)0），故僅用一維數(shù)組即可，其中數(shù)組元素作為靜態(tài)指針指向下一個人，這種實(shí)現(xiàn)方法稱作環(huán)形數(shù)組實(shí)現(xiàn)方法，程序如下： #include “stdio.h” #include “malloc.h” void Josephus(n,m,k

57、) int m,n,k; int R; int i,j; for(i=1;i

58、算法描述（續(xù)）,void main() int n,m,k; printf(“Josephus問題求解：”); scanf(“%d%d%d”, /*main end*/,6.4 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應(yīng)用,6.4.1 Josephus問題 6.4.2 教務(wù)管理與二分圖 6.4.3 學(xué)籍管理系統(tǒng)中的數(shù)據(jù)組織,二分圖,設(shè)G=(V，E)是一個無向圖，其中V=v1，v2，，vn，E e1，e2，，en 。如果頂點(diǎn)集合V可以分割成為兩個互不相交的子集X和Y，使圖中每條邊ei=(vi，vj)都具這樣的性質(zhì)：其一個端點(diǎn)vi是X中的頂點(diǎn)（即viX）而另一個端點(diǎn)vj是Y中的頂點(diǎn)（即vjY），則稱

59、圖G是一個二分圖（bipartite graph）。,教務(wù)管理與二分圖,在高等學(xué)校的教務(wù)管理中，處理學(xué)生選課是一項(xiàng)日常工作。每個學(xué)生可同時選修多門課程，每門課程也允許多個學(xué)生同時選修。這種學(xué)生與課程之間的關(guān)系可以用二分圖表示為如右圖所示，圖中的頂點(diǎn)由學(xué)生和課程組成，邊（s，c）表示學(xué)生s選修課程c。,教務(wù)管理與二分圖（續(xù)）,教務(wù)員經(jīng)常需要做如下一些管理工作： 登記學(xué)生選修的課程； 撤銷學(xué)生的修課登記； 查看某個學(xué)生選修哪些課程； 查看某個課程有哪些學(xué)生選修。 這些管理工作即是對二分圖做相應(yīng)的插入、刪除和檢索操作。 在現(xiàn)實(shí)社會中，諸如商店與商品、商店與顧客、技術(shù)人員與技術(shù)職稱、教師與課程等許多管

60、理問題都和學(xué)生與課程問題類似，都可以用二分圖來表示。二分圖是數(shù)據(jù)庫等應(yīng)用系統(tǒng)的重要的數(shù)據(jù)結(jié)構(gòu)。,教務(wù)管理與二分圖（續(xù)）,由于二分圖中頂點(diǎn)集合V分割成為兩個互不相交的子集X和Y，同一子集中（X中或Y中）的頂點(diǎn)無邊相連，這就使得二分圖的鄰接矩陣呈現(xiàn)為一個對稱分塊矩陣： 即二分圖可以用特殊的存儲結(jié)構(gòu)矩陣B陣來表示。 顯然，用矩陣B表示二分圖比鄰接矩陣A節(jié)省存儲空間。然而矩陣B也可能是一個稀疏矩陣，可針對具體情況作進(jìn)一步的壓縮存儲處理，,教務(wù)管理與二分圖舉例,例如，前例中圖的二分圖SCG的鄰接矩陣如下圖(a)所示，為一對稱分塊矩陣；其特殊存儲表示即矩陣B如下圖 (b)所示。,教務(wù)管理與二分圖（續(xù)）,教

61、務(wù)管理中的另一項(xiàng)重要的日常工作是安排教師教學(xué)工作。在一般情況下，每位教師通?？梢詣偃味嚅T課程的教學(xué)，而在一個學(xué)期內(nèi)只講授他所勝任的一門課程；反之，在一個學(xué)期內(nèi)一門課程只需一位教師主講。這就需要對教師和課程作合理安排，我們可以用一個二分圖來表示教師與課程之間的這種關(guān)系，教師和課程都是圖中的頂點(diǎn)，邊（t，c）表示教師t勝任課程c，右圖給出了五位教師和五門課程之間關(guān)系的二分圖。,教務(wù)管理與二分圖（續(xù)）,為每位教師安排一門課程，相當(dāng)于為每個教師頂點(diǎn)選擇一條和課程頂點(diǎn)相關(guān)聯(lián)的邊，使任何兩個教師頂點(diǎn)不和同一課程頂點(diǎn)相鄰接。這種安排課程給每位教師的問題，實(shí)際上是圖的匹配問題。圖匹配問題的一般描述如下： 給定

62、一個圖G=(V，E)，若邊集合E的一個子集M中任意兩條邊都不依附圖中的同一個頂點(diǎn)，稱M是圖G的一個匹配（matching）；G的邊數(shù)最多的匹配稱作G的最大匹配（maximal matching）。如果在圖G的一個匹配中，圖中每個頂點(diǎn)都是該匹配中某條邊的端點(diǎn)，則稱該匹配為圖G的完全匹配（complete matching）。圖G的任何一個完全匹配，一定都是圖G的最大匹配。,二分圖TCG的匹配和最大匹配示例,下圖(a)和(b)的實(shí)線邊分別給出了前例中二分圖TCG的一個匹配和一個最大匹配的示例。,二分圖TCG的匹配和最大匹配,為了求出一個圖的最大匹配，顯而易見的辦法是列舉出該圖的全部匹配，然后選出邊

63、數(shù)最多的一個匹配。然而，這種方法的時間復(fù)雜度是邊數(shù)的指數(shù)階函數(shù)。因此，需要一種更有效的匹配算法。 下面介紹一種利用增廣路徑求最大匹配的有效算法。 設(shè)M是圖G的一個匹配，我們將M中的邊所關(guān)聯(lián)的頂點(diǎn)稱為已匹配頂點(diǎn)，其余頂點(diǎn)稱為未匹配頂點(diǎn)。若P是圖G中一條連通兩個未匹配頂點(diǎn)的路徑，并且在P上屬于M的邊和不屬于M 的邊交替出現(xiàn)，則稱P為一條關(guān)于M的增廣路徑（augmenting path）。,二分圖TCG的匹配和最大匹配（續(xù)）,由利用增廣路徑求最大匹配的有效算法的定義可有如下結(jié)論： 一條關(guān)于M的增廣路徑的長度必為奇數(shù)，且路徑上的第一條邊和最后一條邊都不屬于M。 對于一條關(guān)于M的增廣路徑P，由對稱差集運(yùn)

64、算MP可以得到一個比M更大的匹配。即這個更大的匹配包括所有在M中但不在P中和在P中但不在M 中的邊的集合構(gòu)成。 M為G的一個最大匹配，當(dāng)且僅當(dāng)不存在關(guān)于M的增廣路徑。 結(jié)論和是顯而易見的。 對于結(jié)論，當(dāng)存在一條關(guān)于M的增廣路徑時，由結(jié)論知M不是最大匹配；反之，當(dāng)M不是最大匹配時，一定可以找到一條關(guān)于M的增廣路徑。,二分圖TCG的匹配和最大匹配（續(xù)）,事實(shí)上，設(shè)N是一個比M更大的匹配，并令=(V，MN)；因?yàn)镸和N都是G的一個匹配，所以V中的頂點(diǎn)最多和M中的一條邊相關(guān)聯(lián)，也最多和N 中的一條邊相關(guān)聯(lián)；于是的每個連通分量都是由M和N中的邊交替組成的一條簡單路徑或環(huán)，每個環(huán)中所含M和N的邊數(shù)相等，而

65、每條簡單路徑是一條關(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的增廣路徑，此時得到的匹配M即為G的最大匹配。,二分圖TCG的匹配和最大匹配（續(xù)）,在上述算法中，關(guān)鍵問題是如何根據(jù)已有匹配M找出G中關(guān)于M 的一條增廣路徑。為簡化起見，我們只討論G是二分圖的情形。 設(shè)M是G的一個匹配，用類似于圖的廣度優(yōu)先搜索過程構(gòu)造一棵樹。設(shè)層號為i，當(dāng)i=0時取G的一個未匹配頂點(diǎn)作為樹根；當(dāng)i為奇數(shù)時，將那些

66、與第i-1層中一個頂點(diǎn)相關(guān)聯(lián)但不屬于M的邊，連同該邊相關(guān)聯(lián)的另一個頂點(diǎn)一起添加到樹上；當(dāng)i為偶數(shù)時，則是添加那些與第i-1層中一個頂點(diǎn)相關(guān)聯(lián)且屬于M的邊以及該邊所關(guān)聯(lián)的另一個頂點(diǎn)。 如果在上述樹的構(gòu)造過程中，發(fā)現(xiàn)一個未匹配頂點(diǎn)v被作為樹的奇數(shù)層頂點(diǎn)，則從樹根到頂點(diǎn)v的路徑就是一條關(guān)于M的增廣路徑；如果在樹的構(gòu)造過程中既沒有找到增廣路徑，又無法按要求往樹上添加新的邊和頂點(diǎn)，則可在剩余頂點(diǎn)中再取一個未匹配頂點(diǎn)作樹根構(gòu)造新的一棵樹。這個過程一直進(jìn)行下去，如果不存在其它未匹配頂點(diǎn)，即最終仍未得到任何增廣路徑，就說明M已為一個最大匹配了。,二分圖TCG的匹配和最大匹配舉例,例如，對前例圖 (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）添加到樹中，同時頂點(diǎn)c4和c5添加到樹中作為第三層； 由于c5是未匹配頂點(diǎn)， 所以到此找到了一條增廣路徑P：t5c1t2c5。