課程設計名稱：資料結構課程設計指導老師：歐陽勇
課程設計周（時）數：1周
指導方式：集體輔導與個別輔導相結合
課程設計適用專業：電腦科學與技術
課程設計教材及主要參考資料：
1、《資料結構》，嚴蔚敏編著，清華大學出版社
一、課程設計教學目的及基本要求
1、了解並掌握資料結構與演算法的設計方法，具備初步的獨立分析和設計能力；
2、初步掌握軟體開發過程的問題分析、系統設計、程式編碼、測試等基本方法和技能；
3、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；
4、訓練用系統的觀點和軟體開發一般規範進行軟體開發，培養軟體工作者所應具備的科學的工作方法和作風。
5、設計的題目要求達到一定工作量（200行以上**），並具有一定的深度和難度。
6、編寫出課程設計說明書，說明書不少於15頁（不包括**）。
二、課程設計內容及安排
1、問題定義與需求分析：根據設計題目的要求，充分地分析和理解問題，確定功能需求和限制條件。
2、資料結構設計：對問題描述中涉及的操作物件定義相應的資料型別和各抽象資料型別，寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的功能說明)，，
3、總體設計：採用結構化設計方法，按照以資料結構為中心的原則劃分模組，設計軟體層次結構和模組間的呼叫關係，定義主程式，畫出模組之間的呼叫關係圖。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，
4、詳細設計：定義資料儲存結構，各個主要模組的演算法定義。詳細設計的結果是對資料結構和基本操作作出進一步的求精，寫出資料儲存結構的型別定義，用偽碼寫出函式的演算法。
5、程式編碼：把詳細設計的結果進一步求精為程式語言程式。同時加入一些註解，使程式中邏輯概念清楚。要求用c語言編寫。
6、程式除錯與測試：採用自底向上，分模組進行，即先除錯低層函式。能夠熟練掌握除錯工具的各種功能，設計測試資料確定疑點，通過修改程式來證實它或繞過它。
除錯正確後，認真整理源程式及其注釋，形成格式和風格良好的源程式清單和結果。
7、設計結果分析：程式執行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。演算法的時間、空間複雜性分析。
8、編寫課程設計報告。
題目：(1) 問題描述
設計資料結構完成乙個學院學生相關資訊的儲存，並在此基礎上編寫演算法實現學生成績管理。
(2) 課程設計目的
應用線性資料結構儲存資訊，並能夠合理的應用排序及查詢演算法，學會應用雜湊法。
(3) 基本要求
1 乙個學院由若干個班組成；所有學生修相同的考試課和考查課。
2 管理系統能夠實現：學生加入，學生畢業，學生成績統計，學生查詢，學生排名等管理操作。（要考慮考試課和考查課的比重關係）
3 為方便查詢，要求針對學生姓名進行雜湊法查詢。
4 管理系統應有完整地介面（最好是圖形化介面）。
(4) 實現提示
主要集中在雜湊函式的構造和衝突的解決上。
(1) 問題描述
設計演算法生成乙個n×m(n行m列)的迷宮，並完成迷宮的組織和儲存。實現兩種不同的迷宮路由演算法：廣度優先，深度優先演算法。並比較(包括理論和實驗)三種方法的時空複雜性。
(2) 課程設計目的
理解棧的應用，理解深(廣)度優先思想，理解問題的理論和實驗分析。
(3) 基本要求
① n和m是使用者可配置的，預設值為50和50。
② 迷宮的入口和出口分別在第0行和第n-1行上，隨機選擇。
③ 生成的迷宮要求是連通的。
④ 實現圖形化介面(可用vc++，也可用c語言的圖形庫)。
⑤ 三種方法的試驗比較應該在多個迷宮例項上(尤其可以選一些特定的迷宮)。
(4) 實現提示
多考慮棧上的運算。
(1) 問題描述
有一類問題總稱為「隨機漫步」（random walk）問題，這類問題長久以來吸引著數學界的興趣。所有這些問題即使是最簡單的解決起來也是極其困難的。而且它們在很大程度上還遠沒有得到解決。
乙個這樣的問題可以描述為：
在矩形的房間裡，鋪有n×m塊瓷磚，現將乙隻（醉酒的）蟑螂放在地板中間乙個指定方格裡。蟑螂隨機地從一塊瓷磚「漫步」到另一塊瓷磚（可能是在找一片阿司匹林）。假設它可能從其所在的瓷磚移動到其周圍八塊瓷磚中的任何乙個（除非碰到牆壁），那麼它把每一塊瓷磚都至少接觸一次將花費多長時間？
雖然這個問題可能很難用純粹的概率技術來解決，但是使用計算機的話卻十分容易。使用計算機解決此問題的技術稱為「模擬」。這種技術廣泛應用於工業中，用來**運輸流量，存貨控制等等。
該問題可採用如下方法進行模擬：
用乙個n×m陣列作為計數器來表示蟑螂到達每一塊瓷磚的次數，每個陣列單元的初始值均置為零。蟑螂在地板上的位置用座標（ibug，jbug）表示。蟑螂的八種可能移動用在位置(ibug + imove[k]，jbug + jmove[k])的瓷磚表示，其中0≤k≤7，並且
imove[0] = -1 jmove[0] = 1
imove[1] = 0 jmove[1] = 1
imove[2] = 1 jmove[2] = 1
imove[3] = 1 jmove[3] = 0
imove[4] = 1 jmove[4] = -1
imove[5] = 0 jmove[5] = -1
imove[6] = -1 jmove[6] = -1
imove[7] = -1 jmove[7] = 0
蟑螂向其相鄰的八個方格的隨機漫步通過產生乙個隨機數值k(0≤k≤7)來模擬。當然，蟑螂不能爬出屋外，所以應該去掉通往牆壁的座標值並形成乙個新的隨機組合。蟑螂每次進入乙個方格，該方格的計數器就增加一，從而計數器的乙個非零元素就表示蟑螂到達對應方格的次數。
當每乙個方格被至少進入一次時，試驗就完成了。試編寫程式進行上述規定的模擬試驗。
（2）設計目的
利用二維陣列解決複雜的實際問題；
了解實際問題到計算機問題的轉化；
了解演算法設計中邊界條件的重要性
(3) 基本要求
你的程式必須：
（a）能夠處理所有的n和m值, n和m滿足：2（b）能夠對「n = 15，m = 15，起始點為（10，10）」和「n = 39，m = 19，起始點為（1，1）」進行實驗。
（c）具有迭代限制，即實驗過程中蟑螂進入方塊的最大次數為em =50000時，程式能夠終止。
對於每次試驗，列印：
（d）蟑螂進行的合法移動的總次數。
（e）最終的計數器陣列，顯示出漫步的「密度」，即在實驗中每一塊瓷磚被接經過的次數。
（4）實現提示
無(1) 問題描述
西洋棋為許多令人著迷的娛樂提供了固定的框架，這些框架獨立於遊戲本身。其中很多都是基於奇異的騎士「l型」（l-shaped）移動。乙個經典的例子就是騎士巡遊（knight's tour）問題，自從十八世紀初以來，這個問題吸引了數學家們的興趣，也使熱心者們感到困惑。
簡而言之，這個問題要求從棋盤上任意給定的方格開始移動騎士，相繼地到達所有的64個方格，進入每個方格一次且僅進入一次。通常情況下，我們用如下方法表示乙個解：即把數字0，1，…，63放入棋盤中的方格來表示到達這些方格的順序。
解決騎士巡遊問題更具創意的方法之一是由j. c. warnsdorff在2023年提出的。
其規則是：騎士總是移向具有最少出口且沒有到達過的方格之一。
（2）設計目的
利用（二維）陣列解決複雜的實際問題；
了解實際問題到計算機問題的轉化；
了解演算法設計中邊界條件的重要性
(3) 基本要求
a)使用warnsdorff規則，設計並實現解決騎士巡遊問題的演算法；
b) 列印棋盤，並顯示騎士巡遊問題的解，然後終止演算法。
（4）實現提示
a) 用乙個二維陣列表示西洋棋棋盤；
b) 騎士的八種可能移動表示：如果騎士當前位於方格（i，j），則騎士可能移到的方格有（i – 2，j + 1），（i - 1，j + 2），（i + 1，j + 2），（i + 2，j + 1），（i + 2，j - 1）（i + 1，j -2），（i - 1，j - 2），（i - 2，j - 1）。然而，我們注意到，如果（i，j）處於接近棋盤的邊緣方格，在這些可能的移動中，有些移動就會使騎士移出棋盤，這當然是不允許的。
我們可以很容易地使用兩個陣列ktmove1和ktmove2把騎士的八種可能移動表示為：
ktmove1 ktmove2
2112
1221
21 12
1221
於是，位於（i，j）的騎士就可能移到（i + ktmove1[k]，j + ktmove2[k]），其中k是介於0和7之間de
某個值，且假定新方塊仍然位於棋盤上。。
(1) 問題描述
稀疏矩陣的每個結點包含down，right，row，col和value五個域。用單獨乙個結點表示乙個非零項，並將所有結點連線在一起，形成兩個迴圈鍊錶。使得第乙個錶即行表，把所有結點按照行序（同一行內按列序）用right域鏈結起來。
使得第二個錶即列表，把所有結點按照列序（同一列內按行序）用down鏈結起來。這兩個表共用乙個頭結點。另外，增加乙個包含矩陣維數的結點。
稀疏矩陣的這種儲存表示稱為完全煉表表式。
實現乙個完全鍊錶系統進行稀疏矩陣運算，並分析下列操作函式的計算時間和額外儲存空間的開銷。
（2）設計目的
認識和掌握稀疏矩陣的完全鍊錶表示；能夠建立並運用這種儲存結構
(3) 基本要求
建立乙個使用者友好、選單式系統進行下列操作，並使用合當的測試資料測試該系統。
（a） 讀取乙個稀疏矩陣建立其完全鍊錶表示
（b） 輸出乙個稀疏矩陣的內容
（c） 刪除乙個稀疏矩陣
（d） 兩個稀疏矩陣相加
（e） 兩個稀疏矩陣相減
（f） 兩個稀疏矩陣相乘
（g） 稀疏矩陣的轉置
（4）實現提示
鍊錶上的操作。
倉庫管理系統（線性表應用）
資料結構課程設計
指導書山東建築大學 電腦科學與技術學院 二 六年十二月 課程設計基本情況 課程名稱 資料結構課程設計 相關課程 c語言程式設計 visual c 程式設計 資料結構 適合專業 電腦科學與技術 網路工程 軟體工程 設計週數 2周 學分 2學分 開課學期 第4學期 開課單位 電腦科學與技術學院 一 課程...
資料結構課程設計
總結報告 專業軟體工程 班級軟體1007 學號 20103540 姓名 日期 2012.9.17 東北大學軟體學院 第一章需求分析 問題定義 實現乙個網上拍賣系統，根據需求描述和附加的框架 完成乙個網上拍賣系統。分析 整個系統執行於windows平台，是基於b s結構的商業應用程式，程式為使用者提供...
資料結構課程設計
環境與測繪學院 1 c 物件導向程式設計基礎 實驗簡介 學會用演算法語言c 描述抽象資料型別。理解資料結構的組成分為兩部分，第一部分是資料集 資料元素 第二部分是在此資料集上的操作。從物件導向的觀點看，這兩部分代表了物件的屬性和方法。掌握用c 描述資料結構的基本方法，即通過建立類來描述抽象資料型別。...