順序表實(shí)現(xiàn)約瑟夫環(huán)的問題,C語言

1、計(jì)算機(jī)科學(xué)與工程學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告一專業(yè)班級(jí)10級(jí)計(jì)算機(jī)工程02試驗(yàn)地點(diǎn)計(jì)算機(jī)大樓計(jì)工教研室學(xué)生學(xué)號(hào)1005080222指導(dǎo)教師蔡瓊學(xué)生姓名肖宇博試驗(yàn)時(shí)間2012-2-29試驗(yàn)項(xiàng)目算法與數(shù)據(jù)結(jié)構(gòu)試驗(yàn)類別基礎(chǔ)性（） 設(shè)計(jì)性（） 綜合性（） 其它（ ）試驗(yàn)?zāi)康募耙螅?）掌握用VC+上機(jī)調(diào)試線性表的基本方法； （2）掌握順序表的存儲(chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)。成 績 評(píng) 定 表類 別評(píng) 分 標(biāo) 準(zhǔn)分值得分合 計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律主動(dòng)完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分備注：評(píng)閱教師： 日 期： 年 月 日試 驗(yàn) 內(nèi) 容一、實(shí)驗(yàn)?zāi)康暮鸵?、實(shí)驗(yàn)

2、目的：（1）掌握用VC+上機(jī)調(diào)試線性表的基本方法； （2）掌握順序表的存儲(chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)。2、實(shí)驗(yàn)內(nèi)容約瑟夫環(huán)問題：設(shè)編號(hào)為1，2，3，n的n(n>0個(gè)人按順時(shí)針方向圍坐一圈，m為任意一個(gè)正整數(shù)。從第一個(gè)人開始順時(shí)針方向自1起順序報(bào)數(shù)，報(bào)到m時(shí)停止并且報(bào)m的人出列，再從他的下一個(gè)人開始重新從1報(bào)數(shù)，報(bào)到m時(shí)停止并且報(bào)m的人出列。如此下去，直到所有人全部出列為止。要求設(shè)計(jì)一個(gè)程序模擬此過程，對任意給定的m和n，求出出列編號(hào)序列。3、實(shí)驗(yàn)要求：用順序表實(shí)現(xiàn)。2、設(shè)計(jì)分析根據(jù)實(shí)驗(yàn)要求，采用順序表來完成本次實(shí)驗(yàn)。實(shí)驗(yàn)中定義了兩個(gè)順序表，一個(gè)用來存儲(chǔ)n個(gè)人的序號(hào)，另一個(gè)用來存儲(chǔ)n個(gè)人的出隊(duì)

3、順序及序號(hào)。程序中充分考慮了如果出隊(duì)的元素大于隊(duì)列的元素個(gè)數(shù)時(shí)應(yīng)該有的情況，如果出現(xiàn)這樣的錯(cuò)誤就提示！否則繼續(xù)出隊(duì)！3、源程序代碼#include #include #define MAXSIZE 10 / 宏替換最大值typedef structint dataMAXSIZE;int length;Sqlist;void CreatList(Sqlist *&L,int a,int n /創(chuàng)建順序表L=(Sqlist *malloc(sizeof(Sqlist;for(int i=0;i L->datai=ai;L->length=n;void InitList(Sqli

4、st *&L /初始化順序表L=(Sqlist *malloc(sizeof(Sqlist;L->length=0;void DestoryList(Sqlist *&L /釋放順序表空間free(L;void josephus(Sqlist *&L /約瑟夫環(huán)的核心代碼int t=0;int m=0;printf("請輸入數(shù)到幾個(gè)人出來"printf("n"scanf("%d",&m;if(m>L->lengthprintf("沒有這么多人呀！(_"elsepri

5、ntf("出列順序?yàn)椋?quot;for(int q=L->length;q>=1;q-t=(t+m-1%q;printf("n"printf("t%dt",L->datat;for(int j=t+1;j<=q-1;j+L->dataj-1=L->dataj;printf("n"void main(Sqlist *s;InitList(s;int aMAXSIZE;int n=0;printf("請鍵入要輸入幾個(gè)數(shù)"printf("n"scanf(

6、"%d",&n;for(int i=0;i ai=i+1;CreatList(s,a,n;josephus(s;DestoryList(s;printf("n"四、測試用例（盡量覆蓋所有分支）1.當(dāng)輸入1，2，3，4。n的這些數(shù)字范圍以內(nèi)的話，可以得到正確的結(jié)果如圖：2.當(dāng)輸入的n比較大的時(shí)候的情況如圖：3.當(dāng)輸入序列少，出對數(shù)大時(shí):4.當(dāng)輸入要出列的元素大于隊(duì)列里的元素，這將會(huì)提示錯(cuò)誤如圖：5.當(dāng)你的輸入出隊(duì)的序列數(shù)有誤時(shí)將會(huì)提示錯(cuò)誤6.當(dāng)你的要輸入的數(shù)大于定義的最大值時(shí)提示錯(cuò)誤如圖：7.當(dāng)你的要輸入的數(shù)小于定義的最大值時(shí)提示錯(cuò)誤如圖：五、實(shí)驗(yàn)

7、總結(jié)先后學(xué)習(xí)了C/C+,對編程語言基本上有一些了解，但在數(shù)據(jù)結(jié)構(gòu)試驗(yàn)程序設(shè)計(jì)過程中還是學(xué)到了很多。經(jīng)過兩天的設(shè)計(jì)，在不斷翻閱以前資料的情況下，有針對性的復(fù)習(xí)了C/C+中指針、循環(huán)的相關(guān)理論知識(shí)和vc6.0的基礎(chǔ)知識(shí)和應(yīng)用技巧，最后比較成功的完成了本次的設(shè)計(jì)。本次設(shè)計(jì)是運(yùn)用已學(xué)的線性表中順序表的相關(guān)內(nèi)容，由于以前的指針方面知識(shí)沒有學(xué)好，剛開始時(shí)有些措手不及，尤其是運(yùn)用指針申請動(dòng)態(tài)內(nèi)存，遇到了不小的麻煩，程序檢查時(shí)沒有錯(cuò)誤，但運(yùn)行不了，經(jīng)過仔細(xì)的思考，終于發(fā)現(xiàn)了問題所在，特別高興。程序運(yùn)行后，開始考慮各種BUG，比如輸入的數(shù)大于數(shù)組定義的最大值的時(shí)候抑或是數(shù)組的數(shù)小于應(yīng)該輸入的最小值（比如0），比如輸入的要出列的元素大于隊(duì)列中已有的元素抑或是小于數(shù)組中應(yīng)該出現(xiàn)的元素，比如一些錯(cuò)誤輸入等等之內(nèi)的BUG 都考慮之后的問題。然后思考與反思后，發(fā)現(xiàn)程序還是有美中不足的地方，算法的核心存在一些不足，比如依次從后往前挪動(dòng)一個(gè)元素的時(shí)候存在一些效率上的問題，當(dāng)元素較多時(shí)，效率不高！考慮到可以采用標(biāo)記法，把出隊(duì)元素標(biāo)記為0，以后的出隊(duì)的時(shí)候跳過0，而不是進(jìn)行挪動(dòng)，這樣程序的效率就大大提高了！本次實(shí)驗(yàn)運(yùn)用的是C語言，大一時(shí)就學(xué)過了，