北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一約瑟夫問題實(shí)驗(yàn)報(bào)告(遞歸做法)

北京郵電大學(xué)信息與通信工程學(xué)院第2頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)一——線性表學(xué)生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：1．實(shí)驗(yàn)要求（1）實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面四個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法學(xué)習(xí)指針、模板類、異常處理的使用掌握線性表的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用線性表解決實(shí)際問題的能力（2）實(shí)驗(yàn)內(nèi)容利用循環(huán)鏈表實(shí)現(xiàn)約瑟夫問題的求解。約瑟夫問題如下：已知n個(gè)人（n>=1）圍坐一圓桌周圍，從1開始順序編號(hào)。從序號(hào)為1的人開始報(bào)數(shù)，順時(shí)針數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)則重復(fù)下去，直到所有人全部出列。請(qǐng)問最后一個(gè)出列的人的編號(hào)。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)為單循環(huán)鏈表，線性表簡(jiǎn)稱表，是由零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。鏈表為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)元素值的同時(shí)，還要存儲(chǔ)該元素的直接后繼元素的位置信息，這兩部分信息構(gòu)成了實(shí)際的存儲(chǔ)結(jié)構(gòu)，稱為結(jié)點(diǎn)。此循環(huán)鏈表只為解決約瑟夫問題，所以有參構(gòu)造函數(shù)讓尾指針存儲(chǔ)著最后一個(gè)元素的數(shù)據(jù)，然后指向第一個(gè)元素，形成單循環(huán)鏈表。如圖：a3a2……ana1a3a2……ana1（（rear）2.2關(guān)鍵算法分析1．關(guān)鍵算法約瑟夫問題的實(shí)質(zhì)就是在含n個(gè)元素的循環(huán)鏈表中依次刪除第m個(gè)元素，返回鏈表中最后一個(gè)元素值。即用含那n個(gè)元素的數(shù)組初始化循環(huán)鏈表，從第一個(gè)元素開始查找第m-1個(gè)元素，刪除第m個(gè)元素，然后從第m+1個(gè)元素開始繼續(xù)查找第m-1個(gè)元素，刪除第m個(gè)元素，循環(huán)此過程直到鏈表中只剩下最后一個(gè)元素。關(guān)鍵算法偽代碼如下：[1]讓用戶輸入要?jiǎng)h第幾個(gè)元素和總?cè)藬?shù)n，并給含n個(gè)元素的數(shù)組賦值；[2]用含n個(gè)元素的數(shù)組初始化循環(huán)鏈表（頭插法）；[3]調(diào)用單循環(huán)表類的刪除函數(shù)，實(shí)參為數(shù)組和尾指針的下一結(jié)點(diǎn)（即第一個(gè)元素）；[3.1]定義新結(jié)點(diǎn)p，用以存儲(chǔ)要?jiǎng)h除的結(jié)點(diǎn)；[3.2]進(jìn)行循環(huán)找到要?jiǎng)h除元素的上一結(jié)點(diǎn)；[3.3]初始化指針p指向b->next，p的指針域指向b的指針域，第m個(gè)元素摘鏈，刪除p，指針b后移，人數(shù)n自減1；[3.4.1]判斷如果n等于1，輸出剩下一元素的序號(hào)，然后刪除最后一結(jié)點(diǎn)，此為遞歸結(jié)束條件；[3.4.2]判斷如果n大于1，則進(jìn)行自身遞歸調(diào)用，直至遇到結(jié)束條件停止；[3.4.3]如果n等于0，即一開始鏈表只有一個(gè)結(jié)點(diǎn)，輸出“無人剩下！”；2.代碼詳細(xì)分析:（1）刪除操作的算法步驟：①從第一個(gè)結(jié)點(diǎn)開始，查找第m-1個(gè)元素，設(shè)為b指向該結(jié)點(diǎn)；②設(shè)p指向第i個(gè)元素：p=b->next;③摘鏈，即將b元素從鏈表中摘除：b->next=p->next;④釋放q元素：deleteq;(2)遞歸調(diào)用算法步驟：①判斷如果n等于1，輸出剩下一元素的序號(hào)，然后刪除最后一結(jié)點(diǎn)，此為遞歸結(jié)束條件：if(n==1){cout<<”剩下一人的序號(hào)：”<<b->next->data<<endl;deleteb;}②判斷如果n大于1，則進(jìn)行自身遞歸調(diào)用，直至遇到結(jié)束條件停止:elseif(n>1)Delete(m,b->next,n);③如果n等于0，即一開始鏈表只有一個(gè)結(jié)點(diǎn)，輸出“無人剩下！”:elseif(n==0) { cout<<"無人剩下!"<<endl; system("pause"); }3．時(shí)間復(fù)雜度的計(jì)算[1]O(n)[2]O(n)[3]O(1)[3.1]O(1)[3.2]O(m)[3.3]O(1)[3.4.1]O(1)[3.4.2]O(n*m)[3.4.3]O(1)2.3其他（1）在此需要說明的是，在初始化鏈表時(shí)，特使用了頭插法，并對(duì)頭插法做了相應(yīng)的修改。使尾指針rear存儲(chǔ)著最后一個(gè)結(jié)點(diǎn)。偽代碼如下：[1]用含n個(gè)元素的數(shù)組a[]初始化循環(huán)鏈表；[2]尾指針的data域存儲(chǔ)最后一個(gè)結(jié)點(diǎn)a[n-1]；[3]進(jìn)行循環(huán)初始化新結(jié)點(diǎn)s存儲(chǔ)a[i];[4]s->next=rear->next;[5]rear指向s:rear->next=s;（2）在這里為了使代碼簡(jiǎn)潔，在刪除函數(shù)里使用了遞歸調(diào)用，結(jié)束條件時(shí)只剩一個(gè)人時(shí)，并輸出該人序號(hào)。3.程序運(yùn)行結(jié)果1．流程流程圖如下：開始開始調(diào)用單循環(huán)表類的刪除函數(shù)，實(shí)參為數(shù)組和尾指針的下一結(jié)點(diǎn)調(diào)用單循環(huán)表類的刪除函數(shù)，實(shí)參為數(shù)組和尾指針的下一結(jié)點(diǎn)定義新結(jié)點(diǎn)p，用以存儲(chǔ)要?jiǎng)h除的結(jié)點(diǎn)定義新結(jié)點(diǎn)p，用以存儲(chǔ)要?jiǎng)h除的結(jié)點(diǎn)查找第m-1個(gè)元素，刪除第m查找第m-1個(gè)元素，刪除第m個(gè)元素，指針b后移，人數(shù)n減1判斷判斷人數(shù)nn>1n=0n=1n>1n=0n=1進(jìn)行自身遞歸調(diào)用進(jìn)行自身遞歸調(diào)用如果n等于0，即一開始鏈表只有一個(gè)結(jié)點(diǎn)，輸出“無人剩下！”判斷如果n等于1，輸出剩下一元素的序號(hào)，然后刪除最后一結(jié)點(diǎn)判斷如果n等于1，輸出剩下一元素的序號(hào)，然后刪除最后一結(jié)點(diǎn)結(jié)束結(jié)束2．測(cè)試條件：人數(shù)n和刪除數(shù)m必須為整數(shù)。3.測(cè)試結(jié)論：4.總結(jié)（1）調(diào)試時(shí)出現(xiàn)的問題及解決方法①在調(diào)試時(shí)出現(xiàn)了執(zhí)行錯(cuò)誤，在析構(gòu)函數(shù)中設(shè)置了斷點(diǎn)。在執(zhí)行時(shí)，發(fā)現(xiàn)析構(gòu)函數(shù)停不下來，原來在刪除函數(shù)里已經(jīng)析構(gòu)到只剩一個(gè)結(jié)點(diǎn)，而且尾指針可能已經(jīng)被刪除，所以我去掉了析構(gòu)函數(shù)，而在輸出最后一個(gè)結(jié)點(diǎn)后析構(gòu)該結(jié)點(diǎn)。②在執(zhí)行時(shí)發(fā)現(xiàn)剩下一人的序號(hào)不對(duì)，在刪除函數(shù)的摘鏈操作中設(shè)置了斷點(diǎn)，在執(zhí)行時(shí)，發(fā)現(xiàn)每次刪除的結(jié)點(diǎn)不正確，原來刪除函數(shù)的實(shí)參錯(cuò)誤寫為了尾指針，該為第一個(gè)結(jié)點(diǎn)后程序正確。（2）心得體會(huì)在本次實(shí)驗(yàn)中，熟悉了單循環(huán)鏈表的各種基本操作，特別對(duì)插入操作、查找操作和刪除操作有了較深的理解。對(duì)于數(shù)組和指針的用法也更熟練，在程序的調(diào)試和異常處理方面有了一定的經(jīng)驗(yàn)。相信在本次實(shí)驗(yàn)中積累的經(jīng)驗(yàn)、提高的能力將在今后的實(shí)驗(yàn)中展現(xiàn)出來。尤其在遞歸函數(shù)的使用方面有了很大的提高，熟悉了遞歸函數(shù)使用條件，了解了要設(shè)置遞歸結(jié)束條件。（3）下一步的改進(jìn)程序有的代碼不夠簡(jiǎn)潔，可以寫得更簡(jiǎn)潔，可能還有更好的方法，此程序把尾指針存儲(chǔ)了一個(gè)元素，違反了尾指針的原意，可以進(jìn)一步改進(jìn)。附代碼：//ClinkList.h#include<iostream>usingnamespacestd;template<classT>structNode//儲(chǔ)存節(jié)點(diǎn)的結(jié)構(gòu){ Tdata; structNode<T>*next;};template<classT>classClinkList//單循環(huán)鏈表類{public: ClinkList(){rear=newNode<T>;rear->next=rear;}//無參構(gòu)造函數(shù) ClinkList(Ta[],intn);//有參構(gòu)造函數(shù) voidDelete(intm,Node<T>*b,intn);//刪除結(jié)點(diǎn)函數(shù) Node<T>*rear;//尾指針};template<classT>ClinkList<T>::ClinkList(Ta[],intn)//頭插法{ rear=newNode<T>; rear->next=rear; rear->data=a[n-1]; for(inti=n-2;i>=0;i--) { Node<T>*s=newNode<T>; s->data=a[i]; s->next=rear->next; rear->next=s; }}template<classT>voidClinkList<T>::Delete(intm,Node<T>*b,intn){ Node<T>*p; for(intj=0;j<(m-2+n)%n;j++)//找到要?jiǎng)h結(jié)點(diǎn)的前一結(jié)點(diǎn) { b=b->next;}p=b->next; b->next=p->next;deletep; n--; if(n==1)//遞歸結(jié)束條件 { cout<<"剩下一人的序號(hào)是:"<<b->next->data<<endl; system("pause"); deleteb; } elseif(n>1)Delete(m,b->next,n);//遞歸函數(shù)，遞歸刪除 elseif(n==0) { cout<<"無人剩下!"<<endl; system("pause"); }}//main.cpp#include<iostream>#include"ClinkList.h"usingnamesp