實驗6--約瑟夫環(huán)的實現(xiàn)(大作業(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上浙江大學(xué)城市學(xué)院實驗報告課程名稱 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 實驗項目名稱 實驗六 約瑟夫環(huán)的實現(xiàn) 學(xué)生姓名 專業(yè)班級 學(xué)號 實驗成績 指導(dǎo)老師（簽名 ） 日期 一. 實驗?zāi)康暮鸵?、學(xué)會通過對問題的分析，設(shè)計一種合理的數(shù)據(jù)結(jié)構(gòu)，并進行定義及操作的實現(xiàn)。2、掌握利用線性表的各種操作來進行具體的實際應(yīng)用。3、加強程序設(shè)計的能力。二. 實驗內(nèi)容1、編寫程序，模擬約瑟夫環(huán)（josephus）問題： n個人（編號為1，2，3，n (n0) ）按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出兩個值：一個為首先報數(shù)的人的編號i (0i=n)，另一個為起始報數(shù)上限值m。接著從編號為

2、i的人開始按順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，且報到m的人出列，并將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1報數(shù)，如此下去，直到所有人全部出列為止。要求設(shè)計一個程序模擬此過程，給出出列人的編號序列。基本要求:（1） 人數(shù)n、每人的正整數(shù)密碼、首次報數(shù)人編號i、初始報數(shù)上限值m均由鍵盤輸入。（2） 參照線性表的抽象數(shù)據(jù)類型定義，設(shè)計本實驗的抽象數(shù)據(jù)類型。（3） 根據(jù)你設(shè)計的抽象數(shù)據(jù)類型，分別用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)約瑟夫環(huán)問題。并請分別將順序存儲結(jié)構(gòu)的程序存放在文件test6_Seq.h（基本操作函數(shù)）、test6_Seq.cpp（主函數(shù)）中，鏈?zhǔn)酱鎯Y(jié)構(gòu)的

3、程序存放在文件test6_Link.h（基本操作函數(shù)）、test6_Link.cpp（主函數(shù)）中。（4） 設(shè)計測試數(shù)據(jù)，并調(diào)試程序，直到正確運行。2、填寫實驗報告，實驗報告文件取名為report6.doc。3、上傳實驗報告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、test6_Link.h、test6_Link.cpp到Ftp服務(wù)器（ 22:2007 ）自己的文件夾下。同時上交一份書面的實驗報告。三. 抽象數(shù)據(jù)類型定義（需說明你設(shè)計的每個基本操作的功能）1. 初始化線性表2. 清除線性表3. 在線性表中插入某個元素4.

4、 刪除線性表中的某個元素5約瑟夫函數(shù)四. 兩種類型（順序和鏈?zhǔn)剑┑拇鎯Y(jié)構(gòu)定義及算法思路1.順序typedef struct List ElemType *list; int size; int MaxSize; SeqList;void InitList(SeqList &L)；void ClearList(SeqList &L)；bool InsertList(SeqList &L, ElemType item, int pos)；bool DeleteList(List &L,ElemType &item,int pos)2.鏈?zhǔn)絫ypedef struct LNode int code

5、; int num; struct LNode *next; LNode;void josephus(int n,int m,int s)。五. 實驗結(jié)果與分析1.順序輸出結(jié)果2.鏈?zhǔn)捷敵鼋Y(jié)果六. 心得體會（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）1、學(xué)會通過對問題的分析，設(shè)計一種合理的數(shù)據(jù)結(jié)構(gòu)，并進行定義及操作的實現(xiàn)2、掌握利用線性表的各種操作來進行具體的實際應(yīng)用3、加強程序設(shè)計的能力，同時對前面所學(xué)習(xí)的只是進行了回顧，掌握了鏈表的基本技巧【附錄-源程序】1. 順序test6_Seq.cpp專心-專注-專業(yè)#include #include #include

6、 typedef int ElemType;#include test6_Seq.htypedef struct List ElemType *list; int size; int MaxSize; SeqList;void main()SeqList L;int n,m,i,j;printf(輸入人數(shù) n, 首次報數(shù)人編號i, 初始報數(shù)上限值m :);scanf(%d%d%d,&n,&i,&m);InitList (L);for(j=0;jn;j+)InsertList(L,j+1,0);for(j=0;jn;j+)cout L.listj endl;/Josephusint count=

7、0,k=0,no=1,item;j=i-1;while(count=n)j=0;while(jn)if(L.listj!=0)k+;if(k=m)printf(No%d: %dn, no, L.listj);k=0;count+;no+;m=L.listj;L.listj=0;DeleteList(L,item,L.listj);j+;ClearList(L);test6_Seq.hvoid InitList(SeqList &L) /初始化線性表 L.MaxSize=100; L.list=new ElemTypeL.MaxSize; if(L.list=NULL) cout動態(tài)可分配的存儲

8、空間用完，退出運行！endl; exit(1); L.size=0;void ClearList(SeqList &L) /清除線性表 if(L.list!=NULL) delete L.list; L.list=NULL; L.MaxSize=0; L.size=0;bool InsertList(SeqList &L, ElemType item, int pos) /按給定條件pos向線性表插入一個元素if(posL.size+1)coutpos值無效!endl; return false;int i;if(pos=0)for(i=0;iL.size;i+)if(itemL.listi)

9、 break;pos=i+1;else if(pos=-1) pos=L.size+1;if(L.size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout動態(tài)可分配的存儲空間用完，退出運行！=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.size+;return true;bool DeleteList(List &L,ElemType &item,int pos) if(L.size=0) co

10、ut線性表為空，刪除無效endl; return false; if(posL.size )coutpos值無效endl;return false;int i; /根據(jù)pos值，確定需刪除元素的位置，使下標(biāo)保存到pos中if(pos=0) /查找刪除for(i=0;iL.size ;i+) if(item=L.listi) break;if(i=L.size) return false;pos=i+1;else if(pos=-1) pos=L.size ; /表尾元素刪除item=L.listpos-1; /被刪元素保存返回/從被刪元素后開始依次前移，即從下標(biāo)pos開始移動for(i=pos

11、;iL.size ;i+)L.list i-1=L.list i;L.size -; /長度減1/調(diào)整線性表空間，空余太多，小于40%時調(diào)整if(float(L.size )/L.MaxSize 10)int k=sizeof(ElemType);L.list =(ElemType *)realloc(L.list ,L.MaxSize *k/2); L.MaxSize =L.MaxSize /2; /新長度空間return true; /成功2. 鏈?zhǔn)絫est6_Link.cpp#include #include typedef struct LNode int code; int num;

12、 struct LNode *next; LNode;#include test6_Link.hvoid main() int m,n,s; printf(輸入人數(shù) n, 首次報數(shù)人編號i, 初始報數(shù)上限值m :);scanf(%d%d%d,&n,&s,&m);josephus(n,m,s);test6_Link.hvoid josephus(int n,int m,int s)struct LNode *head;struct LNode *p1,*p2; int i,j; p1=(struct LNode*)malloc(sizeof(LNode); head = p1;for(i=1;inext =(struct LNode*)malloc(sizeof(LNode); printf(輸入第 %d 個人的密碼:,i);scanf(%d,&p1-next-code);p1-next-num = i;p1 = p1-next; p1-next = head-next; p2 = head-next; delete head; for(i=1;inex