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

1、算法與數(shù)據(jù)結構試驗報告一專業(yè)班級10級計算機工程02試驗地點計算機大樓計工教研室學生學號1005080222指導教師蔡瓊學生姓名肖宇博試驗時間20GG-2-29試驗項目算法與數(shù)據(jù)結構試驗類別基礎性（） 設計性（） 綜合性（2）其它（）試 驗 目 的 及 要 求（1）掌握用VC+上機調(diào)試線性表的基本方法；（2）掌握順序表的存儲結構以及基本運算的實現(xiàn)。成績評定表類另S評分標準分值得分合計上機表現(xiàn)積極出勤、遵守紀律主動完成設計任務30分程序與報告程序代碼規(guī)范、功能止確報告詳實完整、體現(xiàn)收獲70分備注：評閱教師：日期：年 月 日試驗內(nèi)容一、實驗目的和要求1、實驗目的：（1）掌握用VC+上機調(diào)試線性表的

2、基本方法；（2）掌握順序表的存儲結構以及基本運算的實現(xiàn)。2、實驗內(nèi)容約瑟夫環(huán)問題：設編號為1 , 2, 3,n的n（n0）個人按順時針方向圍坐一圈，m為任意一個正整數(shù)。從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止并且報m的人出列，再從 他的下一個人開始重新從1報數(shù)，報到m時停止并且報m的人出 列。如此下去，直到所有人全部出列為止。要求設計一個程序模擬 此過程，對任意給定的 m和n,求出出列編號序列。3、實驗要求：用順序表實現(xiàn)。二、設計分析根據(jù)實驗要求，采用順序表來完成本次實驗。實驗中定義了兩個順序表，一個用來存儲n個人的序號，另一個用來存儲 n個人的出隊順序及序號。程序中充分考慮了如果

3、出隊的元素大于隊列的元素個數(shù)時應該有的情況，如果出現(xiàn)這樣的錯誤就提示！否則繼續(xù)出隊！三、源程序代碼#i nclude#i nclude#define MAGSIZE 10/宏替換最大值typedef structint dataMAGSIZE;int len gth;Sqlist;void CreatList(Sqlist G&L,int a,int n)/ 創(chuàng)建順序表L=(Sqlist G)malloc(sizeof(Sqlist);for(int i=0;idatai=ai;L-le ngth=n;void InitList(Sqlist G&L)/ 初始化順序表L=(Sqlist G)m

4、alloc(sizeof(Sqlist);L-le ngth=O;/釋放順序表空間/約瑟夫環(huán)的核心代碼void DestoryList(Sqlist G&L) free(L);void josephus(Sqlist G&L)int t=0;int m=0;printf（請輸入數(shù)到幾個人出來）;prin tf(n);sca nf(%d,&m);if（mL-le ngth）printf（沒有這么多人呀！、（丿_產(chǎn)）;elseprin tf(出列順序為：);for(i nt q=L-le ngth;q=1;q-)t=(t+m-1)%q;prin tf(n);prin tf(t%dt,L-datat

5、);for(i nt j=t+1;jdataj-1=L-dataj;prin tf(n);void mai n()Sqlist Gs;In itList(s);int aMAGSIZE;int n=0;printf(請鍵入要輸入幾個數(shù));prin tf(n);sca nf(%d,&n);for(int i=0;in;i+)ai=i+1;CreatList(s,a, n);josephus(s);DestoryList(s);prin tf(n);四、測試用例(盡量覆蓋所有分支)1.當輸入1 , 2 , 3, 4。n的這些數(shù)字范圍以內(nèi)的話，可以得到正確的結五、實驗總結先后學習了 C/C+,對編程

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