【正文】 第一篇：數據結構實驗指導書數據結構實驗指導書信息工程學院計算機系實驗一 線性表實驗實驗目的熟悉線性表的基本運算在順序存儲結構和鏈式存儲結構上的實現(xiàn)，其中重點熟悉鏈表的各種操作。時間要求：4學時 問題描述：約瑟夫（Joseph）問題的一種描述是：編號為1，2，3，…，n的n個人按順時針方向圍坐一圈，每人持有一個密碼〈正整數〉，一開始任選一個正整數作為報數上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序?；疽? 利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序打印出各人的編號。實現(xiàn)提示：程序運行后首先要求用戶指定初始報數上限值，然后讀取各人的密碼(小于30)。選作內容：在順序存儲結構上實現(xiàn)上述問題的操作。Input 輸入包括兩行，第一行包括報數上限值m和人數n，第二行為n個人的密碼，所有數據之間由空格分隔。Output 輸出一行，共n個整數，表示各編號人的出列順序。各數之間由空格分隔。Sample Input 20 7 3 1 7 2 4 8 4 Sample Output 6 1 4 7 2 3 5 2實驗二 棧和隊列實驗實驗目的熟悉棧和隊列的基本特性，掌握棧和隊列基本運算的實現(xiàn)過程。時間要求：4+4學時 問題描述：設停車場內只有一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進出，汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿 n 輛汽車，則后來的汽車只能在門外的便道上等候, 一旦有車開走，則排在便道上的第一輛車即可開入，當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用，當便道上汽車要離開時，排在它前面的汽車要先開走讓路，然后再依次排到隊尾，并且在便道上停車不收費。試為停車場編制按上述要求進行管理的模擬程序?；疽螅阂詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列管理，每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時間，對每一組輸入數據進行操作后的輸出數據為： 若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便遞上停留的時間不收費），棧以順序結構實現(xiàn)，隊列以鏈表結構實現(xiàn)。實現(xiàn)提示：需另設一棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現(xiàn)。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含有兩個數據項：汽車牌照號碼和進入停車場的時間。選作內容：（1）兩個棧共享空間，思考應開辟數組的空間是多少 ?（2）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如 1 輛客車和 輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。（3）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這神要求。Input 輸入第一行，包括兩個數據，第一個整數為停車場最多可停放車輛數，第二個浮點數表示單位時間的停車費用。接下來有多行數據，每行有三個整數，第一個為0或1，0表示進 入車場，1表示離開車場；第二個整數為車號；第三個整數為進入或離開的時間。當一行中三個數均為0時表示輸入結束，所有數據之間由空格分隔。Output 輸出為三部分，第一部分為按離開停車場順序打印出的各車費用，每車一行，包括車號和費用(保留小數點后兩位)。第二部分占一行為當前停車場中的所有車輛，從北到南順序輸出各車車號。第三部分占一行為當前便道上的所有車輛，從前向后順序輸出各車車號。各車號之間由一個空格分隔。Sample Input 2 0 1 5 0 2 10 1 1 15 0 3 20 0 4 25 0 5 30 0 6 35 1 2 40 0 7 45 1 6 50 0 0 0 Sample Output 1 2 3 4 7 5 4實驗三 哈夫曼樹實驗實驗目的熟悉非線性結構的特點 , 掌握非線性結構的存儲方式及各種操作的實現(xiàn)方法，同時對自頂向下的程序設計方法、應用程序界面的設計、非線性結構的文件存儲方法等方面的輯程技術進行訓練。時間要求：4+4學時 問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數據預先編碼；在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)，試為這樣的信息收發(fā)站寫一個哈夫曼編譯碼系統(tǒng)。基本要求：一個完整的系統(tǒng)應具有以下功能：（1）I： 初始化。從終端讀入字符集大小 n，及 n 個字符和 n 個權值，建立哈夫曼樹，并將其存于文件hfmtree中。（2）C： 編碼。利用已建好的哈夫曼樹（如不在內存，則從文件hfmtree中讀入），對文件tobetrans中的正文進行編碼，然后將結果存入文件codefile中。（3）D： 譯碼。利用已建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結果存入文件textfile中。（4）P： 打印代碼文件。將文件codefi1e以緊湊格式顯示在終端上,每行50個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。（5）T：打印哈夫曼樹。將已在內存中的哈夫曼樹以直觀的方式（樹或凹凸表形式）顯示在屏幕上，同時將此字符形式的哈夫曼樹寫入文件treeprint中。實現(xiàn)提示：（1）用戶界面可以設計為“菜單”方式：顯示上述功能號，再加上“E”表示結束運性行結束，用戶鍵入一個選擇功能字符，則執(zhí)行相應的功能，此功能執(zhí)行完畢后再顯示此菜單，直至用戶選擇了“E”為止。（1）在程序的一次執(zhí)行過程中，第一次執(zhí)行了I、D 或 C 命令之后，哈夫曼樹已經在內存中存在了，不必再讀入。每次執(zhí)行中不一定執(zhí)行 I 命令，因為文件 hfmtree 可能早已建好。選作內容：（1）修改你的系統(tǒng)，使系統(tǒng)實現(xiàn)對自身源程序的編碼和譯碼（注意特殊符號的編/譯碼問題）。（2）實現(xiàn)各個轉換操作的源/目的文件均由用戶自己指定。實驗四 圖的搜索實驗實驗目的熟悉圖的相關操作，掌握圖的搜索算法及其應用，同時進一步練習棧與隊列在實際問題中的應用。時間要求：4+4學時 問題描述：一只老鼠走進了一個迷宮，這個迷宮是由M行N列（如:10行8列）的方格構成的，相鄰方格之間可能是相通的，也可能有墻相隔，各方格位置由其對應坐標確定，如圖所示。迷宮在（1，1）處有一個入口，在（M,N）處有一個出口，在入口和出口之間有通路相通。問題是讓你幫助老鼠找出從入口到出口的一條最短路徑。00001000 11001010 00010000 00001010 10100000 00111011 10001000 基本要求：為老鼠找出一條從入口到出口的最短路徑。實現(xiàn)提示：迷宮用數組表示，1代表是墻走不通，0表示可以通行。邊界可以擴充為墻，即MN迷宮用(M+2)(N+2)數組表示。向4個方向前進時的位移量可以用以下數組表示，處理時方便。int move[4][2]={ {0,1},{1,0},{0,1},{1,0} }。采用圖的廣度優(yōu)先搜索算法。選作內容：對給定的迷宮，統(tǒng)計出共有多少條不同的路徑。實驗五 排序實驗實驗目的熟練掌握各種排序算法的實現(xiàn)方法，以及不同算法的特點，掌握各種排序方法的時間效率。時間要求：4+4學時 問題描述：各種內部排序算法的時間復雜度分析結果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。對一組給定的數據，設計出各不同排序算法對其進行排序，給出各算法在排序中的關鍵字比較次數和關鍵字移動次數，以取得直觀感受?；疽螅海?）對以下各排序算法進行比較：直接插入排序、冒泡排序、快速排序、簡單選擇排序、歸并排序。（2）待排序表的表長為100；一共有n組不同的數據，對每組數據用以上各排序方法進行排序，比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數。實現(xiàn)提示：在算法的適當地方加入計數操作，計算關鍵字的比較次數和移動次數。選作內容：對算法的穩(wěn)定性作驗證。Input 輸入部分第一行為待排關鍵字的組數n，接下來為n行待排關鍵字，第行有100個整數所有數據之間由空格分隔。Output 輸出共n行，每行共有10個整數，表示5種排序方法排序的關鍵字比較次數和移動次數，即為：直接插入排序比較次數 直接插入排序移動次數 冒泡排序比較次數 冒泡排序移動次數 快速排序比較次數、快速排序移動次數 簡單選擇排序比較次數、簡單選擇排序移動次數 歸并排序比較次數 歸并排序移動次數（下例待排關鍵字為5，實際提交測試數據為100）Sample Input 3 1 2 3 4 5 5 4 3 2 1 4 2 5 1 3 Sample Output 4 0 4 0 10 16 10 0 7 12 14 18 10 30 12 16 10 6 5 12 10 12 10 18 11 14 10 6 7 12數據結構實驗報告實驗一 線性表實驗班級：____________ 姓名：____________ 學號：____________實驗目的：熟悉線性表的基本運算在順序存儲結構和鏈式存儲結構上的實現(xiàn)，其中重點掌握線性表的鏈式表示時各種操作的實現(xiàn)。問題描述：約瑟夫（Joseph）問題的一種描述是：編號為1，2，3，?，n的n個人按順時針方向圍坐一圈，每人持有一個密碼〈正整數〉，一開始任選一個正整數作為報數上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序。需求分析：（包括對問題的理解，解決問題的策略、方法描述）系統(tǒng)設計：（包括數據結構定義、抽象出基本操作描述、主程序模塊處理過程描述）調試分析：（包括調試過程中對原設計的修改，以及遇到的問題和解決的方法）測試結果：（輸入的測試數據及運行結果、正確性、在線測試情況）基本操作的實現(xiàn)：（對各基本操作實現(xiàn)的描述）數據結構實驗報告實驗二 棧和隊列實驗班級：____________ 姓名：____________ 學號：____________實驗目的：熟悉棧和隊列的基本特性，掌握棧和隊列基本運算的實現(xiàn)過程。重點掌握棧和隊列各種操作的實現(xiàn)。問題描述：設停車場內只有一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進出，汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿 n 輛汽車，則后來的汽車只能在門外的便道上等候, 一旦有車開走，則排在便道上的第一輛車即可開入，當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用，試為停車場編制按上述要求進行管理的模擬程序。需求分析：（包括對問題的理解，解決問題的策略、方法描述）系統(tǒng)設計：（包括數據結構定義、抽象出基本操作描述、主程序模塊處理過程描述）調試分析：（包括調試過程中對原設計的修改，以及遇到的問題和解決的方法）測試結果：（輸入的測試數據及運行結果、正確性、在線測試情況）基本操作的實現(xiàn)：（對各基本操作實現(xiàn)的描述）數據結構實驗報告實驗三 哈夫曼樹實驗班級：____________ 姓名：____________ 學號：____________實驗目的：熟悉非線性結構的特點 , 掌握非線性結構的存儲方式及各種操作的實現(xiàn)方法，同時對自頂向下的程序設計方法、應用程序界面的設計、非線性結構的文件存儲方法等方面的輯程技術進行訓練。問題描述：利用哈夫曼編碼進行