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

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

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

3、進(jìn)一步加深對鏈表結(jié)構(gòu)類型及鏈表操作的理解。通過該課程設(shè)計，能運用所學(xué)知識，能上機(jī)解決一些實際問題，了解并初步掌握設(shè)計、實現(xiàn)較大程序的完整過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計、實現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開發(fā)打好基礎(chǔ)。目錄摘要1序言2目錄3正文4一、問題描述4二、邏輯設(shè)計5三、詳細(xì)設(shè)計7四、程序代碼13五、程序調(diào)試與測試13設(shè)計總結(jié)18參考文獻(xiàn)19致謝20附錄21正文一、問題描述約瑟夫環(huán)問題描述的是：設(shè)編號為1，2，n的n（n>0）個人按順時針方向圍坐一圈，每個人持有一正整數(shù)密碼。開始時選擇一個正整數(shù)作為報數(shù)上限m，從第一個人開始順時針方向

4、自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,3,5,6，7,8,9,0，）這就是第三步的位置，這時他的密碼作為新的m值，即m=9，同時得到的第二個密碼為9；9號出去向下走9，

5、到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è)計1、循環(huán)鏈表抽象數(shù)據(jù)類型定義typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結(jié)構(gòu) int num;/編號

6、int pwd;/passwordstruct LNode *next;/指向下一結(jié)點的指針LNode;2、本程序包含一下幾個模塊（1）構(gòu)造結(jié)點模塊LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結(jié)點 p->num=m_num;/把實參賦給相應(yīng)的數(shù)據(jù)域p->pwd=m_pwd;p->next=NULL;/指針域為空return p; （2）創(chuàng)建鏈表模塊void createList(LNode *ppHead,int n)（3）出隊處理模塊void jose

7、(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：一個簡單的輸出函數(shù)，用于說明約瑟夫環(huán)；void instruction()Case

8、 0:default : 輸入0，退出 exit(0)；三、詳細(xì)設(shè)計1. 主函數(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í)行的操作程序運行完，自動返回到功能菜單圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)流程圖，主函數(shù)程序如下：int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf("n請選擇要執(zhí)行的操作：&qu

9、ot;); scanf("%d",&x); system("cls"); switch(x)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")

10、; printf("m作為新的m值,從他在順時針方向上的下一人開始重新從1報數(shù),如此下去,n"); printf("直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); main();break; case 2: printf("n請輸入總?cè)藬?shù)n："); scanf("%d",&n); printf("請輸入開始上限數(shù)m："); scanf("%d",&m); createList(&ppHead,n);

11、printf("n");printf("出隊順序：n"); jose(ppHead,m); printf("n約瑟夫環(huán)游戲結(jié)束!n"); main();break; case 0: exit(0); default: system("cls"); printf("n您選擇的操作有誤，請重新選擇.nnn"); main(); return 0; 2. 鏈表的創(chuàng)建否是createList（）;從主函數(shù)中獲取玩家信息n如果n>0創(chuàng)建循環(huán)單鏈表，儲存各個玩家密碼退出創(chuàng)建鏈表完成返回主函數(shù)main(

12、)創(chuàng)建儲存玩家密碼的循環(huán)單鏈表的方法Main()函數(shù)圖5 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流程圖/*創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個數(shù)為n，并輸入每個人的密碼值，若建立失敗則生成頭結(jié)點，讓cur指向他，若建立成功則插入結(jié)點P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的節(jié)點，再把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=1;i<=n;i+)printf("輸入第%d個人的密碼：",i);

13、scanf("%d",&m_pwd);/輸入持有密碼 p=createNode(i,m_pwd);/調(diào)用構(gòu)造結(jié)點函數(shù)if(*ppHead=NULL)/如果頭結(jié)點為空 *ppHead=cur=p;/生成頭結(jié)點，讓cur指向他 cur->next=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點 p->next = cur->next;cur->next = p;cur= p;/cur指向新插入結(jié)點 printf("完成創(chuàng)建！n"); /提示鏈表創(chuàng)建完成 3. 出隊處理Main()函數(shù)從循環(huán)鏈表中按初

14、始密碼依次掃描，找出對應(yīng)的玩家序列輸出其持有的密碼i=ppHead->pwd; j=ppHead->num;移動浮標(biāo)指針m_pwd=ppHead->pwd;輸出密碼后，刪除相應(yīng)的結(jié)點，并釋放所占的儲存空間free(ppHead); ppHead=p->next;執(zhí)行完后返回主函數(shù)jose()；出隊函數(shù)出隊處理的方法圖6 出隊函數(shù)的數(shù)據(jù)流程圖/*p指向要刪除節(jié)點的前一個節(jié)點，ppHead指向要刪除的節(jié)點，使p=ppHead，ppHead再指向要刪除節(jié)點的下一個節(jié)點，使p和ppHead鏈接，輸出p指向節(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除

15、為止！*/根據(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;j<m_pwd;+j)p=ppHead;/p賦值為ppHead，p指向要刪除結(jié)點的前一個結(jié)點ppHead=ppHead->next;/ppHead指向下一個元素p->next = ppHead->next;/p結(jié)點與頭結(jié)點鏈接i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為pp

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

17、uot;,j,i); free(ppHead);/釋放頭結(jié)點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作為新

18、的m值,從他在順時針方向上的下一人開始重新從1報數(shù),如此下去,n"); printf("直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); return 0;5. 菜單模塊void menu()printf("*約瑟夫環(huán) *n");printf(" n");printf(" 1約瑟夫環(huán)問題的闡述 n");printf(" 2按要求求解約瑟夫環(huán) n");printf(" 0退出 n");printf("* 歡迎

19、使用！ *n"); 四、程序代碼見附錄源程序。五、程序調(diào)試與測試1. 調(diào)用模塊時，結(jié)點結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩次錯誤，加入子函數(shù)的聲明后錯誤消失。2 . 剛開始時曾忽略了一些變量參數(shù)的標(biāo)識"&"和“*”，使調(diào)試程序時費時不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識。3. 本次課程設(shè)計采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序劃分為三個層次結(jié)構(gòu)：元素節(jié)點、單向循環(huán)鏈表，主控制模塊。思路較為清晰，實現(xiàn)調(diào)用順利。 經(jīng)過本次實驗，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了進(jìn)一步的了解，每一個程序經(jīng)過需求分析、概要設(shè)計、詳細(xì)設(shè)計之后，思路即清晰呈現(xiàn)，程序也很

20、快就出來了，最后經(jīng)過調(diào)試、運行又有新的體驗。<測試用例>這是一個使用循環(huán)鏈表的經(jīng)典問題。本程序開始運行界面如下：圖7 約瑟夫環(huán)開始運行界面選擇1進(jìn)入約瑟夫環(huán)問題闡述。圖8 約瑟夫環(huán)問題闡述選擇2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：7請輸入開始上限數(shù)m：20；請依次輸入每個人的密碼：3 1 7 2 4 8 4出隊順序：6 1 4 7 2 3 5圖9 約瑟夫環(huán)測試1繼續(xù)選擇2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：5請輸入開始上限數(shù)m：30請依次輸入每個人的密碼：3 4 5 6 7 出隊順序：5 3 1 2 4圖10 約瑟夫環(huán)測試2繼續(xù)選擇2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：8請輸入開始

21、上限數(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ù)結(jié)構(gòu)課程設(shè)計的題目是:約瑟夫環(huán),通過對該題目的設(shè)計,我加深了對數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的理解,進(jìn)一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對單循環(huán)鏈表上基本運算的實現(xiàn),學(xué)會了如何把學(xué)到的知識用于解決實際問題,鍛煉了自己動手的能力。通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設(shè)計最大

22、的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結(jié)點，增加一個結(jié)點等。在調(diào)試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時候還是會出現(xiàn)很多錯誤，因此我們不能認(rèn)為容易就不認(rèn)真對待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。兩周的課程設(shè)計很短暫，但其間的內(nèi)容是很充實的，在其中我學(xué)習(xí)到了很多平時書本中無法學(xué)到的東西，積累了經(jīng)驗，鍛煉了自己分析問題，解決問題的能力，并學(xué)會了如何將所學(xué)的各課知識融會，組織起來進(jìn)行學(xué)習(xí)，總而言之這兩周中我學(xué)到很多，受益匪淺。參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C

23、語言版）.清華大學(xué)出版社.2嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學(xué)出版社.3DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學(xué)出版社（影印版）. 4譚浩強(qiáng).c語言程序設(shè)計. 清華大學(xué)出版社. 致謝這次的課程設(shè)計，我們兩人一個小組去完成我們自己的課程，但是還是得到了來自很多方面的幫助。在此首先要感謝學(xué)院提供給我這次實踐的機(jī)會，讓我們有機(jī)會貼近現(xiàn)實，感受成功的喜悅；其次要感謝實驗機(jī)房的老師提供優(yōu)良的實驗設(shè)備供我們做課設(shè)，正是這種良好的課設(shè)環(huán)境讓我們整個課設(shè)過程心情都非常愉快。再次要感謝指導(dǎo)老師們的辛勤指導(dǎo)，每當(dāng)我們遇到疑難問題

24、時，是他們一次次不厭其煩的解釋和悉心的指導(dǎo)，我們才能闖過一個個難關(guān)，到達(dá)勝利的彼岸，是他們給我們提供了一次寶貴的檢驗自己機(jī)會。最后也要感謝同學(xué)們的幫助，有了他們的支持使我遇到任何困難都不是一個人在戰(zhàn)斗。感謝所有在我課程設(shè)計過程中幫助過我的人！附錄 源代碼：#include <stdio.h>/輸入輸出函數(shù)頭文件#include <stdlib.h>/字符串轉(zhuǎn)短整形函數(shù)的頭文件10140219/typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結(jié)構(gòu) int num;/編號 int pwd;/passwordstruct LNode *next;/指向下一結(jié)點

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

26、的數(shù)據(jù)元素為p,后續(xù)為"空"的節(jié)點，再把P插入循環(huán)鏈表ppHead中*/int i,m_pwd;LNode *p,*cur;/cur:浮標(biāo)指針for(i=1;i<=n;i+)printf("輸入第%d個人的密碼：",i);scanf("%d",&m_pwd);/輸入持有密碼 p=createNode(i,m_pwd);/調(diào)用構(gòu)造結(jié)點函數(shù)if(*ppHead=NULL)/如果頭結(jié)點為空 *ppHead=cur=p;/生成頭結(jié)點，讓cur指向他 cur->next=*ppHead;/cur的指針域指向自身 else/如

27、果不為空，則插入結(jié)點 p->next = cur->next;cur->next = p;cur= p;/cur指向新插入結(jié)點 printf("完成創(chuàng)建！n"); /提示鏈表創(chuàng)建完成 /*出隊處理*/void jose(LNode *ppHead,int m_pwd)/*p指向要刪除節(jié)點的前一個節(jié)點，ppHead指向要刪除的節(jié)點，使p=ppHead，ppHead再指向要刪除節(jié)點的下一個節(jié)點，使p和ppHead鏈接，輸出p指向節(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/int i,j;LNode *p,*p_del;/

28、定義指針變量for(i=1;p!=ppHead;i+)for(j=1;j<m_pwd;+j)p=ppHead;/p賦值為ppHead，p指向要刪除結(jié)點的前一個結(jié)點ppHead=ppHead->next;/ppHead指向下一個元素p->next = ppHead->next;/p結(jié)點與頭結(jié)點鏈接i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為ppHead->num，j為要刪除的密碼值printf("第%d個人出列，密碼：%dn",j,i); m_pwd=ppHead->

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

30、("約瑟夫環(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;void menu()printf("*約瑟夫環(huán) *n");printf(" n");printf(" 1約瑟夫環(huán)問題的闡述 n");