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

1、-PAGE . z. . . . 資料 . .*實(shí)踐教學(xué)* 理工大學(xué)軟件職業(yè)技術(shù)學(xué)院2021年春季學(xué)期算法與數(shù)據(jù)構(gòu)造課程設(shè)計題 目： 約瑟夫環(huán) 專業(yè)班級：姓 名：學(xué) 號：指導(dǎo)教師：成 績：摘要約瑟夫環(huán)問題是典型的線性表的應(yīng)用實(shí)例，其開發(fā)主要包括后臺數(shù)據(jù)庫的建立和維護(hù)以及前端應(yīng)用程序的開發(fā)兩個方面。對于前者要求建立起數(shù)據(jù)一致性和完整性強(qiáng)、數(shù)據(jù)平安性好的庫。而對于后者則要求應(yīng)用程序功能完備，易使用等特點(diǎn)。 經(jīng)過分析，我們使用 MICROSOFT公司的Microsoft Visual C+6.0開發(fā)工具，利用其提供的各種面向?qū)ο蟮拈_發(fā)工具，尤其是數(shù)據(jù)窗口這一能方便而簡潔操縱數(shù)據(jù)庫的智能化對象，首先在

2、短時間建立系統(tǒng)應(yīng)用原型，然后，對初始原型系統(tǒng)進(jìn)展需求迭代，不斷修正和改良，直到形成用戶滿意的可行系統(tǒng)。關(guān)鍵詞：單循環(huán)鏈表；c語言；約瑟夫環(huán)； 序言數(shù)據(jù)構(gòu)造是研究數(shù)據(jù)元素之間的邏輯關(guān)系的一門課程，以及數(shù)據(jù)元素及其關(guān)系在計算機(jī)中的存儲表示和對這些數(shù)據(jù)所施加的運(yùn)算。該課程設(shè)計的目的是通過課程設(shè)計的綜合訓(xùn)練，培養(yǎng)分析和編程等實(shí)際動手能力，系統(tǒng)掌握數(shù)據(jù)構(gòu)造這門課程的主要容。本次課程設(shè)計的容是用單循環(huán)鏈表模擬約瑟夫環(huán)問題，循環(huán)鏈表是一種首尾相接鏈表，其特點(diǎn)是無須增加存儲容量，僅對表的方式稍作改變，使表處理更加靈活，約瑟夫環(huán)問題就是用單循環(huán)鏈表處理的一個實(shí)際應(yīng)用。通過這個設(shè)計實(shí)例，了解單鏈表和單循環(huán)鏈表的一

3、樣與不同之處，進(jìn)一步加深對鏈表構(gòu)造類型及鏈表操作的理解。通過該課程設(shè)計，能運(yùn)用所學(xué)知識，能上機(jī)解決一些實(shí)際問題，了解并初步掌握設(shè)計、實(shí)現(xiàn)較大程序的完整過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)構(gòu)造的選擇、設(shè)計、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開發(fā)打好根底。目錄 TOC o 1-3 h z u HYPERLINK l _Toc298072296摘要 PAGEREF _Toc298072296 h 1HYPERLINK l _Toc298072297序言 PAGEREF _Toc298072297 h 2HYPERLINK l _Toc298072298目錄 PAGEREF

4、 _Toc298072298 h 3HYPERLINK l _Toc298072299正文 PAGEREF _Toc298072299 h 4HYPERLINK l _Toc298072300一、問題描述 PAGEREF _Toc298072300 h 4HYPERLINK l _Toc298072301二、邏輯設(shè)計 PAGEREF _Toc298072301 h 5HYPERLINK l _Toc298072302三、詳細(xì)設(shè)計 PAGEREF _Toc298072302 h 7HYPERLINK l _Toc298072303四、程序代碼 PAGEREF _Toc298072303 h 13

5、HYPERLINK l _Toc298072304五、程序調(diào)試與測試 PAGEREF _Toc298072304 h 13HYPERLINK l _Toc298072305設(shè)計總結(jié) PAGEREF _Toc298072305 h 18HYPERLINK l _Toc298072306參考文獻(xiàn) PAGEREF _Toc298072306 h 19HYPERLINK l _Toc298072307致 PAGEREF _Toc298072307 h 20HYPERLINK l _Toc298072308附錄 PAGEREF _Toc298072308 h 21正文一、問題描述約瑟夫環(huán)問題描述的是：設(shè)

6、編號為1，2，n的nn0個人按順時針方向圍坐一圈，每個人持有一正整數(shù)密碼。開場時選擇一個正整數(shù)作為報數(shù)上限m，從第一個人開場順時針方向自1起順序報數(shù)，報到m時停頓報數(shù)，報m的人出圈，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新從1報數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計一個程序模擬此過程，求出出圈的編號序列。如以下圖分析：1234567890這是第一個人，他的密碼是“1，個他輸一個m值，如果m=3,則從他開場向下走3個這就是第二步的位置，這時他的密碼作為新的m值，即m=4,同時得到的第一個密碼為4；4號出去向下走4，到9這兒；這這一步完了剩余的為：1,2

7、,3,5,6，7,8,9,0，這就是第三步的位置，這時他的密碼作為新的m值，即m=9，同時得到的第二個密碼為9；9號出去向下走9，到0這兒；繼續(xù)走就行了這兒剩余的就是：1，2，3，5，6,7,8,0圖1約瑟夫環(huán)問圖解3271484約瑟夫環(huán)原理演示圖1234567第二部：第一次停下的位置，此時6號出列，并將他的值作為新的m值，即：新的m=8；從7好開場繼續(xù)向下走8次，到1號的位置最后排序后的密碼序列：本圖只演示前兩步8第三步：第二次，1號出列第四步：第三次，4號出列3第一步：給第一個人賦初始密碼為：20則從它開場向下走20次，到6號位置241746147235圖2 約瑟夫環(huán)原理演示圖二、邏輯設(shè)計

8、1、循環(huán)鏈表抽象數(shù)據(jù)類型定義typedef struct LNode/定義單循環(huán)鏈表中節(jié)點(diǎn)的構(gòu)造 int num;/編號 int pwd;/passwordstruct LNode *ne*t;/指向下一結(jié)點(diǎn)的指針LNode;2、本程序包含一下幾個模塊1構(gòu)造結(jié)點(diǎn)模塊LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結(jié)點(diǎn) p-num=m_num;/把實(shí)參賦給相應(yīng)的數(shù)據(jù)域p-pwd=m_pwd;p-ne*t=NULL;/指針域為空return p; 2創(chuàng)立鏈表模塊void crea

9、teList(LNode *ppHead,int n)3出隊處理模塊void jose(LNode *ppHead,int m_pwd)4約瑟夫環(huán)說明輸出模塊void instruction()5菜單模塊void menu()6主函數(shù)模塊int main函數(shù)的調(diào)用關(guān)系圖如下：Case 2:建立的約瑟夫環(huán),并輸出已建立的約瑟夫環(huán)：createList(LNode *ppHead,int n)輸出該約瑟夫環(huán)的每個人的出列順序: jose(LNode *ppHead,int m_pwd)圖3 約瑟夫環(huán)函數(shù)調(diào)用關(guān)系圖菜單函數(shù)；void menu()主函數(shù)調(diào)用函數(shù)；main()Case 1：一個簡單的輸

10、出函數(shù)，用于說明約瑟夫環(huán)；void instruction()Case 0:default : 輸入0，退出 e*it(0)；三、詳細(xì)設(shè)計主函數(shù)Main()開場Menu()功能菜單功能1：約瑟夫環(huán)說明功能2：按要求求解約瑟夫環(huán)功能3：退出系統(tǒng)輸入總?cè)藬?shù)n輸入開場上線數(shù)：m輸入每個玩家的密碼調(diào)用：createList(&ppHead,n);jose(ppHead,m);函數(shù)求解所需的密碼序列選擇要執(zhí)行的操作程序運(yùn)行完，自動返回到功能菜單圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)流程圖，主函數(shù)程序如下：int main()int n,m,*;LNode *ppHead=NULL;menu();for(;) pri

11、ntf(n請選擇要執(zhí)行的操作：); scanf(%d,&*); system(cls); switch(*)case 1: printf(*n); printf(約瑟夫環(huán):n); printf( 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n); printf(碼(正整數(shù)).一開場任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開場n); printf(按順時針方向自1開場順序報數(shù),報到m時停頓.報m的人出列，將他的密碼n); printf(m作為新的m值,從他在順時針方向上的下一人開場重新從1報數(shù),如此下去,n); printf(直到所有人全部出列為止.編程打印出列順序.

12、n); printf(*n); main();break; case 2: printf(n請輸入總?cè)藬?shù)n：); scanf(%d,&n); printf(請輸入開場上限數(shù)m：); scanf(%d,&m); createList(&ppHead,n); printf(n);printf(出隊順序：n); jose(ppHead,m); printf(n約瑟夫環(huán)游戲完畢!n); main();break; case 0: e*it(0); default: system(cls); printf(n您選擇的操作有誤，請重新選擇.nnn);main(); return 0; 鏈表的創(chuàng)立否是cre

13、ateList;從主函數(shù)中獲取玩家信息n如果n0創(chuàng)立循環(huán)單鏈表，儲存各個玩家密碼退出創(chuàng)立鏈表完成返回主函數(shù)main()創(chuàng)立儲存玩家密碼的循環(huán)單鏈表的方法Main()函數(shù)圖5 創(chuàng)立鏈表函數(shù)的數(shù)據(jù)流程圖/*創(chuàng)立單向循環(huán)鏈表ppHead，人數(shù)個數(shù)為n，并輸入每個人的密碼值，假設(shè)建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，假設(shè)建立成功則插入結(jié)點(diǎn)P，cur指向的數(shù)據(jù)元素為p,后續(xù)為空的節(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/根據(jù)流程圖，創(chuàng)立鏈表函數(shù)程序如下：void createList(LNode *ppHead,int n)int i,m_pwd;LNode *p,*cur;/cur:浮標(biāo)指針for(i

14、=1;ine*t=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p-ne*t = cur-ne*t;cur-ne*t = p;cur= p;/cur指向新插入結(jié)點(diǎn) printf(完成創(chuàng)立！n); /提示鏈表創(chuàng)立完成 出隊處理Main()函數(shù)從循環(huán)鏈表中按初始密碼依次掃描，找出對應(yīng)的玩家序列輸出其持有的密碼i=ppHead-pwd; j=ppHead-num;移動浮標(biāo)指針m_pwd=ppHead-pwd;輸出密碼后，刪除相應(yīng)的結(jié)點(diǎn)，并釋放所占的儲存空間free(ppHead); ppHead=p-ne*t;執(zhí)行完后返回主函數(shù)jose()；出隊函數(shù)出隊處理的方法圖6

15、出隊函數(shù)的數(shù)據(jù)流程圖/*p指向要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)，ppHead指向要刪除的節(jié)點(diǎn)，使p=ppHead，ppHead再指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)，使p和ppHead，輸出p指向節(jié)點(diǎn)的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點(diǎn)都打印和刪除為止！*/根據(jù)流程圖，出隊函數(shù)程序如下：void jose(LNode *ppHead,int m_pwd)int i,j;LNode *p,*p_del;/定義指針變量for(i=1;p!=ppHead;i+)for(j=1;jne*t;/ppHead指向下一個元素p-ne*t = ppHead-ne*t;/p結(jié)點(diǎn)與頭結(jié)點(diǎn)i=ppHead-pwd

16、;/i賦值為ppHead-pwd j=ppHead-num;/j賦值為ppHead-num，j為要刪除的密碼值printf(第%d個人出列，密碼：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd賦值為ppHead-pwdfree(ppHead);/釋放頭結(jié)點(diǎn)ppHead=p-ne*t;/ppHead重新賦值給p-ne*t,即釋放前的ppHead-pwd指針/刪除報數(shù)結(jié)點(diǎn) i=ppHead-pwd;/i賦值為ppHead-pwdj=ppHead-num;/j賦值為ppHead-numprintf(最后一個出列是%d號，密碼是:%dn,j,i); free(ppHead);/釋放

17、頭結(jié)點(diǎn)4. 約瑟夫環(huán)說明模塊void instruction() printf(*n); printf(約瑟夫環(huán):n); printf( 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n); printf(碼(正整數(shù)).一開場任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開場n); printf(按順時針方向自1開場順序報數(shù),報到時停頓.報m的人出列，將他的密碼n); printf(m作為新的m值,從他在順時針方向上的下一人開場重新從1報數(shù),如此下去,n); printf(直到所有人全部出列為止.編程打印出列順序.n); printf(*n); return 0;5. 菜單

18、模塊void menu()printf(*約瑟夫環(huán) *n);printf( n);printf( 1約瑟夫環(huán)問題的闡述 n);printf( 2按要求求解約瑟夫環(huán) n);printf( 0退出 n);printf(* 歡送使用！ *n); 四、程序代碼見附錄源程序。五、程序調(diào)試與測試1. 調(diào)用模塊時，結(jié)點(diǎn)構(gòu)造的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩次錯誤，參加子函數(shù)的聲明后錯誤消失。2 . 剛開場時曾忽略了一些變量參數(shù)的標(biāo)識&和“*，使調(diào)試程序時費(fèi)時不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識。3. 本次課程設(shè)計采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序劃分為三個層次構(gòu)造：元素節(jié)點(diǎn)、單向循

19、環(huán)鏈表，主控制模塊。思路較為清晰，實(shí)現(xiàn)調(diào)用順利。 經(jīng)過本次實(shí)驗，使我對數(shù)據(jù)構(gòu)造這門課程有了進(jìn)一步的了解，每一個程序經(jīng)過需求分析、概要設(shè)計、詳細(xì)設(shè)計之后，思路即清晰呈現(xiàn)，程序也很快就出來了，最后經(jīng)過調(diào)試、運(yùn)行又有新的體驗。這是一個使用循環(huán)鏈表的經(jīng)典問題。本程序開場運(yùn)行界面如下：圖7 約瑟夫環(huán)開場運(yùn)行界面選擇1進(jìn)入約瑟夫環(huán)問題闡述。圖8 約瑟夫環(huán)問題闡述選擇2，輸入以下數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：7請輸入開場上限數(shù)m：20；請依次輸入每個人的密碼：3172484出隊順序：614723 5圖9 約瑟夫環(huán)測試1繼續(xù)選擇2，輸入以下數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：5請輸入開場上限數(shù)m：30請依次輸入每個人的密碼

20、：3 4 5 6 7 出隊順序：5 3 1 2 4圖10 約瑟夫環(huán)測試2繼續(xù)選擇2，輸入以下數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：8請輸入開場上限數(shù)m：14請依次輸入每個人的密碼：3 4 5 6 7 8 9 10出隊順序：6 7 2 8 3 5 1 4圖11 約瑟夫環(huán)測試3測試完成，選擇0退出。設(shè)計總結(jié)我的這次數(shù)據(jù)構(gòu)造課程設(shè)計的題目是:?約瑟夫環(huán)?,通過對該題目的設(shè)計,我加深了對數(shù)據(jù)構(gòu)造及存儲構(gòu)造的理解,進(jìn)一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)構(gòu)造，尤其是對單循環(huán)鏈表上根本運(yùn)算的實(shí)現(xiàn),學(xué)會了如何把學(xué)到的知識用于解決實(shí)際問題,鍛煉了自己動手的能力。通過這次數(shù)據(jù)構(gòu)造課程設(shè)計，我感受最深的就是對于循環(huán)鏈表的使用

21、，可以說對循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設(shè)計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結(jié)點(diǎn)，增加一個結(jié)點(diǎn)等。在調(diào)試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時候還是會出現(xiàn)很多錯誤，因此我們不能認(rèn)為容易就不認(rèn)真對待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從缺乏之處出發(fā)，在不斷學(xué)習(xí)中提高自己。兩周的課程設(shè)計很短暫，但其間的容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時書本中無法學(xué)到的東西，積累了經(jīng)歷，鍛煉了自己分析問題，解決問題的能力

22、，并學(xué)會了如何將所學(xué)的各課知識融會，組織起來進(jìn)展學(xué)習(xí)，總而言之這兩周中我學(xué)到很多，受益匪淺。參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民.?數(shù)據(jù)構(gòu)造C語言版?.清華大學(xué).2嚴(yán)蔚敏，吳偉民.?數(shù)據(jù)構(gòu)造題集C語言版?.清華大學(xué).3?DATA STRUCTURE WITH C+?. William Ford,William Topp .清華大學(xué)影印版.4譚浩強(qiáng).?c語言程序設(shè)計?. 清華大學(xué).致這次的課程設(shè)計，我們兩人一個小組去完成我們自己的課程，但是還是得到了來自很多方面的幫助。在此首先要感學(xué)院提供應(yīng)我這次實(shí)踐的時機(jī)，讓我們有時機(jī)貼近現(xiàn)實(shí)，感受成功的喜悅；其次要感實(shí)驗機(jī)房的教師提供優(yōu)良的實(shí)驗設(shè)備供我們做課設(shè)，正是這種

23、良好的課設(shè)環(huán)境讓我們整個課設(shè)過程心情都非常愉快。再次要感指導(dǎo)教師們的辛勤指導(dǎo)，每當(dāng)我們遇到疑難問題時，是他們一次次不厭其煩的解釋和悉心的指導(dǎo)，我們才能闖過一個個難關(guān)，到達(dá)勝利的此岸，是他們給我們提供了一次珍貴的檢驗自己時機(jī)。最后也要感同學(xué)們的幫助，有了他們的支持使我遇到任何困難都不是一個人在戰(zhàn)斗。感所有在我課程設(shè)計過程中幫助過我的人！附錄源代碼：*include /輸入輸出函數(shù)頭文件*include /字符串轉(zhuǎn)短整形函數(shù)的頭文件10140219/typedef struct LNode/定義單循環(huán)鏈表中節(jié)點(diǎn)的構(gòu)造 int num;/編號 int pwd;/passwordstruct LNod

24、e *ne*t;/指向下一結(jié)點(diǎn)的指針LNode;/*構(gòu)造結(jié)點(diǎn)*/LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結(jié)點(diǎn) p-num=m_num;/把實(shí)參賦給相應(yīng)的數(shù)據(jù)域p-pwd=m_pwd;p-ne*t=NULL;/指針域為空return p; /*創(chuàng)立循環(huán)鏈表*/void createList(LNode *ppHead,int n)/*創(chuàng)立單向循環(huán)鏈表ppHead，人數(shù)個數(shù)為n，并輸入每個人的密碼值，假設(shè) 建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，假設(shè)建立成功則插入結(jié)點(diǎn)P，c

25、ur指 向的數(shù)據(jù)元素為p,后續(xù)為空的節(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/int i,m_pwd;LNode *p,*cur;/cur:浮標(biāo)指針for(i=1;ine*t=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p-ne*t = cur-ne*t;cur-ne*t = p;cur= p;/cur指向新插入結(jié)點(diǎn) printf(完成創(chuàng)立！n); /提示鏈表創(chuàng)立完成 /*出隊處理*/void jose(LNode *ppHead,int m_pwd)/*p指向要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)，ppHead指向要刪除的節(jié)點(diǎn)，使p=ppHead，ppHead再指向要刪除節(jié)點(diǎn)

26、的下一個節(jié)點(diǎn)，使p和ppHead，輸出p指向節(jié)點(diǎn)的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點(diǎn)都打印和刪除為止！*/int i,j;LNode *p,*p_del;/定義指針變量for(i=1;p!=ppHead;i+)for(j=1;jne*t;/ppHead指向下一個元素p-ne*t = ppHead-ne*t;/p結(jié)點(diǎn)與頭結(jié)點(diǎn)i=ppHead-pwd;/i賦值為ppHead-pwd j=ppHead-num;/j賦值為ppHead-num，j為要刪除的密碼值printf(第%d個人出列，密碼：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd賦值為ppHead

27、-pwdfree(ppHead);/釋放頭結(jié)點(diǎn)ppHead=p-ne*t;/ppHead重新賦值給p-ne*t,即釋放前的ppHead-pwd指針/刪除報數(shù)結(jié)點(diǎn) i=ppHead-pwd;/i賦值為ppHead-pwdj=ppHead-num;/j賦值為ppHead-numprintf(最后一個出列是%d號，密碼是:%dn,j,i); free(ppHead);/釋放頭結(jié)點(diǎn)void instruction() printf(*n); printf(約瑟夫環(huán):n); printf( 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n); printf(碼(正整數(shù)).一開場任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開場n); printf(按順時針方向自1開場