實驗一約瑟夫問題實驗報告.doc

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