【正文】 算法與數(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) =程序 ” 的公式 ，得到了計算機科學界的普遍認可 。 ?在程序設計語言中如何表示數(shù)據(jù)和控制 ， 很大程度上決定了如何使用這個語言來編寫程序；所以在程序設計語言中不僅提供了與程序控制流程有關的控制結(jié)構(gòu) ， 同時也提供了與程序中數(shù)據(jù)信息組織有關的數(shù)據(jù)結(jié)構(gòu) 。 ?程序設計的主要任務就是在選取或組織適當?shù)臄?shù)據(jù)結(jié)構(gòu)的基礎上 ， 利用三種基本結(jié)構(gòu) （ 順序 、 選擇 、 重復 ） 把逐級分解得到的一系列基本操作組織起來 ， 形成用某種特定語言書寫的源程序 。 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) (續(xù) ) ?《 算法與數(shù)據(jù)結(jié)構(gòu) 》 課程討論數(shù)據(jù)結(jié)構(gòu)的目的 ， 就是為了在設計給定問題的求解算法時 ， 應用這些數(shù)據(jù)結(jié)構(gòu)來組織程序中的數(shù)據(jù)；從而降低問題的分析與設計難度 ， 提高程序 （ 或算法 ） 的設計質(zhì)量 ， 縮短設計周期 。 ?這里就有一個在程序中如何實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的問題 。 實現(xiàn)是使用的前提 ， 只有在程序中實現(xiàn)了數(shù)據(jù)結(jié)構(gòu) ， 才能在程序中利用數(shù)據(jù)結(jié)構(gòu)對給定問題進行有效地求解 。 ?本章將從幾個不同的角度討論如何在程序中實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的問題 。 第 6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 基本的實現(xiàn)策略 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 大批量數(shù)據(jù)的組織策略 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應用 基本的實現(xiàn)策略 ?程序設計語言中提供了與程序中數(shù)據(jù)信息組織有關的數(shù)據(jù)結(jié)構(gòu) ， 但沒有也不可能提供所有的數(shù)據(jù)結(jié)構(gòu) 。 ?一方面 ， 受科學技術和生產(chǎn)力發(fā)展水平的限制 ， 人類認知世界具有歷史局限性；人們不可能在某一天完成對現(xiàn)實世界的認知過程 ， 同樣也不可能在某一天說對數(shù)據(jù)結(jié)構(gòu)的認知過程已經(jīng)完結(jié) ， 這種認知過程是一個漸進式不斷深化和逐步完善的過程 。 ?另一方面 ， 受計算機科學發(fā)展和計算機系統(tǒng)本身的限制 ， 人們不可能研制出一種設施包羅萬象 、 功能應有盡有的計算機語言和語言翻譯系統(tǒng) 。 ?因此 ， 程序設計語言中只可能提供一些基本的和常用的數(shù)據(jù)結(jié)構(gòu)設施 ， 并提供一些構(gòu)造求解現(xiàn)實世界中問題所需數(shù)據(jù)結(jié)構(gòu)的基本設施和方法手段 。 基本的實現(xiàn)策略 簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 數(shù)據(jù)結(jié)構(gòu)的鏈式實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實現(xiàn) 簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) ? 簡單的數(shù)據(jù)結(jié)構(gòu) ， 在程序設計語言中已經(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等 。 基本的實現(xiàn)策略 簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 數(shù)據(jù)結(jié)構(gòu)的鏈式實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實現(xiàn) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) ?還有一些簡單類型和構(gòu)造類型 ， 也是在程序設計語言中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu) 。 如枚舉型 、 子界型 、日期型 、 集合 、 數(shù)組 、 字符串 、 記錄 、 文件等 。 ?程序設計語言中提供了程序設計人員在程序中說明這些數(shù)據(jù)類型的方法 ， 程序設計人員只要在程序中的適當位置按照相應的格式和要求對程序中的數(shù)據(jù)進行說明就可以使用了 。 如 C語言中的枚舉 、 數(shù)組 、字符串 、 結(jié)構(gòu)體 、 共同體 、 文件等 。 基本的實現(xiàn)策略 簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 數(shù)據(jù)結(jié)構(gòu)的鏈式實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的鏈式實現(xiàn) ? 其它的數(shù)據(jù)結(jié)構(gòu) ， 如鏈表 、 循環(huán)鏈表 、 棧 、 隊列 、廣義表 、 樹 、 二叉樹 、 圖 、 網(wǎng)和堆等 ， 在程序設計語言中一般都沒有提供其相應的數(shù)據(jù)類型 ， 程序設計人員不能夠在程序中用類型說明的辦法直接引入 。 ?然而 ， 許多程序設計語言都提供有指針類型 ， 程序設計人員可以利用指針類型在程序中動態(tài)建立所需要的某種數(shù)據(jù)結(jié)構(gòu) 。 ?一般地 ， 在建立某種數(shù)據(jù)結(jié)構(gòu)之前 ， 先需要說明其數(shù)據(jù)元素的結(jié)點類型 ， 如說明成記錄 、 結(jié)構(gòu)體等 ，再用指針變量動態(tài)建立起相應的數(shù)據(jù)結(jié)構(gòu) ， 以供求解問題的程序使用或處理 。 基本的實現(xiàn)策略 簡單數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 構(gòu)造型數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 數(shù)據(jù)結(jié)構(gòu)的鏈式實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)的數(shù)組實現(xiàn) ?如果在程序設計語言中沒有提供指針變量 ， 就不能動態(tài)實現(xiàn)程序中需要的數(shù)據(jù)結(jié)構(gòu)；還有一些數(shù)據(jù)結(jié)構(gòu) ， 不宜借助指針來實現(xiàn) ， 如順序表 、 順序棧 、 順序隊列等 。 對于這兩種情況 ， 程序設計人員都可以在程序中利用數(shù)組模擬實現(xiàn)程序中需要的一些數(shù)據(jù)結(jié)構(gòu) 。 ? 數(shù)組是每一種高級程序設計語言都提供了的數(shù)據(jù)結(jié)構(gòu) 。 可以利用一維數(shù)組模擬實現(xiàn)順序表 、 順序棧 、 順序隊列 。 可以利用二維數(shù)組模擬實現(xiàn)鏈表或循環(huán)鏈表 ， 其中一列描寫一個數(shù)據(jù)元素 （ 或結(jié)點 ） ；若構(gòu)成數(shù)據(jù)元素各字段類型不一致 ，也可改用兩個或多個一維數(shù)組來模擬實現(xiàn)之 。 可用三個一維數(shù)組來模擬實現(xiàn)二叉樹 ， 其中一個數(shù)組存放數(shù)據(jù)域的值 ， 兩個數(shù)組分別作為左右鏈域 。 樹可通過左孩子右兄弟表示法轉(zhuǎn)化為二叉樹用數(shù)組表示 ， 而圖和網(wǎng)的鄰接矩陣表示法本身就是用二維數(shù)組表示的方法 。 第 6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 基本的實現(xiàn)策略 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 大批量數(shù)據(jù)的組織策略 數(shù)據(jù)結(jié)構(gòu)在問題建模中的應用 動態(tài)結(jié)構(gòu)的靜態(tài)實現(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ù) ， 在編譯時無法預先規(guī)定它們所需要分配的存儲空間大小 ， 只有在運行時進行動態(tài)存儲分配 ， 與之相對應的是 靜態(tài)數(shù)據(jù)結(jié)構(gòu) （ static data structure） ，數(shù)據(jù)所需存儲空間是一個固定的有限區(qū)域 ， 可在程序說明中顯式規(guī)定 ， 在編譯時靜態(tài)進行存儲分配 。 ? 凡是可以用指針動態(tài)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu) ， 都可以利用數(shù)組靜態(tài)地模擬實現(xiàn) 。 有時也把這種利用數(shù)組靜態(tài)模擬實現(xiàn)了的動態(tài)結(jié)構(gòu)稱之為 半靜態(tài)數(shù)據(jù)結(jié)構(gòu) （ semistatic data structure） 。當然 ， 半動態(tài)結(jié)構(gòu)中也包含可變數(shù)組和變長記錄等部分采用靜態(tài)分配 、 部分采用動態(tài)分配的數(shù)據(jù)結(jié)構(gòu) 。 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 靜態(tài)鏈表 二叉樹的靜態(tài)二叉鏈表表示法 樹和森林的雙親表示法 哈夫曼算法的靜態(tài)實現(xiàn) 靜態(tài)鏈表 ?在利用提供指針類型的高級程序設計語言編寫程序時 ， 鏈表的實現(xiàn)是很簡單和很自然的 。 如果語言中沒有提供指針類型 ， 可以用 數(shù)組 來模擬實現(xiàn)鏈表結(jié)構(gòu) ， 并稱之為 靜態(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為結(jié)點類型標識符 */ snode s[maxsize]。 /*s為基類型是 snode的一維數(shù)組 ， 即記錄數(shù)組 */ 靜態(tài)鏈表（續(xù) ） ?注意 這里的 next域說明與單鏈表中的說明不同 ， 在單鏈表中是指向結(jié)構(gòu)體的指針類型 ， 值為結(jié)點的實際地址；在靜態(tài)鏈表中是 int類型 ， 值為結(jié)點在 s 數(shù)組中的下標值 ， 指針值為空時用 1表示 。 ? 對于靜態(tài)鏈表實現(xiàn)線性表的各種運算操作與動態(tài)的單鏈表上的實現(xiàn)基本相同 ， 所不同的是在存儲區(qū)的管理上有差別 。 ?單鏈表上的運算操作實現(xiàn)不要考慮存儲區(qū)的管理問題 ， 是通過 malloc函數(shù)獲得結(jié)點空間并利用 free函數(shù)釋放結(jié)點空間 ，存儲區(qū)的管理交由系統(tǒng)完成； ?而靜態(tài)鏈表的存儲區(qū)就是這個記錄數(shù)組 s， 獲得結(jié)點空間和釋放結(jié)點空間都對數(shù)組 s進行 ， 必須在程序中設計相應的管理程序段 。 靜態(tài)鏈表及其存儲區(qū)管理 舉例 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 靜態(tài)鏈表 二叉樹的靜態(tài)二叉鏈表表示法 樹和森林的雙親表示法 哈夫曼算法的靜態(tài)實現(xiàn) 二叉樹的靜態(tài)二叉鏈表表示法 ?對于沒有提供指針類型的高級程序設計語言 ， 程序中要用到二叉樹結(jié)構(gòu)組織數(shù)據(jù)信息 ， 可用 靜態(tài)二叉鏈表 （ static binary linked list） 表示法實現(xiàn)二叉樹結(jié)構(gòu) 。 和靜態(tài)鏈表類似 ，靜態(tài)二叉鏈表的存儲區(qū)管理也是利用以結(jié)點類型作為基類型的一維數(shù)組實現(xiàn)；獲得結(jié)點空間的函數(shù) malloc和釋放結(jié)點空間的 free函數(shù)的實現(xiàn)也是類似的 。 ?用靜態(tài)二叉鏈表表示二叉樹的類型定義如下： define maxsize 100 typedef struct /*定義結(jié)點類型為結(jié)構(gòu)體 */ {elementype data。 /*數(shù)據(jù)域為元素類型 */ int lchild,rchild。 /*定義左右孩子域為整型 */ }sbinarytree。 sbinarytree st[maxsize]。 二叉樹的靜態(tài)二叉鏈表表示法 ? 和靜態(tài)鏈表一樣 ， 靜態(tài)二叉鏈表的左孩子域和右孩子域也都是 int類型 ， 其值為數(shù)組中的下標值 。 ?靜態(tài)二叉鏈表的存儲區(qū)管理是利用右孩子域形成的靜態(tài)鏈棧 av， 用 1表示指針為 NULL的情況 。 ? 除了在插入結(jié)點時獲取一個結(jié)點空間以及在刪除時釋放一個結(jié)點空間的存儲區(qū)管理是要在程序中完成之外 ， 用靜態(tài)二叉鏈表表示的二叉樹的各種運算操作與用二叉鏈表表示的二叉樹的相應運算操作一致 。 二叉樹的靜態(tài)二叉鏈表表示法舉例 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 靜態(tài)鏈表 二叉樹的靜態(tài)二叉鏈表表示法 樹和森林的雙親表示法 哈夫曼算法的靜態(tài)實現(xiàn) 樹和森林的雙親表示法舉例 ?在前面我們介紹了樹和森林的兩種存儲表示方法 ， 即孩子鏈表表示法和左孩子右兄弟表示法；這兩種表示方法 ， 都可以通過靜態(tài)鏈表和靜態(tài)二叉鏈表來實現(xiàn) 。 ?樹和森林還有一種存儲表示方法 ， 就是雙親表示法 。 因為樹和森林中的每一個結(jié)點 ， 其雙親結(jié)點是惟一的；利用這一性質(zhì) ， 在存儲結(jié)點信息時為每個結(jié)點增加一個指向其雙親的指針 parent， 就可以惟一地表示樹或森林 。 ? 若用靜態(tài)鏈表實現(xiàn)樹和森林的雙親表示法 ， 其類型定義如下： define maxsize 100 typedef struct {elementype data。 int parent。 }sptnode。 sptnode pt[maxsize]。 樹和森林的雙親表示法 動態(tài)結(jié)構(gòu)的靜態(tài)實現(xiàn) 靜態(tài)鏈表 二叉樹的靜態(tài)二叉鏈表表示法 樹和森林的雙親表示法 哈夫曼算法的靜態(tài)實現(xiàn) 哈夫曼算法的靜態(tài)實現(xiàn) ? 由于哈夫曼樹中沒有度為 1的結(jié)點 ， 一棵有 n個葉子結(jié)點的哈夫曼樹有 2n1個結(jié)點 ， 所以可用大小為 2n1個元素的數(shù)組構(gòu)造靜態(tài)鏈表來存儲哈夫曼樹 ， 一個數(shù)組元素中存放一個結(jié)點 。 ?結(jié)點的結(jié)構(gòu)可以這樣來考慮 ， 由于每個葉子結(jié)點都有一個權(quán)重值 ，構(gòu)造哈夫曼樹的過程中每個分枝結(jié)點的權(quán)重值等于兩個孩子結(jié)點權(quán)重值的和 ， 所以應該有一個權(quán)重域和指向左右孩子的兩個指針域； ?另外在建成哈夫曼樹之后 ， 為了求得每個葉子結(jié)點的哈夫曼編碼 ，需要走一條從葉子結(jié)點到根結(jié)點的路徑 ， 而譯碼的過程是從根結(jié)點出發(fā)到葉子結(jié)點的不斷匹配的過程 ， 所以既需要知道孩子結(jié)點的信息 ， 也需要知道雙親結(jié)點的信息 ， 應該再有一個指向雙親結(jié)點的指針域 。 ?由此可知每個結(jié)點至少應該有一個權(quán)重域 weight和三個指針域parent、 lchild和 rchild， 也就是說要用靜態(tài)三叉鏈表來表示哈夫曼樹 。 哈夫曼樹及其靜態(tài)三叉鏈表存儲表示示例 哈夫曼算法的靜態(tài)實現(xiàn) (續(xù) ) ?由于在實際構(gòu)造哈夫曼樹時 ， 是由葉子結(jié)點的權(quán)值逐級構(gòu)造最后生成樹根 ， 且在構(gòu)造過程中僅與葉子結(jié)點的權(quán)值有關而與葉子結(jié)點的數(shù)據(jù)域值無關； ?所以構(gòu)造算法的實現(xiàn)中可以不考慮葉子結(jié)點的數(shù)據(jù)域值 ， 并且在靜態(tài)三叉鏈表中從葉子結(jié)點開始存放 ， 然后不斷地把兩棵權(quán)值最小的子