數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告校園導(dǎo)游系統(tǒng)

1、第2章 約瑟夫問題經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué) 號(hào)： 10051701089 姓 名： 班 級(jí)： 管理101 專 業(yè)： 信息管理與信息系統(tǒng) 系 別: 指導(dǎo)教師： - 19 -目 錄目 錄i第1章 校園導(dǎo)游問題- 1 -1.1需求分析- 1 -1.1.1課程設(shè)計(jì)的目的- 1 -1.1.2程序的主要功能體現(xiàn)- 1 -1.1.3數(shù)據(jù)測試- 1 -1.2概要設(shè)計(jì)- 1 -1.2.1功能設(shè)計(jì)- 2 -1.2.2抽象數(shù)據(jù)類型定義- 5 -1.3系統(tǒng)的主要界面設(shè)計(jì)及運(yùn)行說明：- 6 -1.3.1界面設(shè)計(jì)- 6 -1.3.2調(diào)試分析- 9 -1.4總結(jié)- 9 -第2章 約瑟夫問題- 10 -

2、2.1需求分析- 10 -2.1.1課程設(shè)計(jì)的目的- 10 -2.1.2程序的主要功能體現(xiàn)- 10 -2.1.3數(shù)據(jù)測試- 10 -2.2概要設(shè)計(jì)- 11 -2.2.1用循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)解決約瑟夫問題- 11 -2.2.2用線性表存儲(chǔ)結(jié)構(gòu)解決約瑟夫問題- 13 -2.2.3用循環(huán)隊(duì)列儲(chǔ)存結(jié)構(gòu)解決約瑟夫問題- 15 -2.3系統(tǒng)的主要界面設(shè)計(jì)及運(yùn)行說明：- 17 -2.4.實(shí)驗(yàn)總結(jié)：- 19 -參考文獻(xiàn)- 20 -第1章 校園導(dǎo)游問題1.1需求分析1.1.1課程設(shè)計(jì)的目的此次課程設(shè)計(jì)的主要內(nèi)容是校園導(dǎo)游系統(tǒng)，所謂系統(tǒng)其實(shí)也不盡然，只不過是個(gè)小小的提示，為來訪的客人提供各種信息查詢服務(wù)?，F(xiàn)在大多數(shù)

3、的學(xué)校由于不斷的擴(kuò)張，這也就使得學(xué)校不得不建立的更大。這也就為人們拜訪學(xué)校造成了很大的不便。人們往往不熟悉學(xué)校，找個(gè)東西，或某處帶來了極大的不便。往往要花很多時(shí)間在這一方面。然而要是有一個(gè)學(xué)校導(dǎo)游系統(tǒng)這將給乘客帶來極大的方便，使人們一下就能了解到這個(gè)學(xué)校的大致情況主要包括：查看學(xué)校的全景圖各個(gè)景點(diǎn)的簡介學(xué)校主要景點(diǎn)的分布查看某一景點(diǎn)到其它所有景點(diǎn)的最短路徑查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑。1.1.2程序的主要功能體現(xiàn)對(duì)于功能的輸入形式是沒什么要求的，主要就是根據(jù)菜單的提示輸入相應(yīng)的數(shù)字選擇相應(yīng)的功能；對(duì)于功能的輸入形式的要求也比較簡單，要查詢某一景點(diǎn)的簡介直接輸入其對(duì)應(yīng)的編號(hào)即可；對(duì)于功能的輸入

4、形式的要求同功能；對(duì)于功能只需要輸入想要查看的起始景點(diǎn)的編號(hào)即可；對(duì)于功能只需要輸入起始景點(diǎn)和目的景點(diǎn)的編號(hào)即可。此程序在輸入形式上都沒什么特殊的要求只是一些簡單的數(shù)字就可以搞定一切。功能就是輸出由字符構(gòu)成的一幅簡易圖，形式比較單一；景點(diǎn)的簡介方面輸出景點(diǎn)的簡單信息就可以了；要查詢最短路徑的話輸出的自然是從起始景點(diǎn)到目的地的最短路徑中所途經(jīng)的各個(gè)景點(diǎn)及距離。本程序所能達(dá)到的功能就是前面所提到的中的功能。1.1.3數(shù)據(jù)測試當(dāng)選擇i時(shí)進(jìn)行的是查詢系統(tǒng)；當(dāng)選擇5號(hào)所代表的景點(diǎn)時(shí)所顯示的主要內(nèi)容為：當(dāng)選擇s時(shí)進(jìn)行的是最短路徑的查詢；當(dāng)選擇5和4所代表的景點(diǎn)時(shí)所顯示出的最短路徑為：1.2概要設(shè)計(jì)1.2.

5、1功能設(shè)計(jì)該校園導(dǎo)游問題我總共設(shè)計(jì)了八個(gè)旅游景點(diǎn)分別為校園北門、主樓、二教、三教、三食堂、體育館、石頭樓、大學(xué)生活動(dòng)中心，每個(gè)景點(diǎn)間之間相連的距離已知，通過計(jì)算來得出各個(gè)景點(diǎn)之間要到達(dá)所需要的最短距離，又或是在某條路徑上走過所經(jīng)過的所有景點(diǎn)。并且對(duì)各個(gè)景點(diǎn)有做了一些相關(guān)的介紹以便旅游觀光者能更好地選擇自己感性趣的景點(diǎn)進(jìn)行游賞。不論你目前在哪個(gè)景點(diǎn)哪道路上,都可以通過校園導(dǎo)游查詢到達(dá)你所想去的任何一個(gè)地方！為了方便把路徑分為三個(gè)部分，從進(jìn)入校園開始在，再以走出校園為止。而這部分的描述會(huì)在下面給出！具體景點(diǎn)示意圖如下：圖1-1校園主要景點(diǎn)示意圖1.學(xué)校北門3.三教5.三食堂2.體育館4.二教6.大

6、學(xué)生活動(dòng)中心7.石頭樓8.主樓 為了使廣大朋友更能清楚明析的了解本校的主要景點(diǎn)之間的連接，距離繪出了下面的表格，該表格主要是為了描述各個(gè)景點(diǎn)之間的最短距離： 表1-1校園各景點(diǎn)之間最短距離起點(diǎn)終點(diǎn)最短距離1.校園北門 2.體育館25 3.三教104.二教345.三食堂156.大學(xué)生活動(dòng)中心537.石頭樓478主樓552.體育館 3.三教354.二教495.三食堂406.大學(xué)生活動(dòng)中心487.石頭樓428主樓393.三教4.二教245.三食堂256.大學(xué)生活動(dòng)中心637.石頭樓578主樓654.二教5.三食堂496.大學(xué)生活動(dòng)中心507.石頭樓568主樓685.三食堂6.大學(xué)生活動(dòng)中心387.石

7、頭樓328主樓446.大學(xué)生活動(dòng)中心7.石頭樓68主樓187.石頭樓8主樓12在本題中我主要設(shè)置了三個(gè)路徑，都是以校園北門為首得到的，因此各個(gè)路徑上所經(jīng)過的景點(diǎn)如下表： 圖1-2途經(jīng)的景點(diǎn)路徑編號(hào)途經(jīng)的景點(diǎn)（1）校園北門三教二教大學(xué)生活動(dòng)中心石頭樓三食堂校園北門（2）校園北門體育館主樓石頭樓三食堂校園北門（3）校園北門三教二教大學(xué)生活動(dòng)中心石頭樓主樓體育館校園北門1.2.2抽象數(shù)據(jù)類型定義各景點(diǎn)的相關(guān)數(shù)據(jù)定義#define maxvertexnum 50 /*景點(diǎn)個(gè)數(shù)最大50*/#define maxcost 1200 /*定義路徑的無窮大*/#define t 8 /*目前景點(diǎn)個(gè)數(shù)*/typ

8、edef struct char name20; /*景點(diǎn)名稱*/ char number15; /*景點(diǎn)代號(hào)*/ char introduce100; /*景點(diǎn)簡介*/elemtype;typedef struct int num; /*頂點(diǎn)編號(hào)*/ elemtype date; /*頂點(diǎn)信息*/vertex; /*定義頂點(diǎn)*/typedef struct vertex vexsmaxvertexnum; /*存放頂點(diǎn)的一維數(shù)組,數(shù)組第零個(gè)單元沒有用上*/ unsigned int edgesmaxvertexnummaxvertexnum; /*存放路徑的長度*/ int n,e;mgra

9、ph;mgraph mgr; /*全局變量,定義mgr為mgraph類型*/int shortestmaxvertexnummaxvertexnum; /*定義全局變量存貯最小路徑*/int pathmaxvertexnummaxvertexnum; /*定義存貯路徑*/對(duì)于校園導(dǎo)游問題，在本程序中主要定義了幾個(gè)主要類型，有上述代碼可見其主要類型如下：（1）定義了景點(diǎn)個(gè)數(shù)最大值！本程序中假設(shè)為50。（2）定義路徑的無窮大！在本程序中假設(shè)為1200。（3）定義了目前景點(diǎn)個(gè)數(shù)！在本程序中主要設(shè)計(jì)了8個(gè)景點(diǎn)。（4）定義景點(diǎn)，主要是定義了各個(gè)景點(diǎn)的名稱代碼簡介等。（5）定義了各個(gè)代表景點(diǎn)頂點(diǎn)的編號(hào)信息

10、和頂點(diǎn)的定義。1.3系統(tǒng)的主要界面設(shè)計(jì)及運(yùn)行說明：1.3.1界面設(shè)計(jì) 這次的運(yùn)行是運(yùn)用了vissual c+進(jìn)行檢測的！因此當(dāng)進(jìn)入用戶界面時(shí)會(huì)顯示出查詢的方法，通過進(jìn)行選擇不同的字母進(jìn)行不同的選擇，當(dāng)選擇i時(shí)進(jìn)行的是信息查詢！當(dāng)通過選擇s時(shí)進(jìn)行的是最短路徑查詢！當(dāng)通過選擇兩個(gè)不同的（1到8）數(shù)字時(shí)進(jìn)行的是兩個(gè)景點(diǎn)之間的最短路徑查詢！通過選擇e退出查詢！在本次的運(yùn)行中，我的主要運(yùn)行過程在下面也會(huì)體現(xiàn)。該程序的主要運(yùn)行界面如下： 當(dāng)將程序輸入后點(diǎn)擊f5在沒有錯(cuò)誤的前提下就進(jìn)入查詢系統(tǒng)，如下就是進(jìn)入該系統(tǒng)的界面：主要顯示了各個(gè)選擇，你想要查找那個(gè)想知道的信息時(shí)，就可以根據(jù)不同的選擇達(dá)到你的要求！ 當(dāng)

11、選擇i時(shí)進(jìn)行信息查詢主要顯示如下： 當(dāng)選擇序號(hào)5所所代表的景點(diǎn)時(shí)所顯示的查詢結(jié)果如下： 當(dāng)選擇s時(shí)進(jìn)行的是最短路徑查詢 當(dāng)選擇5與4所代表的景點(diǎn)時(shí)所顯現(xiàn)出的最短路徑的查詢結(jié)果如下：1.3.2調(diào)試分析 整個(gè)程序的運(yùn)行還算良好！經(jīng)過幾次的調(diào)試運(yùn)行使得整體來看較成功不過有許多的知識(shí)還是需要我們自己去查找的！總之就是一句話“耐心加細(xì)心再加上靈活”就能很好地完成你所想做的事情！1.4總結(jié) 這次課程設(shè)計(jì)給我的感觸很多，課程設(shè)計(jì)沒開始之前我總是在想今年的課程設(shè)計(jì)會(huì)不會(huì)象去年那樣辛苦，但是這兩周下來我當(dāng)然也感到累，也有心情煩躁的時(shí)候，體會(huì)到調(diào)試成功使的那種喜悅。 課程設(shè)計(jì)之前老師讓我們自己先將設(shè)計(jì)思路寫好，都

12、做了哪些模塊，第一天要檢查。我當(dāng)時(shí)是在電腦上寫了，那天下午編了一下午，沒什么成就弄得我很心煩，再想到快要考試，那種急于求成的心更迫切，自己很難平靜。第二天老師檢查時(shí)我什麼都沒有看到同學(xué)的程序我開始著急了，但那會(huì)我只有一個(gè)念頭我得從新開始，由于對(duì)圖不是很了解，我就從讀寫模塊開始，就使用簡單的c語知識(shí)，那天早上將那兩個(gè)模塊給拿下了。下機(jī)后我在寢室開始編程，開始進(jìn)入真正的圖部分，邊思考怎樣可以將它們聯(lián)系起來，邊進(jìn)行調(diào)試。對(duì)編程興趣很濃，直到晚上十點(diǎn)我已經(jīng)將老師的要求完成差不多。 我又學(xué)到了很多東西,如程序的模塊化設(shè)計(jì)思想，同時(shí)也加深了對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學(xué)會(huì)了如何在實(shí)際中應(yīng)用數(shù)據(jù)結(jié)構(gòu)。這些日子

13、是很辛苦，但我學(xué)到了很多東西，和同學(xué)一起分享調(diào)試成功的那種喜悅，我完成的早，同學(xué)有問題會(huì)讓我?guī)椭?，在幫他們的過程中我也學(xué)會(huì)了很多種不同的思想，讓我對(duì)圖有了更深刻的理解。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且已成為其他理工專業(yè)的熱門選修課。從課程性質(zhì)上講，數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)技術(shù)基礎(chǔ)課。它的教學(xué)要求是：學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。另一方面，本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確意讀，符合軟件工程的規(guī)范。如

14、果說高級(jí)語言程序設(shè)計(jì)的訓(xùn)練過程，要進(jìn)行了結(jié)構(gòu)化的程序設(shè)計(jì)的初步訓(xùn)練的話，那么數(shù)據(jù)結(jié)構(gòu)就要培養(yǎng)我們的數(shù)據(jù)抽象能力。本次設(shè)計(jì)其實(shí)就是數(shù)據(jù)結(jié)構(gòu)中圖類的問題。將校園景點(diǎn)作為圖的結(jié)點(diǎn)，將景點(diǎn)間的路徑作為圖的邊，路徑距離作為邊的權(quán)值。這樣一來，求兩景點(diǎn)間最短路徑的問題就抽象成了求圖中一結(jié)點(diǎn)到另一結(jié)點(diǎn)的問題。這也是計(jì)算機(jī)代替人工的一個(gè)實(shí)例，也是軟件工程必不可少的基礎(chǔ)。第2章 約瑟夫問題2.1需求分析2.1.1課程設(shè)計(jì)的目的 有m個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回?cái)?shù)數(shù)的辦法來決定哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。如果前一個(gè)戰(zhàn)士沒完成任務(wù)，則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，隨便

15、從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計(jì)數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再從下一個(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。2.1.2程序的主要功能體現(xiàn) 系統(tǒng)結(jié)構(gòu)圖本程序有四個(gè)功能模塊，包括三個(gè)解決約瑟夫問題方案的模塊和一個(gè)退出系統(tǒng)模塊。三個(gè)解決方案分別采用了循環(huán)聊表儲(chǔ)存結(jié)構(gòu)、線性表儲(chǔ)存結(jié)構(gòu)、循環(huán)隊(duì)列儲(chǔ)存結(jié)構(gòu)。功能模塊如下圖所示。圖1-1 約瑟夫問題循環(huán)單鏈表儲(chǔ)存結(jié)構(gòu)線性表儲(chǔ)存結(jié)構(gòu)循環(huán)隊(duì)列儲(chǔ)存結(jié)構(gòu)退出2.1.3數(shù)據(jù)測試 當(dāng)選擇不同（1到4）的序號(hào)時(shí)進(jìn)行了不同的方法運(yùn)算，在此次運(yùn)行中分別選擇了不同的方法進(jìn)行了測試！假設(shè)士兵的

16、人數(shù)n=10時(shí)，死亡人數(shù)到5為止時(shí)運(yùn)行的結(jié)果的為：2.2概要設(shè)計(jì)2.2.1用循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)解決約瑟夫問題2.2.1.1 功能設(shè)計(jì)具體簡介如下：以單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)，包含三個(gè)模塊： 1.主程序模塊 包含敢死隊(duì)人數(shù)的輸入，死亡數(shù)字的輸入，函數(shù)的調(diào)用，結(jié)果的輸出。2.構(gòu)造鏈表并初始化構(gòu)造鏈表，給每個(gè)結(jié)點(diǎn)賦值，給隊(duì)員編號(hào)。3刪除當(dāng)報(bào)數(shù)到死亡數(shù)字時(shí)隊(duì)員出列去執(zhí)行任務(wù)，刪除該節(jié)點(diǎn)。2.2.1.2抽象數(shù)據(jù)類型定義創(chuàng)建循環(huán)鏈表 typedef struct node int data; struct node *next;lnode;/* 定義結(jié)點(diǎn)類型 */lnode* creat(int n) /* 創(chuàng)

17、建循環(huán)鏈表 */ lnode *s,*q,*t; int i; if(n!=0) t=q=(lnode *)malloc(sizeof(lnode); q-data=1;/* 生成第一個(gè)結(jié)點(diǎn)并使其data值為1 */ for(i=2;inext=s; q-next-data=i;/*賦值*/ q=q-next; q-next=t; return t;2.2.1.3 算法流程圖開始聲明類型定義變量并初始化初始化單鏈表循環(huán)模塊輸入敢死隊(duì)員總數(shù)剩下的隊(duì)員數(shù)1?隊(duì)員報(bào)數(shù)報(bào)數(shù)值=死亡數(shù)?隊(duì)員出列輸出結(jié)果2.2.2用線性表存儲(chǔ)結(jié)構(gòu)解決約瑟夫問題2.2.2.1功能設(shè)計(jì)具體簡介如下：功能設(shè)計(jì)本程序其實(shí)質(zhì)是約瑟

18、夫環(huán)問題,本次實(shí)驗(yàn)用了線性表數(shù)據(jù)結(jié)構(gòu),并運(yùn)用模塊化的程序設(shè)計(jì)思想,算法的實(shí)現(xiàn)是這樣的:定義類類型1. 定義變量并初始化2. 線性表初始化3. 當(dāng)隊(duì)員數(shù)小于等于1時(shí),輸出結(jié)果2.2.2.2抽象數(shù)據(jù)類型定創(chuàng)建線性表函數(shù)typedef struct klist /*定義數(shù)據(jù)結(jié)構(gòu)體類型*/elemtype *elem; /*存儲(chǔ)空間基址*/int length; /*當(dāng)前長度*/int listsize; /*當(dāng)前分配的存儲(chǔ)容量(以sizeof(elemtype)為單位)*/sqlist;int initlist_sq(sqlist &l) /*創(chuàng)建線性表函數(shù)*/l.elem=(elemtype *)

19、malloc(list_init_size * sizeof(elemtype); if(!l.elem)printf(存儲(chǔ)分配失敗);return error; elsel.length=0; /*空表長度為0*/l.listsize=list_init_size;return ok;/*初始存儲(chǔ)容量*/2.2.2.3 算法流程圖開始聲明數(shù)據(jù)類型定義變量并初始化初始化線性表輸入敢死隊(duì)員總數(shù)隊(duì)員人數(shù)線性表長度隊(duì)員報(bào)數(shù)報(bào)數(shù)值=5？隊(duì)員出列剩下的隊(duì)員數(shù)1?輸出增加存儲(chǔ)分配2.2.3用循環(huán)隊(duì)列儲(chǔ)存結(jié)構(gòu)解決約瑟夫問題2.2.3.1功能設(shè)計(jì)具體簡介如下：本程序其實(shí)質(zhì)是約瑟夫環(huán)問題,本次實(shí)驗(yàn)用了循環(huán)隊(duì)列數(shù)

20、據(jù)結(jié)構(gòu),并運(yùn)用模塊化的程序設(shè)計(jì)思想,算法的實(shí)現(xiàn)是這樣的:這個(gè)方法是用隊(duì)列循環(huán)來做的，實(shí)現(xiàn)的方法是這樣的：首先從第一號(hào)開始報(bào)數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點(diǎn)，直至剩下一個(gè)結(jié)點(diǎn)。然后再比較一下它的號(hào)碼是不是等于1，如果等于則輸出開始計(jì)數(shù)位置，如果不等，繼續(xù)循環(huán)查找，直到找出符合條件的計(jì)數(shù)起始位置，輸出結(jié)果。置，如果不等，繼續(xù)循環(huán)查找，直到找出符合條件的計(jì)數(shù)起始位置，輸出結(jié)果。2.2.3.2抽象數(shù)據(jù)類型定義創(chuàng)建循環(huán)隊(duì)列#define queuesize 1000 /假定預(yù)分配的隊(duì)列空間最多為1000個(gè)元素ypedef struct int dataqueuesize; int front;int r

21、ear; int count; /計(jì)數(shù)器，記錄隊(duì)中元素總數(shù)cirqueue;void initial(cirqueue *q) /將順序隊(duì)列置空q-front=q-rear=0; q-count=0; /計(jì)數(shù)器置 2.2.3.3 算法流程圖開始聲明數(shù)據(jù)類型定義變量并初始化初始化循環(huán)隊(duì)列輸入敢死隊(duì)員總數(shù)隊(duì)列滿？隊(duì)員報(bào)數(shù)報(bào)數(shù)值=5?隊(duì)員出列即清零剩下的隊(duì)員數(shù)1?輸出增加存儲(chǔ)分配編號(hào)=1？給隊(duì)員編號(hào)入隊(duì)列2.3系統(tǒng)的主要界面設(shè)計(jì)及運(yùn)行說明：本程序是運(yùn)用tc20進(jìn)行檢測運(yùn)行的當(dāng)點(diǎn)擊運(yùn)行時(shí)進(jìn)入了用戶主界面，該界面主要顯示了三種可以運(yùn)用進(jìn)行程序的方法，如果不需要運(yùn)行可以選擇4號(hào)退出該程序，選擇者可以通過不同的選擇實(shí)現(xiàn)自己的目的！實(shí)現(xiàn)結(jié)果的方法 當(dāng)選擇第1項(xiàng)功能時(shí)進(jìn)行的是運(yùn)用循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)解決約瑟夫問題，假設(shè)對(duì)員共有十個(gè)人，因此進(jìn)行的是10個(gè)隊(duì)員，死亡數(shù)字設(shè)