data structure course design
課程編號：06311360學時： 15 學分：1
先修課程：程式設計基礎、物件導向程式設計
適用專業：電腦科學與技術、網路工程、軟體工程
一、實驗目的
《資料結構a》課程是電腦科學與技術及其相關專業的一門重要的專業基礎課。在課堂教學中，比較全面、概括性地講述資料結構學科中一些基礎性知識、重要概念及各種演算法，通過該實驗教學和學生的上機實踐，將這些基礎性知識、重要概念及各種演算法，在計算機上程式設計實現，使學生能夠達到以下實驗教學目標：
1. 掌握計算機處理資料的基本方法；
2. 了解演算法的時間及空間分析方法；
3. 能夠為實際應用所涉及的資料選擇適當的邏輯結構、儲存結構及相應的演算法；
4. 通過在計算機上程式設計實現課程中介紹的各種演算法，在程式設計能力方面得到提公升。
二、上機實驗總體要求
1. 每位同學準備乙個實驗本，上機前作好充分的準備工作，預習本次實驗的內容，事先熟悉與實驗有關的軟硬體環境，編寫好程式**，供上機時使用。
2. 實驗時遵守實驗室的規章制度，愛護實驗裝置，原則上每人固定實驗裝置，對於實驗裝置出現的問題，要及時向指導老師匯報。
3. 程式設計序過程中要注意多存檔，避免由於宕機等原因造成的不必要的重複錄入。
4. 內部文件要求：
◆ 每個原始檔和標頭檔案都必須在檔案首部的注釋中註明設計者姓名，專案名（即我們的上機題目名），建立日期和最近一次修改日期。包含main()函式的原始檔必須在首部注釋後另加一段注釋，簡要描述一下程式的目的和用到的主要資料結構。檔案注釋格式如下：
檔名稱：
專案名稱：
建立者：
建立時間：
最後修改時間：
功能：檔案中的函式名稱和簡單功能描述：
檔案中定義的全域性變數和簡單功能描述：
檔案中用到的他處定義的全域性變數及其出處：
與其他檔案的依賴關係：
◆ 每個類必須包含首部注釋塊，適度地描述這個類的目的。類的首部注釋應該緊挨著放在類的宣告（一般在標頭檔案裡）前面。類的注釋格式如下：
類名稱：
定義該類的目的：
類屬性：
類中函式及功能：
與其他類的關係（呼叫/被呼叫哪類物件中的什麼函式）：
◆ 每個函式必須有首部注釋塊，描述該函式的簡要功能，每個引數的邏輯含義(包括它是輸入還是輸出或者輸入/輸出)，函式呼叫之前的預備條件，返回後的處理，返回值（如果有的話），該函式要呼叫到的函式列表（如果有）。這些函式頭注釋可能和函式原型或函式實現放在一起。應該注意到：
這項要求不僅適合於單獨的函式，同樣適合於類的成員函式。函式的注釋格式如下：
函式名稱：
函式功能描述：
函式呼叫之前的預備條件：
返回後的處理：
返回值（如果有的話）：
函式的輸入引數：
函式的輸出引數：
函式的抽象演算法（偽碼）：
函式與其他物件中函式的呼叫和被呼叫關係：
◆ 所有區域性變數或常量的宣告後應該簡要說明一下他們的含義和用途。
◆ 主要的控制結構，例如迴圈或分支結構，應該在前面註明將要完成什麼功能。
◆ 採用清晰一致的縮排格式和其他格式化風格（例如括號的定位）來提高**可讀性。
5. 過程**要求
◆ 識別符號名稱（常量、變數、函式、類等等）應該具有描述性，便於理解。
◆ 要用到某個常數時，最好設定乙個常量來代替這個數字。
◆ 採用列舉型別來表示內部標籤和狀態的分類。
◆ 任何情況下都不要用全域性或檔案範圍變數。但是允許採用全域性範圍內的型別定義（包括類定義）。
◆ 採用適當的途徑傳遞函式引數。當被呼叫函式需要修改實參的值時一般只採用引用傳參。當被呼叫函式只需改變形參（呼叫內部）而保持實參不變時採用傳值傳參。
◆ 採用string物件來儲存字串資料（除了單個字元），而不用字元陣列來表示。
◆ 採用i/o流代替c風格的i/o。
6. 物件導向的**要求
◆ 盡量採用類。不要用成員函式來實現結構型別。
◆ 一般來講，建議採用類模板來表示容器型結構，如列表、樹等，以提高可重用性。
◆ 設計類時，每個類都具有比較好的完整性（即該類的資料成員和函式成員具有比較好的內聚性和一致性，不要把不相干的東西湊合在一起，也不要把相關的東西生生拆散）。
◆ 類的所有資料成員都應該是私有的。
◆ 很多情況下，類的某些成員函式應該也是私有的。視情況而定。
◆ 所有訪問型指標都盡可能加const修飾（以區別於引用型指標）。
◆ 如果乙個類資料成員是乙個指向動態分配記憶體的指標，要求寫出析構函式來釋放記憶體；並寫出乙個用於複製物件的建構函式（copy constructor），而且寫出賦值操作的過載運算（assignment operator overload）。
◆ 僅當有必要時才採用繼承機制。
◆ 盡量少使用mfc庫中的類，可以適當地使用stl的類（但是，如果同學們對於最基本的資料結構，例如棧、佇列等還不熟悉的情況下，還是盡量自己來編寫基本類）。如果要編圖形介面，請盡量把與編譯環境（如vc、c++ builder）有關的類限制在少數幾個檔案中。也就是說，盡量把演算法部分和介面部分的源程式分割開來。
當然，string類例外，大多數情況下同學們可以用它來替代chat *型別。
三、上機實驗報告提交要求
按時完成各個實驗，實驗結束後應完成實驗報告，並以列印或電子文件的形式提交。實習報告內容參見各實驗。
實驗報告提交時打乙個zip（或rar）壓縮包，zip（或rar）壓縮包檔名統一採用以下格式命名：
班級-學號-姓名-實驗題號-版本號.zip
（或為：班級-學號-姓名-實驗題號-版本號.rar）
例：電腦科學與技術專業2002級1班學號為03的姓名是王三的學生的第4個實驗的第1個版本的檔名為：jsj021-03-王三-4-1.
zip（或為j021-03-王三-4-1.rar）。
各專業對應的縮寫如下：
(1) 電腦科學與技術—jsj
(2) 資訊保安—xa
(3) 網路工程—wl
(4) 軟體工程—rj
zip（或rar）壓縮包中應含有：
(1) readme.txt檔案，把你的程式執行環境、編譯執行步驟、程式功能等等簡單說明一下。
(2) 附加了足夠注釋的源程式以及相關的專案和資源檔案。
四、實驗安排
實驗一單鏈表操作
（一） 實驗內容
單鏈表的建立、合併和輸出。
（二） 實驗目的
1. 熟悉用visual c++進行程式設計的方法。
2. 掌握單鏈表的建立、查詢、插入和合併等運算。
（三） 實驗題目
本實驗要求實現以下功能：
1. 從鍵盤輸入順序任意的5個整數，按有序插入的要求生成第乙個有序單鏈表，將該鍊錶輸出顯示。
2. 再從鍵盤輸入順序任意的5個整數，按有序插入的要求生成第二個有序單鏈表，將該鍊錶輸出顯示。
3. 將這兩個有序單鏈表合併成乙個有序單鏈表，要求使用兩個單鏈表的原有空間進行合併，將生成的有序單鏈表輸出顯示。
【測試資料】
輸入第一組整數：23 45 11 78 34
輸出的有序單鏈表應為：11，23，34，45，78
輸入第二組整數：90 13 45 66 10
輸出的有序單鏈表應為：10，13，45，66，90
合併兩個單鏈表，輸出合併後的結果應為：
10，11，13，23，34，45，45，66，78，90
（四） 實驗報告
1. 實驗題目。
2. 程式中使用的資料結構及符號說明。
3. 程式的主要流程圖。
4. 程式主要模組的功能說明。
5. 程式執行時的初值和執行結果。
6. 源程式並附上注釋。
7. 收穫及體會。
實驗二二叉樹操作
（一） 實驗內容
二叉樹的建立和遍歷。
（二） 實驗目的
1. 進一步掌握指標變數的使用。
2. 掌握二叉樹的結構特徵以及各種儲存結構的特點及使用範圍。
3. 掌握用指標型別描述、訪問和處理二叉樹的運算。
4. 掌握棧或佇列的使用。
（三） 實驗題目
本實驗要求實現以下功能：
1. 按前序次序建立一棵二叉樹，以『＃』表示空。
2. 中序、後序遍歷該二叉樹，輸出遍歷序列。
3. 求出該二叉樹的深度並輸出，或求出該二叉樹的葉子數目並輸出。
4. 試以棧為輔助儲存結構實現二叉樹的前序非遞迴演算法或以隊列為輔助儲存結構實現二叉樹的層次遍歷演算法。
【測試資料】
輸入以下字串，建立二叉樹：abc##de#g##f###
輸出中序遍歷序列應為：cbegdfa
輸出後序遍歷序列應為：cgefdba
輸出二叉樹的深度應為：5
輸出二叉樹的葉子數目應為：3
（四） 實驗報告
1. 實驗題目。
2. 程式中使用的資料結構及符號說明。
3. 程式的主要流程圖。
4. 程式主要模組的功能說明。
5. 程式執行時的初值和執行結果，畫出該二叉樹的形態。
6. 源程式並附上注釋。
7. 收穫及體會。
實驗三圖的操作
（一） 實驗內容
圖的生成和圖的遍歷。
（二） 實驗目的
1. 掌握圖的基本儲存方法——鄰接表和鄰接矩陣。
2. 熟練掌握圖的兩種遍歷方法。
（三） 實驗題目
本實驗要求實現以下功能：
1. 以鄰接矩陣或鄰接表作為儲存結構建立乙個無向圖。
2. 按深度優先遍歷該無向圖，輸出遍歷序列。
3. 按廣度優先遍歷該無向圖，輸出遍歷序列。
【測試資料】無向圖如下所示。
（四） 實驗報告
1. 實驗題目。
2. 程式中使用的資料結構及符號說明。
3. 程式的主要流程圖。
4. 程式主要模組的功能說明。
5. 程式執行時的初值和執行結果，畫出該無向圖的形態，寫出其鄰接矩陣或鄰接表。
6. 源程式並附上注釋。
7. 收穫及體會。
實驗四查詢操作
（一） 實驗內容
二叉排序樹的建立、二叉排序樹中結點的查詢
（二） 實驗目的
1. 熟悉二叉排序樹的定義。
2. 理解二叉排序樹的建立過程。
3. 掌握二叉排序樹中查詢結點的演算法。
（三） 實驗題目
本實驗要求實現以下功能：
1. 對從鍵盤輸入的順序任意的若干個正整數建立一顆二叉排序樹，以-1作為結束。
2. 按先序、中序和後序遍歷該二叉排序樹，輸出每種遍歷的結果。
3. 從鍵盤輸入乙個整數，在二叉排序樹中查詢，給出是否查詢成功的結果。
【測試資料】
輸入序列：67 13 11 88 45 9 60 20 -1
輸出先序遍歷序列應為：67 13 11 9 45 20 60 88
輸出中序遍歷序列應為：9 11 13 20 45 60 67 88
輸出後序遍歷序列應為：9 11 20 60 45 13 88 67
輸入要查詢的整數：45
輸出查詢結果：查詢成功
輸入要查詢的整數：55
輸出查詢結果：查詢失敗
（四） 實驗報告
1. 實驗題目。
2. 程式中使用的資料結構及符號說明。
3. 程式的主要流程圖。
4. 程式主要模組的功能說明。
5. 程式執行時的初值和執行結果，畫出該二叉排序樹的形態。
6. 源程式並附上注釋。
7. 收穫及體會。
實驗五內部排序操作
（一） 實驗內容
快速排序。
（二） 實驗目的
1. 熟悉各種內部排序演算法的思想。
《資料結構課程實驗》大綱
一 資料結構課程實驗 的地位與作用 資料結構 是計算機專業一門重要的專業技術基礎課程，是計算機專業的一門核心的關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法，介紹了常用的多種查詢和排序技術，並做了效能分析和比較，內容非常豐富。本課程的學習將為後續課程的學習以及...
《資料結構A》課程實驗大綱
課程編號課程名稱 資料結構a 課內總學時 8實驗學時 8 8 一 實驗課程的性質 目的和任務 資料結構a 是電腦科學與技術以及相關專業的學科基礎課，是計算機軟體設計的重要理論和實踐基礎。課程教學包括理論和上機實驗兩部分。通過上機實驗，加深對電腦科學中的組織 表示和處理資料的基本方法的理解，訓練學生運...
資料結構實驗指導手冊 2019版
五邑大學計算機學院 資料結構實驗指導手冊 2015年3月 目錄實驗一線性表 1 1 實驗目的 1 2 實驗內容 1 3 解題思路 1 實驗二棧 4 1 實驗目的 4 2 實驗內容 4 3 解題思路 4 實驗三佇列 8 1 實驗目的 8 2 實驗內容 8 3 解題思路 8 實驗四二叉樹 12 1 實驗...