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

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

2、i的人開始按順時(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è)程序模擬此過程，給出出列人的編號(hào)序列?；疽?（1） 人數(shù)n、每人的正整數(shù)密碼、首次報(bào)數(shù)人編號(hào)i、初始報(bào)數(shù)上限值m均由鍵盤輸入。（2） 參照線性表的抽象數(shù)據(jù)類型定義，設(shè)計(jì)本實(shí)驗(yàn)的抽象數(shù)據(jù)類型。（3） 根據(jù)你設(shè)計(jì)的抽象數(shù)據(jù)類型，分別用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)約瑟夫環(huán)問題。并請(qǐng)分別將順序存儲(chǔ)結(jié)構(gòu)的程序存放在文件test6_Seq.h（基本操作函數(shù)）、test6_Seq.cpp（主函數(shù)）中，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的

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

4、 刪除線性表中的某個(gè)元素5約瑟夫函數(shù)四. 兩種類型（順序和鏈?zhǔn)剑┑拇鎯?chǔ)結(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)。五. 實(shí)驗(yàn)結(jié)果與分析1.順序輸出結(jié)果2.鏈?zhǔn)捷敵鼋Y(jié)果六. 心得體會(huì)（記錄實(shí)驗(yàn)感受、上機(jī)過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）1、學(xué)會(huì)通過對(duì)問題的分析，設(shè)計(jì)一種合理的數(shù)據(jù)結(jié)構(gòu)，并進(jìn)行定義及操作的實(shí)現(xiàn)2、掌握利用線性表的各種操作來進(jìn)行具體的實(shí)際應(yīng)用3、加強(qiáng)程序設(shè)計(jì)的能力，同時(shí)對(duì)前面所學(xué)習(xí)的只是進(jìn)行了回顧，掌握了鏈表的基本技巧【附錄-源程序】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, 首次報(bào)數(shù)人編號(hào)i, 初始報(bào)數(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動(dòng)態(tài)可分配的存儲(chǔ)

8、空間用完，退出運(yùn)行！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向線性表插入一個(gè)元素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動(dòng)態(tài)可分配的存儲(chǔ)空間用完，退出運(yùn)行！=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開始移動(dòng)for(i=pos

11、;iL.size ;i+)L.list i-1=L.list i;L.size -; /長(zhǎng)度減1/調(diào)整線性表空間，空余太多，小于40%時(shí)調(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; /新長(zhǎng)度空間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, 首次報(bào)數(shù)人編號(hào)i, 初始報(bào)數(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 個(gè)人的密碼:,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