數據結構實驗 約瑟夫環(huán)

實驗報告實驗名稱：約瑟夫環(huán)問題實驗類型：綜合性實驗班級：學號：姓名：實驗日期：2014.5.19問題描述設有編號為1,2,…,n的n（n＞0）個人圍成一個圈，每個人持有一個密碼m。從第一個人開始報數，報到m時停止報數，報m的人出圈，再從他的下一個人起重新報數，報到m時停止報數，報m的出圈，……，如此下去，直到所有人全部出圈為止。當任意給定n和m后，設計算法求n個人出圈的次序。2.數據結構設計首先，設計實現約瑟夫環(huán)問題的存儲結構。由于約瑟夫環(huán)問題本身具有循環(huán)性質，考慮采用循環(huán)鏈表，為了統(tǒng)一對表中任意結點的操作，循環(huán)鏈表不帶頭結點。將循環(huán)鏈表的結點定義為如下結構類型：typedefstructLNode { intM;LNode*next; } Lnode;3.算法設計（1）建立一個循環(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個結點，并輸出該節(jié)點的序號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);}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.運行、測試與分析（1）、運行,例如n=5,m=3得出結果實驗收獲及思考考慮不太周全，剛開始沒有考慮到只有一個人或者密碼是1的情況，以后寫程序要考慮周到。而且之前學習的都是算法，這是第一次寫數據結構的實驗。真正第一次將自己的算法用C語言表達并運行出來。所以，紙上學來終覺淺，只有真正實踐過才會了解。思考：采用順序存儲結構如何實現約瑟夫環(huán)問題？建立一個長度為n的順序表，依次刪除第n個元素，