1、第一次試驗報告一. 實驗題目線性表及其應用約瑟夫環二. 實驗目的幫助學生熟練掌握線性表的根本操作在順序和鏈式兩種存儲結構上的實現，其中以各種鏈表的操作和應用作為重點內容。三. 實驗內容：1. 問題描述：約瑟夫問題的一種描述為，編號為1,2,3,n的n個人按 順時針方向圍坐一圈，每人持有一個密碼正整數。一開始任選一個正整數作為報數上限值m,從第一個人開始按順時針方向自1開始順序報數，報到m時停 止報數。報m的人出 列，將他的密碼作為新的m的值，從他在順時針方向上的下一個人開始重新從1報數, 如此下去，直至所有的人全部出列為止。試設計一個程序求出出列順序。2. 根本操作：利用單向循環鏈表存儲結構模

2、擬此過程，按照出列的順序印出各人的編號。3. 測試數據：m的初值為20; n=7,7個人的密碼依次為：3,1,7,2,4,8,4首先m值 為6 正確的出列順序應為6,1,4,7,235。4. 實現提示：程序運行后，首先要求用戶指定初始報數上限值，然后讀取各人的密碼。可設nW 30此題所用的循環鏈表中不需要頭結點請注意空表 和非空表的界限。四. 實驗程序源代碼#in elude <iostream> using n amespace std; typedef struct LNode int num; /表示該元素的編號 int key; /表示該元素的密碼 struct LNode

3、 *n ext;int/*構建約瑟夫環*LNode,*LinkList; /結點類型，指針類型 In sert(L in kList &L,i nt key, i nt num) Lin kList p;if(L=NULL) / 第一個結點p=(LinkList)malloc(sizeof(LNode); 分配空間 if(!p)cout?"分配空間失敗！"<<e ndl;return -1;p->num=num;p->key=key;L=p； else p=(Li n kList)malloc(sizeof(LNode); if(!p)cou

4、t?"分配空間失敗！"<<e ndl; return -1; p->num=num; p->key=key; L->n ext=p; p->n ext=NULL; L=p; return 0;ff * 出人數出列的順序 * 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 ex t;while(k>0)for(i=1;i<m;i+) q=q->n ext; p=p-&g

5、t;n ext;q->n ext=p->n ext; cout? p->num <<"" m=p->key; / 更新 m 的值 free(p);k-; /人數減1 p=q->n ex t; cout? e ndl;int m,n ,i, t;Lin kList head,p=NULL;cout << "請輸入人的數量(<=30)"v<endl ; coutvv"請輸入人數："/輸入人數n cin>>n; coutvv"請輸入初始密碼："/輸入初始密碼m cin>>m;coutvv"請輸入每個人手中的密碼："<<e n dl; for(i=1;i<=n ;i+) cin> >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("paus