2023年數(shù)據(jù)結(jié)構(gòu)約瑟夫環(huán)實(shí)驗(yàn)報(bào)告新編

他僅沖洗石n《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告書姓名：徐鑫

學(xué)號(hào)：專業(yè):物聯(lián)網(wǎng)工程班級(jí):16042023年10月15日一、實(shí)驗(yàn)?zāi)康?掌握線性表特性.純熟掌握線性表的基本操作.運(yùn)用線性表設(shè)計(jì)算法并實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容.解決約瑟夫環(huán)問題：已知n個(gè)人（以編號(hào)1,2,3...n分別表達(dá)）圍坐在一張圓桌周邊。從編號(hào)為k的人開始報(bào)效，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律反復(fù)下去，直到圓桌周邊的人所有出列。.基本規(guī)定：1）根據(jù)題目規(guī)定設(shè)計(jì)解決約瑟夫環(huán)應(yīng)用問題的數(shù)據(jù)結(jié)構(gòu)。2）規(guī)定采用C++編程語言實(shí)現(xiàn)設(shè)計(jì)的算法。三、設(shè)計(jì)思緒.數(shù)據(jù)邏輯關(guān)系的分析。。令將人的順序簡(jiǎn)樸編號(hào)，從1到n;。o中構(gòu)造一個(gè)循環(huán)鏈表，可以解決首位相連的問題；他將人的編號(hào)插入到結(jié)構(gòu)體的Data域中；電遍歷人的編號(hào)，輸出參與的人的編號(hào)；中開始報(bào)數(shù)，從頭報(bào)數(shù)，報(bào)到k的人出局（刪除此結(jié)點(diǎn)），并釋放此結(jié)點(diǎn)。直到人數(shù)只有一個(gè)人時(shí)，退出循環(huán)，輸出獲勝的人。.存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)\pre\p,count=2（建立約瑟夫環(huán)）

preP（循環(huán)結(jié)束條件）preP.算法的核心思想說明口擬定需要?jiǎng)h除的位置；口。設(shè)立并刪除該位置。已知報(bào)數(shù)間隔m,我們可以把當(dāng)前位置加上m獲得需要?jiǎng)h除的位置，假如獲得的位置超過順序表中實(shí)際元素的總長(zhǎng)度，則可以通過減去數(shù)組的實(shí)際長(zhǎng)度來修正修正（即模擬環(huán)狀計(jì)數(shù)）。然后把順序表中的當(dāng)前指向位置設(shè)立為該位置，繼而刪掉該位置。反復(fù)進(jìn)行上述擬定位置和刪除位置的操作，直到順序表為空。四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1.類的聲明和定義（規(guī)定給出完整的類聲明和核心成員函數(shù)的定義）30#ifndefJoseph_H#defineJoseph_H#include<iostream>usingnamespacestd;structNode//結(jié)點(diǎn)(&intdata;〃存儲(chǔ)數(shù)據(jù)ao&Node*next；〃下一個(gè)節(jié)點(diǎn)的地址I；CircularLinkList//單向循環(huán)鏈表類classpublCircularLinkList//單向循環(huán)鏈表類。?first=newNode;ofirst->data=NULL;ofirst->next=first;g}a?Circu1arLinkList(){dcletefinavoidCreateLinkList(inta[],intn)；，3VoidPrintLinkList();〃遍歷鏈表avoidJoseph(intk,in(n);〃約瑟夫環(huán)實(shí)現(xiàn)privatc:aaNode*first;)；#endif2.算法實(shí)現(xiàn)#includc"JoSeph.h"include<windows,h>inc1ude<iomanip>voidCircularLinkList:：CreateLi(gNode*s,*r=尾指針初始化。。for(inti=0；i<n;i++)//尾插法00{8。s=newNode；，s->data=a[i]；)〃析構(gòu)函數(shù)//創(chuàng)建單向循環(huán)鏈表)〃析構(gòu)函數(shù)//創(chuàng)建單向循環(huán)鏈表nkList(inta[],intn)r->next=first->nexl;//循環(huán))voidCircu1arLinkList::PrintLinkList()(。。intcount=0;〃計(jì)數(shù)器Node*r=first->next：gdo{。cout?setw(3)?r—>data;維ount++；。r=r->next;。if(count%10==0)o?cout?endl<<"。。。}while(r!=first->next);//當(dāng)鏈表循環(huán)到第一節(jié)點(diǎn)時(shí)跳出循環(huán)w?cout?end1；)voidCircularLinkList::Joseph(intk,intn)(intm；。cout?"請(qǐng)輸入約瑟夫密碼："；gein輸入約瑟夫密碼?Node*pre,*p;。pre=first;//工作指針初始化。p—prc->ncxt;ofor(inti=0;i<k-l;i++)

000000pre=00pre=prc->next;"0Iointcount=1;//計(jì)數(shù)器初始化，約瑟夫問題至少有兩個(gè)成員00COUt?***************************丈火**大******************?whiIe(pre!=p)00{。-if(count==m)//假如計(jì)數(shù)器等于密碼皿。。Sleep(l*1000)，執(zhí)行掛起一段時(shí)間(1秒)。cout<<setw(26)?p->datavv"號(hào)死亡!"vvendl;〃顯示結(jié)果。Node*Q=p;g?pre—>next=p->next;。。。de1eteq;//刪除死亡結(jié)點(diǎn)°gp=pre->next;。?count=1J/計(jì)數(shù)器重新計(jì)數(shù)00)空Ise。(gopre=pre->next;〃工作指針后移3g叩=p->next;8gcount++;//計(jì)數(shù)器加一0oJ?cout?************************************************大**\n?cout?，cout?setw(26)<<p—>datavv"號(hào)存活！"<<endl；//顯示最后存活的^deletep;//刪除結(jié)點(diǎn)p?system("pause")；)五、程序測(cè)試與實(shí)現(xiàn).程序在調(diào)試過程中出現(xiàn)的問題及解決辦法.程序運(yùn)營(yíng)過程及結(jié)果界面血C:\Windows\system32\cmd.exe—□X》》約瑟夫環(huán)游戲《《一〉請(qǐng)輸入?yún)⑴c人數(shù)：6國(guó)C:\Windows\system32\cmd.exe—□X》》約瑟夫環(huán)游戲《《—>>請(qǐng)輸入?yún)⑴c人數(shù)：6對(duì)所有人進(jìn)行編號(hào)?。【幪?hào)如下：123456一>>請(qǐng)輸入從第幾人開始：2六、實(shí)驗(yàn)調(diào)試SBC:\Windows\system32\cmd.exe》》約瑟夫環(huán)游戲《《—>>請(qǐng)輸入?yún)⑴c人數(shù)：6對(duì)所有人進(jìn)行編號(hào)！！編號(hào)如下：123456一〉請(qǐng)輸入從第幾人開始：2一分請(qǐng)輸入約瑟夫密碼：45號(hào)死亡!3號(hào)死亡!2號(hào)死亡!4號(hào)死亡!1號(hào)死亡!6號(hào)存活!請(qǐng)按任意鍵繼續(xù)..?搜狗拼音輸入法全：七、問題及解決方法問題：無法從第k個(gè)人開始報(bào)數(shù)。解決方法：用while循環(huán)，找尋開始報(bào)教的編號(hào)k,找到后把他報(bào)的數(shù)標(biāo)記為1.問題：將LinkList.h文獻(xiàn)的LinkList類中的行為函數(shù)放進(jìn)LinkList.cpp文獻(xiàn)中出現(xiàn)錯(cuò)誤“重定義”。解決辦法:將行為函數(shù)的定義與聲明均放進(jìn)LinkList.h文獻(xiàn)中。八、心得體會(huì)通過對(duì)約瑟夫環(huán)問題算法的設(shè)計(jì)，我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解，進(jìn)一步的理解了課本