數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).doc

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