數(shù)據(jù)結(jié)構(gòu)上機實驗報告—約瑟夫環(huán)問題

1、福州大學(xué)數(shù)計學(xué)院數(shù)據(jù)結(jié)構(gòu)上機實驗報告專業(yè)和班級：信息計算科學(xué)與應(yīng)用數(shù)學(xué)6班學(xué)號姓名成績實驗名稱線性表結(jié)構(gòu)及其應(yīng)用實驗內(nèi)容約瑟夫環(huán)問題實驗?zāi)康暮鸵蟆緦嶒災(zāi)康摹坷脝蜗蜓h(huán)鏈表解決約瑟夫環(huán)問題，提高綜合設(shè)計能力?！净疽蟆?利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按歸口炪列的順序印出各人的編號。問題描述和主要步驟【問題描述】 約瑟夫問題：編號為1，2，.n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此

2、下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序?！局饕绦颉?include <stdio.h>#include <stdlib.h>typedef struct node int number; int pwd; struct node * next;Node, *Link; Link Init(void) Link L; L = (Link)malloc(sizeof(Node); L->next = L; return L;void Insert(Link L, int e_pwd, int e_number) Link p,q; p = (Lin

3、k)malloc(sizeof(Node); p->pwd = e_pwd; p->number = e_number; q = L; while(q->next != L)q = q->next; p->next = q->next; q->next = p;void Delete(Link L, int i) Link p,q; q = L; while(q->next != q && q->next->number != i) q = q->next; if(q->next->number =

4、i) p = q->next; q->next = p->next; free(p); void main() Link p,q,L; int i,m,n,pwd; printf("請輸入?yún)⑴c人數(shù)與初始值："); scanf("%d%d",&n,&m); if(n<=0 | m<=0) return; L = Init(); i=1; while(i<=n) printf("請輸入第%d個人的密碼：",i); scanf("%d",&pwd); if(pw

5、d <= 0)continue; Insert(L, pwd, i); i+; i = 1; p = L->next; while(L->next != L) q = p; p = p->next; if(p =L) q = p; p = p->next; i+; if(i = m) printf("t%d",p->number); m = p->pwd; Delete(L, p->number); p = q; i = 0; 【測試數(shù)據(jù)】M的初值為20;n=7,7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6（正確的出列順序應(yīng)為6，1，4，7，2，3，5）【結(jié)果截圖】研究與探討解決約瑟夫環(huán)問題有三個算法：一個