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

1、課程設(shè) 計報告學院' 系：專 業(yè)：班 級：約瑟夫環(huán)2010年10月t2月課程設(shè)計科目學生姓名： 指導教師： 完成時間：約瑟夫環(huán)一、設(shè)計任務(wù)與目標編號為1, 2n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正 整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始按順吋針 方向自1開始順序報數(shù)，報到0）時停止報數(shù)，報m的人出列，將他的密碼作為新 的ni值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有 人全部出列為止。該題目要求用單循環(huán)鏈表作為存儲結(jié)構(gòu)，進行一個帶密碼的約瑟夫環(huán)的運算 問題。而且從鍵盤輸入總?cè)藬?shù)、初始報數(shù)上限值h1及各人密碼，然后輸出出列的 人

2、員的編號順序。二、方案設(shè)計與論證關(guān)于這次題目的設(shè)計，根據(jù)題目的要求，主要用了一個單循環(huán)鏈表作為存儲 結(jié)構(gòu)。首先是進行一系列的定義結(jié)點，其中就有包括每個人的密碼和編號。然后 有空鏈表的創(chuàng)建和循環(huán)鏈表的初始化。在這里，我們將輸入毎個人密碼的步驟放 在循環(huán)鏈表的初始化里，在初始化鏈表時從鍵盤輸入密碼和直接給每個人進行編 號，而不是在主函數(shù)屮進行。然后在主函數(shù)里面主要就是實現(xiàn)約瑟夫環(huán)的運行，從第一個開始，找到對應(yīng) 上限值的的人，然后輸出編號，將頭指針指向下一個結(jié)點，將該編號人員的密碼 賦值為新上限值，然后清空該結(jié)點的數(shù)據(jù)，一直這樣的運行，直到所有結(jié)點都被 清空，就完成了約瑟夫環(huán)的運行。在設(shè)計的前期，本

3、是設(shè)計將密碼輸入的這一部分放在主函數(shù)z中去執(zhí)行，而 建立單循環(huán)鏈表是單獨的一個函數(shù)，但是無法實現(xiàn)將數(shù)據(jù)從主函數(shù)鍵入切能被準 確使用，于是后改成在初始化鏈表的時候鍵入密碼，從而達到目標。三、算法說明按照題目的要求，要采用單循環(huán)鏈表來作為存儲結(jié)構(gòu)，然后在循環(huán)鏈表的基礎(chǔ)上去實現(xiàn)約瑟夫環(huán)的運行。在主函數(shù)之前，先是定義結(jié)點，創(chuàng)建新的空鏈表，和初始化鏈表。在初始化 循環(huán)鏈表的時候，初始化了每個結(jié)點的編號，然后從鍵盤輸入了相對應(yīng)的密碼， 從而完成初始化。而約瑟夫環(huán)的主要實現(xiàn)的算法就是在主函數(shù)里面。在主函數(shù)里，定義完各項之后，我先用一個wh訂e的循環(huán)語句來實現(xiàn)能夠反 復進行運算。關(guān)于約瑟夫環(huán)的運算，先創(chuàng)建一個

4、只有頭結(jié)點的空鏈表，然后輸入 總?cè)藬?shù)n,和初始的上限值m,用總?cè)藬?shù)n去初始化循環(huán)鏈表，然后在循環(huán)鏈表 里面從鍵盤輸入對應(yīng)的密碼值。先是設(shè)立for循環(huán)，確保將所有數(shù)據(jù)都進行運算，然后從第一個結(jié)點開始， 一直向下找，直到找到對應(yīng)上限值m的結(jié)點，然后用一個第三方指針p指向該結(jié) 點，將該結(jié)點的密碼值(password)賦予初始的上限值然后輸出該結(jié)點的編 號值(num),接著指針q指向下一個結(jié)點成為頭結(jié)點，最后清空指針p指向的該 對應(yīng)結(jié)點。如此循環(huán)，一直到所有的結(jié)點都被清空，則已經(jīng)實現(xiàn)了約瑟夫環(huán)的運 算。四、全部源程序清單源代碼：#include<stdio.h>#include<st

5、dlib.h> typedef struct node每個人持有的密碼/人員的編號指向下一個節(jié)點int password;int num;struct node *next;node, *link;/創(chuàng)建一個空的鏈表voi d tni tli st (link &l)l=(node *)malloc(sizcof(node);if (!l) exit (1);l->password=0;l->num=0;l->next=l;/初始化鏈表，初始化人員編號和輸入每個人的密碼void creater(int n,link &l)link p, q;q二 l;f

6、or(int i二l;i<=n;i+)!p=(node *)malloc(sizeof(node);if (!p) exit(1);printf (/z請輸入第%d個人的密碼:",i);seanf("%d", &p->password);p->num=i;l->next=p;l=p;i 廠 >next二q->next;free(q);主函數(shù)，執(zhí)行約瑟夫環(huán)的運行void mainolink l, p, q;int n, m;int a=l;int b=l;/創(chuàng)建一個循環(huán)語句，用于在實現(xiàn)約瑟夫環(huán)運算結(jié)束后是否繼續(xù)執(zhí)行whi1

7、e(b二二1)l二null;tnitlist（l） ;/構(gòu)造出一個只有頭結(jié)點的空鏈表printf （z/請輸入總?cè)藬?shù)n: rt）;scanf （"%d",&n） ;/輸入總共的人數(shù)nwhile （n<=l）判斷輸入數(shù)值是否有誤printfc輸入的總?cè)藬?shù)有誤，請重新輸入大于1的總?cè)藬?shù)：）； scanf （"%d，&n）;printfc請輸入初始的上限值m （正整數(shù)）：n ）；/輸入初始的上限值mprintf （，z輸入上限值有誤，請重新輸入：n）;scanf (“d，&m);creater (n, l);printfc最終出列的順序為:

8、輸入每個人的密碼，構(gòu)成一個約瑟夫環(huán)n"） ; /建立一個循環(huán)列表，賦予初始編號和p二 l;for(int i=l;i=n;i+)/關(guān)于約瑟夫環(huán)的主要實現(xiàn)for(int j=l；j<m；j+)/找到密碼對應(yīng)的節(jié)點p二p->next;q二p->next;m=q->password;/重新賦值給上限值p->next=q->next;/讓下一個節(jié)點成為頭結(jié)點free(q);printfc是否繼續(xù)重新輸入運算（1 繼續(xù)0退出）：n ）;scanf&b);printfcnnn/z);五、程序運行的測試與分析 基本界面，關(guān)于各項值和密碼的輸入。 然后得到

9、正確的結(jié)果。同時進行詢問判斷，是否繼續(xù)。c d: 04080930楊記祥約瑟夫環(huán)ysfhdebugysfh. exe慎輸入總?cè)藬?shù)n：請輸入初始的上限值m履龔缶列的順序為:31254雇否繼續(xù)重新輸入運算1個人的密碼2個人的密碼3個人的密碼4個人的密碼5個人的密碼正整數(shù):1:2:3:4:5<1繼續(xù)0退岀:zj如果選擇繼續(xù)，則可以重復輸入各項繼續(xù)進行運算。cf d: 04080930$記祥約瑟夫環(huán)ysfhdebugysfh. exen數(shù) 人 總 入 輸 請p 環(huán) x x x x x x x x x xxxxx 興<正整數(shù)“n 親 1 2 3 4 5的5重列2續(xù) 入入入入入岀繼 in-1

10、否 3請請請請0>車3是1碼碼碼碼碼 密密密密密: 人人人人人那 個個個個個弟41234cl繼續(xù)0退出:碼碼碼 密密密 人人人 個個個 12 3 1ajaja 4請請請正整數(shù):5:2如果不選擇繼續(xù)，則輸入0后退出。如果一開始輸入的數(shù)據(jù)有錯，則會提示輸入的數(shù)據(jù)有錯，要求重新輸入。如果輸入的初始上限值有錯。也會進行提醒然后要求重新輸岀。經(jīng)過測試，正確地輸入數(shù)據(jù)。就能得出想要的約瑟夫環(huán)運算的結(jié)果。六、結(jié)論與心得在這次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計中，讓我進一步地了解單循環(huán)鏈表的用法，也更 清楚地明口關(guān)于約瑟夫環(huán)的一些內(nèi)容。在設(shè)計的過程中，重點的問題有兩個，一 個是約瑟夫環(huán)該怎么樣去實現(xiàn)，還有就是每個人的密碼應(yīng)該如何輸入。起初，密 碼的輸入是設(shè)計在主函數(shù)中去解決，最后在查閱資料和動手實踐過之后，決定將 密碼的輸入放在循環(huán)鏈表的初始化過程中，這樣的話，能夠更條理清晰?？偟膩碚f，關(guān)于這次課程設(shè)計，我受益不淺。自己動手實踐設(shè)計關(guān)于約瑟夫 環(huán)，讓我對數(shù)據(jù)結(jié)構(gòu)有進一步的了解，雖然這次的設(shè)計只用到鏈表，沒有用到其 他結(jié)構(gòu)，但是也對它們有了更深的理解。課程設(shè)計，鍛煉的是我們的思維能力和 動手能力，在今后，我會繼續(xù)保持自主性的學習和實踐，更深入地去學習和應(yīng)用 關(guān)于數(shù)據(jù)結(jié)構(gòu)的知識。七、參考資料算法與數(shù)據(jù)額結(jié)構(gòu)c