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

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

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

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

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

5、dlib.h> typedef struct node每個(gè)人持有的密碼/人員的編號(hào)指向下一個(gè)節(jié)點(diǎn)int password;int num;struct node *next;node, *link;/創(chuàng)建一個(gè)空的鏈表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;/初始化鏈表，初始化人員編號(hào)和輸入每個(gè)人的密碼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請(qǐng)輸入第%d個(gè)人的密碼:",i);seanf("%d", &p->password);p->num=i;l->next=p;l=p;i 廠 >next二q->next;free(q);主函數(shù)，執(zhí)行約瑟夫環(huán)的運(yùn)行void mainolink l, p, q;int n, m;int a=l;int b=l;/創(chuàng)建一個(gè)循環(huán)語(yǔ)句，用于在實(shí)現(xiàn)約瑟夫環(huán)運(yùn)算結(jié)束后是否繼續(xù)執(zhí)行whi1

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

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

9、正確的結(jié)果。同時(shí)進(jìn)行詢(xún)問(wèn)判斷，是否繼續(xù)。c d: 04080930楊記祥約瑟夫環(huán)ysfhdebugysfh. exe慎輸入總?cè)藬?shù)n：請(qǐng)輸入初始的上限值m履龔缶列的順序?yàn)?31254雇否繼續(xù)重新輸入運(yùn)算1個(gè)人的密碼2個(gè)人的密碼3個(gè)人的密碼4個(gè)人的密碼5個(gè)人的密碼正整數(shù):1:2:3:4:5<1繼續(xù)0退岀:zj如果選擇繼續(xù)，則可以重復(fù)輸入各項(xiàng)繼續(xù)進(jìn)行運(yùn)算。cf d: 04080930$記祥約瑟夫環(huán)ysfhdebugysfh. exen數(shù) 人 總 入 輸 請(qǐng)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請(qǐng)請(qǐng)請(qǐng)請(qǐng)0>車(chē)3是1碼碼碼碼碼 密密密密密: 人人人人人那 個(gè)個(gè)個(gè)個(gè)個(gè)弟41234cl繼續(xù)0退出:碼碼碼 密密密 人人人 個(gè)個(gè)個(gè) 12 3 1ajaja 4請(qǐng)請(qǐng)請(qǐng)正整數(shù):5:2如果不選擇繼續(xù)，則輸入0后退出。如果一開(kāi)始輸入的數(shù)據(jù)有錯(cuò)，則會(huì)提示輸入的數(shù)據(jù)有錯(cuò)，要求重新輸入。如果輸入的初始上限值有錯(cuò)。也會(huì)進(jìn)行提醒然后要求重新輸岀。經(jīng)過(guò)測(cè)試，正確地輸入數(shù)據(jù)。就能得出想要的約瑟夫環(huán)運(yùn)算的結(jié)果。六、結(jié)論與心得在這次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)中，讓我進(jìn)一步地了解單循環(huán)鏈表的用法，也更 清楚地明口關(guān)于約瑟夫環(huán)的一些內(nèi)容。在設(shè)計(jì)的過(guò)程中，重點(diǎn)的問(wèn)題有兩個(gè)，一 個(gè)是約瑟夫環(huán)該怎么樣去實(shí)現(xiàn)，還有就是每個(gè)人的密碼應(yīng)該如何輸入。起初，密 碼的輸入是設(shè)計(jì)在主函數(shù)中去解決，最后在查閱資料和動(dòng)手實(shí)踐過(guò)之后，決定將 密碼的輸入放在循環(huán)鏈表的初始化過(guò)程中，這樣的話，能夠更條理清晰?？偟膩?lái)說(shuō)，關(guān)于這次課程設(shè)計(jì)，我受益不淺。自己動(dòng)手實(shí)踐設(shè)計(jì)關(guān)于約瑟夫 環(huán)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)有進(jìn)一步的了解，雖然這次的設(shè)計(jì)只用到鏈表，沒(méi)有用到其 他結(jié)構(gòu)，但是也對(duì)它們有了更深的理解。課程設(shè)計(jì)，鍛煉的是我們的思維能力和 動(dòng)手能力，在今后，我會(huì)繼續(xù)保持自主性的學(xué)習(xí)和實(shí)踐，更深入地去學(xué)習(xí)和應(yīng)用 關(guān)于數(shù)據(jù)結(jié)構(gòu)的知識(shí)。七、參考資料算法與數(shù)據(jù)額結(jié)構(gòu)c