1、數據結構與算法實驗報告編制老師 袁宇麗 審定 何文孝（適用于計算機科學學院2022級本科同學）專業:班級： 級 班學號:姓名:2022至2022學年其次學期計算機科學學院試驗總結及意見:試驗評價（老師）:試驗名稱：線性表的應用指導老師：余文春試驗日期：2022年 月 日 試驗地點：北503 成果：試驗目的：1、把握線性表及其挨次存儲與鏈式存儲結構的概念。2、把握兩種存儲方式的基本運算、實現方法和技術。3、敏捷應用線性表進行程序設計，解決實際問題。試驗內容：約瑟夫(Joseph)問題的一種描述是：編號為1, 2,，n的n個 人按順時針方向圍坐一圈，一開頭任選一個正整數作為報數上限值m, 從第一個

2、人開頭按順時針方向自1開頭挨次報數，報到m時停止報數。 報m的人出列，從他在順時針方向上的下一個人開頭重新從1報數， 同樣報到m的人出列，如此下去，直至全部人全部出列為止。采用循 環鏈表為存儲結構模擬此過程，根據出列的挨次輸出依次出列人的編 號。基本要求：1、寫出完成試驗內容的試驗方法和源代碼。2、寫出試驗數據及運行結果。3、寫出在試驗過程中所遇到的問題及解決方法。試驗總結及意見:試驗評價（老師）:試驗名稱：棧及隊列的應用指導老師：余文春試驗日期：2022年 月 日 試驗地點：北503 成果：試驗目的：1、把握隊列及其存儲結構的概念。2、把握棧、隊列的基本運算、實現方法和技術。3、能用棧、隊列

3、的學問和操作技術設計有肯定難度的程序。試驗內容：1、假設算術表達式僅由加(+)、減(-)、乘(*)、除()運算符組 成，編寫一個借助堆棧把中綴表達式轉換為后綴表達式的函數，為使 問題簡化，可不考慮中綴表達式不正確的狀況。2、假設在周末舞會上，男士們和女士們進入舞廳時，各自排成 一隊。跳舞開頭時，依次從男隊和女隊的隊頭上各出一人配成舞伴。 若兩隊初始人數不相同，則較長的那一隊中未配對者等待下一輪舞 曲。現要求寫一算法模擬上述舞伴配對問題。基本要求：1、寫出完成試驗內容的試驗方法和源代碼。2、寫出試驗數據及運行結果。3、寫出在試驗過程中所遇到的問題及解決方法。試驗總結及意見:試驗評價（老師）:試驗

4、名稱：二叉樹的建立與遍歷算法指導老師：余文春試驗日期：2022年 月 日 試驗地點：北503成果：試驗目的：1、把握二叉樹的定義。2、二叉樹的鏈式存儲結構及在鏈式存儲結構中三種遍歷（前序, 中序，后序）操作的實現及應用。試驗內容：1、編寫程序，建立一棵二叉樹（以鏈表存儲），對該二叉樹進行 遍歷并輸出該二叉樹的前序，中序，后序遍歷序列。要求前序、中序 遍歷用非遞歸方法，后序遍歷用遞歸方法完成。2、編寫程序，建立一棵二叉樹（以鏈表存儲），實現二叉樹左右 子樹的交換。3、統計二叉樹中葉子結點個數。（要求用非遞歸算法完成） 基本要求：1、寫出完成試驗內容的試驗方法和源代碼。2、寫出試驗數據及運行結果。

5、3、寫出在試驗過程中所遇到的問題及解決方法。試驗總結及意見:試驗評價（老師）:試驗名稱：查找及排序算法指導老師：余文春試驗日期：2022年 月 日 試驗地點：北503 成果：試驗目的：1、把握基本查找和排序技術的原理及其實現方法。2、對于不同的要求，能選擇比較合理的查找、排序算法，得到 初步的算法分析的訓練，提高算法設計的力量。試驗內容：定義一最大長度為20的結構體數組（可以在結構體中只定義關 鍵字域），從鍵盤輸入結構體數組各元素的關鍵字值，以輸入-9999 為結束，對該數組中的元素按關鍵字非遞減的挨次進行排序，分別用 冒泡排序，非遞歸的快速排序，遞歸的快速排序方法完成，再用折半 查找方法對已

6、經有序的結構體數組進行操作，輸入一待查紀錄關鍵 字，若查找勝利輸出“success”，查找不勝利則輸出“unsuccess，以 上各功能模塊均用函數實現。設計相應算法并分析各排序方法的效 率。該程序運行狀況舉例說明：運行主界面如下圖所示：提示用戶輸入相應選項，鍵入數字1則 進行待排序數據值的輸入；鍵入數字2進行冒泡排序；鍵入數字3進 行遞歸的快速排序；鍵入數字4則進行遞歸的快速排序；鍵入數字5 則進行折半（二分）查找；鍵入數字。程序結束并退出。基本要求：1、寫出完成試驗內容的試驗方法和源代碼。2、寫出試驗數據及運行結果。3、寫出在試驗過程中所遇到的問題及解決方法:|主菜單如下:select 1:輸入待排序元素值select 2:直接插入排序select 3:直接