實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：約瑟夫環(huán)問題實(shí)驗(yàn)類型：綜合性實(shí)驗(yàn)班級(jí)：學(xué)號(hào)：姓名：實(shí)驗(yàn)日期：2014.5.19問題描述設(shè)有編號(hào)為1,2,…,n的n（n＞0）個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼m。從第一個(gè)人開始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，再?gòu)乃南乱粋€(gè)人起重新報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的出圈，……，如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)首先，設(shè)計(jì)實(shí)現(xiàn)約瑟夫環(huán)問題的存儲(chǔ)結(jié)構(gòu)。由于約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，考慮采用循環(huán)鏈表，為了統(tǒng)一對(duì)表中任意結(jié)點(diǎn)的操作，循環(huán)鏈表不帶頭結(jié)點(diǎn)。將循環(huán)鏈表的結(jié)點(diǎn)定義為如下結(jié)構(gòu)類型：typedefstructLNode { intM;LNode*next; } Lnode;3.算法設(shè)計(jì)（1）建立一個(gè)循環(huán)鏈表LNode*create_l(intn){ LNode*L,*p; inti; L=(LNode*)malloc(sizeof(LNode)); L->M=1; L->next=L; for(i=n;i>1;i--) { p=(LNode*)malloc(sizeof(LNode)); p->M=i; p->next=L->next; L->next=p; } returnL; }依次刪除第m個(gè)結(jié)點(diǎn)，并輸出該節(jié)點(diǎn)的序號(hào)intDele(LNode*L,intm){LNode*p,*pre; intj; p=L; pre=L; while(pre->next!=L) pre=pre->next; while(p!=p->next) { for(j=1;j<m;j++) { pre=p; p=p->next; } printf("%d",p->M); pre->next=p->next; free(p); p=pre->next; } printf("%d",pre->M); free(pre); }主函數(shù)intmain() { LNode*first; intm,n; printf("Pleaseinputn:"); scanf("%d",&n); printf("Pleaseinputm:"); scanf("%d",&m); create_l(n); first=create_l(n); printf("thedeletenumberis:"); Dele(first,m);}4．程序代碼#include<stdio.h>#include<malloc.h>typedefstructLNode { intM;LNode*next; }LNode; LNode*create_l(intn){ LNode*L,*p; inti; L=(LNode*)malloc(sizeof(LNode)); L->M=1; L->next=L; for(i=n;i>1;i--) { p=(LNode*)malloc(sizeof(LNode)); p->M=i; p->next=L->next; L->next=p; } returnL; }intDele(LNode*L,intm){LNode*p,*pre; intj; p=L; pre=L; while(pre->next!=L) pre=pre->next; while(p!=p->next) { for(j=1;j<m;j++) { pre=p; p=p->next; } printf("%d",p->M); pre->next=p->next; free(p); p=pre->next; } printf("%d",pre->M); free(pre); }intmain() { LNode*first; intm,n; printf("Pleaseinputn:"); scanf("%d",&n); printf("Pleaseinputm:"); scanf("%d",&m); create_l(n); first=create_l(n); printf("thedeletenumberis:"); Dele(first,m);} 5.運(yùn)行、測(cè)試與分析（1）、運(yùn)行,例如n=5,m=3得出結(jié)果實(shí)驗(yàn)收獲及思考考慮不太周全，剛開始沒有考慮到只有一個(gè)人或者密碼是1的情況，以后寫程序要考慮周到。而且之前學(xué)習(xí)的都是算法，這是第一次寫數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)。真正第一次將自己的算法用C語(yǔ)言表達(dá)并運(yùn)行出來(lái)。所以，紙上學(xué)來(lái)終覺淺，只有真正實(shí)踐過(guò)才會(huì)了解。思考：采用順序存儲(chǔ)結(jié)構(gòu)如何實(shí)現(xiàn)約瑟夫環(huán)問題？建立一個(gè)長(zhǎng)度為n的順序表，依次刪除第n個(gè)元素，