一、 《資料結構課程實驗》的地位與作用
「資料結構」是計算機專業一門重要的專業技術基礎課程，是計算機專業的一門核心的關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法，介紹了常用的多種查詢和排序技術，並做了效能分析和比較，內容非常豐富。本課程的學習將為後續課程的學習以及軟體設計水平的提高打下良好的基礎。
由於以下原因，使得掌握這門課程具有較大的難度：
（1） 內容豐富，學習量大，給學習帶來困難；
（2） 貫穿全書的動態鍊錶儲存結構和遞迴技術是學習中的重點也是難點；
（3） 所用到的技術多，而在此之前的各門課程中所介紹的專業性知識又不多，因而加大了學習難度；
（4） 隱含在各部分的技術和方法豐富，也是學習的重點和難點。
根據《資料結構課程》課程本身的技術特性，設定《資料結構課程實驗》實踐環節十分重要。通過實驗實踐內容的訓練，突出構造性思維訓練的特徵, 目的是提高學生組織資料及編寫大型程式的能力。實驗學時為10。
二、《資料結構課程實驗》的目的和要求
不少學生在解答習題尤其是演算法設計題時，覺得無從下手，做起來特別費勁。實驗中的內容和教科書的內容是密切相關的，解決題目要求所需的各種技術大多可從教科書中找到，只不過其出現的形式呈多樣化，因此需要仔細體會，在反覆實踐的過程中才能掌握。
為了幫助學生更好地學習本課程，理解和掌握演算法設計所需的技術，為整個專業學習打好基礎，要求運用所學知識，上機解決一些典型問題，通過分析、設計、編碼、除錯等各環節的訓練，使學生深刻理解、牢固掌握所用到的一些技術。資料結構中稍微複雜一些的演算法設計中可能同時要用到多種技術和方法，如演算法設計的構思方法，動態鍊錶，演算法的編碼，遞迴技術，與特定問題相關的技術等，要求重點掌握線性鍊錶、二叉樹和樹、圖結構、陣列結構相關演算法的設計。在掌握基本演算法的基礎上，掌握分析、解決實際問題的能力。
三、 《資料結構課程實驗》內容
課程實驗共10學時，要求完成以下五個題目：
實習一約瑟夫環問題（2學時）
用迴圈鍊錶實現約瑟夫環問題，熟悉鍊錶結構的使用。
實習二八皇后問題 （2學時）
在8×8的棋盤上放置彼此不受攻擊的8個皇后，熟悉遞迴與回溯程式設計方法。
實習三二叉樹基本操作（2學時）
建立、遍歷、顯示二叉樹，通過二叉樹的基本操作，掌握樹結構的處理方法。
實習四哈夫曼編碼與解碼
針對字符集a及其各字元的頻率值（可統計獲得）給出其中給字元哈夫曼編碼，並針對一段文字（定義在a上）進行編碼和解碼，實現乙個哈夫曼編碼/解碼系統。
實習五最小生成樹問題（2學時）
在n個城市之間建設網路，只需保證連通即可，求最經濟的架設方法。
四、 《資料結構課程實驗》考核方式
採用上機情況、程式質量、實習報告相結合的形式，滿分為100分。
1． 上機情況（30%）
包括出勤情況、除錯表現、是否上網、玩遊戲。
2． 程式質量（50%）
3． 實習報告（20%）
《資料結構課程實驗》指導書
實習一線性表
本次實習的主要目的在於熟悉線性表的基本運算在兩種儲存結構上的實現，其中以熟悉各種鍊錶的操作為側重點。通過本次實習還可幫助讀者複習高階語言的使用方法。
1、城市鍊錶
[問題描述]
將若干城市的資訊，存入乙個帶頭結點的單鏈表。結點中的城市資訊包括：城市名，城市的位置座標。要求能夠利用城市名和位置座標進行有關查詢、插入、刪除、更新等操作。
[基本要求]
（1） 給定乙個城市名，返回其位置座標；
（2） 給定乙個位置座標p和乙個距離d，返回所有與p的距離小於等於d的城市。
[測試資料]
由學生依據軟體工程的測試技術自己確定。注意測試邊界資料。
2、約瑟夫環
[問題描述]
約瑟夫（joeph）問題的一種描述是：編號為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有乙個密碼（正整數）。一開始任選乙個正整數作為報數上限值m，從第乙個人開始按順時針方向自1開始順序報數，報到m時停止報數。
報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人開始重新從1報數，如此下去，直至所有人全部出列為止。試設計乙個程式求出出列順序。
[基本要求]
利用單向迴圈鍊錶儲存結構模擬此過程，按照出列的順序印出各人的編號。
[測試資料]
m的初值為20；密碼：3，1，7，2，4，8，4（正確的結果應為6，1，4，7，2，3，5）。
[實現提示]
程式執行後首先要求使用者指定初始報數上限值，然後讀取各人的密碼。設n≤30。
[選作內容]
向上述程式中新增在順序結構上實現的部分。
3、線性表的逆置
[問題描述]
分別以不同儲存結構實現線性表的就地逆置。線性表的就地逆置就是在原表的儲存空間內將線性表（a1,a2,a3,…,an）逆置為（an，an-1，…，a2，a1）。
[基本要求]
用順序儲存結構實現線性表的就地逆置，並將結果輸出。
[測試資料]
由學生依據軟體工程的測試技術自己確定。注意測試邊界資料，如空表。
[實現提示]
設三個連續的指標，分別指向當前結點、當前結點的前趨、當前結點的後繼。
[選作內容]
利用單鏈表作為儲存結構。首先先建立線性表的帶頭結點的單鏈表表示形式，之後在不借助輔助結點空間的情況下實現單鏈表的逆置，並將結果輸出。
4、長整數運算
[問題描述]
設計乙個程式實現兩個任意長的整數求和運算。
[基本要求]
利用雙項迴圈鍊錶實現長整數的儲存，每個結點含乙個整型變數。任何整型變數的範圍是 -（215-1）~（215-1）。輸入和輸出形式：
按中國對於長整數的表示習慣，每四位一組，組間用逗號隔開。
[測試資料]
（1） 0；0；應輸出「0」。
（2） -2345,6789；-7654,3211；應輸出「-1,0000,0000」。
（3） -9999,9999；1,0000,0000,0000；應輸出「9999,0000,0001」。
（4） 1,0001,000；-1,0001,0001；應輸出「0」。
（5） 1,0001,0001；-1,0001,0000；應輸出「1」。
[實現提示]
（1） 每個結點中可以存放的最大整數為215-1=32767，才能保證兩數相加不會溢位。但若這樣存，即相當於按32768進製數存，在十進位制數與32768進製數之間的轉換十分不方便。故可以在每個結點中僅存十進位制數的4位，即不超過9999的非負整數，整個鍊錶視為萬進製數。
（2） 可以利用頭結點資料域的符號代表長整數的符號。用其絕對值表示元素結點數目。相加過程中不要破壞兩個運算元鍊錶。
兩運算元的頭指標存於指標陣列中是簡化程式結構的一種方法。不能給長整數字數規定上限。
[選作內容]
修改上述程式，使它在整型量範圍是-（2n-1）~（2n-1）的計算機上都能有效地執行。其中，n是由程式讀入的參量。輸入資料的分組方法可以另行規定。
實習二棧、佇列與遞迴演算法設計
僅僅認識到棧和佇列是兩種特殊的線性表是遠遠不夠的，本次實習的目的在於使讀者深入了解棧和佇列的特徵，以便在實際問題背景下靈活運用它們；同時還將鞏固這兩種結構的構造方法，接觸較複雜問題的遞迴演算法設計。
1、數制轉換問題
[問題描述]
將十進位制數n和其它d進製數的轉換是計算機實現計算的基本問題，其解決方案很多，其中最簡單方法基於下列原理：即除d取餘法。例如：（1348）10=（2504）8
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
從中我們可以看出，最先產生的餘數4是轉換結果的最低位，這正好符合棧的特性即後進先出的特性。所以可以用順序棧來模擬這個過程。
[基本要求]
對於鍵盤輸入的任意乙個非負的十進位制整數，列印輸出與其等值的八進位制數。由於上述的計算過程是從低位到高位順序產生的八進位制數的各個數字，而列印輸出，一般來說應從高位到地位進行，恰好和計算過程相反。因此可以先將計算過程中得到的八進位制數的各位進棧，待相對應的八進位制數的各位均產生以後，再使其按順序出棧，並列印輸出。
即得到了與輸入的十進位制數相對應的八進位制數。
[測試資料]
由學生依據軟體工程的測試技術自己確定。注意測試邊界資料。
2、回文判斷
[問題描述]
試寫乙個演算法，判斷依次讀入的乙個以@為結束符的字母序列，是否為形如『序列1 & 序列2』模式的字串行。其中序列1和序列2 中都不含字元『&』，且序列2 是序列1的逆序列。例如，『a+b&b+a』是屬該模式的字串行，而『１+３&３－１』則不是。
[實現提示]
首先，序列1進棧，然後序列1出棧並與序列2比較。
[測試資料]
由學生依據軟體工程的測試技術自己確定。注意測試邊界資料，如序列1和序列2均為空串。
3、商品貨架管理
[問題描述]
商品貨架可以看成乙個棧，棧頂商品的生產日期最早，棧底商品的生產日期最近。 上貨時，需要倒貨架，以保證生產日期較近的商品在較下的位置。
[基本要求]
針對一種特定商品，實現上述管理過程。
[實現提示]
用棧模擬貨架和周轉空間。
[測試資料]
由學生依據軟體工程的測試技術自己確定。注意測試邊界資料，如空棧。
4、括號匹配的檢驗
[問題描述]
假設表示式中允許有兩種括號：圓括號和方括號，其巢狀的順序隨意，即（（）[ ]）或
等為正確格式，[（ ]）或（（（]均為不正確的格式。檢驗括號是否匹配的方法可用「期待的緊迫程度」這個概念來描述。例如：考慮下列的括號序列：
1 2 3 4 5 6 7 8
當計算機接受了第1個括號以後，他期待著與其匹配的第8個括號的出現，然而等來的卻是第2個括號，此時第1個括號「[」只能暫時靠邊，而迫切等待與第2個括號相匹配的第7個括號「）」的出現，類似的，因只等來了第3個括號「[」，此時，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓位於第3個括號，顯然第3個括號的期待緊迫程度高於第2個括號，而第2個括號的期待緊迫程度高於第1個括號；在接受了第4個括號之後，第3個括號的期待得到了滿足，消解之後，第2個括號的期待匹配就成了最急迫的任務了，…… ，依次類推。可見這個處理過程正好和棧的特點相吻合。
[基本要求]
讀入圓括號和方括號的任意序列，輸出「匹配」或「此串括號匹配不合法」。
[測試資料]
輸入（[ ]（）），結果「匹配」
輸入 [（ ）]，結果「此串括號匹配不合法」
[實現提示]
設定乙個棧，每讀入乙個括號，若是左括號，則作為乙個新的更急迫的期待壓入棧中；若是右括號，並且與當前棧頂的左括號相匹配，則將當前棧頂的左括號退出，繼續讀下乙個括號，如果讀入的右括號與當前棧頂的左括號不匹配，則屬於不合法的情況。在初始和結束時，棧應該是空的。
[選作內容]
考慮增加大括號的情況。
5、停車場管理
[問題描述]
設停車場內只有乙個可停放n輛汽車的狹長通道，且只有乙個大門可供汽車進出。汽車在停車場內按車輛到達時間的先後順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則後來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之後開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程式。
[測試資料]
設n=2,輸入資料為：（『a』，1，5），（『a』，2，10），（『d』，1，15），（『a』，3， 20）， （『a』，4，25），（『a』，5，30），（『d』，2，35），（『d』，4，40），（『e』，0，0）。每一組輸入資料報括三個資料項：
汽車「到達」或「離去」資訊、汽車牌照號碼及到達或離去的時刻，其中，『a』表示到達；『d』表示離去，『e』表示輸入結束。
[基本要求]
以棧模擬停車場，以佇列模擬車場外的便道，按照從終端讀入的輸入資料序列進行模擬管理。每一組輸入資料報括三個資料項：汽車「到達」或「離去」資訊、汽車牌照號碼及到達或離去的時刻，對每一組輸入資料進行操作後的輸出資料為：
若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去；則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，佇列以鍊錶實現。
[實現提示]
需另設乙個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序儲存結構實現。輸入資料按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個資料項：
汽車的牌照號碼和進入停車場的時刻。
[選作內容]
（1） 兩個棧共享空間，思考應開闢陣列的空間是多少？
（2） 汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當於3輛小汽車的占地面積。
（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然後再依次排到隊尾。
（4） 停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。
《資料結構A》課程實驗大綱
課程編號課程名稱 資料結構a 課內總學時 8實驗學時 8 8 一 實驗課程的性質 目的和任務 資料結構a 是電腦科學與技術以及相關專業的學科基礎課，是計算機軟體設計的重要理論和實踐基礎。課程教學包括理論和上機實驗兩部分。通過上機實驗，加深對電腦科學中的組織 表示和處理資料的基本方法的理解，訓練學生運...
《資料結構》課程實驗教學大綱
課程名稱 資料結構 data structure 課程負責人 王茜 課程分類 專業課程課程型別 設計性實驗 適用專業 計算機網路工程電腦科學與技術 課程總學時 64課程總學分 3.5 實驗學時 20實驗學分 開課單位 計算機學院 一 實驗教學的目的與要求 實驗目的 通過實驗使學生在基本資料結構的邏輯...
資料結構實驗大綱2019
資料結構 實驗課程教學大綱 1 實驗課程名稱 資料結構 2 實驗課程名稱 英文 data structure 3 課程 130038 4 實驗課程性質 非獨立設課 5 學時 16 6 學分 0.5 7 適用專業 資訊管理與資訊系統專業 8 先修或同修課程 離散數學 高階語言程式設計 9 開課單位 資...