實(shí)驗(yàn)一約瑟夫問(wèn)題實(shí)驗(yàn)報(bào)告.doc

北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)一 約瑟夫問(wèn)題學(xué)生姓名： *班 級(jí)： 20132111*班內(nèi)序號(hào)： *學(xué) 號(hào)： 201321*日 期： 2014年1月4日1 實(shí)驗(yàn)要求實(shí)驗(yàn)題目：利用循環(huán)鏈表實(shí)現(xiàn)約瑟夫問(wèn)題的求解。約瑟夫問(wèn)題如下：已知n個(gè)人（n=1）圍坐一圓桌周圍，從1開(kāi)始順序編號(hào)。從序號(hào)為1的人開(kāi)始報(bào)數(shù)，順時(shí)針數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)則重復(fù)下去，直到所有人全部出列。請(qǐng)問(wèn)最后一個(gè)出列的人的編號(hào)。實(shí)驗(yàn)?zāi)康模菏煜+語(yǔ)言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法學(xué)習(xí)指針、模板類、異常處理的使用掌握線性表的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用線性表解決實(shí)際問(wèn)題的能力2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu) 采用單循環(huán)鏈表實(shí)現(xiàn)約瑟夫問(wèn)題的求解單循環(huán)鏈表示意圖2.2關(guān)鍵算法分析1、關(guān)鍵算法首先通過(guò)尾插法建立單循環(huán)鏈表，若只有一個(gè)人，即只刪除該人即可，若多于一人，則每查到m個(gè)人時(shí)刪除該節(jié)點(diǎn)，并將循環(huán)鏈表連接好，共循環(huán)n-1次，每次刪除均返回被刪數(shù)值。2、代碼詳細(xì)分析：1).指針結(jié)構(gòu)、類的聲明struct Node /創(chuàng)立節(jié)點(diǎn) int number; Node *next; ; class Joseph /建立Joseph類 private: int n; int m; Node *front ; /front頭指針public: Joseph(int nn, int mm); /構(gòu)造函數(shù) Joseph(); /析構(gòu)函數(shù) void Delete(); /刪除函數(shù); 2）.單循環(huán)鏈表的建立 Joseph:Joseph(int nn, int mm) /構(gòu)造函數(shù)，建立循環(huán)鏈表 n=nn; m=mm; Node *p,*rear; /建立兩個(gè)指針.尾插法，p2始終指向?yàn)楣?jié)點(diǎn) for(int i=1; inumber=i; if(i=1) /建立空鏈表 front=p; rear=p; else rear-next=p; rear=p; rear-next=front; /尾指向頭，循環(huán)完成 算法： 設(shè)兩個(gè)指針p,rear, rear為尾節(jié)點(diǎn)，p為新增加的節(jié)點(diǎn) 若是空鏈表，則front=p; rear=p; 否則用尾插法,即p 在rear的后面，將p給rear;rear-next=p; rear=p; 頭結(jié)點(diǎn)賦給rear的指針域，完成循環(huán)循環(huán)次數(shù)為n, 時(shí)間復(fù)雜度為O（n）3）. 輸入值異常的情況coutn;if (n1) /考慮n輸入錯(cuò)誤的情況coutn值輸入錯(cuò)誤endl;coutm;if (m1) /考慮m輸入異常的情況coutm值輸入錯(cuò)誤endl;4）.尋找一定間隔的人，并將其刪除void Joseph:Delete() /刪除人員的函數(shù) Node *p1,*p2,*p; int count; /用來(lái)計(jì)數(shù) p1=front; /頭結(jié)點(diǎn)給p1if(m=1)cout最后一個(gè)人的編號(hào)為nendl;elsecout每次被刪除的人為endl; for(int i=1; i=n-1; i+) /共刪除n-1個(gè)人，循環(huán)n-1次 count=1; while(countnext; /p1向后移 count+; coutnumbernext=p1-next; p1=p1-next; /p1后移，防止刪除后指針懸掛 delete p; coutendl; cout最后一個(gè)人的編號(hào)為 numbernext; p2始終指向第一個(gè)節(jié)點(diǎn) 摘鏈，將p指向待刪除的p1，即將p1元素從鏈表中摘除： 輸出p1的數(shù)值 釋放p元素：delete p;循環(huán)次數(shù)為m(n-1), 時(shí)間復(fù)雜度為O（n）5）析構(gòu)函數(shù)Joseph:Joseph() /析構(gòu)函數(shù) delete front; front=NULL; 6）主函數(shù)void main() int n,m; coutn; coutm; Joseph joseph(n,m); joseph.Delete(); 3. 程序運(yùn)行結(jié)果測(cè)試主函數(shù)流程： 開(kāi)始等待用戶輸入輸入值是否有效 是查找刪除節(jié)點(diǎn)循環(huán)次數(shù)是否大于n-1次 是輸出最后一個(gè)數(shù)值結(jié)束流程圖示意圖1、 測(cè)試條件：n數(shù)量級(jí)無(wú)限制 2、 測(cè)試結(jié)論4. 總結(jié)由于是第一次做數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)，而上學(xué)期的C+也因長(zhǎng)時(shí)間沒(méi)有碰過(guò)而稍顯手生，在碼程序的過(guò)程中遇到了很多問(wèn)題，但通過(guò)翻看教材已基本解決。約瑟夫雖然構(gòu)思起來(lái)比