北京科技大學計算機與通訊工程學院
資料結構實驗報告
專業班級
學生姓名
學號指導教師
實驗地點
實驗時間年月日~ 月日
實驗成績
一、實驗目的與實驗要求
1 實驗目的
（1）加深對常用資料結構和演算法設計基本思路、思考方法及其適用場合的理解，並能運用於解決實際問題；
（2）能根據特定問題需求，分析建立計算模型（包括邏輯結構和物理結構）、設計演算法和程式，並在設計中綜合考慮多種因素，對結果的有效性進行分析；
（3）訓練分析問題、解決問題的能力以及自主學習與程式設計實踐能力；
（4）形成將非數值型問題抽象為計算模型到演算法設計、程式實現、結果有效性分析的能力。
2 實驗要求
（1）由於在有限的實驗課內學時難以較好完成所有實驗內容，因此要求在實驗課前自主完成部分實驗或實驗的部分內容；
（2）對於每個實驗都要針對問題進行分析，設計出有效的資料結構、演算法和程式，對實現結果的正確性進行測試驗證，給出測試用例和結果，分析演算法的時間複雜度、空間複雜度、有效性和不足，在演算法設計和實現過程中體現創新意識，並能綜合考慮時空權衡、使用者的友好性、程式的模組化和擴充套件性等；（如實驗中有優化或改進的設計，請將優化過程進行說明，並給出前後對比分析。）
（3）完成的每個實驗需要在實驗課內經指導教師現場檢查、檢視程式**，回答指導教師提出的問題，以確認實驗實際完成的質量；
（4）在實驗報告中體現問題分析、演算法思路、演算法描述、程式實現和驗證、演算法和結果的有效性分析。
（注：此模板中的紅色文字為解釋性文字，提交時請將所有紅色文字刪除。）
二、實驗裝置（環境）及要求
實驗室提供windows 7系統下的visual c++環境。本實驗目的是對資料結構知識掌握及應用能力的考察，對程式語言和開發環境不做嚴格要求。建議採用c語言，在支援c的編譯環境下執行。
三、實驗內容、步驟與結果分析
1 實驗1：鍊錶的應用
1.1 實驗內容
輸入資料（設為整型）建立單鏈表，並求相鄰k個節點data值之和為最大的第一節點。
要求：（1）建立鍊錶、求最大值功能採用獨立函式實現；
（2）可根據使用者需求多次建表；
（3）資料的輸入可從鍵盤輸入，也可從txt檔案輸入；
（4）程式結束時要釋放鍊錶空間。
1.2 主要步驟
1.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、適合採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
1.2.2 演算法描述
用偽**給出演算法描述。
1.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
1.3 結果分析
1.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
1.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
2 實驗2：棧的應用
2.1 實驗內容
算術表示式求值：輸入中綴形式的算術表示式，如：5+(4-2)*3，將其轉換成字尾表示式並輸出：542-3*+，然後對字尾表示式求值（本例結果為11）並將結果輸出。
要求：（1）「中綴表示式轉換字尾表示式」和「字尾表示式求值」採用獨立函式實現；
（2）運算元支援多位數和小數；
（3）運算子僅考慮可用作結束符）；
（4）中綴表示式可從鍵盤輸入也可以從檔案輸入。對輸入的中綴表示式要進行合法性檢查（表示式頭尾以及運算子左右可以包含若干空格）；
（5）可根據使用者需求，多次計算不同的表示式；
（6）自行定義棧型別以及需要的棧的基本操作。
2.2 主要步驟
2.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、需要採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
2.2.2 演算法描述
用偽**給出演算法描述。
2.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
2.3 結果分析
2.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
2.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
3 實驗3：佇列的應用
3.1 實驗內容
將從鍵盤輸入的一系列字元儲存到鏈式佇列中，當輸入的字元為』0』時，執行出隊操作並將出隊元素列印到螢幕上；當輸入的字元為』@』時，佇列中剩餘所有元素依次出隊並列印到螢幕上；當輸入其他字元時，字元入隊。
要求：可根據使用者需求多次重複該過程；自行補充所需的佇列基本操作。
3.2 主要步驟
3.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、需要採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
3.2.2 演算法描述
用偽**給出演算法描述。
3.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
3.3 結果分析
3.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
3.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
4 實驗4：二叉樹的應用
4.1 實驗內容
樹表的查詢：輸入乙個英文句子，按照字典順序構造一棵二叉排序樹；對此二叉排序樹進行中序遍歷，並將遍歷序列輸出到螢幕上。
要求：（1）英文句子可從鍵盤輸入，也可從txt檔案輸入；
（2）遍歷演算法採用非遞迴遍歷演算法；
（3）程式結束時需釋放樹空間。
4.2 主要步驟
4.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、需要採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
4.2.2 演算法描述
用偽**給出演算法描述。
4.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
4.3 結果分析
4.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
4.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
5 實驗5：圖的應用
5.1 實驗內容
建立有向圖的十字鍊錶儲存結構，利用拓撲排序方法判斷該圖是否為有向無環圖。
要求：有向圖的頂點資訊和弧資訊可以從鍵盤或txt檔案輸入，輸入格式自擬。
5.2 主要步驟
5.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、需要採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
5.2.2 演算法描述
用偽**給出演算法描述。
5.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
5.3 結果分析
5.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
5.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
6 實驗6：綜合應用
6.1 實驗內容
統計若干個大型英文txt檔案（如英文**）中所有單詞出現的次數，並輸出出現次數最多的前10個單詞及其出現次數。假設單詞字元定義為大小寫字母、數字和下劃線，其他字元均看作單詞分隔符。
要求：（1）自行設計合適的資料結構及相關演算法；
（2）程式執行結束時將txt檔名以及統計結果寫入磁碟；
（3）每次程式啟動時（除了首次執行）將上次的結果讀入記憶體、顯示；
（4）能根據使用者選擇實現重新初始化、查詢某單詞出現次數、追加統計、退出等功能。
6.2 主要步驟
6.2.1 問題分析與演算法思路
通過對問題進行分析，得出求解問題的演算法思路。包括問題分析的過程、適合採用的資料結構、演算法思路。在演算法設計中體現創新意識，能綜合考慮時空權衡等。
6.2.2 演算法描述
用偽**給出演算法描述。
6.2.3 程式實現
給出完整的程式源**和注釋，說明在程式實現中對使用者的友好性、程式的模組化和擴充套件性等是如何考慮的。為了減少篇幅，源**採用較小的字型列印，也可適當採用分欄排版。
6.3 結果分析
6.3.1 測試
說明測試的思路，是如何驗證在不同輸入下（包括邊界情況）程式正確性的；給出測試用例和測試結果。
6.3.2 演算法和結果的有效性分析
分析演算法的時間複雜度、空間複雜度、有效性、不足和改進意見。如果同時採用了多種實現方法，進行對比說明、分析。
資料結構實驗
資訊23 2120502060 古碧野一 實驗題目 建立乙個線性表，實現線性表的建立，插入，刪除和遍歷 二.實驗目的和要求 實驗目的 熟練掌握線性表的基本操作在順序儲存結構上的實現。實驗要求 用c語言編寫源程式，並除錯通過，測試正確。三.主要儀器裝置 windows xp操作平台，visual c ...
資料結構實驗
一 實驗目的 1 了解二叉樹的定義及基本運算。2 掌握二叉樹的描述方法 特點 性質及儲存結構。3 掌握二叉樹的基本操作演算法。4 自主設計二叉樹建立 遍歷等操作的整個程式。二 實驗內容 根據建立任意給定的二叉樹，並對此二叉樹進行前序 中序 後序 層次四種遍歷。基本要求 1 具有二叉樹的建立功能 2 ...
資料結構實驗
一 實驗題目編寫乙個程式實現雙鏈隊的各種基本運算，並在此基礎上設計乙個主程式完成如下功能 1 初始化鏈隊q 2 判斷鏈隊q是否為空 3 依次進隊元素a,b,c 4 出隊乙個元素，輸出該元素 5 輸出鏈隊q的元素個數 6 依次進鏈隊元素d,e,f 7 輸出鏈隊q的元素個數 8 輸出出隊序列 9 釋放鏈...