第13章實習(xí)指導(dǎo)和實習(xí)題13.1實習(xí)目的和要求13.2實習(xí)步驟13.3實習(xí)報告13.4實習(xí)題13.5實習(xí)報告范例13.6上機(jī)考核

13.1實習(xí)目的和要求

13.1.1實習(xí)目的

“數(shù)據(jù)結(jié)構(gòu)”是一門計算機(jī)類專業(yè)的基礎(chǔ)課，該課程的目標(biāo)之一是使學(xué)生學(xué)會如何從問題出發(fā)，分析數(shù)據(jù)，構(gòu)造求解問題的數(shù)據(jù)結(jié)構(gòu)和算法，培養(yǎng)學(xué)生進(jìn)行較復(fù)雜程序設(shè)計的能力?！皵?shù)據(jù)結(jié)構(gòu)”是一門實踐性較強(qiáng)的課程，為了學(xué)好這門課程，實現(xiàn)課程目標(biāo)，要求每位學(xué)生完成一定數(shù)量的上機(jī)作業(yè)。通過上機(jī)作業(yè)，一方面使學(xué)生加深對課內(nèi)所學(xué)的各種數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲表示、運算以及算法等基本內(nèi)容的理解，學(xué)習(xí)如何運用所學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法知識處理應(yīng)用問題的方法；另一方面也使學(xué)生在程序設(shè)計方法(如抽象數(shù)據(jù)類型、結(jié)構(gòu)化分析、模塊化設(shè)計和結(jié)構(gòu)化程序設(shè)計)、C語言編程環(huán)境以及程序的調(diào)試和測試方面得到必要的訓(xùn)練。

13.1.2實習(xí)要求

實習(xí)題是與理論知識單元的學(xué)習(xí)配套的，因此在實習(xí)之前有必要先熟悉相關(guān)的理論知識。在實習(xí)的過程中有以下要求：

(1)要求仔細(xì)審題，明確題意，確定問題的要求是什么，而不要急于考慮如何做。

(2)按照抽象數(shù)據(jù)類型原則選擇和設(shè)計數(shù)據(jù)結(jié)構(gòu)，并定義運算。對每個ADT或運算必須給出它們完整的規(guī)范。

(3)所設(shè)計的C語言函數(shù)和程序，要求結(jié)構(gòu)清晰，可讀性好。

(4)學(xué)會分析所設(shè)計的算法的時間和空間復(fù)雜度。

(5)上機(jī)前還應(yīng)對程序進(jìn)行仔細(xì)的靜態(tài)檢查，合理選擇足夠的測試用例進(jìn)行測試，在TC2.0調(diào)試環(huán)境下診斷和糾正錯誤。

(6)一般需要對所設(shè)計的數(shù)據(jù)結(jié)構(gòu)和算法(函數(shù))進(jìn)行逐步求精，如果需要這樣做，還應(yīng)重復(fù)前面的步驟。

(7)上機(jī)實習(xí)結(jié)束后，認(rèn)真整理所編寫的源程序代碼和可執(zhí)行程序，遞交實習(xí)報告和程序代碼。報告的具體格式請參考13.3和13.5節(jié)。

13.2實習(xí)步驟

數(shù)據(jù)結(jié)構(gòu)上機(jī)實習(xí)應(yīng)體現(xiàn)附錄A.1介紹的結(jié)構(gòu)化方法的思想，分以下步驟進(jìn)行：

(1)問題分析：充分地分析和理解題目本身，明確題意，切實弄清題目要求做什么，限制條件是什么。這時不要急于考慮怎樣做的問題。

(2)模塊設(shè)計：采用自頂向下結(jié)構(gòu)化設(shè)計方法劃分模塊，設(shè)計程序的層次結(jié)構(gòu)，使用附錄A.2的結(jié)構(gòu)圖描述程序結(jié)構(gòu)。

(3)確定抽象數(shù)據(jù)類型：定義數(shù)據(jù)的邏輯結(jié)構(gòu)；定義運算的功能，確定輸入和輸出參數(shù)的個數(shù)和類型。使用附錄A.2的結(jié)構(gòu)圖描述函數(shù)間的調(diào)用關(guān)系，包括調(diào)用方式和數(shù)據(jù)傳遞方式。

(4)數(shù)據(jù)的存儲表示和算法設(shè)計：設(shè)計數(shù)據(jù)的存儲表示和實現(xiàn)運算的算法。使用示意圖和C語言數(shù)據(jù)類型描述數(shù)據(jù)的存儲結(jié)構(gòu)；算法可采用附錄A.2的流程圖描述，也可采用自然語言和C語言相結(jié)合的偽代碼描述。偽代碼描述的詳細(xì)程度建議為：按照該描述能準(zhǔn)確無誤地翻譯成C程序。

(5)分析算法的時間和空間復(fù)雜度。

(6)設(shè)計簡單的人機(jī)界面，如文本菜單等。

(7)使用附錄A.3的方法設(shè)計測試用例，應(yīng)包括正確的輸入及其預(yù)期的輸出結(jié)果，以及有錯誤的輸入及其輸出結(jié)果。

(8)編寫C語言程序代碼。

(9)應(yīng)當(dāng)對數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行逐步求精，如果這樣，還需重復(fù)前面的步驟。

(10)使用測試用例測試程序，發(fā)現(xiàn)、診斷和糾正錯誤；運行程序，分析整理運行結(jié)果；測試一個程序的實際運行時間。

(11)認(rèn)真整理文檔，完成實習(xí)報告。

13.3實習(xí)報告

實習(xí)報告應(yīng)包括以下各項內(nèi)容。

1．問題陳述和需求分析

(1)以簡潔明了的語言說明程序設(shè)計的任務(wù)和目標(biāo)。

(2)給出程序規(guī)范，包括程序的功能、程序的輸入和輸出數(shù)據(jù)的形式和值的范圍。

(3)給出系統(tǒng)測試數(shù)據(jù)，包括程序正確的輸入數(shù)據(jù)和預(yù)期的輸出結(jié)果，以及錯誤的輸入和可能的結(jié)果。

2．系統(tǒng)設(shè)計

(1)劃分模塊，給出各模塊(抽象數(shù)據(jù)類型、函數(shù))的功能說明。

(2)使用附錄A.2的結(jié)構(gòu)圖描述主程序(或菜單驅(qū)動程序)和各模塊間的層次調(diào)用關(guān)系。

(3)給出模塊測試數(shù)據(jù)：輸入數(shù)據(jù)和預(yù)期的輸出結(jié)果。

3．詳細(xì)設(shè)計

(1)描述數(shù)據(jù)結(jié)構(gòu)，包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

(2)使用附錄A.2的流程圖和/或偽代碼描述核心算法。

(3)描述函數(shù)間的調(diào)用關(guān)系。

4．算法分析

分析主要算法的時間復(fù)雜度，必要時分析空間復(fù)雜度。

5．程序清單

給出帶有注釋的C程序源代碼和編譯連接后的可執(zhí)行程序，使用學(xué)號為文件名。

6．測試用例和運行結(jié)果

列出所用的測試用例和相應(yīng)的程序運行結(jié)果。

7．用戶使用說明

必要時，編寫程序使用說明書，說明如何使用你所編寫的程序。

8．分析和體會 13.4實習(xí)題

實習(xí)1數(shù)組操作

1．實習(xí)目的

(1)復(fù)習(xí)C語言程序設(shè)計，加深對C語言基本要素的理解。

(2)掌握數(shù)組的構(gòu)造方法以及操作。

2．實習(xí)內(nèi)容和要求

(1)一維數(shù)組操作：

①設(shè)有長度為n的一維整型數(shù)組A，設(shè)計一個函數(shù)，將數(shù)組中所有的負(fù)數(shù)存放在數(shù)組的前部，所有的正數(shù)存放在數(shù)組的后部。

②設(shè)有長度為n的一維整型數(shù)組A，設(shè)計一個函數(shù)將原數(shù)組中的元素以逆序排列。

③設(shè)計主函數(shù)，驗證(a)和(b)兩個算法。

(2)二維數(shù)組操作。

#字棋游戲的規(guī)則是：從一個空的棋盤開始，白子先行，執(zhí)黑、白子兩方輪流放置棋子，若某一游戲者有三枚棋子占據(jù)了一橫行或一豎行或一對角線，則該游戲者獲勝；若直到整個棋盤被占滿時還沒有一方獲勝則為和局。棋盤結(jié)構(gòu)如圖13－1所示。設(shè)計一個游戲主程序類，由黑、白雙方在計算機(jī)鍵盤(或鼠標(biāo))上輸入棋步下棋，白子先行，黑、白兩方輪流輸入各自的棋步，直到出現(xiàn)勝局或和局為止。圖13－1#字棋棋盤實習(xí)2鏈表操作

1．實習(xí)目的

(1)復(fù)習(xí)C語言程序設(shè)計，加深對C語言基本要素的理解。

(2)掌握鏈表的構(gòu)造方法及其操作。

2．實習(xí)內(nèi)容和要求

設(shè)帶表頭的單循環(huán)鏈表中的每個結(jié)點存放一個字符。

(1)設(shè)計一個函數(shù)，從鍵盤輸入元素，建立一個鏈表。

(2)設(shè)計一個函數(shù)，打印(1)所建立的鏈表。

(3)設(shè)計一個函數(shù)，按字母、數(shù)字和其他字符將一個鏈表拆成三個鏈表(利用原來的結(jié)點)。

(4)設(shè)計一個函數(shù)，將數(shù)字鏈表鏈接到字母鏈表的尾部；將其他字符組成的鏈表鏈接到數(shù)字鏈表的尾部，形成一個帶表頭結(jié)點的單循環(huán)鏈表。要求回收多余的表頭結(jié)點。

(5)設(shè)計主函數(shù)，測試(1)、(2)、(3)和(4)的四個函數(shù)功能。實習(xí)3表達(dá)式計算

1．實習(xí)目的

(1)理解棧的后進(jìn)先出特性，學(xué)習(xí)使用棧處理應(yīng)用問題的方法。

(2)學(xué)習(xí)和理解棧，實現(xiàn)將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式后對后綴表達(dá)式求值的算法。

2．實習(xí)內(nèi)容和要求

(1)設(shè)計一個計算器程序，它具有下列功能：

①接收用戶輸入的中綴表達(dá)式。中綴表達(dá)式以#號結(jié)束，只允許包括?+、－、*、/、^(乘方)五種運算符，操作數(shù)可為正雙精度型，表達(dá)式允許出現(xiàn)嵌套的圓括號。

②將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式。

③計算后綴表達(dá)式的值。

④輸出表達(dá)式的計算結(jié)果。

(2)程序包括簡單的錯誤檢查功能，如缺少操作數(shù)、缺少運算符、括號不匹配等，并給出相應(yīng)的提示信息。

實習(xí)4隊列運算和用戶界面設(shè)計

1．實習(xí)目的

(1)理解隊列的先進(jìn)先出特性。

(2)掌握隊列的順序和鏈接存儲表示方法。

(3)掌握在不同的存儲結(jié)構(gòu)上實現(xiàn)隊列運算的算法。

2．實習(xí)內(nèi)容和要求

(1)使用循環(huán)隊列實現(xiàn)隊列ADT上定義的運算。

(2)使用帶表頭的單循環(huán)鏈表實現(xiàn)隊列運算。要求只使用一個隊列指針，且要求入隊列和出隊列運算的時間復(fù)雜度都是O(1)。

(3)編寫用于測試循環(huán)隊列和鏈?zhǔn)疥犃械牟藛畏绞降臏y試驅(qū)動程序，分別測試(1)和(2)的隊列運算。實習(xí)5線性表運算及應(yīng)用

1．實習(xí)目的

(1)理解線性表數(shù)據(jù)結(jié)構(gòu)。

(2)掌握線性表的順序和鏈接這兩種存儲表示方法。

(3)熟練掌握順序表和鏈表的各種基本操作。

(4)學(xué)習(xí)使用線性表解決應(yīng)用問題的方法。

2．實習(xí)內(nèi)容和要求

(1)順序表操作。假定順序表是有序的(設(shè)表中元素已按非遞減次序排列)，編寫函數(shù)，實現(xiàn)下列運算：

①?intSearch_Insert(List*lst，Tx)

在有序順序表中搜索元素x。若x在表中，則返回x在表中的位置。否則，若表未滿，則在表中插入新元素x，并且插入后線性表仍然是有序的，返回新元素x的位置；若表已滿，無法插入新元素，則返回－1。

②?voidSearch_Delete(List*lst,Tx,Ty)

設(shè)x≤y，刪除有序順序表中元素值在x和y之間(含x和y)的所有元素。

(2)單鏈表應(yīng)用。約瑟夫環(huán)(Josephus)問題描述如下，設(shè)n個人圍圓桌坐一圈，從第s個人開始報數(shù)，數(shù)到第m個人就離座，然后從離座的下一個人開始重新報數(shù)，數(shù)到第m個人再離座

如此反復(fù)，直到所有的人全部離座為止。使用不帶表頭結(jié)點的單循環(huán)鏈表存儲在座人，并設(shè)計和實現(xiàn)按離座順序輸出離座人的算法。實習(xí)6一元多項式的相加和相乘

1．實習(xí)目的

(1)深入理解線性表結(jié)構(gòu)，熟練掌握鏈表的基本操作。

(2)學(xué)會使用線性表解決應(yīng)用問題的方法。

2．實習(xí)內(nèi)容和要求

(1)建立一個多項式。

(2)打印(顯示)一個多項式。

(3)實現(xiàn)兩個多項式相加。

(4)實現(xiàn)兩個多項式相乘。

(5)多項式采用帶表頭的非循環(huán)鏈表存儲。

提示：可將乘數(shù)多項式的每一項與被乘數(shù)多項式的所有項分別相乘(即系數(shù)相乘，指數(shù)相加)，得到中間多項式后累加。實習(xí)7對稱矩陣的壓縮存儲

1．實習(xí)目的

(1)理解對稱矩陣的壓縮存儲方法。

(2)掌握使用壓縮存儲的對稱矩陣的存儲和輸出顯示的算法。

2．實習(xí)內(nèi)容和要求

(1)以行優(yōu)先方式將對稱矩陣的下三角元素保存在一維數(shù)組中。

(2)以普通方陣的形式輸出由(1)所生成的一維數(shù)組中的對稱矩陣。

(3)以列優(yōu)先方式將對稱矩陣的上三角元素保存在一維數(shù)組中。

(4)以普通方陣的形式輸出由(3)所生成的一維數(shù)組中的對稱矩陣。實習(xí)8稀疏矩陣的三元組表

1．實習(xí)目的

(1)理解稀疏矩陣的壓縮存儲方法。

(2)掌握使用三元組表的稀疏矩陣的轉(zhuǎn)置算法。

(3)掌握使用三元組表的稀疏矩陣的加法和乘法算法。

(4)掌握使用三元組表的稀疏矩陣的輸出和顯示算法。

2．實習(xí)內(nèi)容和要求

(1)輸入稀疏矩陣，并將其保存在行三元組表中。

(2)在行三元組表方式下實現(xiàn)矩陣轉(zhuǎn)置運算。

(3)在行三元組表方式下實現(xiàn)矩陣相加運算。

(4)在行三元組表方式下實現(xiàn)矩陣相乘運算。

(5)以普通矩陣的形式顯示和輸出稀疏矩陣。

提示：稀疏矩陣相加和相乘算法本質(zhì)上與普通矩陣是完全相同的，必須在行三元組表上確定被加數(shù)(被乘數(shù))和加數(shù)(乘數(shù))的行、列號。實習(xí)9稀疏矩陣的正交鏈表

1．實習(xí)目的

(1)理解稀疏矩陣的壓縮存儲方法。

(2)掌握使用正交鏈表的稀疏矩陣的算法。

2．實習(xí)內(nèi)容和要求

(1)輸入稀疏矩陣，建立正交鏈表存儲結(jié)構(gòu)。

(2)在正交鏈表方式下實現(xiàn)矩陣相加運算。

(3)以普通矩陣的形式顯示和輸出稀疏矩陣。

提示：設(shè)稀疏矩陣采用教材所示的正交鏈表存儲。從鍵盤讀入稀疏矩陣的行數(shù)、列數(shù)和非零元素個數(shù)，并按行讀入稀疏矩陣中的非零元素，建立一個正交鏈表。以矩陣的一般形式，按行輸出一個稀疏矩陣。要求補(bǔ)上原矩陣中的0。實習(xí)10字符串運算和文本處理

1．實習(xí)目的

(1)理解字符串的定義和運算。

(2)掌握字符串的存儲方式。

(3)掌握順序表示下串運算的算法。

(4)學(xué)會使用串運算解決簡單文本處理問題。

2．實習(xí)內(nèi)容和要求

事先創(chuàng)建磁盤文本文件original.txt，實現(xiàn)對該文本文件的查找、刪除和替換。

(1)設(shè)字符串采用如下定義的結(jié)構(gòu)存儲，在此存儲結(jié)構(gòu)上實現(xiàn)字符串ADT上定義的所有運算。

typedefstructstring{

charchs[MaxSise];

intLength,MaxSise,Current;

}String;

(2)編寫主函數(shù)，以菜單方式選擇執(zhí)行如下操作：

①讀入磁盤文件。

②查找：輸入待查找的子串，從主串的當(dāng)前位置開始查找子串第一次出現(xiàn)的位置；若存在，則顯示該子串出現(xiàn)的位置，否則顯示“未發(fā)現(xiàn)所查子串”。

③刪除：輸入待查找的子串，從主串的當(dāng)前位置開始查找子串第一次出現(xiàn)的位置；若存在，則刪除該子串，并顯示結(jié)果文本，否則顯示“未發(fā)現(xiàn)所查子串”。

④替換：輸入待查找的子串和一個替換串，從主串的當(dāng)前位置開始查找子串第一次出現(xiàn)的位置；若存在，則以替換串替換之，并顯示結(jié)果文本，否則顯示“未發(fā)現(xiàn)所查子串”。

⑤全部替換：輸入待查找的子串和一個替換串，在主串中查找子串；對子串的每次出現(xiàn)都以替換串替換之，并顯示全部替換后的結(jié)果文本。實習(xí)11二叉樹的基本運算和應(yīng)用

1．實習(xí)目的

(1)理解二叉樹的數(shù)據(jù)結(jié)構(gòu)。

(2)掌握二叉鏈表上實現(xiàn)二叉樹基本運算的方法。

(3)學(xué)會設(shè)計基于遍歷的、求解二叉樹應(yīng)用問題的算法。

2．實習(xí)內(nèi)容和要求

(1)實現(xiàn)二叉樹ADT的各基本運算。

(2)設(shè)計遞歸算法：

①刪除一棵二叉樹。

②求一棵二叉樹的高度。

③求一棵二叉樹中葉子結(jié)點數(shù)。

④復(fù)制一棵二叉樹。

⑤交換一棵二叉樹的左右子樹。

(3)設(shè)計算法，按自上而下、自左向右的次序，按層次遍歷一棵二叉樹。

(4)設(shè)計main函數(shù)，測試上述每個運算。實習(xí)12哈夫曼編碼和譯碼系統(tǒng)

1．實習(xí)目的

(1)理解哈夫曼樹的定義。

(2)掌握哈夫曼樹的構(gòu)造以及哈夫曼編碼和譯碼算法。

2．實習(xí)內(nèi)容和要求

所設(shè)計的系統(tǒng)能重復(fù)顯示以下菜單項：

(1)?B——建樹：讀入字符集和各字符頻度，建立哈夫曼樹。

(2)?T——遍歷：先序和中序遍歷二叉樹。

(3)?E——生成編碼：根據(jù)已建成的哈夫曼樹，產(chǎn)生各字符的哈夫曼編碼。

(4)?C——編碼：輸入由字符集中字符組成的任意字符串，利用已生成的哈夫曼編碼進(jìn)行編碼，顯示編碼結(jié)果，并將輸入的字符串及其編碼結(jié)果分別保存在磁盤文件textfile.txt和codefile.txt中。

(5)?D——譯碼：讀入codefile.txt，利用已建成的哈夫曼樹進(jìn)行譯碼，并將譯碼結(jié)果存入磁盤文件result.txt中。

(6)?P——打?。涸谄聊簧巷@示文件textfile.txt、codefile.txt和result.txt。

(7)?X——退出。實習(xí)13B?-?樹檢索

1．實習(xí)目的

(1)理解B-?樹的定義。

(2)設(shè)計B-?樹的數(shù)據(jù)結(jié)構(gòu)。

(3)掌握B-?樹的搜索、插入和刪除運算的算法。

2．實習(xí)內(nèi)容和要求

設(shè)有電話號碼本，每個記錄包含下列數(shù)據(jù)項：電話號碼、用戶名稱、地址?，F(xiàn)使用B?-?樹形式將其存儲在磁盤文件中。試設(shè)計一個系統(tǒng)使之具有下列功能：

(1)從鍵盤輸入各記錄，建立B－樹，并保存在磁盤文件中。

(2)搜索某用戶的電話號碼，顯示相關(guān)信息。

(3)增加一個新用戶。

(4)取消一個用戶。

(5)按電話號碼順序打印號碼本。實習(xí)14散列表檢索

1．實習(xí)目的

(1)理解散列表的定義。

(2)掌握除留余數(shù)法散列函數(shù)、開地址法解決沖突的散列表的基本運算的算法。

(3)學(xué)習(xí)使用散列表解決應(yīng)用問題的方法。

2．實習(xí)內(nèi)容和要求

設(shè)有學(xué)生情況表，每個記錄包含下列數(shù)據(jù)項：學(xué)號、姓名、性別、年齡。現(xiàn)使用散列表表示該學(xué)生情況表，并采用雙散列法解決沖突。試設(shè)計一個系統(tǒng)使之具有下列功能：

(1)從一個文本文件中輸入各記錄(記錄項用空格分隔)，建立散列表。

(2)搜索并顯示給定學(xué)號的學(xué)生記錄。

(3)插入一個學(xué)生記錄。

(4)刪除一個學(xué)生記錄。

(5)在多次刪除后，重新整理學(xué)生情況表。

(6)打印學(xué)生情況表。實習(xí)15圖運算及其應(yīng)用

1．實習(xí)目的

(1)理解圖數(shù)據(jù)結(jié)構(gòu)。

(2)掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)。

(3)掌握實現(xiàn)圖的基本運算的算法。

(4)學(xué)習(xí)使用圖算法解決應(yīng)用問題的方法。

2．實習(xí)內(nèi)容和要求

(1)設(shè)以鄰接表表示有向圖，求有向圖中從頂點u到頂點v的所有簡單路徑。

①設(shè)計一個函數(shù)實現(xiàn)從鍵盤輸入邊集，建立鄰接表結(jié)構(gòu)。

②設(shè)計一個函數(shù)顯示該鄰接表結(jié)構(gòu)。

③設(shè)計算法求有向圖中，從頂點u到頂點v的所有簡單路徑。

(2)求解飛機(jī)最少換乘次數(shù)問題

設(shè)以鄰接矩陣表示有向圖，現(xiàn)有n個城市，編號為0～n－1，m條航線的起點和終點由用戶輸入提供。尋找一條換乘次數(shù)最少的線路方案。實習(xí)16內(nèi)排序算法及其性能比較

1．實習(xí)目的

(1)理解和掌握各種排序算法。

(2)比較和改進(jìn)排序算法的性能。

2．實習(xí)內(nèi)容和要求

(1)驗證教材的各種內(nèi)排序算法。

(2)分析各種排序算法的時間復(fù)雜度。

(3)使用隨機(jī)數(shù)發(fā)生器產(chǎn)生大數(shù)據(jù)集合，運行上述各排序算法，使用系統(tǒng)時鐘測量各算法所需的實際時間，并進(jìn)行比較。

(4)改進(jìn)教材中的快速排序算法，使得當(dāng)子集合小于10個元素時改用直接插入排序。測量算法的時間，并與改進(jìn)前作比較。實習(xí)17外排序

1．實習(xí)目的

(1)熟練掌握C語言的文件操作。

(2)掌握采用置換選擇和K路合并的外排序算法。

2．實習(xí)內(nèi)容和要求

設(shè)由記錄類型的元素組成的數(shù)據(jù)文件中，每個記錄包含一個可以比較大小的關(guān)鍵字域。設(shè)計的系統(tǒng)重復(fù)顯示以下菜單項：

(1)?I：從磁盤文件中輸入記錄，構(gòu)造初始堆，并顯示之。

(2)?R：從磁盤文件中輸入記錄，使用置換選擇算法產(chǎn)生初始游程，每個初始游程保存為一個磁盤文件。

(3)?M：產(chǎn)生最佳合并方案。

(4)?S：使用敗方樹進(jìn)行K路合并，完成外排序。

(5)?P：給定磁盤文件名，在屏幕上顯示磁盤文件的內(nèi)容。

(6)?X：退出。

13.5實習(xí)報告范例

13.5.1實習(xí)題：表達(dá)式計算

1．實習(xí)目的

(1)深刻理解棧的后進(jìn)先出特性，學(xué)習(xí)使用棧處理應(yīng)用問題的方法。

(2)學(xué)習(xí)和理解利用棧實現(xiàn)將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式后，對后綴表達(dá)式求值的算法。

(3)學(xué)習(xí)設(shè)計測試用例進(jìn)行測試的方法，學(xué)習(xí)使用調(diào)試器診斷和修正錯誤。

2．實習(xí)內(nèi)容和要求

設(shè)計一個計算器程序，它具有下列功能：

(1)接收用戶輸入的中綴表達(dá)式。中綴表達(dá)式以'='號結(jié)束，只允許包括+、－、*、/、^(乘方)五種運算符，允許的操作數(shù)為正數(shù)(整型、浮點和雙精度型)，表達(dá)式允許出現(xiàn)嵌套的圓括號。

(2)將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式。

(3)計算后綴表達(dá)式的值。

(4)輸出表達(dá)式的計算結(jié)果。13.5.2實習(xí)報告

1．問題描述

設(shè)計一個計算器，使用戶可以重復(fù)輸入中綴表達(dá)式，并顯示表達(dá)式的計算結(jié)果。

2．概要設(shè)計

程序包括Calculator.c、InfixtoPostfix.h、Eval.h、CStack.h和FStack.h，共5個模塊，它們構(gòu)成如圖13－2所示的模塊結(jié)構(gòu)圖。圖13－2計算器結(jié)構(gòu)圖圖中，Calculator為主程序模塊，它調(diào)用下層模塊InfixtoPostfix和Eval實現(xiàn)計算器功能。模塊InfixtoPostfix的功能是從鍵盤輸入中綴表達(dá)式，并將其轉(zhuǎn)換成后綴表達(dá)式后輸出。Eval模塊的功能在于計算給定的后綴表達(dá)式并輸出計算結(jié)果。模塊InfixtoPostfix需要使用運算符堆棧模塊CStack，其數(shù)據(jù)元素是運算符。Eval模塊需要使用操作數(shù)堆棧模塊FStack，其數(shù)據(jù)元素是操作數(shù)。圖13－2的模塊結(jié)構(gòu)圖說明了模塊間的層次調(diào)用關(guān)系，也指明了模塊間的數(shù)據(jù)傳遞關(guān)系。標(biāo)識符post_exp是后綴表達(dá)式，它是模塊InfixtoPostfix的輸出數(shù)據(jù)，經(jīng)模塊Calculator傳遞給模塊Eval。模塊InfixtoPostfix與模塊CStack之間傳遞的數(shù)據(jù)是運算符，即將運算符c進(jìn)?；虺鰲?。模塊Eval接收后綴表達(dá)式，將操作數(shù)op進(jìn)?；虺鰲！?/p>

3．詳細(xì)設(shè)計

1)數(shù)據(jù)結(jié)構(gòu)設(shè)計

(1)算法需要使用兩個堆棧，其中，模塊InfixtoPostfix需要使用數(shù)據(jù)元素為運算符的堆棧，而模塊Eval需要使用數(shù)據(jù)元素為操作數(shù)的堆棧。為此需設(shè)計兩個元素類型不同的堆棧：CStack和FStack，其中CStack的元素類型是字符，而FStack的元素類型是雙精度。

(2)在C語言環(huán)境下，也可設(shè)計數(shù)據(jù)元素為viod*的堆棧，這樣做，可使模塊InfixToPostfix和模塊Eval使用具有相同元素類型的兩個堆棧。

2)模塊設(shè)計

(1)模塊CStack和FStack的實現(xiàn)算法見教材。

(2)模塊Calculator中只有一個main函數(shù)，它調(diào)用函數(shù)InfixtoPostfix和Eval實現(xiàn)計算器功能。

(3)模塊InfixtoPostfix中，函數(shù)InfixtoPostfix調(diào)用模塊內(nèi)部函數(shù)icp和isp，并使用模塊CStack的堆棧數(shù)據(jù)和函數(shù)，完成從鍵盤輸入中綴表達(dá)式，轉(zhuǎn)換成后綴表達(dá)式后輸出至模塊Calculator的功能。函數(shù)icp和isp分別返回一個運算符c的棧外或棧內(nèi)優(yōu)先級。模塊InfixtoPostfix的結(jié)構(gòu)如圖13－3所示。

(4)模塊Eval中，函數(shù)Eval接收模塊Calculator傳遞的后綴表達(dá)式，調(diào)用函數(shù)GetItem從后綴表達(dá)式串post_exp中的指定位置i開始，讀取表達(dá)式的一個雙精度數(shù)項，將其存入堆棧。函數(shù)DoOperation接收函數(shù)Eval傳遞的運算符c，調(diào)用函數(shù)GetOperands從堆棧讀取兩個雙精度操作數(shù)op1和op2，計算op1<c>op2的雙目運算，并將計算得到的中間操作數(shù)進(jìn)棧。模塊Eval的結(jié)構(gòu)如圖13－4所示。

3)算法流程圖

圖13－5是函數(shù)Eval的程序流程圖。post_exp是為以字符串形式保存的后綴表達(dá)式。一個合法的后綴表達(dá)式包括允許的運算符和雙精度操作數(shù)，并以'#'結(jié)束。此處，假定以空格符分隔這些項。還應(yīng)給出其他主要算法的程序流程圖，例如函數(shù)InfixtoPostfix的程序流程圖，但限于篇幅，本樣例此處省略其他流程圖。圖13－3模塊InfixtoPostfix的結(jié)構(gòu)圖圖13－4模塊Eval的結(jié)構(gòu)圖圖13－5函數(shù)Eval的程序流程圖

4)算法分析

主要算法InfixtoPostfix()和Eval()的時間復(fù)雜度和空間復(fù)雜度均為O(n)，這里的n是輸入的中綴表達(dá)式中包含的字符數(shù)。這兩個函數(shù)都只需自左向右掃描一遍以字符串形式表示的表達(dá)式即可。

4．程序代碼

報告中應(yīng)當(dāng)給出最核心的代碼，并作詳細(xì)注釋。限于篇幅，下面僅給出函數(shù)Eval的程序代碼。

voidEval(charpost_exp[])

{/*字符數(shù)組post_exp存放后綴表達(dá)式，表達(dá)式的各項之間以空格分隔*/

charc;doubleop;inti=0;/*c為運算符，op為操作數(shù)*/

CreateStackF(&s,Size); /*創(chuàng)建存放操作數(shù)的堆棧s*/

c=post_exp[i]; /*取post_exp的首字符復(fù)制到c*/

while(c!=‘#’){ /*若c不是‘#’*/

switch(c){

case'+':case'-':case'*':case'/':case'^':/*若c是運算符*/

5．測試和調(diào)試

采用黑盒測