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

1、*實踐教學(xué)*蘭州理工大學(xué)軟件職業(yè)技術(shù)學(xué)院2011 年春季學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目：專業(yè)班級：姓名：學(xué)號：指導(dǎo)教師：成績：約瑟夫環(huán)摘要約瑟夫環(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)；1序言數(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ǔ)。2目錄摘要1序言2目錄3正文4一、問題描述4二、邏輯設(shè)計5三、詳細(xì)設(shè)計7四、程序代碼13五、程序調(diào)試與測試13設(shè)計總結(jié)18參考文獻(xiàn)19致謝20附錄213正文一、問題描述約瑟夫環(huán)問題描述的是：設(shè)編號為1，2， n 的 n（n>0）個人按順時針方向圍坐一圈， 每個人持有一正整數(shù)密碼。 開始時選擇一個正整數(shù)作為報

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

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

6、圖二、邏輯設(shè)計1、循環(huán)鏈表抽象數(shù)據(jù)類型定義typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結(jié)構(gòu)int num;/編號int pwd;/passwordstruct LNode *next;/ 指向下一結(jié)點的指針LNode;2、本程序包含一下幾個模塊（ 1）構(gòu)造結(jié)點模塊LNode *createNode(int m_num,int m_pwd)5LNode *p;p=(LNode *)malloc(sizeof(LNode);/ 生成一個結(jié)點p->num=m_num;/把實參賦給相應(yīng)的數(shù)據(jù)域p->pwd=m_pwd;p->next=NULL;/ 指針域為空ret

7、urn p;（ 2）創(chuàng)建鏈表模塊void createList(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)系圖如下：6主函數(shù)調(diào)用函數(shù)；菜單函數(shù)；main()void menu()圖 3 約瑟夫環(huán)函數(shù)調(diào)用關(guān)系圖三、詳細(xì)設(shè)計1. 主函數(shù)Case 1：一個簡單的輸出函數(shù)，用于說明約瑟夫環(huán)；void instruction()Case 2:建立的約瑟夫環(huán) ,并輸出已建

8、立的約瑟夫環(huán)：createList(LNode *ppHead,int n)輸出該約瑟夫環(huán)的每個人的出列順序 :jose(LNode *ppHead,int m_pwd)Case 0:default : 輸入 0，退出 exit(0) ；7Main() 開始選擇要執(zhí)行的操作Menu() 功能菜單約瑟夫功能 2：按要求功能 3：退出系功能 1：環(huán)說明求解約瑟夫環(huán)統(tǒng)輸入總?cè)藬?shù)n輸入開始上線數(shù)：m輸入每個玩家的密碼調(diào)用： createList(&ppHead,n);jose(ppHead,m); 函 數(shù) 求 解 所 需的密碼序列圖 4 主函數(shù)數(shù)據(jù)流程圖根據(jù)流程圖，主函數(shù)程序如下：intmai

9、n()int n,m,x;LNode *ppHead=NULL;menu();for(;)printf("n 請選擇要執(zhí)行的操作：");scanf("%d",&x);system("cls");switch(x)case 1:printf("* *n");程序運行完，自動返回到功能菜單8printf(" 約瑟夫環(huán) :n");printf("編號為 1,2,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個密n");printf(" 碼(正整數(shù) ).一

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

11、d",&n);printf(" 請輸入開始上限數(shù)m：");scanf("%d",&m);createList(&ppHead,n);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&qu

12、ot;); main();return 0;2. 鏈表的創(chuàng)建9Main() 函數(shù)createList（） ;創(chuàng)建儲存玩家密碼的循環(huán)單鏈表的方法從主函數(shù)中獲取玩家信息 n如果 n>0否是退出創(chuàng)建循環(huán)單鏈表，儲存各個玩家密碼創(chuàng)建鏈表完成返回主函數(shù) main()圖 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ù)程序如下：voi

13、d createList(LNode *ppHead,int n)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 指向他10cur->next=*ppHead;/cur 的指針域指向自身else/如果不為空，則

14、插入結(jié)點p->next = cur->next;cur->next = p;cur= p;/cur 指向新插入結(jié)點printf(" 完成創(chuàng)建！ n"); / 提示鏈表創(chuàng)建完成3. 出隊處理Main() 函數(shù)jose()；出隊函數(shù)從循環(huán)鏈表中按初始密碼依次掃描，找出對應(yīng)的玩家序列輸出其持有的密碼i=ppHead->pwd;j=ppHead->num;移動浮標(biāo)指針m_pwd=ppHead->pwd;輸出密碼后， 刪除相應(yīng)的結(jié)點，并釋放所占的儲存空間free(ppHead); ppHead=p->next;圖 6 出隊函數(shù)的數(shù)據(jù)流程圖出隊

15、處理的方法執(zhí)行完后返回主函數(shù)/*p 指向要刪除節(jié)點的前一個節(jié)點，ppHead 指向要刪除的節(jié)點，使p=ppHead，11ppHead 再指向要刪除節(jié)點的下一個節(jié)點，使 p 和 ppHead 鏈接，輸出 p 指向節(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/根據(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 指向要刪

16、除結(jié)點的前一個結(jié)點ppHead=ppHead->next;/ppHead指向下一個元素p->next = ppHead->next;/p 結(jié)點與頭結(jié)點鏈接i=ppHead->pwd;/i 賦值為 ppHead->pwdj=ppHead->num;/j 賦值為 ppHead->num， j 為要刪除的密碼值printf(" 第%d 個人出列，密碼： %dn",j,i);m_pwd=ppHead->pwd;/m_pwd 賦值為 ppHead->pwdfree(ppHead);/釋放頭結(jié)點ppHead=p->next;/

17、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é)點4. 約瑟夫環(huán)說明模塊void instruction()printf("* *n");printf(" 約瑟夫環(huán) :n");printf("編號為 1,2

18、,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個密 n");printf(" 碼(正整數(shù) ).一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始 n");printf(" 按順時針方向自 1 開始順序報數(shù) ,報到時停止 .報 m 的人出列， 將他的密碼 n");printf("m 作為新的m 值,從他在順時針方向上的下一人開始重新從1 報數(shù) ,如此下去 ,n");12printf(" 直到所有人全部出列為止.編程打印出列順序 .n");printf("*n");retu

19、rn 0;5. 菜單模塊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é)點結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩次錯誤，加入子函數(shù)的聲明后錯誤消失。2 . 剛開始時曾忽略了一些變量參數(shù)的標(biāo)識"&&q

20、uot; 和“ * ”，使調(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)，程序也很快就出來了，最后經(jīng)過調(diào)試、運行又有新的體驗。13<測試用例 >這是一個使用循環(huán)鏈表的經(jīng)典問題。本程序開始運行界面如下：圖 7約瑟夫環(huán)開始運行界面選擇 1 進(jìn)入約瑟夫環(huán)問題闡述。圖 8 約瑟夫環(huán)問題闡述14選擇 2，輸入下列

21、數(shù)據(jù)測試：請輸入總?cè)藬?shù) n：7請輸入開始上限數(shù)m：20；請依次輸入每個人的密碼：3 1 7 2 4 8 4出隊順序：6147235圖 9約瑟夫環(huán)測試1繼續(xù)選擇 2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù) n：5請輸入開始上限數(shù)m：30請依次輸入每個人的密碼：3 4 5 6 7出隊順序：5312415圖 10約瑟夫環(huán)測試2繼續(xù)選擇 2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù) n：8請輸入開始上限數(shù)m：14請依次輸入每個人的密碼：3 4 5 6 7 8 9 10出隊順序：6728351416圖 11約瑟夫環(huán)測試3測試完成，選擇0 退出。17設(shè)計總結(jié)我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的題目是 :約瑟夫環(huán) ,通過對該題目的設(shè)計

22、 , 我加深了對數(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è)計最大的收獲就在于對循環(huán)鏈表有了一定的理解， 包括其中的一系列操作， 如建立一個循環(huán)鏈表， 刪除鏈表中的一個結(jié)點，增加一個結(jié)點等。在調(diào)試程序的時候我也有所體會， 雖然約瑟夫環(huán)問題不是很難， 但調(diào)試的時候還是會出現(xiàn)

23、很多錯誤， 因此我們不能認(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é)到很多，受益匪淺。18參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu)（ C 語言版）.清華大學(xué)出版社 .2嚴(yán)蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu)題集（ C 語言版）.清華大學(xué)出版社 .3 DATA STRUCTURE WITH C+ . William F

24、ord,William Topp . 清華大學(xué)出版社（影印版） .4譚浩強(qiáng) .c 語言程序設(shè)計 . 清華大學(xué)出版社 .19致謝這次的課程設(shè)計， 我們兩人一個小組去完成我們自己的課程， 但是還是得到了來自很多方面的幫助。 在此首先要感謝學(xué)院提供給我這次實踐的機(jī)會， 讓我們有機(jī)會貼近現(xiàn)實， 感受成功的喜悅； 其次要感謝實驗機(jī)房的老師提供優(yōu)良的實驗設(shè)備供我們做課設(shè)， 正是這種良好的課設(shè)環(huán)境讓我們整個課設(shè)過程心情都非常愉快。再次要感謝指導(dǎo)老師們的辛勤指導(dǎo)， 每當(dāng)我們遇到疑難問題時， 是他們一次次不厭其煩的解釋和悉心的指導(dǎo)，我們才能闖過一個個難關(guān)，到達(dá)勝利的彼岸，是他們給我們提供了一次寶貴的檢驗自己機(jī)會

25、。 最后也要感謝同學(xué)們的幫助， 有了他們的支持使我遇到任何困難都不是一個人在戰(zhàn)斗。 感謝所有在我課程設(shè)計過程中幫助過我的人！20附錄源代碼：#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é)點的指針LNode;/* 構(gòu)造結(jié)點 */LNode *createNode(int m_num,int m_pwd)L

26、Node *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 指向的數(shù)據(jù)元素為 p,后續(xù)為 "空"的節(jié)點，再把 P 插入循環(huán)鏈表 ppHead

27、 中*/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/如果不為空，則插入結(jié)點21p->next = cur->next

28、;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;/ 定義指針變量for(i=1;p

29、!=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->pwdj=ppHead->num;/j 賦值為 ppHead->num， j 為要刪除的密碼值printf(" 第%d 個人出列，密碼： %dn",j,i);m_pwd=ppHead->pwd;

30、/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");

31、printf(" 約瑟夫環(huán) :n");printf("編號為 1,2,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個密 n");printf(" 碼(正整數(shù) ).一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始 n");22printf(" 按順時針方向自 1 開始順序報數(shù) ,報到時停止 .報 m 的人出列， 將他的密碼 n");printf("m 作為新的 m 值,從他在順時針方向上的下一人開始重新從 1 報數(shù) , 如此下去 ,n");printf(" 直到所有人全部出列為止 .編程打印出列順序 .n"); printf("*n"); return 0;void menu()printf("*約瑟夫環(huán)*n");printf("n");pri