數(shù)據(jù)結構課程設計.doc

第1頁課程設計說明書設計題目：數(shù)據(jù)結構課程設計專業(yè)：電子信息科學與技術班級：2008級1班設計人：山東科技大學年月日第2頁課程設計任務書學院：專業(yè)：班級：姓名：一、課程設計題目：數(shù)據(jù)結構課程設計二、課程設計主要參考資料：（1）（2）（3）三、課程設計應解決的主要問題：（1）約瑟夫環(huán)問題（2迷宮問題（2）三元組表示的稀疏矩陣的轉置、加法和乘法實現(xiàn)（3）前綴算術表達式轉換及表達式計算（4）有向無環(huán)圖每個頂點出發(fā)的最短路徑及其長度；（5）2-路歸并排序四、課程設計相關附件（如圖紙、軟件等）：五、任務發(fā)出日期：課程設計完成日期：指導教師簽字：系主任簽字：第3頁指導教師對課程設計的評語指導教師簽字：年月日第4頁設計1約瑟夫環(huán)問題一、需求分析一、具體目標包括：1實現(xiàn)單循環(huán)鏈表的初始化2理解約瑟夫環(huán)的定義，用循環(huán)找到每次報數(shù)人的序號3.從單循環(huán)鏈表中刪除節(jié)點，并判斷鏈表空與非空的臨界條件。二、單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADTCircleList數(shù)據(jù)對象：Dai|aiElemset,i=1,2,n,n0數(shù)據(jù)關系：R=,|ai-1,aiD,i=2,n基本操作：LinkInitList（intn）操作結果：構造一個含有n個元素的單向循環(huán)鏈表。三、問題描述設編號為1，2，n(n0)個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m，從第一人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順指針方向上的下一個人起重新自1起順序報數(shù)；下去，直到所有人全部出列為止。要求設計一個程序模擬此過程。第5頁四、基本要求利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序印出個人的編號。二、概要設計一、本程序分三個模塊1）主模塊Voidmain()初始化；接受命令；處理命令；2）單向循環(huán)表單元模塊，實現(xiàn)單向循環(huán)鏈表的抽象數(shù)據(jù)類型功能；3）節(jié)點結構單元模塊，定義單向循環(huán)鏈表的節(jié)點結構。三、詳細設計1、構建一個單循環(huán)鏈表算法流程圖1第6頁2主模塊實現(xiàn)算法從頭結點開始，根據(jù)報數(shù)上限找到下一個出列人的序號，并讀出該人的密碼作為新的報數(shù)上限，從此節(jié)點的下一個節(jié)點開始進行新的查找。通過指針依次刪除出列人相應的節(jié)點，直到該鏈表中無節(jié)點，退出循環(huán)。P指向申請空間inext=qp=qp-next=L結束第7頁四、運行結果及分析測試用例1：（一般數(shù)據(jù)）輸入報數(shù)上限jnm=1?inex