算法與數(shù)據(jù)結構,第6章 數(shù)據(jù)結構的程序實現(xiàn),數(shù)據(jù)結構的程序實現(xiàn),數(shù)據(jù)結構是對程序中數(shù)據(jù)信息的結構組織，供給定問題求解算法的控制結構來處理。 Niklaus wirth曾經(jīng)給出“算法+數(shù)據(jù)結構=程序”的公式，得到了計算機科學界的普遍認可。 在程序設計語言中如何表示數(shù)據(jù)和控制，很大程度上決定了如何使用這個語言來編寫程序；所以在程序設計語言中不僅提供了與程序控制流程有關的控制結構，同時也提供了與程序中數(shù)據(jù)信息組織有關的數(shù)據(jù)結構。 程序設計的主要任務就是在選取或組織適當?shù)臄?shù)據(jù)結構的基礎上，利用三種基本結構（順序、選擇、重復）把逐級分解得到的一系列基本操作組織起來，形成用某種特定語言書寫的源程序。,數(shù)據(jù)結構的程序實現(xiàn)(續(xù)),算法與數(shù)據(jù)結構課程討論數(shù)據(jù)結構的目的，就是為了在設計給定問題的求解算法時，應用這些數(shù)據(jù)結構來組織程序中的數(shù)據(jù)；從而降低問題的分析與設計難度，提高程序（或算法）的設計質(zhì)量，縮短設計周期。 這里就有一個在程序中如何實現(xiàn)各種數(shù)據(jù)結構的問題。實現(xiàn)是使用的前提，只有在程序中實現(xiàn)了數(shù)據(jù)結構，才能在程序中利用數(shù)據(jù)結構對給定問題進行有效地求解。 本章將從幾個不同的角度討論如何在程序中實現(xiàn)各種數(shù)據(jù)結構的問題。,第6章 數(shù)據(jù)結構的程序實現(xiàn),6.1 基本的實現(xiàn)策略 6.2 動態(tài)結構的靜態(tài)實現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結構在問題建模中的應用,基本的實現(xiàn)策略,程序設計語言中提供了與程序中數(shù)據(jù)信息組織有關的數(shù)據(jù)結構，但沒有也不可能提供所有的數(shù)據(jù)結構。 一方面，受科學技術和生產(chǎn)力發(fā)展水平的限制，人類認知世界具有歷史局限性；人們不可能在某一天完成對現(xiàn)實世界的認知過程，同樣也不可能在某一天說對數(shù)據(jù)結構的認知過程已經(jīng)完結，這種認知過程是一個漸進式不斷深化和逐步完善的過程。 另一方面，受計算機科學發(fā)展和計算機系統(tǒng)本身的限制，人們不可能研制出一種設施包羅萬象、功能應有盡有的計算機語言和語言翻譯系統(tǒng)。 因此，程序設計語言中只可能提供一些基本的和常用的數(shù)據(jù)結構設施，并提供一些構造求解現(xiàn)實世界中問題所需數(shù)據(jù)結構的基本設施和方法手段。,6.1 基本的實現(xiàn)策略,6.1.1 簡單數(shù)據(jù)結構的程序實現(xiàn) 6.1.2 構造型數(shù)據(jù)結構的程序實現(xiàn) 6.1.3 數(shù)據(jù)結構的鏈式實現(xiàn) 6.1.4 數(shù)據(jù)結構的數(shù)組實現(xiàn),簡單數(shù)據(jù)結構的程序實現(xiàn),簡單的數(shù)據(jù)結構，在程序設計語言中已經(jīng)實現(xiàn)了，并作為數(shù)據(jù)類型提供給程序設計人員。 諸如整型數(shù)據(jù)、實型數(shù)據(jù)、布爾型數(shù)據(jù)和字符型數(shù)據(jù)等等。 程序設計人員只要在程序中用相應的類型標識符直接說明程序中數(shù)據(jù)變量的類型就可以直接使用了，如C語言中的int，unsigned int，long int，short int，unsigned short int，char，float和double等。,6.1 基本的實現(xiàn)策略,6.1.1 簡單數(shù)據(jù)結構的程序實現(xiàn) 6.1.2 構造型數(shù)據(jù)結構的程序實現(xiàn) 6.1.3 數(shù)據(jù)結構的鏈式實現(xiàn) 6.1.4 數(shù)據(jù)結構的數(shù)組實現(xiàn),構造型數(shù)據(jù)結構的程序實現(xiàn),還有一些簡單類型和構造類型，也是在程序設計語言中已經(jīng)實現(xiàn)了的數(shù)據(jù)結構。如枚舉型、子界型、日期型、集合、數(shù)組、字符串、記錄、文件等。 程序設計語言中提供了程序設計人員在程序中說明這些數(shù)據(jù)類型的方法，程序設計人員只要在程序中的適當位置按照相應的格式和要求對程序中的數(shù)據(jù)進行說明就可以使用了。如C語言中的枚舉、數(shù)組、字符串、結構體、共同體、文件等。,6.1 基本的實現(xiàn)策略,6.1.1 簡單數(shù)據(jù)結構的程序實現(xiàn) 6.1.2 構造型數(shù)據(jù)結構的程序實現(xiàn) 6.1.3 數(shù)據(jù)結構的鏈式實現(xiàn) 6.1.4 數(shù)據(jù)結構的數(shù)組實現(xiàn),數(shù)據(jù)結構的鏈式實現(xiàn),其它的數(shù)據(jù)結構，如鏈表、循環(huán)鏈表、棧、隊列、廣義表、樹、二叉樹、圖、網(wǎng)和堆等，在程序設計語言中一般都沒有提供其相應的數(shù)據(jù)類型，程序設計人員不能夠在程序中用類型說明的辦法直接引入。 然而，許多程序設計語言都提供有指針類型，程序設計人員可以利用指針類型在程序中動態(tài)建立所需要的某種數(shù)據(jù)結構。 一般地，在建立某種數(shù)據(jù)結構之前，先需要說明其數(shù)據(jù)元素的結點類型，如說明成記錄、結構體等，再用指針變量動態(tài)建立起相應的數(shù)據(jù)結構，以供求解問題的程序使用或處理。,6.1 基本的實現(xiàn)策略,6.1.1 簡單數(shù)據(jù)結構的程序實現(xiàn) 6.1.2 構造型數(shù)據(jù)結構的程序實現(xiàn) 6.1.3 數(shù)據(jù)結構的鏈式實現(xiàn) 6.1.4 數(shù)據(jù)結構的數(shù)組實現(xiàn),數(shù)據(jù)結構的數(shù)組實現(xiàn),如果在程序設計語言中沒有提供指針變量，就不能動態(tài)實現(xiàn)程序中需要的數(shù)據(jù)結構；還有一些數(shù)據(jù)結構，不宜借助指針來實現(xiàn)，如順序表、順序棧、順序隊列等。對于這兩種情況，程序設計人員都可以在程序中利用數(shù)組模擬實現(xiàn)程序中需要的一些數(shù)據(jù)結構。 數(shù)組是每一種高級程序設計語言都提供了的數(shù)據(jù)結構?？梢岳靡痪S數(shù)組模擬實現(xiàn)順序表、順序棧、順序隊列?？梢岳枚S數(shù)組模擬實現(xiàn)鏈表或循環(huán)鏈表，其中一列描寫一個數(shù)據(jù)元素（或結點）；若構成數(shù)據(jù)元素各字段類型不一致，也可改用兩個或多個一維數(shù)組來模擬實現(xiàn)之?？捎萌齻€一維數(shù)組來模擬實現(xiàn)二叉樹，其中一個數(shù)組存放數(shù)據(jù)域的值，兩個數(shù)組分別作為左右鏈域。樹可通過左孩子右兄弟表示法轉化為二叉樹用數(shù)組表示，而圖和網(wǎng)的鄰接矩陣表示法本身就是用二維數(shù)組表示的方法。,第6章 數(shù)據(jù)結構的程序實現(xiàn),6.1 基本的實現(xiàn)策略 6.2 動態(tài)結構的靜態(tài)實現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結構在問題建模中的應用,動態(tài)結構的靜態(tài)實現(xiàn),所謂動態(tài)數(shù)據(jù)結構（dynamic data structure）是指可以隨著程序的執(zhí)行而動態(tài)地改變大小程形狀的一類數(shù)據(jù)結構，如鏈表、樹和圖等。動態(tài)結構的數(shù)據(jù)，在編譯時無法預先規(guī)定它們所需要分配的存儲空間大小，只有在運行時進行動態(tài)存儲分配，與之相對應的是靜態(tài)數(shù)據(jù)結構（static data structure），數(shù)據(jù)所需存儲空間是一個固定的有限區(qū)域，可在程序說明中顯式規(guī)定，在編譯時靜態(tài)進行存儲分配。 凡是可以用指針動態(tài)實現(xiàn)的數(shù)據(jù)結構，都可以利用數(shù)組靜態(tài)地模擬實現(xiàn)。有時也把這種利用數(shù)組靜態(tài)模擬實現(xiàn)了的動態(tài)結構稱之為半靜態(tài)數(shù)據(jù)結構（semi-static data structure）。當然，半動態(tài)結構中也包含可變數(shù)組和變長記錄等部分采用靜態(tài)分配、部分采用動態(tài)分配的數(shù)據(jù)結構。,6.2 動態(tài)結構的靜態(tài)實現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實現(xiàn),靜態(tài)鏈表,在利用提供指針類型的高級程序設計語言編寫程序時，鏈表的實現(xiàn)是很簡單和很自然的。如果語言中沒有提供指針類型，可以用數(shù)組來模擬實現(xiàn)鏈表結構，并稱之為靜態(tài)鏈表（static linked list），用以記錄類型作為基類型的數(shù)組來模擬實現(xiàn)靜態(tài)鏈表。 模擬實現(xiàn)靜態(tài)鏈表的數(shù)組可如下定義： #define maxsize 100 typedef struct elementype data; /*數(shù)據(jù)域為元素類型*/ int next; /*指針域為整型*/ snode; /*snode為結點類型標識符*/ snode smaxsize; /*s為基類型是snode的一維數(shù)組，即記錄數(shù)組*/,靜態(tài)鏈表（續(xù)）,注意這里的next域說明與單鏈表中的說明不同，在單鏈表中是指向結構體的指針類型，值為結點的實際地址；在靜態(tài)鏈表中是int類型，值為結點在s數(shù)組中的下標值，指針值為空時用-1表示。 對于靜態(tài)鏈表實現(xiàn)線性表的各種運算操作與動態(tài)的單鏈表上的實現(xiàn)基本相同，所不同的是在存儲區(qū)的管理上有差別。 單鏈表上的運算操作實現(xiàn)不要考慮存儲區(qū)的管理問題，是通過malloc函數(shù)獲得結點空間并利用free函數(shù)釋放結點空間，存儲區(qū)的管理交由系統(tǒng)完成； 而靜態(tài)鏈表的存儲區(qū)就是這個記錄數(shù)組s，獲得結點空間和釋放結點空間都對數(shù)組s進行，必須在程序中設計相應的管理程序段。,靜態(tài)鏈表及其存儲區(qū)管理舉例,6.2 動態(tài)結構的靜態(tài)實現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實現(xiàn),二叉樹的靜態(tài)二叉鏈表表示法,對于沒有提供指針類型的高級程序設計語言，程序中要用到二叉樹結構組織數(shù)據(jù)信息，可用靜態(tài)二叉鏈表（static binary linked list）表示法實現(xiàn)二叉樹結構。和靜態(tài)鏈表類似，靜態(tài)二叉鏈表的存儲區(qū)管理也是利用以結點類型作為基類型的一維數(shù)組實現(xiàn)；獲得結點空間的函數(shù)malloc和釋放結點空間的free函數(shù)的實現(xiàn)也是類似的。 用靜態(tài)二叉鏈表表示二叉樹的類型定義如下： #define maxsize 100 typedef struct /*定義結點類型為結構體*/ elementype data; /*數(shù)據(jù)域為元素類型*/ int lchild,rchild; /*定義左右孩子域為整型*/ sbinarytree; sbinarytree stmaxsize;,二叉樹的靜態(tài)二叉鏈表表示法,和靜態(tài)鏈表一樣，靜態(tài)二叉鏈表的左孩子域和右孩子域也都是int類型，其值為數(shù)組中的下標值。 靜態(tài)二叉鏈表的存儲區(qū)管理是利用右孩子域形成的靜態(tài)鏈棧av，用-1表示指針為NULL的情況。 除了在插入結點時獲取一個結點空間以及在刪除時釋放一個結點空間的存儲區(qū)管理是要在程序中完成之外，用靜態(tài)二叉鏈表表示的二叉樹的各種運算操作與用二叉鏈表表示的二叉樹的相應運算操作一致。,二叉樹的靜態(tài)二叉鏈表表示法舉例,6.2 動態(tài)結構的靜態(tài)實現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實現(xiàn),樹和森林的雙親表示法舉例,在前面我們介紹了樹和森林的兩種存儲表示方法，即孩子鏈表表示法和左孩子右兄弟表示法；這兩種表示方法，都可以通過靜態(tài)鏈表和靜態(tài)二叉鏈表來實現(xiàn)。 樹和森林還有一種存儲表示方法，就是雙親表示法。因為樹和森林中的每一個結點，其雙親結點是惟一的；利用這一性質(zhì)，在存儲結點信息時為每個結點增加一個指向其雙親的指針parent，就可以惟一地表示樹或森林。 若用靜態(tài)鏈表實現(xiàn)樹和森林的雙親表示法，其類型定義如下： #define maxsize 100 typedef struct elementype data; int parent; sptnode; sptnode ptmaxsize;,樹和森林的雙親表示法,6.2 動態(tài)結構的靜態(tài)實現(xiàn),6.2.1 靜態(tài)鏈表 6.2.2 二叉樹的靜態(tài)二叉鏈表表示法 6.2.3 樹和森林的雙親表示法 6.2.4 哈夫曼算法的靜態(tài)實現(xiàn),哈夫曼算法的靜態(tài)實現(xiàn),由于哈夫曼樹中沒有度為1的結點，一棵有n個葉子結點的哈夫曼樹有2n-1個結點，所以可用大小為2n-1個元素的數(shù)組構造靜態(tài)鏈表來存儲哈夫曼樹，一個數(shù)組元素中存放一個結點。 結點的結構可以這樣來考慮，由于每個葉子結點都有一個權重值，構造哈夫曼樹的過程中每個分枝結點的權重值等于兩個孩子結點權重值的和，所以應該有一個權重域和指向左右孩子的兩個指針域； 另外在建成哈夫曼樹之后，為了求得每個葉子結點的哈夫曼編碼，需要走一條從葉子結點到根結點的路徑，而譯碼的過程是從根結點出發(fā)到葉子結點的不斷匹配的過程，所以既需要知道孩子結點的信息，也需要知道雙親結點的信息，應該再有一個指向雙親結點的指針域。 由此可知每個結點至少應該有一個權重域weight和三個指針域parent、lchild和rchild，也就是說要用靜態(tài)三叉鏈表來表示哈夫曼樹。,哈夫曼樹及其靜態(tài)三叉鏈表存儲表示示例,哈夫曼算法的靜態(tài)實現(xiàn)(續(xù)),由于在實際構造哈夫曼樹時，是由葉子結點的權值逐級構造最后生成樹根，且在構造過程中僅與葉子結點的權值有關而與葉子結點的數(shù)據(jù)域值無關； 所以構造算法的實現(xiàn)中可以不考慮葉子結點的數(shù)據(jù)域值，并且在靜態(tài)三叉鏈表中從葉子結點開始存放，然后不斷地把兩棵權值最小的子樹合并成為一棵權值為其和的較大的子樹，逐步生成各內(nèi)部結點直到樹根。 哈夫曼樹的類型定義如下： #define maxvalue 10000 #define maxnodenumber 100 typedef struct int weight; int parent,lchild,rchild; htnode; /*定義結點類型標識符*/ type htnode *huffmantree; /*定義哈夫曼樹類型*/ htnode htmaxnodenumber;,建立哈夫曼樹的算法的描述,在以上類型定義的基礎上，對于給定的一組權重值，建立其哈夫曼樹的算法可描述如下： huffmantree crthuffmantree(int n) int i,j,m1,m2,k1,k2; for(i=0;i<2*n-1;i+) hti.weight=0; /*權重初始化為0*/ hti.parent= -1; hti.lchild= -1; hti.rchild= -1; for(i=0;i<n;i+) scanf(“%d”,建立哈夫曼樹的算法的描述(續(xù)),for(i=0;i<n-1;i+) m1=maxvalue; m2=maxvalue; k1=0; k2=0; for(j=0;j<n+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 */ 注意，在建立哈夫曼樹的算法描述中，有效地利用了每個結點的雙親域parent的值是否為-1來區(qū)分該結點是否是哈夫曼森林中一棵樹的根結點；每次是在根結點中找出兩個權重值weight最小的樹作為左右子樹構造一棵更大的樹。,求哈夫曼編碼的方法,求哈夫曼編碼的方法是，在已建好的哈夫曼樹中從每個葉子結點開始沿雙親鏈域回退到根結點，每回退一步走過哈夫曼樹的一個分枝得到一位哈夫曼編碼值；由于每個葉子結點的哈夫曼編碼是從根結點到相應葉子結點的路徑上各分枝代碼所組成的0、1序列，所以先得到的分枝代碼為所求編碼的低位碼而后得到的為高位碼。 對于每個葉子結點的哈夫曼編碼可以考慮用一個一維數(shù)組bit從后向前依次保存所求得的各位編碼值，并用start記住編碼在數(shù)組bit中的開始位置。由此可做如下的類型定義： #define maxbit 10 typedef struct int bitmaxbit; int start; hcodetype; /*定義哈夫曼編碼類型*/,求哈夫曼編碼的算法描述,從葉子結點到根結點逆向求每個葉子結點所代表值的哈夫曼編碼的算法可描述如下： void gethuffmancode(htnode ht,int n) int i,j,c,p; hcodetype cdn; for(i=0;i<n;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);,求哈夫曼編碼的算法描述(續(xù)),cdi.start=j; for(i=0;i<n;i+) for(j=cdi.start;j<maxbit;j+) printf(“%d”,cdi.bitj); printf(“n”); /*gethuffmancode end*/,求哈夫曼編碼的算法舉例,例如，已知某系統(tǒng)在通訊聯(lián)絡中只可能出現(xiàn)六種字符，其使用各字符的頻度分別為（0.05，0.20，0.12，0.07，0.47，0.09）。若要為這六種字符設計哈夫曼編碼，可設權w=(5，20，12，7，47，9)，n=6，2n-1=11；按上述crthuffmantree算法構造的哈夫曼樹如下左圖所示。按gethuffmancode算法求得的哈夫曼編碼在cd數(shù)組中的狀態(tài)如下右圖所示。,求哈夫曼編碼的算法舉例(續(xù)),其存儲結構的靜態(tài)三叉鏈表ht的初始狀態(tài)如下左圖所示，最終狀態(tài)如下右圖所示。,第6章 數(shù)據(jù)結構的程序實現(xiàn),6.1 基本的實現(xiàn)策略 6.2 動態(tài)結構的靜態(tài)實現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結構在問題建模中的應用,6.3 大批量數(shù)據(jù)的組織策略,6.3.1 文件的組織 6.3.2 數(shù)據(jù)庫技術,1.文件的基本概念,文件的概念和線性表類似，是由大量性質(zhì)相同的記錄組成的集合；二者的區(qū)別在于線性表是把記錄全部組織在內(nèi)存儲器中，而文件則是把大量記錄都組織在外存儲器中。 按照記錄的類型，可以把文件分為操作系統(tǒng)文件和數(shù)據(jù)庫文件兩大類。 操作系統(tǒng)文件中的記錄只是一個字符序列，無結構，無解釋，僅是為了加工，存取的方便劃分的字符組。 而數(shù)據(jù)庫文件中的記錄是有結構的，可以由一個或多個數(shù)據(jù)項組成，是存取文件中數(shù)據(jù)的基本單位；數(shù)據(jù)項是不可再分的最基本單位，也是文件中可使用數(shù)據(jù)的最小單位。,文件的基本概念（續(xù)）,按照記錄的長度特性，可以把文件分為定長記錄文件和不定長記錄文件。 定長記錄文件中每個記錄含有的信息長度相同， 不定長記錄文件中每個記錄含有的信息長度不等。 按照記錄中關鍵字的多少，可以把文件分為單關鍵字文件和多關鍵字文件。 單關鍵字文件中的記錄只有一個惟一標識記錄的主關鍵字； 多關鍵字文件中的記錄除了主關鍵字外，還含有一個或多個次關鍵字，記錄中所有非關鍵字的數(shù)據(jù)項稱作記錄的屬性。,文件的基本概念（續(xù)）,記錄有邏輯結構和物理結構之分。 邏輯結構是指記錄在用戶或應用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方式；用戶讀寫一個記錄是指邏輯記錄。 記錄的物理結構是數(shù)據(jù)在物理存儲器上存儲的方式，是數(shù)據(jù)的物理表示和組織方式。一個物理記錄是指計算機用一條I/O命令進行讀寫的基本數(shù)據(jù)單位，對于固定的設備和操作系統(tǒng)，它的大小基本上是固定不變的； 而邏輯記錄的大小是根據(jù)使用的需要確定的。 一個物理記錄可以存放一個或多個邏輯記錄，多個物理記錄可以表示一個邏輯記錄。用戶讀寫的是邏輯記錄，查找其對應的物理記錄是操作系統(tǒng)的職責。,文件的基本概念（續(xù)）,文件的操作有三類，檢索、修改和排序。 檢索的方式有三種： 順序檢索，按記錄的相對位置檢索下一個邏輯記錄； 按記錄號檢索，根據(jù)記錄存入文件時的順序編號，檢索第i個邏輯記錄； 按關鍵字檢索，檢索關鍵字值與給定值相關的一個或多個邏輯記錄，在數(shù)據(jù)庫文件中又可按給定關鍵字值、給定關鍵字的范圍、給定關鍵字的某個函數(shù)以及組合條件等方式進行檢索。 修改操作包括插入、刪除和更新一個記錄這三種操作。 排序操作則是為了檢索方便高效對文件中記錄的重新有序整理。,文件的基本概念（續(xù)）,文件的操作可以有實時和批處理兩種不同的方式。 實時處理通常對應答時間要求嚴格，應在接收詢問后立即完成相應的操作； 而批處理則不同，可以根據(jù)需要對積累一段時間的記錄進行成批處理。 文件在存儲介質(zhì)上的組織方式（即物理結構）有順序組織、隨機組織和鏈式組織等基本方式，具體選用哪種方式應結合存儲介質(zhì)類型（磁盤、磁帶等）、記錄類型、記錄大小、關鍵字數(shù)目以及對文件進行何種操作等各種因素綜合考慮。,2.順序文件,順序文件（sequential file）是把記錄按建立文件時的邏輯順序依次存放在外存儲器中，文件中的物理記錄順序和邏輯記錄順序一致。 若次序相繼的兩個物理記錄在存儲器上的存儲位置是相鄰的，則又稱為連續(xù)文件； 若物理記錄之間的次序由指針鏈接，則稱為串聯(lián)文件。 順序文件的存取方式是根據(jù)記錄號或記錄的相對位置進行的，其特點是： 存取第i個記錄必須先搜索在它之前的i-1個記錄； 插入的新記錄只能加在文件的未尾； 若要更新文件中的某個記錄，必須在整個文件的復制過程中進行。,順序文件（續(xù)）,由于順序文件的優(yōu)點是連續(xù)存取速度快，因此主要用于順序存取和批量修改的情況。 若對應答時間要求不嚴時亦可進行直接存取。 在對順序文件作修改時，可對原文件中的記錄復制一遍，并在復制的過程中插入新的記錄、跳過待刪除的記錄、或用修改過的新記錄代替原記錄。 為了修改方便起見，要求待修改文件按關鍵字有序（對非數(shù)據(jù)庫文件可將邏輯記錄號作為關鍵字）。,順序文件（續(xù)）,磁帶是一種典型的順序存取設備，存儲在磁帶上的文件就是順序文件。然而現(xiàn)在很少使用磁帶，較多使用的是磁盤上的順序文件。對磁盤上的順序文件進行修改時，若不增加記錄的長度，也可在原文件上直接修改而不必復制文件。 對順序文件進行順序檢索的方法類似于靜態(tài)表的順序檢索，其平均檢索長度為(n+1)/2，其中n為文件中所含物理記錄的數(shù)目（內(nèi)存檢索時間可以忽略不計）。也可以對磁盤文件進行分塊檢索或二分法檢索。但當文件很大時，二分法檢索將會引起磁頭在存儲文件的多個柱面之間來回移動而增加檢索時間。,3.索引文件,除了主文件（即數(shù)據(jù)文件）之外，再建立一張索引表來指示邏輯記錄和物理記錄之間的一一對應關系；索引表中的每一項稱作索引項，由記錄的關鍵字和記錄的存放地址構成；把索引表和主文件總稱為索引文件（indexed file）。 索引表通常是按關鍵字的升序排列。若主文件也按關鍵字升序排列，則構成的索引文件稱作索引順序文件； 若主文件是無序的，則稱所構造的索引文件為索引非順序文件。,索引文件（續(xù)）,索引文件只適用于直接存取的外存儲器（如磁盤）。索引文件的存儲分索引區(qū)和數(shù)據(jù)區(qū)來進行，索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。 在輸入記錄建立數(shù)據(jù)區(qū)的同時建立索引表，表中的索引項按記錄輸入的先后次序排列；待全部記錄輸入完畢后再對索引表按關鍵字排序，排序后的索引表和主文件一起構成了索引文件。,索引非順序文件舉例,索引文件（續(xù)）,索引文件的檢索，應先在索引表中檢索。若在索引表中找到關鍵字值等于給定值的索引項，則按索引項指示從外部存儲器讀取該記錄；否則說明待檢索記錄不存在無需訪問外存儲器。 相對于記錄而言索引項長度較小，即由索引項構成的索引表所占空間較小，通?？梢淮巫x入內(nèi)存。然而當主文件中記錄數(shù)目很大時，索引表仍可能超出一個物理塊的容量，這樣對索引表的檢索就可能需要多次訪問外存儲器。 為此，可對索引表再次建立二級索引；檢索時先在二級索引中找，再檢索索引表，然后讀取記錄。 索引表和二級索引表都是有序表，在內(nèi)存儲器中可用檢索效率較高的方法如二分法檢索方法進行檢索。,4.ISAM文件,ISAM（indexed sequential access method）即索引順序存取方法，是一種專為磁盤存取設計的文件組織方式。 由于磁盤是以盤組、柱面和磁道三級地址存取的設備，所以可以對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。 文件的記錄在同一盤組上存放時，應先集中放在一個柱面上，然后再順序存放在相鄰柱面上；對同一柱面，則應按盤面的次序順序存放。,ISAM文件結構舉例,ISAM文件（續(xù)）,在一個磁盤組上的ISAM文件，每個柱面建立一個磁道索引，每個磁道索引項由基本索引項和溢出索引項兩部分組成，每一部分都包括關鍵字和指針兩個域，前者表示該磁道中最大關鍵字，后者指示該磁道中第一個記錄的位置。 柱面索引的每一個索引項也由關鍵字和指針兩部分組成，前者表示該柱面中的最大關鍵字，后者指示該柱面上的磁道索引位置。 柱面索引存放在某個柱面上，若柱面索引較大占多個磁道時，則可建立柱面索引的一個主索引。,ISAM文件（續(xù)）,在ISAM文件上檢索記錄時，先從主索引出發(fā)找到相應的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直至找到為止；反之，若找遍磁道而不存在此記錄，則表明文件中無此記錄。 在前例中為每個柱面開辟了一個溢出區(qū)，并在磁道索引項中有溢出索引項（后面兩個域），這是為插入記錄所設置的。,ISAM文件（續(xù)）,由于ISAM文件中記錄是按關鍵字順序存放的，在插入一個記錄時需要向后移動記錄，并將同一磁道上的最后一個記錄移至溢出區(qū)，同時修改磁道索引項。除了為每個柱面設置一個溢出區(qū)的方法外，還可只集中設置一個大的公共溢出區(qū)；也可以既為每個柱面設置溢出區(qū)，同時也設置了一個公共溢出區(qū)，在柱面溢出區(qū)滿后再使用公共溢出區(qū)。 ISAM文件中刪除記錄比較簡單，只需作刪除標記而不用移動記錄或改變指針。當然應該周期性地把記錄讀入內(nèi)存重排整理ISAM文件，以盡量填滿基本區(qū)而空出溢出區(qū)。,5.VSAM文件,VSAM（virtual storage access method）即虛擬存儲存取方法。它利用了操作系統(tǒng)的虛擬存儲器的功能，使用戶只需考慮控制區(qū)間等邏輯存儲單位，而無需考慮其物理位置以及何時對外存儲器進行讀寫操作，給用戶使用文件提供了方便。 VSAM文件的結構由索引集、順序集和數(shù)據(jù)集三部分組成。 數(shù)據(jù)集存放文件的所有記錄， 順序集和索引集構成一棵B+樹是文件的索引部分。數(shù)據(jù)集中的一個結點稱為控制區(qū)間（control interval），它由一組連續(xù)的存儲單元組成，是讀寫操作的基本單位。,VSAM文件的結構舉例,VSAM文件（續(xù)）,同一文件上的控制區(qū)間大小相同，含有一個或多個按關鍵字升序排列的記錄。 順序集中的一個結點，存放著若干相鄰控制區(qū)間的索引項，每個索引項由控制區(qū)間中的最大關鍵字和指向該控制區(qū)間的指針組成。 順序集中的一個結點連同其下層所有控制區(qū)間形成的整體稱作控制區(qū)域（control range）。 順序集中的結點之間用指針相鏈接；在它們上層的結點又以它們?yōu)榛A形成索引，并逐級向上建立索引，形成B+樹的非終端結點。,VSAM文件（續(xù)）,對VSAM文件中記錄的檢索，既可以從最高層的索引逐層往下按關鍵字進行查找，又可以在順序集中沿著指針鏈順序查找。 VSAM文件沒有專門的溢出區(qū)，但可利用控制區(qū)間中的空隙或控制區(qū)域中空的控制區(qū)間來插入記錄（即在B+樹上插入記錄）。 在控制區(qū)間中插入記錄時，為了保證區(qū)間內(nèi)記錄按關鍵字有序需要移動記錄；而當區(qū)間中記錄已滿時，為了插入記錄需要將區(qū)間分裂。 在VSAM文件中刪除記錄時，也是需要移動記錄的。,VSAM文件（續(xù)）,VSAM文件占有較多的存儲空間，存儲空間的利用率一般也只能保持在75%左右。 然而它具有許多優(yōu)點，如動態(tài)地分配和釋放存儲空間，無需像ISAM文件那樣定期重排文件，并能較快地執(zhí)行插入操作和保持較高的檢索效率。 VSAM文件通常作為組織大型索引順序文件的標準形式。,6.散列文件,散列文件（Hash file）也稱作直接存取文件，它是利用哈希方法組織的數(shù)據(jù)文件；即根據(jù)某個哈希函數(shù)和一定的沖突消解策略而得到的存放在外存儲器上的散列表。 與哈希表不同的是，磁盤上的文件記錄通常是成組存放的。 若干個記錄組成一個存儲單位，在散列文件中這個存儲單位稱作桶。 一個桶能存放的邏輯記錄的總數(shù)稱作桶的容量。假如桶的容量為m，即m個同義詞的記錄可以存放在同一地址的桶中，當?shù)趍+1個同義詞記錄出現(xiàn)時則發(fā)生溢出。處理溢出也可采用哈希表中的各種處理沖突的方法，但對散列文件主要是采用鏈地址法消解沖突。,散列文件（續(xù)）,當發(fā)生溢出時，需要將第m+1個同義詞存放到另一個桶中，通常稱作“溢出桶”；相應地把存放前m個同義詞的桶稱作“基桶”。 溢出桶可以有多個，它們和基桶大小相同，相互之間用指針相鏈接。當在基桶中沒有檢索到待查記錄時，就順指針所指到溢出桶中去檢索； 因此，同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠，最好是在同一柱面上。,散列文件舉例,例如，某文件有20個記錄，其關鍵字分別為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ù)給定的關鍵字值k求得哈希地址，即基桶號； 然后將基桶的記錄讀入內(nèi)存進行順序檢索，若找到關鍵字值為k的記錄則檢索成功； 若基桶中雖無關鍵字值為k的記錄但指針域非空，需要把溢出桶中的記錄讀入內(nèi)存繼續(xù)檢索，直到檢索成功或檢索不成功。 檢索不成功的情況為基桶沒有填滿記錄，或雖填滿但指針域為空（無溢出桶），或雖有溢出桶但仍未找到關鍵字為k的記錄。,散列文件（續(xù)）,在散列文件中，裝填因子為 ，其中n為文件中的記錄數(shù)，b為桶數(shù)，m為桶的容量；而存取桶數(shù)的期望值為 。如上例， 。在散列文件中，刪除記錄時僅需對被刪記錄作一刪除標記即可。 總之，散列文件的優(yōu)點是插入和刪除方便，存取速度比索引文件要快；不需要索引區(qū)，節(jié)省存儲空間。其缺點是不能進行順序存取，只能按關鍵字隨機存取，且詢問方式只有簡單詢問；在經(jīng)過多次的插入和刪除之后，也可能造成溢出桶滿而基桶內(nèi)多數(shù)為被刪除記錄的不合理文件結構，亦需對文件進行重新整理。,7.多關鍵字文件,多關鍵字文件（multiple key file）的特點是，在對文件進行檢索操作時不僅對主關鍵字進行簡單詢問，還經(jīng)常需要對次關鍵字進行其它類型的詢問檢索。 因此，對多關鍵字文件還需要建立一系列的次關鍵字索引。次關鍵字索引和主關鍵字索引所不同的是，每個索引項應包含次關鍵字和具有同一次關鍵字的多個記錄的主關鍵字或物理記錄號。 多重表文件和倒排文件是常見的兩種多關鍵字文件組織方法。,多關鍵字文件（續(xù)）,多重表文件（multilist file）的特點是，記錄按主關鍵字的順序構成一個串聯(lián)文件，并建立主關鍵字索引（稱為主索引）；對每一個次關鍵字項建立次關鍵字索引（稱為次索引），所有具有同一次關鍵字的記錄構成一個鏈表。 主索引為非稠密索引，一組記錄建立一個索引項；次索引為稠密索引，每個記錄建立一個索引項，每個索引項包括次關鍵字、頭指針和鏈表長度。,多關鍵字文件舉例,例如，下圖所示為一個多重表文件。其中工號為主關鍵字，記錄按工號順序鏈接。,多關鍵字文件舉例（續(xù)）,對工號非稠密索引分成三個子鏈表，其索引如下圖(b)所示，索引項中的主關鍵字為各組中關鍵字的最大值。職稱和專業(yè)是兩個次關鍵字項，其索引分別如下圖(c)和(d)所示，具有相同次關鍵字值的記錄鏈接在同一鏈表中。,多關鍵字文件（續(xù)）,有了這些次關鍵字索引，根據(jù)關鍵字值找到鏈表頭指針，然后從頭指針出發(fā)可列出鏈表中所有記錄。比如查詢數(shù)學專業(yè)的教授，可以專業(yè)索引表中找到“數(shù)學”的頭指針和表長，逐一讀取記錄查看哪些記錄的職稱為教授即可。此查詢也可從職稱索引入手進行。當然，較好的方法是先讀長度較短的鏈表中的記錄。 在多重表文件中插入一個記錄是容易的，只要修改指針將記錄插在鏈表的頭指針之后即可。然而要刪去一個記錄卻很繁瑣 ，需要在每個次關鍵字的鏈表中刪去該記錄。,多關鍵字文件（續(xù)）,倒排文件（inverted file）和多重表文件的區(qū)別在于次關鍵字索引的結構不同。倒排文件的次關鍵字索引稱為倒排表，在倒排表的索引項中沒有頭指針和鏈長度，而是直接用一個項存放具有同一關鍵字的所有記錄的物理記錄號或主關鍵字值。值得注意的是，倒排表中具有同一次關鍵字的記錄號是有序排列的。上例的倒排表如下圖所示：,多關鍵字文件（續(xù)）,倒排表作索引的好處在于檢索記錄較快。特別是對某些詢問，不用讀取記錄就可得到答案。例如上例查詢數(shù)學專業(yè)教授，只要將“數(shù)學”索引中的記錄號和“教授”索引中的記錄號求集合的交集運算就可以了，即2，5，92，6=2就得到記錄號為2者便是數(shù)學教授。 在插入和刪除記錄時，倒排表也要進行相應修改；需要移動索引項中記錄號以保持其有序排列。若數(shù)據(jù)文件是索引順序文件（如ISAM文件），倒排表中應存放記錄的主關鍵字而不是物理記錄號。 倒排文件的缺點是維護困難。同一倒排表中各項長度不同，不同倒排表的長度也不同，這些都給倒排文件的維護帶來一定的困難。,6.3 大批量數(shù)據(jù)的組織策略,6.3.1 文件的組織 6.3.2 數(shù)據(jù)庫技術,文件系統(tǒng)的缺陷,利用文件組織大批量數(shù)據(jù)是數(shù)據(jù)組織中行之有效的方法，然而，文件系統(tǒng)也存在著一些明顯的缺陷。如： 數(shù)據(jù)冗余大。因為每個文件都是為特定用途設計的，因此會造成同樣的數(shù)據(jù)在多個文件中的重復存儲。 數(shù)據(jù)的不一致性，這往往是由于數(shù)據(jù)冗余所造成的；在數(shù)據(jù)更新時，稍有不慎就會造成同一數(shù)據(jù)在不同文件中的不一致。 程序和數(shù)據(jù)之間的獨立性差。應用程序依賴于文件的存儲結構，使得在對文件的存儲結構進行修改時，必須修改應用程序。 數(shù)據(jù)聯(lián)系弱。文件與文件之間是獨立的，文件之間的聯(lián)系必須通過程序來構造。因此，文件系統(tǒng)是一個不具有彈性的無結構的數(shù)據(jù)集合，難以反應客觀世界中事物之間的聯(lián)系。,數(shù)據(jù)庫技術誕生,為了克服上述文件系統(tǒng)的不足，20世紀60年代后期開始誕生了解決大批量數(shù)據(jù)組織和管理的數(shù)據(jù)庫技術。數(shù)據(jù)庫技術誕生的標志性事件是： 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 language）下屬的數(shù)據(jù)庫任務組DBTG（database task group）對數(shù)據(jù)庫方法進行了系統(tǒng)的研究，在20世紀60年代末期和70年代初期發(fā)表了若干個報告（稱為DBTG報告），該報告建立了數(shù)據(jù)庫的許多概念、方法和技術。DBTG所提議的方法是基于網(wǎng)狀數(shù)據(jù)模型的。 從1970年起，IBM的研究員E.F.Codd發(fā)表了一系列的論文，提出了數(shù)據(jù)庫的關系模型，開創(chuàng)了數(shù)據(jù)庫關系方法和關系數(shù)據(jù)理論的研究，為關系數(shù)據(jù)庫的發(fā)展和理論研究奠定了基礎。,數(shù)據(jù)庫技術,數(shù)據(jù)庫技術發(fā)展到現(xiàn)在，已經(jīng)是一門非常成熟的技術，作為算法與數(shù)據(jù)結構課程的后續(xù)課程。 概括地講，數(shù)據(jù)庫具有如下基本特征： 數(shù)據(jù)庫是相互關聯(lián)的數(shù)據(jù)的集合。 數(shù)據(jù)庫用綜合的方法組織數(shù)據(jù)，并保證盡可能高的訪問效率。 數(shù)據(jù)庫具有較小的數(shù)據(jù)冗余，可供多個用戶共享。 數(shù)據(jù)庫具有較高的數(shù)據(jù)獨立性。 數(shù)據(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ù)模型的基礎上的數(shù)據(jù)庫，層次數(shù)據(jù)模型以樹結構來表示實體之間的聯(lián)系。 樹中的結點表示實體集（文件或記錄型），連線表示兩個實體之間的聯(lián)系，且這種聯(lián)系只能是一對多的。 對于多對多的聯(lián)系不能直接用層次模型表示，需要分解成兩個層次型。 層次數(shù)據(jù)庫的典型代表是IBM公司1969年誕生的IMS。,網(wǎng)狀數(shù)據(jù)庫,網(wǎng)狀數(shù)據(jù)庫是建立在網(wǎng)狀數(shù)據(jù)模型的基礎上的數(shù)據(jù)庫，網(wǎng)狀數(shù)據(jù)模型以圖結構來表示實體之間的聯(lián)系，這種聯(lián)系是一種多對多的聯(lián)系。 然而，多對多的聯(lián)系實現(xiàn)起來太復雜了，所以在一些實際的支持網(wǎng)狀數(shù)據(jù)模型的數(shù)據(jù)庫管理系統(tǒng)上，對多對多聯(lián)系還是做了限制。如網(wǎng)狀模型的典型代表CODASYL系統(tǒng)就僅支持一對多的聯(lián)系，它按系（set）組織數(shù)據(jù)。系可理解為命了名的聯(lián)系，由一個雙親記錄和一個或多個子記錄型組成。,關系數(shù)據(jù)庫,關系數(shù)據(jù)庫可以看作是第二代數(shù)據(jù)庫系統(tǒng)。 關系數(shù)據(jù)庫是建立在關系數(shù)據(jù)模型基礎之上的數(shù)據(jù)庫，關系數(shù)據(jù)模型用關系（即二維表格數(shù)據(jù)）表示實體之間的聯(lián)系。 通俗地講，關系就是二維表格；表格中的每一行稱作一個元組，相當于一個記錄值；每一列是一個屬性值集，列可以命名，稱作屬性名。 由此可以說，關系是元組的集合，如果表格有n列，則稱該關系為n元關系。,關系模型中的操作,關系模型中的操作有： 傳統(tǒng)的集合運算：交、并、差和廣義笛卡積等； 專門的關系運算：選擇、投影、連接和除等； 有關的數(shù)據(jù)操作：查詢、插入、刪除和修改等。,對數(shù)據(jù)庫技術的研究,對數(shù)據(jù)庫技術的研究是從以下三個方面進行的： 數(shù)據(jù)模型。數(shù)據(jù)模型的研究是數(shù)據(jù)庫系統(tǒng)的基礎研究，重點研究如何構造數(shù)據(jù)模型，如何表示數(shù)據(jù)及其聯(lián)系。現(xiàn)在的重點研究課題是面向對象模型。 應用領域。數(shù)據(jù)庫技術的最初應用主要是信息管理領域，事實上，只要有大量數(shù)據(jù)要管理或者需要大批量數(shù)據(jù)支持的工作，都可以使用數(shù)據(jù)庫。 計算機技術。計算機技術的發(fā)展促進了數(shù)據(jù)庫技術的發(fā)展。通過將計算機技術的一些研究領域與數(shù)據(jù)庫技術相結合，產(chǎn)生了許多新的數(shù)據(jù)庫系統(tǒng)。,第6章 數(shù)據(jù)結構的程序實現(xiàn),6.1 基本的實現(xiàn)策略 6.2 動態(tài)結構的靜態(tài)實現(xiàn) 6.3 大批量數(shù)據(jù)的組織策略 6.4 數(shù)據(jù)結構在問題建模中的應用,6.4 數(shù)據(jù)結構在問題建模中的應用,6.4.1 Josephus問題 6.4.2 教務管理與二分圖 6.4.3 學籍管理系統(tǒng)中的數(shù)據(jù)組織,Josephus問題,Josephus問題是由古羅馬著名史學家Josephus所提出的問題演變而來的。Josephus問題的提法很多，如“猴子選大王問題”、“旅行社獎游客問題”等，就其數(shù)學本質(zhì)而言是相同的問題。Josephus問題的一般描述如下： 設有n個人圍坐一圈并由1到n編號。從某個人（例如編號為k的人）開始報數(shù)，數(shù)到m的人出列；接著從出列的下一個人開始重新1到m報數(shù)，數(shù)到m的人又出列；如此反復地報數(shù)和出列，直到最后一個人出列為止。試設計確定這n個人出列序列的程序。,Josephus問題（續(xù)）,由問題描述可以很自然地聯(lián)想到循環(huán)鏈表，用循環(huán)鏈表對Josephus問題建模，可以做到程序世界和問題世界的完全一致性，符合面向對象的程序設計思想。 考慮到反復報數(shù)的過程，可選用不帶頭結點的單循環(huán)鏈表，以避免報數(shù)過程中識別頭結點的麻煩。 由此，程序中可以先構建一個具有n個結點的單循環(huán)鏈表，然后從約定的結點開始1到m計數(shù)，計到m時從鏈表中刪除對應結點；接著從被刪除結點的下一個結點起計數(shù)，直到最后一個結點從鏈表中刪除后結束。,Josephus問題舉例,例如，若n8，m=3，k=1時，出列的序列為3，6，1，5，2，8，4，7。如下圖給出了問題求解過程示意圖，圖中的箭頭表示當前報數(shù)的位置，虛線框中為要出列者的序號，實黑框中為已出列者的序號，空白框中為未出列者的序號。,Josephus問題算法描述,用C語言編寫利用單循環(huán)鏈表求解Josephus問題程序如下： #include “stdio.h” #include “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; /*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*/,Josephus問題算法描述（續(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ù)組下標與n個人的編號可以一致起來（不用下標0），故僅用一維數(shù)組即可，其中數(shù)組元素作為靜態(tài)指針指向下一個人，這種實現(xiàn)方法稱作環(huán)形數(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;i<n;i+) Ri=i+1;,Josephus問題算法描述（續(xù)）,Rn=1; if(k=1) j=n; else j=k-1; /*初始化報數(shù)變量j*/ while(Rj!=j) for(i=1;i<=m;i+) /*由1到m報數(shù)*/ J=Rj; printf(“%dn”,Rj);/*出列*/ Rj=RRj; /*刪除第j個結點*/ printf(“%dn”,Rj); /*最后一個出列者*/ /*Josephus end*/,Josephus問題算法描述（續(xù)）,void main() int n,m,k; printf(“Josephus問題求解：”); scanf(“%d%d%d”, /*main end*/,6.4 數(shù)據(jù)結構在問題建模中的應用,6.4.1 Josephus問題 6.4.2 教務管理與二分圖 6.4.3 學籍管理系統(tǒng)中的數(shù)據(jù)組織,二分圖,設G=(V，E)是一個無向圖，其中V=v1，v2，vn，E e1，e2，en 。如果頂點集合V可以分割成為兩個互不相交的子集X和Y，使圖中每條邊ei=(vi，vj)都具這樣的性質(zhì)：其一個端點vi是X中的頂點（即viX）而另一個端點vj是Y中的頂點（即vjY），則稱圖G是一個二分圖（bipartite graph）。,教務管理與二分圖,在高等學校的教務管理中，處理學生選課是一項日常工作。每個學生可同時選修多門課程，每門課程也允許多個學生同時選修。這種學生與課程之間的關系可以用二分圖表示為如右圖所示，圖中的頂點由學生和課程組成，邊（s，c）表示學生s選修課程c。,教務管理與二分圖（續(xù)）,教務員經(jīng)常需要做如下一些管理工作： 登記學生選修的課程； 撤銷學生的修課登記； 查看某個學生選修哪些課程； 查看某個課程有哪些學生選修。 這些管理工作即是對二分圖做相應的插入、刪除和檢索操作。 在現(xiàn)實社會中，諸如商店與商品、商店與顧客、技術人員與技術職稱、教師與課程等許多管理問題都和學生與課程問題類似，都可以用二分圖來表示。二分圖是數(shù)據(jù)庫等應用系統(tǒng)的重要的數(shù)據(jù)結構。,教務管理與二分圖（續(xù)）,由于二分圖中頂點集合V分割成為兩個互不相交的子集X和Y，同一子集中（X中或Y中）的頂點無邊相連，這就使得二分圖的鄰接矩陣呈現(xiàn)為一個對稱分塊矩陣： 即二分圖可以用特殊的存儲結構矩陣B陣來表示。 顯然，用矩陣B表示二分圖比鄰接矩陣A節(jié)省存儲空間。然而矩陣B也可能是一個稀疏矩陣，可針對具體情況作進一步的壓縮存儲處理，,教務管理與二分圖舉例,例如，前例中圖的二分圖SCG的鄰接矩陣如下圖(a)所示，為一對稱分塊矩陣；其特殊存儲表示即矩陣B如下圖 (b)所示。,教務管理與二分圖（續(xù)）,教務管理中的另一項重要的日常工作是安排教師教學工作。在一般情況下，每位教師通?？梢詣偃味嚅T課程的教學，而在一個學期內(nèi)只講授他所勝任的一門課程；反之，在一個學期內(nèi)一門課程只需一位教師主講。這就需要對教師和課程作合理安排，我們可以用一個二分圖來表示教師與課程之間的這種關系，教師和課程都是圖中的頂點，邊（t，c）表示教師t勝任課程c，右圖給出了五位教師和五門課程之間關系的二分圖。,教務管理與二分圖（續(xù)）,為每位教師安排一門課程，相當于為每個教師頂點選擇一條和課程頂點相關聯(lián)的邊，使任何兩個教師頂點不和同一課程頂點相鄰接。這種安排課程給每位教師的問題，實際上是圖的匹配問題。圖匹配問題的一般描述如下： 給定一個圖G=(V，E)，若邊集合E的一個子集M中任意兩條邊都不依附圖中的同一個頂點，稱M是圖G的一個匹配（matching）；G的邊數(shù)最多的匹配稱作G的最大匹配（maximal matching）。如果在圖G的一個匹配中，圖中每個頂點都是該匹配中某條邊的端點，則稱該匹配為圖G的完全匹配（complete matching）。圖G的任何一個完全匹配，一定都是圖G的最大匹配。,二分圖TCG的匹配和最大匹配示例,下圖(a)和(b)的實線邊分別給出了前例中二分圖TCG的一個匹配和一個最大匹配的示例。,二分圖TCG的匹配和最大匹配,為了求出一個圖的最大匹配，顯而易見的辦法是列舉出該圖的全部匹配，然后選出邊數(shù)最多的一個匹配。然而，這種方法的時間復雜度是邊數(shù)的指數(shù)階函數(shù)。因此，需要一種更有效的匹配算法。 下面介紹一種利用增廣路徑求最大匹配的有效算法。 設M是圖G的一個匹配，我們將M中的邊所關聯(lián)的頂點稱為已匹配頂點，其余頂點稱為未匹配頂點。若P是圖G中一條連通兩個未匹配頂點的路徑，并且在P上屬于M的邊和不屬于M 的邊交替出現(xiàn)，則稱P為一條關于M的增廣路徑（augmenting path）。,二分圖TCG的匹配和最大匹配（續(xù)）,由利用增廣路徑求最大匹配的有效算法的定義可有如下結論： 一條關于M的增廣路徑的長度必為奇數(shù)，且路徑上的第一條邊和最后一條邊都不屬于M。 對于一條關于M的增廣路徑P，由對稱差集運算MP可以得到一個比M更大的匹配。即這個更大的匹配包括所有在M中但不在P中和在P中但不在M 中的邊的集合構成。 M為G的一個最大匹配，當且僅當不存在關于M的增廣路徑。 結論和是顯而易見的。 對于結論，當存在一條關于M的增廣路徑時，由結論知M不是最大匹配；反之，當M不是最大匹配時，一定可以找到一條關于M的增廣路徑。,二分圖TCG的匹配和最大匹配（續(xù)）,事實上，設N是一個比M更大的匹配，并令=(V，MN)；因為M和N都是G的一個匹配，所以V中的頂點最多和M中的一條邊相關聯(lián)，也最多和N 中的一條邊相關聯(lián)；于是的每個連通分量都是由M和N中的邊交替組成的一條簡單路徑或環(huán)，每個環(huán)中所含M和N的邊數(shù)相等，而每條簡單路徑是一條關于M的增廣路徑或關于N的增廣路徑，由于中的邊MN所含N的邊數(shù)較M多，所以中必含一條關于M的增廣路徑。 由此，求圖G=(V，E)的最大匹配M的算法可描述如下： 置M為空集； 找出一條關于M的增廣路徑P，并用MP代替M； 重復步驟直至不存在關于M的增廣路徑，此時得到的匹配M即為G的最大匹配。,二分圖TCG的匹配和最大匹配（續(xù)）,在上述算法中，關鍵問題是如何根據(jù)已有匹配M找出G中關于M 的一條增廣路徑。為簡化起見，我們只討論G是二分圖的情形。 設M是G的一個匹配，用類似于圖的廣度優(yōu)先搜索過程構造一棵樹。設層號為i，當i=0時取G的一個未匹配頂點作為樹根；當i為奇數(shù)時，將那些與第i-1層中一個頂點相關聯(lián)但不屬于M的邊，連同該邊相關聯(lián)的另一個頂點一起添加到樹上；當i為偶數(shù)時，則是添加那些與第i-1層中一個頂點相關聯(lián)且屬于M的邊以及該邊所關聯(lián)的另一個頂點。 如果在上述樹的構造過程中，發(fā)現(xiàn)一個未匹配頂點v被作為樹的奇數(shù)層頂點，則從樹根到頂點v的路徑就是一條關于M的增廣路徑；如果在樹的構造過程中既沒有找到增廣路徑，又無法按要求往樹上添加新的邊和頂點，則可在剩余頂點中再取一個未匹配頂點作樹根構造新的一棵樹。這個過程一直進行下去，如果不存在其它未匹配頂點，即最終仍未得到任何增廣路徑，就說明M已為一個最大匹配了。,二分圖TCG的匹配和最大匹配舉例,例如，對前例圖 (a)中實線邊（圖TCG的匹配M）： 按上述方法取未匹配頂點t5作為樹根，頂點c1是樹上惟一的第一層中的頂點，未匹配邊（t5，c1）是樹上的一條邊； 頂點t2處于樹的第二層，邊（c1，t2）屬于M且關聯(lián)于c1是樹上的又一條邊； 與t2相關聯(lián)但不屬于M的邊有（t2，c4）和（t2，c5）添加到樹中，同時頂點c4和c5添加到樹中作為第三層； 由于c5是未匹配頂點， 所以到此找到了一條增廣路徑P：t5c1t2c5。