1、第一次試驗(yàn)報(bào)告一. 實(shí)驗(yàn)題目 線性表及其應(yīng)用 約瑟夫環(huán)二. 實(shí)驗(yàn)?zāi)康膸椭鷮W(xué)生熟練掌握線性表的基本操作在順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以各種鏈表的操作和應(yīng)用作為重點(diǎn)內(nèi)容。三. 實(shí)驗(yàn)內(nèi)容：1. 問題描述：約瑟夫問題的一種描述為，編號(hào)為 1,2,3,n的n個(gè)人按 順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作 為報(bào)數(shù)上限值m,從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停 止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的 m的值，從他在順時(shí)針方向上的 下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一 個(gè)程序求出出列順序。2. 基本操作：利用單向循環(huán)

2、鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序 印出各人的編號(hào)。3. 測(cè)試數(shù)據(jù)：m的初值為20; n=7,7個(gè)人的密碼依次為：3,1,7,2,4,8,4首 先m值為6 （正確的出列順序應(yīng)為6,1,4,7,235）。4. 實(shí)現(xiàn)提示：程序運(yùn)行后，首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。可設(shè)nW 30此題所用的循環(huán)鏈表中不需要 頭結(jié)點(diǎn)”請(qǐng)注意空表 和非空表的界限。四. 實(shí)驗(yàn)程序源代碼#in elude using n amespace std; typedef struct LNode int num; /表示該元素的編號(hào) int key; /表示該元素的密碼 struct LNode *n e

3、xt;LNode,*LinkList; /結(jié)點(diǎn)類型，指針類型構(gòu)建約瑟夫環(huán)*intIn sert(L in kList &L,i nt key, int num) Lin kList p;if(L=NULL) / 第一個(gè)結(jié)點(diǎn)p=(LinkList)malloc(sizeof(LNode); 分配空間 if(!p)cout分配空間失敗！ num=num;p-key=key;L=p;else p=(Li nkList)malloc(sizeof(LNode); if(!p)cout分配空間失敗！ num=num; p-key=key; L-n ext=p; p-n ext=NULL; L=p; re

4、turn 0;*出人數(shù)出列的順序 * voidJoseph(L in kList &L,i nt k,i nt m) int i;Lin kList p,q;p=q=L;while(q-n ext!=L)q=q-n ext;while(k0)for(i=1;in ext; p=p-n ext;q-n ext=p-n ext; coutp-num key; /更新 m 的值 free(p);k-; /人數(shù)減1p=q-n ext; coute ndl;int m,n ,i,t;Lin kList head,p=NULL;cout 請(qǐng)輸入人的數(shù)量(=30)n;coutvv請(qǐng)輸入初始密碼：;/輸入初始密碼m cinm;coutvv請(qǐng)輸入每個(gè)人手中的密碼：e ndl; for(i=1;i t;if(ln sert(p,t,i)=-1) return 0;if(i=1)head=p;p-n ext=head; cout出列的順序如下：e ndl; Joseph(head, n, m);system(pause);re