C++數(shù)據(jù)結構之約瑟夫環(huán)

1、2009級數(shù)據(jù)結構實驗報告實驗名稱：實驗線性表實現(xiàn)約瑟夫冋題求解學生姓名：桂柯易班級：2009211120班內序號：07學號:09210580日期：2010年10月31日1. 實驗要求【實驗目的】1. 熟悉C+語言的基本編程方法,掌握集成編譯環(huán)境的調試方法；2. 學習指針、模板類、異常處理的使用；3. 掌握線性表的操作實現(xiàn)方法；4. 培養(yǎng)使用線性表解決實際問題的能力?！緦嶒瀮热荨坷醚h(huán)鏈表實現(xiàn)約瑟夫問題的求解。約瑟夫問題如下：已知 n個人（n>=1 ）圍坐一圓桌周圍，從1開始順序編號。從序號 為1的人開始報數(shù)，順時針數(shù)到m的那個人出列。他的下一個人又從1開始報數(shù)，數(shù)到 m的那個人又出列

2、。依此規(guī)則重復下去，直到所有人全部出列。 請問最后一個出列的人的編號。2. 程序分析2.1存儲結構存儲結構：循環(huán)鏈表>142fa-3nk IFfirst2.2關鍵算法分析【設計思想】首先，設計實現(xiàn)約瑟夫環(huán)問題的存儲結構。由于約瑟夫環(huán)本身具有循環(huán)性質，考慮采循環(huán)鏈表的結點定義用循環(huán)鏈表，為了統(tǒng)一對表中任意節(jié)點的操作，循環(huán)鏈表不帶頭結點。為如下結構類型：struct Nodeint nu mber;Node *n ext;；其次，建立一個不帶頭結點的循環(huán)鏈表并由頭指針first指示。最后，設計約瑟夫環(huán)問題的算法?！緜未a】1、工作指針first， r，s, p, q初始化2、輸入人數(shù)(n)和

3、報數(shù)(m)3、循環(huán)n次，用尾插法創(chuàng)建鏈表Node *q;for(i nt i=1;i<=n ;i+)Node *p;p=new Node;p->nu mber=i;p-> next=NULL;if(i=1) L=q=p;elseq_>n ext=p;q=q_>n ext;q_>n ext=L;if(L!=NULL)return(L);4、 輸入報數(shù)的起始人號數(shù)k;5、Node *q = new Node;計數(shù)器初始化 i=1;6、 循環(huán)n次刪除結點并報出位置(其中第一個人后移k個) 當i<n時移動指針m-2次p=p->next;刪除p結點的后一結

4、點qq=p->n ext;p_>n ext=q _>n ext;*L = p_>n ext;報出位置后Delete q;計數(shù)器i+;【復雜度】for(i nt i=1;i<=n ;i+)Node *p;p=new Node;p->nu mber=i;p-> next=NULL;if(i=1) L=q=p;elseq_>n ext=p;q=q_>n ext;時間復雜度：O (n)if(i=1) i+=Le ngthList(*L);Node *p;p=*L;int j=0;while(j<i-2) p=p->n ext;j+;q

5、= p_>n ext;p->n ext=p->n ext->n ext;*L = p_>n ext; return(q);時間復雜度：O (n2) 算法的空間復雜度：O (n2)2.3其他程序源代碼：#in clude<iostream>using n amespace std;struct Node/循環(huán)節(jié)點的定義int number;/ 編號Node *n ext;Node *CreateList(Node *L,i nt &n,int &m);建立約瑟夫環(huán)函數(shù)void Joseph(Node *L,int n,int m);/ 輸

6、出每次出列號數(shù)函數(shù)Node *DeleteList(Node *L,i nt i,Node *q);/尋找每次出列人的號數(shù)int LengthList(Node *L);/計算環(huán)上所有人數(shù)函數(shù)void main() 主函數(shù)Node *L;L=NULL;初始化尾指針int n, m;cout<<"請輸入人數(shù) N :"cin>>n;環(huán)的長度if(* 1)cout<<"請輸入正整數(shù)!"/人數(shù)異常處理elsecout<<"請輸入所報數(shù) M :"cin»m;if(m<1)cout&

7、lt;<"請輸入正整數(shù)!"/號數(shù)異常處理elseL=CreateList(L,n,m);重新給尾指針賦值Joseph(L ,n, m);system("pause");Node *CreateList(Node *L,int &n,int & m)建立一個約瑟夫環(huán)(尾插法)Node *q;for(i nt i=1;i<=n ;i+)Node *p;p=new Node;p->nu mber=i;p-> next=NULL;if(i=1) L=q=p; 工作指針的初始化elseq_>n ext=p;q=q_&g

8、t;n ext;q_>n ext=L;if(L!=NULL)return(L);返回尾指針else cout<<"尾指針異常!"<<endl;尾指針異常處理void Joseph(Node *L,int n,int m) 輸出每次出列的人int k;cout<<"請輸入第一個報數(shù)人："cin> >k;if(k<1|k>n)cout<<"請輸入 1-"<<*<"之間的數(shù)"<<endl;elsecout<&

9、lt;"n 出列順序:n"for(i nt i=1;i< n;i+)Node *q = new Node;if(i=1) q=DeleteList (&L,k+m-1,q);第一個出列人的號數(shù)else q=DeleteList(&L,m,q);cout<<"號數(shù)："<<q->number<<endl;delete q;/釋放出列人的存儲空間cout<<"最后一個出列號數(shù)是："<<L->number<<endl;輸出最后出列人的號數(shù)

10、Node *DeleteList(Node *L,i nt i,Node *q) /尋找每次出列的人if(i=1) i+=Le ngthList(*L);順序依次出列情況的處理方式Node *p;P=*L;int j=0;while(j<i-2) p=p->n ext;j+;q = p_>n ext;p->n ext=p->n ext- >n ext;*L = p_>n ext;return(q); int LengthList(Node *L)/ 計算環(huán)上的人數(shù)if(L)cout<<"尾指針錯誤!"<<en

11、dl;異常處理elseint i=1;Node *p=L->n ext;while(p!=L)i+;p=p->n ext;return(i);3程序運行結果1.測試主函數(shù)流程：2. 測試條件：如上圖所示，人數(shù)為 20人，所報數(shù)為6,第一個報數(shù)的人是 1號。3. 測試結論：得出最后出列的人是20號，與算得的結果一致，證明程序正常運行，能夠解決一般的約瑟夫環(huán)問題。4.總結1調試時出現(xiàn)的問題及解決辦法：利用帶頭結點的尾插法建立鏈表求解的時候，頭節(jié)點的作用無法確定，導致編譯通過， 但是運行之后的結果都不是正確的運行結果。苦苦思索，包括和同學討論，一直沒能解決， 最后決定改用另一種存儲方法，將頭節(jié)點直接改成NULL，最終測試的結果是正確的。（但是還未能完全理解原因是什么）用函數(shù)返回存儲節(jié)點的地址的時候，函數(shù)中的一句沒有問題的語句出現(xiàn)訪問錯誤，更改函數(shù)從而解決了問題。2. 心得體會：這次做數(shù)據(jù)結構作業(yè)， 不僅對開學一段時間內所學的知識有了更好的理解，而且很好地鍛煉了自己的編程能力。 發(fā)現(xiàn)心中了解程序的主要算法和真正寫出來完全不是一回事，一開始做多項式