數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)約瑟夫環(huán)

1、課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：約瑟夫環(huán)約瑟夫環(huán)院（系）：專 業(yè)：班 級：學(xué) 號：姓 名：指導(dǎo)教師： i 目目 錄錄1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.11.1 課程設(shè)計(jì)內(nèi)容.11.2 課程設(shè)計(jì)要求.12 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.22.1 課設(shè)題目粗略分析.22.2 原理圖介紹.22.2.1 功能模塊圖.22.2.2 流程圖分析.33 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.73.1 存儲(chǔ)結(jié)構(gòu).73.2 算法描述.74 4 調(diào)試與分析調(diào)試與分析.84.1 調(diào)試過程.84.2 程序執(zhí)行過程.9參考文獻(xiàn)參考文獻(xiàn).12附附 錄（關(guān)鍵部分程序清單）錄

2、（關(guān)鍵部分程序清單）.13 1 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容 編號為 1,2n 的 n 個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)） 。一開始人選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值 m，從第一個(gè)人開始順時(shí)針方向自 1 開始順序報(bào)數(shù)，報(bào)道 m 時(shí)停止報(bào)數(shù)，報(bào) m 的人出列，將他的密碼作為新的 m 值，從他的順時(shí)針向上的下一個(gè)開始重新從 1 報(bào)數(shù)，如此下去，直至所有人全部出列為止，設(shè)計(jì)一個(gè)程序求出出列順序。使用單循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)。1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求1.參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。2.交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。 2 2

3、2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為 2 大模塊。此 2 個(gè)模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，以下是 2 個(gè)模塊的大體分析：1.建立初始化單循環(huán)鏈表，將每個(gè)結(jié)點(diǎn)的座位號及密碼給定；2 建立伴隨指針，將循環(huán)進(jìn)行一邊，使跟隨指針指向頭結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)。然后進(jìn)行遍歷，循環(huán) m-1 次時(shí)輸出此時(shí)所指向的結(jié)點(diǎn)的座位號，將此結(jié)點(diǎn)的密碼作為新的 m 值，刪除這個(gè)結(jié)點(diǎn)，循環(huán)至剩下最后一個(gè)結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的座位號。2.22.2 原理圖介紹原理圖介紹2.2.12.2.1 功能模塊圖功能模塊圖mian()yue_list( )init_list(

4、 )圖 2.1 功能模塊圖 3 2.2.22.2.2 流程圖分析流程圖分析1. 如圖 2.1 通過主函數(shù)進(jìn)行座位號 n 和初始值 m 的輸入，調(diào)用建立單煦暖鏈表函數(shù) init_list 和約瑟夫環(huán)出列函數(shù) yue_list。圖 2.2 主函數(shù) main( )流程圖 4 2. 如圖 2.2，建立單循環(huán)鏈表，并且將鏈表的座位號賦值給 q-info，輸入每個(gè)座位號的密碼給 q-code；圖 2.3 建立單循環(huán)鏈表流程圖 5 3.如圖 2.3 進(jìn)行約瑟夫環(huán)出列算法，按先后順序輸出座位號。 6 圖 2.4 進(jìn)行約瑟夫環(huán)出列算法 yue_list( )流程圖 7 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析3.1 存儲(chǔ)結(jié)

5、構(gòu)存儲(chǔ)結(jié)構(gòu)typedef struct nodeint info; /節(jié)點(diǎn)的座位數(shù)int code; /節(jié)點(diǎn)的密碼struct node *next;*pnode, *linklist;3.2 算法描述算法描述1. 建立 n 個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，簡單算法說明如下：定義*p，*q 兩個(gè)結(jié)點(diǎn)指針，使頭結(jié)點(diǎn)的*next 指針指向自己，先給第一個(gè)結(jié)點(diǎn)的密碼 code，及座位號 info 賦值；從第二個(gè)結(jié)點(diǎn)開始用 for 循環(huán)進(jìn)行建立鏈表并給鏈表中結(jié)點(diǎn)的 code 和 info賦值。2. 進(jìn)行約瑟夫環(huán)算法的循環(huán)，將出列的人按順序輸出，簡單算法說明如下：定義兩個(gè)指針，一個(gè)為 p 一個(gè)為 p 的前一個(gè)指針

6、pre；先進(jìn)行一次遍歷，使 pre 的指針指向頭結(jié)點(diǎn)的前一個(gè)位置；進(jìn)行循環(huán)遍歷，用 while (p!=p-next) 判斷結(jié)點(diǎn)數(shù)是否大于 1,若大于 1，用 for 循環(huán)找到第 m 個(gè)結(jié)點(diǎn)，并輸出這個(gè)結(jié)點(diǎn)的座位號，將結(jié)點(diǎn)的座位密碼賦給m 值，并且刪除這個(gè)結(jié)點(diǎn)；如果要?jiǎng)h除的結(jié)點(diǎn)是頭結(jié)點(diǎn)，需要將頭結(jié)點(diǎn)移動(dòng)到下一個(gè)位置。重新進(jìn)行for 循環(huán)，直到剩下最后一個(gè)結(jié)點(diǎn)；跳出循環(huán)，輸出最后一個(gè)結(jié)點(diǎn)的座位號，并釋放。 8 4 4 調(diào)試與分析調(diào)試與分析4.14.1 調(diào)試過程調(diào)試過程在調(diào)試程序是主要遇到一下幾類問題：問題 1：問題描述：當(dāng)輸入 m 值等于 1 的時(shí)候總是從第二個(gè)作為開始輸出。問題分析：由于程序遍

7、歷的結(jié)點(diǎn)先進(jìn)行了一步，才開始遍歷。解決方法：建立伴隨指針的時(shí)候先將程序遍歷一遍，使初始化伴隨指針指向頭結(jié)點(diǎn)的上個(gè)位置。問題 2：問題描述： 先輸出第一個(gè)結(jié)點(diǎn)后總是無法正確輸出。問題分析： 沒有判斷輸出的是否是頭結(jié)點(diǎn)。解決方法： 判斷輸出的是否是頭結(jié)點(diǎn)，如果是把頭結(jié)點(diǎn)向后移動(dòng)。問題 3：問題描述：輸入 n,m 的時(shí)候如果輸入的不是正整數(shù)，程序無法正常運(yùn)行。問題分析：沒有判斷 n，m 是否是正整數(shù)。解決方法：用 do while 循環(huán)語句，如果不是正整數(shù)需要重新輸入。 9 4.24.2 程序執(zhí)行過程程序執(zhí)行過程（1）第一次的具體的測試結(jié)果如圖 4.1 所示。圖 4.1 第一次測試結(jié)果（2）第二次的

8、具體的測試結(jié)果如圖 4.2 所示。圖 4.2 第二次測試結(jié)果 10 （3）第三次的具體的測試結(jié)果如圖 4.3 所示。圖 4.3 第三次測試結(jié)果（4）第四次的具體的測試結(jié)果如圖 4.4 所示。圖 4.4 第四次測試結(jié)果 11 （5）第五次的具體的測試結(jié)果如圖 4.5 所示。圖 4.5 第五次測試結(jié)果系統(tǒng)使用說明：1. 輸入的數(shù)據(jù)座位數(shù) n，初始值 m，密碼必須是正整數(shù)； 2. 輸入結(jié)束后自動(dòng)輸出結(jié)果，按任意鍵退出。 12 參考文獻(xiàn)參考文獻(xiàn)1.數(shù)據(jù)結(jié)構(gòu) （用面向?qū)ο蟮姆椒ㄅc c+描述） ，殷人昆等，清華大學(xué)出版社，2009。2.算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo) ，寧正元等，清華大學(xué)出版社，2007

9、。3. 譚浩強(qiáng). .c 程序設(shè)計(jì)m.北京：清華大學(xué)出版社，2005。 13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）程序代碼程序代碼#include #include #include #define error 0#define ok 1typedef struct nodeint info; /節(jié)點(diǎn)的座位數(shù)int code; /節(jié)點(diǎn)的密碼struct node *next;*pnode, *linklist;typedef linklist *plinklist;int init_list(plinklist plist, int n)/建立循環(huán)鏈表，從 1 到 n 輸入節(jié)點(diǎn)的密

10、碼。 struct node *p,*q; int i; q=(pnode)malloc(sizeof(struct node); if (q=null) return error; 14 *plist=q; q-info=1; q-next=q; printf(請輸入第 1 個(gè)座位的密碼:); scanf(%d,&q-code); if(q-code=0) return error; if (n=1) return ok; for(i=2;icodenext=q-next; q-next=p; q=p; scanf(%d,&q-code); q-info=i; 15 return ok;vo

11、id yue_list( plinklist plist,int m) /約瑟夫算法pnode p,pre; int i; p=*plist; pre =p; p=p-next; while (p!=*plist) pre =p; p=p-next; while (p!=p-next) /當(dāng)鏈表中結(jié)點(diǎn)個(gè)數(shù)大于 1 時(shí) for(i=1;inext; 16 printf(輸出: %dn,p-info); m=p-code; if (*plist=p) /該結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)時(shí)，首節(jié)點(diǎn)應(yīng)移向下一個(gè) *plist=p-next; pre-next=p-next; /刪除該結(jié)點(diǎn) free(p); p=pr

12、e-next; /循環(huán)結(jié)束，剩下最后一個(gè)節(jié)點(diǎn)printf(輸出: %d n,p-info);*plist=null;free(p);main( )linklist y_list;int n,m;/ 輸入所需各參數(shù)的值 do 17 printf(n 輸入總座位數(shù) n(n0，否則重新輸入):); scanf(%d,&n); while (n0，否則重新輸入):); scanf(%d,&m); while (m1);if (init_list(&y_list,n) yue_list(&y_list,m);else printf(輸入有錯(cuò)誤!n); 18 課程設(shè)計(jì)總結(jié)：課程設(shè)計(jì)總結(jié)：本次課程設(shè)計(jì)涉及到的范圍很廣，讓本人能夠比較系統(tǒng)的對 c 語言和數(shù)據(jù)結(jié)構(gòu)進(jìn)行一次整理和復(fù)習(xí)。同時(shí)有了很多的體會(huì)和經(jīng)驗(yàn)。1. 鞏固了以前學(xué)過的 c 語言的知識，在這次課程設(shè)計(jì)中我體會(huì)到 c 語言超強(qiáng)的邏輯性，能夠熟練使用 vc+的編譯環(huán)境，也對這兩門課程有了新的認(rèn)識，他們既有聯(lián)系，又相互區(qū)別，在編寫程序過程中要靈活應(yīng)用。2. 對數(shù)據(jù)結(jié)構(gòu)的理解有待加強(qiáng)，算法的知識面也有待于提高。不同的人會(huì)選擇不同的算法，所以即使同樣的程序，不同的人必然會(huì)設(shè)計(jì)出不同的方案，所以以后的學(xué)習(xí)生活中，一定要廣泛涉獵，掌握更多更好的解決問題的方法。3. 此次設(shè)計(jì)讓