基于單向循環(huán)鏈表的約瑟夫環(huán)設(shè)計

1、長春建筑學(xué)院基于單向循環(huán)鏈表的約瑟夫環(huán)設(shè)計Design of Joseph ring way circular linked list based on 學(xué) 院： 電氣信息學(xué)院 班 級： 計算機1201班 學(xué) 號： 121500140 姓 名： 盧玉琨 指導(dǎo)老師: 常大俊 摘 要約瑟夫環(huán)問題是由古羅馬著名的史學(xué)家Josephus提出的問題演變而來，所以通常稱為Josephus問題。改進約瑟夫環(huán)問題的描述是：編號為1，2，n的n個人按順時針方向圍坐一圈, 每人有一個密碼K（整數(shù)），留作其出圈后應(yīng)報到K后出圈。報數(shù)方法采用順時針報數(shù)和逆時針報數(shù)交替進行，初始密碼可任意確定。求最后剩下的人的編號。這

2、個就是約瑟夫環(huán)問題的實際場景。約瑟夫環(huán)問題如果采用單循環(huán)鏈表則能很好的解決。循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head解決問題的核心步驟是：先建立一個具有n個鏈結(jié)點，無頭結(jié)點的循環(huán)鏈表，然后確定第一個報數(shù)人的位置，并不斷地從鏈表中刪除鏈結(jié)點，直到鏈表為空?！娟P(guān)鍵詞】約瑟夫環(huán)；單循環(huán)鏈表；數(shù)據(jù)結(jié)構(gòu)；刪除結(jié)點AbstractJosephus ring problem is evolved by the question that raised by Josephus,the famous historican of ancient Rome.SO

3、it always be called Josephus Problem.The description of improving Josephus problem is :people was numbered 1,2,3,.,n sitted as a clockwise direction around circle,each with a password of K(integer),reserved for the ring should be reported K out of the ring .The report adapted the method that changed

4、 alternately with the clockwise and anticlockwise, the initial password can be determined.Solving the number of the last person.This is the real sense of the Joseph central problems. Joseph central problems can be well-solved if it adapted the circular linked list .The configuration of the list is j

5、ust pointed to the first team elements with the Omoto So pointer. P->link=head.The core process to solving the problem is:Firstly established a no-head-node circular linked list which have n chain nodes.Then determined the location of the first person.And striked out the chain nodes constantly un

6、til the chain table was empty.Keywords Joseph ring; circular linked list; data structure; deleting node目 錄前言1第一章 問題分析21.1 設(shè)計目的21.2 設(shè)計內(nèi)容21.3 設(shè)計要求21.4 設(shè)計思想第二章 邏輯設(shè)計42.1 循環(huán)鏈表抽象數(shù)據(jù)類型定義42.2本程序包含的模塊設(shè)計4第三章 詳細設(shè)計63.1 主函數(shù)63.2 鏈表的創(chuàng)建73.3 出隊處理93.4 約瑟夫環(huán)說明模塊103.5菜單模塊10第四章 程序調(diào)試與測試11第五章 結(jié)論14參考文獻15致謝16附錄17前 言數(shù)據(jù)結(jié)構(gòu)是一門研究非

7、數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。該課程設(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)鏈表的相同與不同之處，進一步加深對鏈表結(jié)構(gòu)類型及鏈表操作的理解。通過該課程設(shè)計，能運用所學(xué)知識，上機解決一些實際問題，了解并初步掌握設(shè)計，實現(xiàn)較大程序的完整過程，包括系統(tǒng)分析、編碼設(shè)

8、計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計、實現(xiàn)以及操作方法，為進一步的應(yīng)用開發(fā)打好基礎(chǔ)。第1章 問題分析1.1 設(shè)計目的1、 掌握單向循環(huán)鏈表的建立。 2、掌握單向循環(huán)鏈表的操作。 1.2 設(shè)計內(nèi)容 編號是1,2,n的n個人按照順時針方向圍坐一圈,每個人只有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù),報到m時停止報數(shù)。報m的人出列,將他的密碼作為新的m值,從他在順時針方向的下一個人開始重新從1報數(shù),如此下去,直到所有人全部出列為止。請設(shè)計一個程序求出出列順序。1.3 設(shè)計要求1、利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程,按照出列

9、的順序輸出各個人的編號。 2、測試數(shù)據(jù)：m的初值為20,n=7,7個人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什么？ 3、輸入數(shù)據(jù)：建立輸入函數(shù)處理輸入的數(shù)據(jù),輸入m的初值n,輸入每個人的密碼,建立單向循環(huán)鏈表。 4、輸出形式：建立一個輸出函數(shù),將正確的出列順序輸出。 1.4 設(shè)計思想約瑟夫環(huán)問題描述的是：設(shè)編號為1，2，n的n（n>0）個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時選擇一個正整數(shù)作為報數(shù)上限m，從第一個人開始順時針方向自1起按順序報數(shù)，報到m時停止報數(shù)，報m的人出圈，將他的密碼作為新的m值，從他的順時針方向上的下一個人起重新從1報數(shù)

10、。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計一個程序模擬此過程，求出出圈的編號序列。具體描述如圖1和圖2所示：圖1 約瑟夫環(huán)問題圖解t圖2 約瑟夫環(huán)原理演示圖第二章 邏輯設(shè)計2.1 循環(huán)鏈表抽象數(shù)據(jù)類型定義typedef struct LNode/定義單循環(huán)鏈表中結(jié)點的結(jié)構(gòu) int num;/編號 int pwd;/passwordstruct LNode *next;/指向下一結(jié)點的指針 LNode;2.2本程序包含的模塊設(shè)計（1）構(gòu)造結(jié)點模塊LNode *createNode(int m_num,int m_pwd) LNode *p; p=(LNode *)malloc

11、(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(LNode *ppHead,int m_pwd)（4）約瑟夫環(huán)說明輸出模塊void instruction()（5）菜單模塊void menu()（6）主函數(shù)模塊int main（）函數(shù)的調(diào)用關(guān)系圖如圖3所示：第三章 詳細設(shè)計3.1 主函數(shù)圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)圖

12、4，主函數(shù)程序如下：int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf("n請選擇要執(zhí)行的操作："); scanf("%d",&x); system("cls"); switch(x) case 1: printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值m,

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

14、,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您選擇的操作有誤，請重新選擇.n "); main(); return 0; 3.2 鏈表的創(chuàng)建圖5 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流程圖 /*創(chuàng)建單向循環(huán)鏈表ppHead，參加人數(shù)個數(shù)為n，并輸入每人的密碼值，若建立失敗則生成頭結(jié)

15、點，讓cur指向他，若建立成功則插入結(jié)點P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點，再把P插入循環(huán)鏈表ppHead中*/根據(jù)圖5，創(chuàng)建鏈表函數(shù)程序如下：void createList(LNode *ppHead,int n) int i,m_pwd;LNode *p,*cur;/cur:浮標指針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=

16、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.3 出隊處理圖6 出對函數(shù)的數(shù)據(jù)流程圖/*p指向要刪除結(jié)點的前一個結(jié)點，ppHead指向要刪除的結(jié)點，使p=ppHead，ppHead再指向要刪除結(jié)點的下一個結(jié)點，使p和ppHead鏈接，輸出p指向結(jié)點的

17、編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點都打印和刪除為止！*/根據(jù)圖6，出隊函數(shù)程序如下：void jose(LNode *ppHead,int m_pwd)int i,j;LNode *p;/定義指針變量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-&

18、gt;pwd j=ppHead->num;/j賦值為ppHead->num，j為要刪除的密碼值 printf("第%d個人出列，密碼：%dn",j,i); m_pwd=ppHead->pwd;/m_pwd賦值為ppHead->pwd free(ppHead);/釋放頭結(jié)點 ppHead=p->next;/ppHead重新賦值給p->next,即釋放前的ppHead->pwd指針/刪除報數(shù)結(jié)點 i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為ppHead->n

19、um printf("最后一個出列是%d號，密碼是:%dn",j,i); free(ppHead);/釋放頭結(jié)點 3.4 約瑟夫環(huán)說明模塊void instruction() printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始按順時針方向自1開始按順序報數(shù),報到m時停止.報m的人出列，將他的密碼m作為新的m值,從他的順時針方向上的下一人開始重新從1報數(shù),如此下

20、去,直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); 3.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)致每一行都出

21、現(xiàn)兩個錯誤，加入子函數(shù)的聲明后，錯誤消失。2. 剛開始時忽略了一些變量參數(shù)的標識，如："&"和“*”，使調(diào)試程序時費時不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。3. 本次課程設(shè)計采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序劃分為三個結(jié)構(gòu)：元素結(jié)點、單向循環(huán)鏈表，主控制模塊。思路較為清晰，實現(xiàn)調(diào)用順利。 經(jīng)過本次實驗，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了進一步的了解，每一個程序經(jīng)過問題分析、概要設(shè)計、詳細設(shè)計之后，思路清晰呈現(xiàn)，程序也很快就出來了，最后經(jīng)過調(diào)試、運行，又有了新的體驗。<測試用例>這是一個使用循環(huán)鏈表的經(jīng)典問題。本程序開始運行界面如圖7所示：圖7 約

22、瑟夫環(huán)開始運行界面 選擇1進入約瑟夫環(huán)問題闡述，如圖8所示：圖8 約瑟夫環(huán)問題闡述選擇2，輸入下列數(shù)據(jù)測試，測試結(jié)果如圖9所示：請輸入總?cè)藬?shù)n：8請輸入開始上限數(shù)m：9請依次輸入每個人的密碼：9 3 7 9 12 6 11 10 13出隊順序：1 4 3 8 2 5 7 6 圖9 約瑟夫環(huán)測試1選擇2，輸入下列數(shù)據(jù)測試，測試結(jié)果如圖10所示：請輸入總?cè)藬?shù)n：6請輸入開始上限數(shù)m：16請依次輸入每個人的密碼：32 5 6 9 8 7 出隊順序：4 2 3 1 6 5圖10 約瑟夫環(huán)測試2繼續(xù)選擇2，輸入下列數(shù)據(jù)測試，測試結(jié)果如圖11所示：請輸入總?cè)藬?shù)n：7請輸入開始上限數(shù)m：20請依次輸入每個人

23、的密碼：2 4 6 3 8 4 0 出隊順序：6 3 4 1 5 2 7圖11 約瑟夫環(huán)測試3第五章 結(jié)論我這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的題目是:約瑟夫環(huán)問題。通過對該題目的設(shè)計,我加深了對數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的理解,進一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對單循環(huán)鏈表的基本運算的實現(xiàn),學(xué)會了如何把學(xué)到的知識用于解決實際問題,鍛煉了自己動手的能力。 在這次課程設(shè)計中，我們組四個人一同討論這個算法的運算過程以及算法涉及的一些數(shù)據(jù)結(jié)構(gòu)的知識，討論出一個大概框架后我們四個人分工合作。在此課程設(shè)計中我主要承擔畫流程圖以及測試的工作，通過畫流程圖，我更熟識了Microsoft visio 2003這個

24、畫圖軟件的運用。通過用visualc+ 6.0這個程序開發(fā)軟件測試，我發(fā)現(xiàn)存在很多的錯誤，深知自己的不足之處，然后通過提示改正錯誤。兩周的課程設(shè)計很短暫，但其間的內(nèi)容是很充實的，在其中我學(xué)習(xí)到了很多平時書本中無法學(xué)到的東西，積累了經(jīng)驗，鍛煉了自己分析問題，解決問題的能力。總而言之這兩周中我學(xué)到很多，受益匪淺。參考文獻 1 嚴蔚敏，吳偉民 著.數(shù)據(jù)結(jié)構(gòu)（C語言版）M.北京：清華大學(xué)出版社，1997.2 嚴蔚敏，吳偉民 著.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）M.北京：清華大學(xué)出版社，1997.3 William Ford,William Topp 著. DATA STRUCTURE WITH C+ M.北京

25、：清華大學(xué)出版社，1996 .4 譚浩強 著. C語言程序設(shè)計M.北京： 清華大學(xué)出版社，2000.5 周云靜 著數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機指導(dǎo)M北京：冶金工業(yè)出版社，2004.6 陳慧南 著數(shù)據(jù)結(jié)構(gòu)C+語言描述M北京：人民郵電出版社，2005.7 Adam Drozdek 著數(shù)據(jù)結(jié)構(gòu)與算法M北京：清華大學(xué)出版社，2006.8 徐孝凱 著數(shù)據(jù)結(jié)構(gòu)實驗M北京：中央廣播電視大學(xué)出版社，2001.致 謝這次的課程設(shè)計，我們四人一小組完成自己所選的課題，但是還是得到了來自很多方面的幫助。在此首先要感謝學(xué)院提供給我這次實踐的機會，讓我們有機會貼近現(xiàn)實，感受成功的喜悅；其次要感謝實驗機房的老師提供優(yōu)良的實驗設(shè)

26、備供我們做課程設(shè)計，正是這種良好的課程設(shè)計的環(huán)境讓我們整個課程設(shè)計過程心情都非常愉快。再次要感謝指導(dǎo)老師的辛勤指導(dǎo)，每當我們遇到疑難問題時，是他一次次不厭其煩地解釋和悉心地指導(dǎo)，我們才能闖過一個個難關(guān)，到達勝利的彼岸，是他給我們提供了一次寶貴的檢驗自己的機會。最后也要感謝同伴們的幫助，有了他們的支持使我遇到任何困難都覺得不是一個人在戰(zhàn)斗。感謝所有在課程設(shè)計過程中幫助過我的人！附 錄 源代碼： #include <stdio.h>/輸入輸出函數(shù)頭文件 #include <stdlib.h>/字符串轉(zhuǎn)短整形函數(shù)的頭文件 typedef struct LNode/定義單循環(huán)鏈

27、表中結(jié)點的結(jié)構(gòu) int num;/編號 int pwd;/password struct LNode *next;/指向下一結(jié)點的指針 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) /*

28、創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個數(shù)為n，并輸入每個人的密碼值，若建立失敗則生成頭結(jié)點，讓cur指向他，若建立成功則插入結(jié)點P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點，再把P插入循環(huán)鏈表ppHead中*/ int i,m_pwd; LNode *p,*cur;/cur:浮標指針 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)/如

29、果頭結(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)建完成 /*出隊處理*/void jose(LNode *ppHead,int m_pwd) /*p指向要刪除結(jié)點的前一個結(jié)點，ppHead指向要刪除的結(jié)點，使p=ppHead，ppHead再指向要刪除結(jié)點的下一個結(jié)點，使p和pp

30、Head鏈接，輸出p指向結(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點都打印和刪除為止！*/ int i,j; LNode *p;/定義指針變量 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賦值為p

31、pHead->num，j為要刪除的密碼值 printf("第%d個人出列，密碼：%dn",j,i); m_pwd=ppHead->pwd;/m_pwd賦值為ppHead->pwd free(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("約瑟夫環(huán):n"); printf(" 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始按順時針方向自1開始順序報數(shù),報到時停止.報m的人出列，將他的密碼m作為新的m值,從他在順時針方向上的下一人開始重新從1報數(shù),如此下去, 直到所有人全部出列為止.編程