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

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

3、順序及序號。程序中充分考慮了如果出隊的元素大于隊列的元素個數時應該有的情況，如果出現這樣的錯誤就提示！否則繼續出隊！3、源程序代碼#include #include #define MAXSIZE 10 / 宏替換最大值typedef structint dataMAXSIZE;int length;Sqlist;void CreatList(Sqlist *&L,int a,int n /創建順序表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 /約瑟夫環的核心代碼int t=0;int m=0;printf("請輸入數到幾個人出來"printf("n"scanf("%d",&m;if(m>L->lengthprintf("沒有這么多人呀！(_"elsepri

5、ntf("出列順序為："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("請鍵入要輸入幾個數"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.當輸入1，2，3，4。n的這些數字范圍以內的話，可以得到正確的結果如圖：2.當輸入的n比較大的時候的情況如圖：3.當輸入序列少，出對數大時:4.當輸入要出列的元素大于隊列里的元素，這將會提示錯誤如圖：5.當你的輸入出隊的序列數有誤時將會提示錯誤6.當你的要輸入的數大于定義的最大值時提示錯誤如圖：7.當你的要輸入的數小于定義的最大值時提示錯誤如圖：五、實驗

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