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

數(shù)據(jù)結(jié)構(gòu)A課程實(shí)驗指導(dǎo)書Data Structure Course Design課程編號：06311360 學(xué)時： 15 學(xué)分：1先修課程：程序設(shè)計基礎(chǔ)、面向?qū)ο蟪绦蛟O(shè)計適用專業(yè)：計算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程一、實(shí)驗?zāi)康臄?shù)據(jù)結(jié)構(gòu)A課程是計算機(jī)科學(xué)與技術(shù)及其相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。在課堂教學(xué)中，比較全面、概括性地講述數(shù)據(jù)結(jié)構(gòu)學(xué)科中一些基礎(chǔ)性知識、重要概念及各種算法，通過該實(shí)驗教學(xué)和學(xué)生的上機(jī)實(shí)踐，將這些基礎(chǔ)性知識、重要概念及各種算法，在計算機(jī)上編程實(shí)現(xiàn)，使學(xué)生能夠達(dá)到以下實(shí)驗教學(xué)目標(biāo)：1. 掌握計算機(jī)處理數(shù)據(jù)的基本方法；2. 了解算法的時間及空間分析方法；3. 能夠為實(shí)際應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法；4. 通過在計算機(jī)上編程實(shí)現(xiàn)課程中介紹的各種算法，在程序設(shè)計能力方面得到提升。二、上機(jī)實(shí)驗總體要求1. 每位同學(xué)準(zhǔn)備一個實(shí)驗本，上機(jī)前作好充分的準(zhǔn)備工作，預(yù)習(xí)本次實(shí)驗的內(nèi)容，事先熟悉與實(shí)驗有關(guān)的軟硬件環(huán)境，編寫好程序代碼，供上機(jī)時使用。2. 實(shí)驗時遵守實(shí)驗室的規(guī)章制度，愛護(hù)實(shí)驗設(shè)備，原則上每人固定實(shí)驗設(shè)備，對于實(shí)驗設(shè)備出現(xiàn)的問題，要及時向指導(dǎo)老師匯報。3. 編程序過程中要注意多存盤，避免由于死機(jī)等原因造成的不必要的重復(fù)錄入。4. 內(nèi)部文檔要求：u 每個源文件和頭文件都必須在文件首部的注釋中注明設(shè)計者姓名，項目名（即我們的上機(jī)題目名），創(chuàng)建日期和最近一次修改日期。包含main()函數(shù)的源文件必須在首部注釋后另加一段注釋，簡要描述一下程序的目的和用到的主要數(shù)據(jù)結(jié)構(gòu)。文件注釋格式如下：文件名稱：項目名稱：創(chuàng)建者：創(chuàng)建時間：最后修改時間：功能： 文件中的函數(shù)名稱和簡單功能描述：文件中定義的全局變量和簡單功能描述：文件中用到的他處定義的全局變量及其出處：與其他文件的依賴關(guān)系：u 每個類必須包含首部注釋塊，適度地描述這個類的目的。類的首部注釋應(yīng)該緊挨著放在類的聲明（一般在頭文件里）前面。類的注釋格式如下：類名稱：定義該類的目的：類屬性：類中函數(shù)及功能：與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對象中的什么函數(shù)）：u 每個函數(shù)必須有首部注釋塊，描述該函數(shù)的簡要功能，每個參數(shù)的邏輯含義(包括它是輸入還是輸出或者輸入/輸出)，函數(shù)調(diào)用之前的預(yù)備條件，返回后的處理，返回值（如果有的話），該函數(shù)要調(diào)用到的函數(shù)列表（如果有）。這些函數(shù)頭注釋可能和函數(shù)原型或函數(shù)實(shí)現(xiàn)放在一起。應(yīng)該注意到：這項要求不僅適合于單獨(dú)的函數(shù)，同樣適合于類的成員函數(shù)。函數(shù)的注釋格式如下：函數(shù)名稱：函數(shù)功能描述：函數(shù)調(diào)用之前的預(yù)備條件：返回后的處理：返回值（如果有的話）：函數(shù)的輸入?yún)?shù)：函數(shù)的輸出參數(shù)：函數(shù)的抽象算法（偽碼）： 函數(shù)與其他對象中函數(shù)的調(diào)用和被調(diào)用關(guān)系：u 所有局部變量或常量的聲明后應(yīng)該簡要說明一下他們的含義和用途。u 主要的控制結(jié)構(gòu)，例如循環(huán)或分支結(jié)構(gòu)，應(yīng)該在前面注明將要完成什么功能。u 采用清晰一致的縮進(jìn)格式和其他格式化風(fēng)格（例如括號的定位）來提高代碼可讀性。5. 過程代碼要求u 標(biāo)識符名稱（常量、變量、函數(shù)、類等等）應(yīng)該具有描述性，便于理解。u 要用到某個常數(shù)時，最好設(shè)置一個常量來代替這個數(shù)字。u 采用枚舉類型來表示內(nèi)部標(biāo)簽和狀態(tài)的分類。u 任何情況下都不要用全局或文件范圍變量。但是允許采用全局范圍內(nèi)的類型定義（包括類定義）。u 采用適當(dāng)?shù)耐緩絺鬟f函數(shù)參數(shù)。當(dāng)被調(diào)用函數(shù)需要修改實(shí)參的值時一般只采用引用傳參。當(dāng)被調(diào)用函數(shù)只需改變形參（調(diào)用內(nèi)部）而保持實(shí)參不變時采用傳值傳參。u 采用string對象來存儲字符串?dāng)?shù)據(jù)（除了單個字符），而不用字符數(shù)組來表示。u 采用I/O流代替C風(fēng)格的I/O。6. 面向?qū)ο蟮拇a要求u 盡量采用類。不要用成員函數(shù)來實(shí)現(xiàn)結(jié)構(gòu)類型。u 一般來講，建議采用類模板來表示容器型結(jié)構(gòu)，如列表、樹等，以提高可重用性。u 設(shè)計類時，每個類都具有比較好的完整性（即該類的數(shù)據(jù)成員和函數(shù)成員具有比較好的內(nèi)聚性和一致性，不要把不相干的東西湊合在一起，也不要把相關(guān)的東西生生拆散）。u 類的所有數(shù)據(jù)成員都應(yīng)該是私有的。u 很多情況下，類的某些成員函數(shù)應(yīng)該也是私有的。視情況而定。u 所有訪問型指針都盡可能加const修飾（以區(qū)別于引用型指針）。u 如果一個類數(shù)據(jù)成員是一個指向動態(tài)分配內(nèi)存的指針，要求寫出析構(gòu)函數(shù)來釋放內(nèi)存；并寫出一個用于復(fù)制對象的構(gòu)造函數(shù)（copy constructor），而且寫出賦值操作的重載運(yùn)算（assignment operator overload）。u 僅當(dāng)有必要時才采用繼承機(jī)制。u 盡量少使用MFC庫中的類，可以適當(dāng)?shù)厥褂肧TL的類（但是，如果同學(xué)們對于最基本的數(shù)據(jù)結(jié)構(gòu)，例如棧、隊列等還不熟悉的情況下，還是盡量自己來編寫基本類）。如果要編圖形界面，請盡量把與編譯環(huán)境（如VC、C+ Builder）有關(guān)的類限制在少數(shù)幾個文件中。也就是說，盡量把算法部分和界面部分的源程序分割開來。當(dāng)然，string類例外，大多數(shù)情況下同學(xué)們可以用它來替代chat *類型。三、上機(jī)實(shí)驗報告提交要求按時完成各個實(shí)驗，實(shí)驗結(jié)束后應(yīng)完成實(shí)驗報告，并以打印或電子文檔的形式提交。實(shí)習(xí)報告內(nèi)容參見各實(shí)驗。實(shí)驗報告提交時打一個zip（或rar）壓縮包，zip（或rar）壓縮包文件名統(tǒng)一采用以下格式命名：班級-學(xué)號-姓名-實(shí)驗題號-版本號.zip（或為：班級-學(xué)號-姓名-實(shí)驗題號-版本號.rar）例：計算機(jī)科學(xué)與技術(shù)專業(yè)2002級1班學(xué)號為03的姓名是王三的學(xué)生的第4個實(shí)驗的第1個版本的文件名為：jsj021-03-王三-4-1.zip（或為j021-03-王三-4-1.rar）。各專業(yè)對應(yīng)的縮寫如下：(1) 計算機(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)行步驟、程序功能等等簡單說明一下。(2) 附加了足夠注釋的源程序以及相關(guān)的項目和資源文件。四、實(shí)驗安排實(shí)驗一 單鏈表操作（一） 實(shí)驗內(nèi)容單鏈表的創(chuàng)建、合并和輸出。（二） 實(shí)驗?zāi)康?. 熟悉用Visual C+進(jìn)行程序設(shè)計的方法。2. 掌握單鏈表的創(chuàng)建、查找、插入和合并等運(yùn)算。（三） 實(shí)驗題目本實(shí)驗要求實(shí)現(xiàn)以下功能：1. 從鍵盤輸入順序任意的5個整數(shù)，按有序插入的要求生成第一個有序單鏈表，將該鏈表輸出顯示。2. 再從鍵盤輸入順序任意的5個整數(shù)，按有序插入的要求生成第二個有序單鏈表，將該鏈表輸出顯示。3. 將這兩個有序單鏈表合并成一個有序單鏈表，要求使用兩個單鏈表的原有空間進(jìn)行合并，將生成的有序單鏈表輸出顯示?！緶y試數(shù)據(jù)】輸入第一組整數(shù)：23 45 11 78 34輸出的有序單鏈表應(yīng)為：11，23，34，45，78輸入第二組整數(shù)：90 13 45 66 10輸出的有序單鏈表應(yīng)為：10，13，45，66，90合并兩個單鏈表，輸出合并后的結(jié)果應(yīng)為： 10，11，13，23，34，45，45，66，78，90（四） 實(shí)驗報告1. 實(shí)驗題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。3. 程序的主要流程圖。4. 程序主要模塊的功能說明。5. 程序運(yùn)行時的初值和運(yùn)行結(jié)果。6. 源程序并附上注釋。7. 收獲及體會。實(shí)驗二 二叉樹操作（一） 實(shí)驗內(nèi)容二叉樹的建立和遍歷。（二） 實(shí)驗?zāi)康?. 進(jìn)一步掌握指針變量的使用。2. 掌握二叉樹的結(jié)構(gòu)特征以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。3. 掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。4. 掌握?；蜿犃械氖褂谩＃ㄈ?實(shí)驗題目本實(shí)驗要求實(shí)現(xiàn)以下功能：1. 按前序次序建立一棵二叉樹，以表示空。2. 中序、后序遍歷該二叉樹，輸出遍歷序列。3. 求出該二叉樹的深度并輸出，或求出該二叉樹的葉子數(shù)目并輸出。4. 試以棧為輔助存儲結(jié)構(gòu)實(shí)現(xiàn)二叉樹的前序非遞歸算法或以隊列為輔助存儲結(jié)構(gòu)實(shí)現(xiàn)二叉樹的層次遍歷算法?！緶y試數(shù)據(jù)】輸入以下字符串，建立二叉樹：ABC#DE#G#F#輸出中序遍歷序列應(yīng)為：CBEGDFA輸出后序遍歷序列應(yīng)為：CGEFDBA輸出二叉樹的深度應(yīng)為：5輸出二叉樹的葉子數(shù)目應(yīng)為：3（四） 實(shí)驗報告1. 實(shí)驗題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。3. 程序的主要流程圖。4. 程序主要模塊的功能說明。5. 程序運(yùn)行時的初值和運(yùn)行結(jié)果，畫出該二叉樹的形態(tài)。6. 源程序并附上注釋。7. 收獲及體會。實(shí)驗三 圖的操作（一） 實(shí)驗內(nèi)容圖的生成和圖的遍歷。（二） 實(shí)驗?zāi)康?. 掌握圖的基本存儲方法鄰接表和鄰接矩陣。2. 熟練掌握圖的兩種遍歷方法。（三） 實(shí)驗題目本實(shí)驗要求實(shí)現(xiàn)以下功能：1. 以鄰接矩陣或鄰接表作為存儲結(jié)構(gòu)建立一個無向圖。2. 按深度優(yōu)先遍歷該無向圖，輸出遍歷序列。3. 按廣度優(yōu)先遍歷該無向圖，輸出遍歷序列。【測試數(shù)據(jù)】無向圖如下所示。（四） 實(shí)驗報告1. 實(shí)驗題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。3. 程序的主要流程圖。4. 程序主要模塊的功能說明。5. 程序運(yùn)行時的初值和運(yùn)行結(jié)果，畫出該無向圖的形態(tài)，寫出其鄰接矩陣或鄰接表。6. 源程序并附上注釋。7. 收獲及體會。實(shí)驗四 查找操作（一） 實(shí)驗內(nèi)容二叉排序樹的建立、二叉排序樹中結(jié)點(diǎn)的查找（二） 實(shí)驗?zāi)康?. 熟悉二叉排序樹的定義。2. 理解二叉排序樹的建立過程。3. 掌握二叉排序樹中查找結(jié)點(diǎn)的算法。（三） 實(shí)驗題目本實(shí)驗要求實(shí)現(xiàn)以下功能：1. 對從鍵盤輸入的順序任意的若干個正整數(shù)建立一顆二叉排序樹，以-1作為結(jié)束。2. 按先序、中序和后序遍歷該二叉排序樹，輸出每種遍歷的結(jié)果。3. 從鍵盤輸入一個整數(shù)，在二叉排序樹中查找，給出是否查找成功的結(jié)果。【測試數(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 20 45 60 67 88輸出后序遍歷序列應(yīng)為：9 11 20 60 45 13 88 67輸入要查找的整數(shù)：45輸出查找結(jié)果：查找成功輸入要查找的整數(shù)：55輸出查找結(jié)果：查找失?。ㄋ模?實(shí)驗報告1. 實(shí)驗題目。2. 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。3. 程序的主要流程圖。4. 程序主要模塊的功能說明。5. 程序運(yùn)行時的初值和運(yùn)行結(jié)果，畫出該二叉排序樹的形態(tài)。6. 源程序并附上注釋。7. 收獲及體會。實(shí)驗五 內(nèi)部排序操作（一） 實(shí)驗內(nèi)容快速排序。（二） 實(shí)驗?zāi)康?. 熟悉各種內(nèi)部排序算法的思想。2. 理解快速排序算法。（三） 實(shí)驗題目本實(shí)驗要求實(shí)現(xiàn)以下功能：對從鍵盤輸入的順序任意的8個正整數(shù)，通過快速排序使之成為有序的序列。輸出每一趟排序的結(jié)果。【測試數(shù)據(jù)】輸入序列：49 38 65 97 76 13 50 27輸出的每一趟排序的結(jié)果應(yīng)為：初始序列: 49 38 65 97 76 13 50 27第1趟結(jié)果: 27 38 13 49