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

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

2、個(gè)就是約瑟夫環(huán)問(wèn)題的實(shí)際場(chǎng)景。約瑟夫環(huán)問(wèn)題如果采用單循環(huán)鏈表則能很好的解決。循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個(gè)鏈表的尾元素指針指向隊(duì)首元素。 p->link=head解決問(wèn)題的核心步驟是：先建立一個(gè)具有n個(gè)鏈結(jié)點(diǎn)，無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表，然后確定第一個(gè)報(bào)數(shù)人的位置，并不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空?！娟P(guān)鍵詞】約瑟夫環(huán)；單循環(huán)鏈表；數(shù)據(jù)結(jié)構(gòu)；刪除結(jié)點(diǎn)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第一章 問(wèn)題分析21.1 設(shè)計(jì)目的21.2 設(shè)計(jì)內(nèi)容21.3 設(shè)計(jì)要求21.4 設(shè)計(jì)思想第二章 邏輯設(shè)計(jì)42.1 循環(huán)鏈表抽象數(shù)據(jù)類(lèi)型定義42.2本程序包含的模塊設(shè)計(jì)4第三章 詳細(xì)設(shè)計(jì)63.1 主函數(shù)63.2 鏈表的創(chuàng)建73.3 出隊(duì)處理93.4 約瑟夫環(huán)說(shuō)明模塊103.5菜單模塊10第四章 程序調(diào)試與測(cè)試11第五章 結(jié)論14參考文獻(xiàn)15致謝16附錄17前 言數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非

7、數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。該課程設(shè)計(jì)的目的是通過(guò)課程設(shè)計(jì)的綜合訓(xùn)練，以培養(yǎng)分析和編程等實(shí)際動(dòng)手能力，是系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)這門(mén)課程的主要內(nèi)容。本次課程設(shè)計(jì)的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問(wèn)題，循環(huán)鏈表是一種首尾相接的鏈表，其特點(diǎn)是無(wú)須增加存儲(chǔ)容量，僅對(duì)表的鏈接方式稍作改變，使表處理更加靈活。約瑟夫環(huán)問(wèn)題就是用單循環(huán)鏈表處理的一個(gè)實(shí)際應(yīng)用。通過(guò)這個(gè)設(shè)計(jì)實(shí)例，了解單鏈表和單循環(huán)鏈表的相同與不同之處，進(jìn)一步加深對(duì)鏈表結(jié)構(gòu)類(lèi)型及鏈表操作的理解。通過(guò)該課程設(shè)計(jì)，能運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些實(shí)際問(wèn)題，了解并初步掌握設(shè)計(jì)，實(shí)現(xiàn)較大程序的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)

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

9、的順序輸出各個(gè)人的編號(hào)。 2、測(cè)試數(shù)據(jù)：m的初值為20,n=7,7個(gè)人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什么？ 3、輸入數(shù)據(jù)：建立輸入函數(shù)處理輸入的數(shù)據(jù),輸入m的初值n,輸入每個(gè)人的密碼,建立單向循環(huán)鏈表。 4、輸出形式：建立一個(gè)輸出函數(shù),將正確的出列順序輸出。 1.4 設(shè)計(jì)思想約瑟夫環(huán)問(wèn)題描述的是：設(shè)編號(hào)為1，2，n的n（n>0）個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一個(gè)正整數(shù)密碼。開(kāi)始時(shí)選擇一個(gè)正整數(shù)作為報(bào)數(shù)上限m，從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?起按順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，將他的密碼作為新的m值，從他的順時(shí)針?lè)较蛏系南乱粋€(gè)人起重新從1報(bào)數(shù)

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

11、(sizeof(LNode);/生成一個(gè)結(jié)點(diǎn) p->num=m_num;/把實(shí)參賦給相應(yīng)的數(shù)據(jù)域 p->pwd=m_pwd; p->next=NULL;/指針域?yàn)榭?return p; （2）創(chuàng)建鏈表模塊void createList(LNode *ppHead,int n)（3）出隊(duì)處理模塊void jose(LNode *ppHead,int m_pwd)（4）約瑟夫環(huán)說(shuō)明輸出模塊void instruction()（5）菜單模塊void menu()（6）主函數(shù)模塊int main（）函數(shù)的調(diào)用關(guān)系圖如圖3所示：第三章 詳細(xì)設(shè)計(jì)3.1 主函數(shù)圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)圖

12、4，主函數(shù)程序如下：int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf("n請(qǐng)選擇要執(zhí)行的操作："); scanf("%d",&x); system("cls"); switch(x) case 1: printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,

13、從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始按順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他的順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去,直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); main(); break; case 2: printf("請(qǐng)輸入總?cè)藬?shù)n：n"); scanf("%d",&n); printf("請(qǐng)輸入開(kāi)始上限數(shù)m:"); scanf("%d",&m); createList(&ppHead

14、,n); printf("n"); printf("出隊(duì)順序：n"); jose(ppHead,m); printf("n約瑟夫環(huán)游戲結(jié)束!n"); main(); break; case 0: exit(0); default: system("cls"); printf("n您選擇的操作有誤，請(qǐng)重新選擇.n "); main(); return 0; 3.2 鏈表的創(chuàng)建圖5 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流程圖 /*創(chuàng)建單向循環(huán)鏈表ppHead，參加人數(shù)個(gè)數(shù)為n，并輸入每人的密碼值，若建立失敗則生成頭結(jié)

15、點(diǎn)，讓cur指向他，若建立成功則插入結(jié)點(diǎn)P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/根據(jù)圖5，創(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個(gè)人的密碼：",i); scanf("%d",&m_pwd);/輸入持有密碼 p=createNode(i,m_pwd);/調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù) if(*ppHead=

16、NULL)/如果頭結(jié)點(diǎn)為空 *ppHead=cur=p;/生成頭結(jié)點(diǎn)，讓cur指向他 cur->next=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p->next = cur->next; cur->next = p; cur= p;/cur指向新插入結(jié)點(diǎn) printf("完成創(chuàng)建！n"); /提示鏈表創(chuàng)建完成 3.3 出隊(duì)處理圖6 出對(duì)函數(shù)的數(shù)據(jù)流程圖/*p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，ppHead指向要?jiǎng)h除的結(jié)點(diǎn)，使p=ppHead，ppHead再指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使p和ppHead鏈接，輸出p指向結(jié)點(diǎn)的

17、編號(hào)和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點(diǎn)都打印和刪除為止！*/根據(jù)圖6，出隊(duì)函數(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ǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) ppHead=ppHead->next;/ppHead指向下一個(gè)元素 p->next = ppHead->next;/p結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接 i=ppHead->pwd;/i賦值為ppHead-&

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

19、um printf("最后一個(gè)出列是%d號(hào)，密碼是:%dn",j,i); free(ppHead);/釋放頭結(jié)點(diǎn) 3.4 約瑟夫環(huán)說(shuō)明模塊void instruction() printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始按順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他的順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下

20、去,直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); 3.5菜單模塊void menu() printf("*約瑟夫環(huán)*n"); printf("n"); printf(" 1約瑟夫環(huán)問(wèn)題的闡述 n"); printf(" 2按要求求解約瑟夫環(huán) n"); printf(" 0退出 n"); printf("* 歡迎使用！*n");第四章 程序調(diào)試與測(cè)試1. 調(diào)用模塊時(shí)，結(jié)點(diǎn)結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出

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

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

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

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

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

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

27、鏈表中結(jié)點(diǎn)的結(jié)構(gòu) int num;/編號(hào) int pwd;/password struct LNode *next;/指向下一結(jié)點(diǎn)的指針 LNode;/*構(gòu)造結(jié)點(diǎn)*/LNode *createNode(int m_num,int m_pwd) LNode *p; p=(LNode *)malloc(sizeof(LNode);/生成一個(gè)結(jié)點(diǎn) p->num=m_num;/把實(shí)參賦給相應(yīng)的數(shù)據(jù)域 p->pwd=m_pwd; p->next=NULL;/指針域?yàn)榭?return p; /*創(chuàng)建循環(huán)鏈表*/ void createList(LNode *ppHead,int n) /

28、*創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個(gè)數(shù)為n，并輸入每個(gè)人的密碼值，若建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，若建立成功則插入結(jié)點(diǎn)P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/ int i,m_pwd; LNode *p,*cur;/cur:浮標(biāo)指針 for(i=1;i<=n;i+) printf("輸入第%d個(gè)人的密碼：",i); scanf("%d",&m_pwd);/輸入持有密碼 p=createNode(i,m_pwd);/調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù) if(*ppHead=NULL)/

29、如果頭結(jié)點(diǎn)為空 *ppHead=cur=p;/生成頭結(jié)點(diǎn)，讓cur指向他 cur->next=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p->next = cur->next; cur->next = p; cur= p;/cur指向新插入結(jié)點(diǎn) printf("完成創(chuàng)建！n"); /提示鏈表創(chuàng)建完成 /*出隊(duì)處理*/void jose(LNode *ppHead,int m_pwd) /*p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，ppHead指向要?jiǎng)h除的結(jié)點(diǎn)，使p=ppHead，ppHead再指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使p和p

30、pHead鏈接，輸出p指向結(jié)點(diǎn)的編號(hào)和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點(diǎn)都打印和刪除為止！*/ int i,j; LNode *p;/定義指針變量 for(i=1;p!=ppHead;i+) for(j=1;j<m_pwd;+j) p=ppHead;/p賦值為ppHead，p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) ppHead=ppHead->next;/ppHead指向下一個(gè)元素 p->next = ppHead->next;/p結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接 i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為

31、ppHead->num，j為要?jiǎng)h除的密碼值 printf("第%d個(gè)人出列，密碼：%dn",j,i); m_pwd=ppHead->pwd;/m_pwd賦值為ppHead->pwd free(ppHead);/釋放頭結(jié)點(diǎn) ppHead=p->next;/ppHead重新賦值給p->next,即釋放前的ppHead->pwd指針/刪除報(bào)數(shù)結(jié)點(diǎn) i=ppHead->pwd;/i賦值為ppHead->pwdj=ppHead->num;/j賦值為ppHead->numprintf("最后一個(gè)出列是%d號(hào)，密碼是:%dn",j,i); free(ppHead);/釋放頭結(jié)點(diǎn)void instruction() printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù),報(bào)到時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他在順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去, 直到所有人全部出列為止.編程