2012版《數(shù)據(jù)結(jié)構(gòu)A》課程實(shí)驗(yàn)指導(dǎo)書(shū)

1、數(shù)據(jù)結(jié)構(gòu)A課程實(shí)驗(yàn)指導(dǎo)書(shū)Data Structure Course Design課程編號(hào)：06311360學(xué)時(shí)： 15學(xué)分：1先修課程：程序設(shè)計(jì)基礎(chǔ)、面向?qū)ο蟪绦蛟O(shè)計(jì) 適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程一、實(shí)驗(yàn)?zāi)康臄?shù)據(jù)結(jié)構(gòu)A課程是計(jì)算機(jī)科學(xué)與技術(shù)及其相關(guān)專業(yè)的一門(mén)重要的專業(yè)基礎(chǔ) 課。在課堂教學(xué)中，比較全面、概括性地講述數(shù)據(jù)結(jié)構(gòu)學(xué)科中一些基礎(chǔ)性知識(shí)、重 要概念及各種算法，通過(guò)該實(shí)驗(yàn)教學(xué)和學(xué)生的上機(jī)實(shí)踐，將這些基礎(chǔ)性知識(shí)、重要 概念及各種算法，在計(jì)算機(jī)上編程實(shí)現(xiàn)，使學(xué)生能夠達(dá)到以下實(shí)驗(yàn)教學(xué)目標(biāo)：掌握計(jì)算機(jī)處理數(shù)據(jù)的基本方法；了解算法的時(shí)間及空間分析方法；能夠?yàn)閷?shí)際應(yīng)用所涉及的數(shù)據(jù)選擇適

2、當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法；通過(guò)在計(jì)算機(jī)上編程實(shí)現(xiàn)課程中介紹的各種算法，在程序設(shè)計(jì)能力方面得到提 升。二、上機(jī)實(shí)驗(yàn)總體要求每位同學(xué)準(zhǔn)備一個(gè)實(shí)驗(yàn)本，上機(jī)前作好充分的準(zhǔn)備工作，預(yù)習(xí)本次實(shí)驗(yàn)的內(nèi)容 事先熟悉與實(shí)驗(yàn)有關(guān)的軟硬件環(huán)境，編寫(xiě)好程序代碼，供上機(jī)時(shí)使用。實(shí)驗(yàn)時(shí)遵守實(shí)驗(yàn)室的規(guī)章制度，愛(ài)護(hù)實(shí)驗(yàn)設(shè)備，原則上每人固定實(shí)驗(yàn)設(shè)備，對(duì) 于實(shí)驗(yàn)設(shè)備出現(xiàn)的問(wèn)題，要及時(shí)向指導(dǎo)老師匯報(bào)。編程序過(guò)程中要注意多存盤(pán)，避免由于死機(jī)等原因造成的不必要的重復(fù)錄入。內(nèi)部文檔要求：每個(gè)源文件和頭文件都必須在文件首部的注釋中注明設(shè)計(jì)者姓名，項(xiàng)目名(即我們的上機(jī)題目名)，創(chuàng)建日期和最近一次修改日期。包含main ()函數(shù)的源

3、文件必須在首部注釋后另加一段注釋，簡(jiǎn)要描述一下程序的目的和用到 的主要數(shù)據(jù)結(jié)構(gòu)。文件注釋格式如下：文件名稱：項(xiàng)目名稱：創(chuàng)建者：創(chuàng)建時(shí)間：最后修改時(shí)間：功能： 文件中的函數(shù)名稱和簡(jiǎn)單功能描述： 文件中定義的全局變量和簡(jiǎn)單功能描述： 文件中用到的他處定義的全局變量及其出處： 與其他文件的依賴關(guān)系：每個(gè)類必須包含首部注釋塊，適度地描述這個(gè)類的目的。類的首部注釋?xiě)?yīng)該緊挨著放在類的聲明（一般在頭文件里）前面。類的注釋格式如下： 類名稱：定義該類的目的：類屬性： 類中函數(shù)及功能： 與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對(duì)象中的什么函數(shù)）：每個(gè)函數(shù)必須有首部注釋塊，描述該函數(shù)的簡(jiǎn)要功能，每個(gè)參數(shù)的邏輯含義（包括它

4、是輸入還是輸出或者輸入/輸出），函數(shù)調(diào)用之前的預(yù)備條件，返回后 的處理，返回值（如果有的話），該函數(shù)要調(diào)用到的函數(shù)列表（如果有）。這 些函數(shù)頭注釋可能和函數(shù)原型或函數(shù)實(shí)現(xiàn)放在一起。應(yīng)該注意到：這項(xiàng)要求 不僅適合于單獨(dú)的函數(shù)，同樣適合于類的成員函數(shù)。函數(shù)的注釋格式如下： 函數(shù)名稱：函數(shù)功能描述： 函數(shù)調(diào)用之前的預(yù)備條件：返回后的處理： 返回值（如果有的話）： 函數(shù)的輸入?yún)?shù)： 函數(shù)的輸出參數(shù)： 函數(shù)的抽象算法（偽碼）： 函數(shù)與其他對(duì)象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：所有局部變量或常量的聲明后應(yīng)該簡(jiǎn)要說(shuō)明一下他們的含義和用途。主要的控制結(jié)構(gòu)，例如循環(huán)或分支結(jié)構(gòu)，應(yīng)該在前面注明將要完成什么功能。采用清晰一

5、致的縮進(jìn)格式和其他格式化風(fēng)格（例如括號(hào)的定位）來(lái)提高代碼 可讀性。過(guò)程代碼要求標(biāo)識(shí)符名稱（常量、變量、函數(shù)、類等等）應(yīng)該具有描述性，便于理解。要用到某個(gè)常數(shù)時(shí)，最好設(shè)置一個(gè)常量來(lái)代替這個(gè)數(shù)字。采用枚舉類型來(lái)表示內(nèi)部標(biāo)簽和狀態(tài)的分類。任何情況下都不要用全局或文件范圍變量。但是允許采用全局范圍內(nèi)的類型 定義（包括類定義）。采用適當(dāng)?shù)耐緩絺鬟f函數(shù)參數(shù)。當(dāng)被調(diào)用函數(shù)需要修改實(shí)參的值時(shí)一般只采 用引用傳參。當(dāng)被調(diào)用函數(shù)只需改變形參（調(diào)用內(nèi)部）而保持實(shí)參不變時(shí)采 用傳值傳參。采用string對(duì)象來(lái)存儲(chǔ)字符串?dāng)?shù)據(jù)（除了單個(gè)字符），而不用字符數(shù)組來(lái)表示。采用I/O流代替C風(fēng)格的I /0。面向?qū)ο蟮拇a要求盡量

6、采用類。不要用成員函數(shù)來(lái)實(shí)現(xiàn)結(jié)構(gòu)類型。一般來(lái)講，建議采用類模板來(lái)表示容器型結(jié)構(gòu)，如列表、樹(shù)等，以提高可重 用性。設(shè)計(jì)類時(shí)，每個(gè)類都具有比較好的完整性（即該類的數(shù)據(jù)成員和函數(shù)成員具 有比較好的內(nèi)聚性和一致性，不要把不相干的東西湊合在一起，也不要把相 關(guān)的東西生生拆散）。類的所有數(shù)據(jù)成員都應(yīng)該是私有的。很多情況下，類的某些成員函數(shù)應(yīng)該也是私有的。視情況而定。所有訪問(wèn)型指針都盡可能加const修飾（以區(qū)別于引用型指針）。如果一個(gè)類數(shù)據(jù)成員是一個(gè)指向動(dòng)態(tài)分配內(nèi)存的指針，要求寫(xiě)出析構(gòu)函數(shù)來(lái) 釋放內(nèi)存；并寫(xiě)出一個(gè)用于復(fù)制對(duì)象的構(gòu)造函數(shù)（copy constructor），而且 寫(xiě)出賦值操作的重載運(yùn)算（as

7、signment operator overload）僅當(dāng)有必要時(shí)才采用繼承機(jī)制。盡量少使用MFC庫(kù)中的類，可以適當(dāng)?shù)厥褂肧TL的類（但是，如果同學(xué)們對(duì) 于最基本的數(shù)據(jù)結(jié)構(gòu)，例如棧、隊(duì)列等還不熟悉的情況下，還是盡量自己來(lái) 編寫(xiě)基本類）。如果要編圖形界面，請(qǐng)盡量把與編譯環(huán)境（如V C、C+ Builder） 有關(guān)的類限制在少數(shù)幾個(gè)文件中。也就是說(shuō)，盡量把算法部分和界面部分的 源程序分割開(kāi)來(lái)。當(dāng)然，string類例外，大多數(shù)情況下同學(xué)們可以用它來(lái)替 代chat *類型。三、上機(jī)實(shí)驗(yàn)報(bào)告提交要求 按時(shí)完成各個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)束后應(yīng)完成實(shí)驗(yàn)報(bào)告，并以打印或電子文檔的形式提 交。實(shí)習(xí)報(bào)告內(nèi)容參見(jiàn)各實(shí)驗(yàn)。實(shí)驗(yàn)

8、報(bào)告提交時(shí)打一個(gè)zip （或rar）壓縮包，zip （或rar）壓縮包文件名統(tǒng)一采用 以下格式命名：班級(jí)-學(xué)號(hào)-姓名-實(shí)驗(yàn)題號(hào)-版本號(hào)zip（或?yàn)椋喊嗉?jí)-學(xué)號(hào)-姓名-實(shí)驗(yàn)題號(hào)-版本號(hào)rar）例：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)2002級(jí)1班學(xué)號(hào)為03的姓名是王三的學(xué)生的第4個(gè)實(shí)驗(yàn) 的第1個(gè)版本的文件名為：jsjO21-03-王三-4-1zip （或?yàn)閖O21-03-王三-4-1rar）各專業(yè)對(duì)應(yīng)的縮寫(xiě)如下：（1）計(jì)算機(jī)科學(xué)與技術(shù)一jsj（2）信息安全一xa（3）網(wǎng)絡(luò)工程一wl（4）軟件工程一rjzip （或rar）壓縮包中應(yīng)含有：（1）readme.txt文件，把你的程序運(yùn)行環(huán)境、編譯運(yùn)行步驟、程序功能等

9、等簡(jiǎn) 單說(shuō)明一下。（2）附加了足夠注釋的源程序以及相關(guān)的項(xiàng)目和資源文件。四、實(shí)驗(yàn)安排實(shí)驗(yàn)一 單鏈表操作（一）實(shí)驗(yàn)內(nèi)容單鏈表的創(chuàng)建、合并和輸出。（二）實(shí)驗(yàn)?zāi)康氖煜び肰isual C+進(jìn)行程序設(shè)計(jì)的方法。掌握單鏈表的創(chuàng)建、查找、插入和合并等運(yùn)算。（三）實(shí)驗(yàn)題目本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：從鍵盤(pán)輸入順序任意的5個(gè)整數(shù)，按有序插入的要求生成第一個(gè)有序單鏈表， 將該鏈表輸出顯示。再?gòu)逆I盤(pán)輸入順序任意的5個(gè)整數(shù)，按有序插入的要求生成第二個(gè)有序單鏈 表，將該鏈表輸出顯示。將這兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表，要求使用兩個(gè)單鏈表的原有空 間進(jìn)行合并，將生成的有序單鏈表輸出顯示。測(cè)試數(shù)據(jù)】輸入第一組整數(shù)：23 4

10、5 11 78 34 輸出的有序單鏈表應(yīng)為：11，23，34，45，78輸入第二組整數(shù)：90 13 45 66 10 輸出的有序單鏈表應(yīng)為：10，13，45，66，90 合并兩個(gè)單鏈表，輸出合并后的結(jié)果應(yīng)為：10，11，13，23，34，45，45，66，78，90（四）實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)題目。程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號(hào)說(shuō)明。程序的主要流程圖。程序主要模塊的功能說(shuō)明。程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果。源程序并附上注釋。收獲及體會(huì)。實(shí)驗(yàn)二 二叉樹(shù)操作（一）實(shí)驗(yàn)內(nèi)容 二叉樹(shù)的建立和遍歷。（二）實(shí)驗(yàn)?zāi)康倪M(jìn)一步掌握指針變量的使用。掌握二叉樹(shù)的結(jié)構(gòu)特征以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及使用范圍。掌握用指針類型描述、訪問(wèn)

11、和處理二叉樹(shù)的運(yùn)算。掌握棧或隊(duì)列的使用。（三）實(shí)驗(yàn)題目 本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：按前序次序建立一棵二叉樹(shù)，以表示空。中序、后序遍歷該二叉樹(shù)，輸出遍歷序列。求出該二叉樹(shù)的深度并輸出，或求出該二叉樹(shù)的葉子數(shù)目并輸出。試以棧為輔助存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)的前序非遞歸算法或以隊(duì)列為輔助存儲(chǔ) 結(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)的層次遍歷算法?！緶y(cè)試數(shù)據(jù)】輸入以下字符串，建立二叉樹(shù)：ABC#DE#G#F#輸出中序遍歷序列應(yīng)為：CBEGDFA 輸出后序遍歷序列應(yīng)為： CGEFDBA 輸出二叉樹(shù)的深度應(yīng)為： 5 輸出二叉樹(shù)的葉子數(shù)目應(yīng)為： 3（四）實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)題目。程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號(hào)說(shuō)明。程序的主要流程圖。程序主要模塊的

12、功能說(shuō)明。程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果，畫(huà)出該二叉樹(shù)的形態(tài)源程序并附上注釋。收獲及體會(huì)。實(shí)驗(yàn)三 圖的操作（一）實(shí)驗(yàn)內(nèi)容 圖的生成和圖的遍歷。（二）實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的基本存儲(chǔ)方法鄰接表和鄰接矩陣。熟練掌握?qǐng)D的兩種遍歷方法。（三）實(shí)驗(yàn)題目 本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：以鄰接矩陣或鄰接表作為存儲(chǔ)結(jié)構(gòu)建立一個(gè)無(wú)向圖。按深度優(yōu)先遍歷該無(wú)向圖，輸出遍歷序列。按廣度優(yōu)先遍歷該無(wú)向圖，輸出遍歷序列。 【測(cè)試數(shù)據(jù)】無(wú)向圖如下所示。四）實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號(hào)說(shuō)明。程序的主要流程圖。程序主要模塊的功能說(shuō)明。程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果，畫(huà)出該無(wú)向圖的形態(tài)，寫(xiě)出其鄰接矩陣或鄰 接表。源程序并附

13、上注釋。收獲及體會(huì)。實(shí)驗(yàn)四 查找操作（一）實(shí)驗(yàn)內(nèi)容二叉排序樹(shù)的建立、二叉排序樹(shù)中結(jié)點(diǎn)的查找（二）實(shí)驗(yàn)?zāi)康氖煜ざ媾判驑?shù)的定義。理解二叉排序樹(shù)的建立過(guò)程。掌握二叉排序樹(shù)中查找結(jié)點(diǎn)的算法。（三）實(shí)驗(yàn)題目本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：對(duì)從鍵盤(pán)輸入的順序任意的若干個(gè)正整數(shù)建立一顆二叉排序樹(shù)，以-1作為結(jié) 束。按先序、中序和后序遍歷該二叉排序樹(shù)，輸出每種遍歷的結(jié)果。3. 從鍵盤(pán)輸入一個(gè)整數(shù)，在二叉排序樹(shù)中查找，給出是否查找成功的結(jié)果。 【測(cè)試數(shù)據(jù)】輸入序列：67 13 11 88 45 9 60 20 -1輸出先序遍歷序列應(yīng)為：67 13 11 9 45 20 60 88輸出中序遍歷序列應(yīng)為：9 11 13

14、20 45 60 67 88輸出后序遍歷序列應(yīng)為：9 11 20 60 45 13 88 67 輸入要查找的整數(shù)：45輸出查找結(jié)果：查找成功輸入要查找的整數(shù)：55輸出查找結(jié)果：查找失敗四）實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號(hào)說(shuō)明。程序的主要流程圖。程序主要模塊的功能說(shuō)明。程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果，畫(huà)出該二叉排序樹(shù)的形態(tài)源程序并附上注釋。收獲及體會(huì)。實(shí)驗(yàn)五 內(nèi)部排序操作（一）實(shí)驗(yàn)內(nèi)容快速排序。（二）實(shí)驗(yàn)?zāi)康?. 熟悉各種內(nèi)部排序算法的思想。2. 理解快速排序算法。（三）實(shí)驗(yàn)題目 本實(shí)驗(yàn)要求實(shí)現(xiàn)以下功能：對(duì)從鍵盤(pán)輸入的順序任意的8個(gè)正整數(shù)，通過(guò)快速排 序使之成為有序的序列。輸出每一趟排序的結(jié)果?！緶y(cè)試數(shù)據(jù)】輸入序列：49 38 65 97 76 13 50 27輸出的每一趟排序的結(jié)果應(yīng)為：初始序列: 4938659776