數(shù)據(jù)結(jié)構(gòu)實踐報告剖析

1、冬M哪范學ftANYANG NORMAL UNIVERSITY數(shù)據(jù)結(jié)構(gòu)實踐報告學 號：150906112姓名：武錦蓉班級：NET2班指導老師：田喜平時 間：2016-12-21項目名稱一、項目構(gòu)思程序由三個模塊組成：（1） 輸入模塊：無提示語句，直接輸入總?cè)藬?shù) n和報數(shù)次數(shù)m,中間用逗 號隔開。（2）處理模塊：將元素儲存于順序表中。在主函數(shù)中根據(jù)報數(shù)間隔確定需 要刪除的元素的位置，在順序表中設(shè)置該位置并刪除該位置，同時輸出該位 置的值。反復設(shè)置并刪除直到表空。（3）輸出模塊：分別在DOS下和文件中，按移除元素的順序依次顯示其位 置。約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置， 而這種數(shù)據(jù)是存在“第一元

2、素、 最后元素”，并且存在“唯一的前驅(qū)和后繼的”，符合線性表的特點。由于需 要模擬約瑟夫環(huán)的出列問題，可以采用順序表來實現(xiàn)線性表，完成出列順序 的輸出。核心算法主要分為兩步：1、確定需要刪除的位置，2、設(shè)置并刪除該位置。已知報數(shù)間隔m,我們可以把當前位置加上 m獲得需要刪除的位置，如 果獲得的位置超過順序表中實際元素的總長度，則可以通過減去數(shù)組的實際 長度來修正（即模擬環(huán)狀計數(shù)）。然后把順序表中的當前指向位置設(shè)置為該 位置，繼而刪掉該位置。反復進行上述確定位置和刪除位置的操作，直到順序表為空。程序主要功能模塊1、輸入的形式和輸入值的范圍：每一次輸入的值為兩個正整數(shù)，中間用逗號隔開。 若分別設(shè)為

3、n,m，則輸入格式為：“n,m”。不對非法輸入做處理，即假設(shè)輸入都是合法的。2、輸出的形式：輸出格式1:在字符界面上輸出這n個數(shù)的輸出序列輸出格式2:將這n個數(shù)的輸出序列寫入到文件中3、程序所能達到的功能：對于輸入的約瑟夫環(huán)長度n和間隔m，輸出約瑟夫環(huán)的出列順序。4、測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。正確：輸入：10,3輸出：3 6 9 2 7 1 8 5 10 4輸入：41,3輸出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 713 20 26 34 40 8 17 29 38

4、 11 25 2 22 4 35 16 31錯誤：輸入：10 3輸出：6 8 7 1 3 4 2 9 5 10二、程序清單1、抽象數(shù)據(jù)類型的定義：為實現(xiàn)上述程序的功能，可以用整數(shù)存儲用戶的輸入。并將用戶輸入的值存儲于線性表中。線性表 ADT定義如下：ADT list數(shù)據(jù)對象：整形數(shù)據(jù)關(guān)系：線性關(guān)系，即(0w av n)?；静僮鳎篵ool remove(i nt & elem)/移除一個元素，被移除的元素賦給elem如果操作成功，返回true,否則返回falsebool isEmpty()/判斷數(shù)組的元素是否清空，空返回true否則返回falsebool setPos(i nt place)/

5、設(shè)置當前元素的位置，設(shè)置成功返回true,否則返回falseint getLe ngth()獲取數(shù)組的實際長度2、各程序模塊之間的層次(調(diào)用)關(guān)系：主函數(shù)會按設(shè)計的方法調(diào)用順序表中“獲取實際長度”、“設(shè)置需要刪除元素 的位置”、“移除該位置元素”和“判斷是否為空表”四種方法方法，使元素依次 出列，并正確結(jié)束程序。用整形存儲用戶輸入的整數(shù) 用順序表實現(xiàn)線性表：class AListprivate:int *listArray;指向數(shù)組的指針int realSize;/數(shù)組中含有元素的實際長度int fen ce;指向當前元素下標public:AList(i nt s)構(gòu)造函數(shù)，初始化數(shù)組list

6、Array=new in ts;for(i nt i=O;is;i+)listArrayi=i+1;數(shù)組值等于數(shù)組下標+1realSize=s;fen ce=O;指 向首元素bool remove(i nt & elem)/ 移除一個元素if(isEmpty()return false;/如果數(shù)組為空返回 falseelem = listArrayfe nee;for(int i=fence;i=0&place=realSize)fen ce=place;return true;return false; int getLe ngth()獲取數(shù)組長度 return realSize;；在主函數(shù)

7、中調(diào)用上述模塊的方法：ofstream fout;/文 件流fout.ope n(C:Josephus.txt);設(shè)置文件路徑 int n,m,elem,poi nt=0;scanf(%d,%d,&n,&m); 獲得用戶輸入AList alist (n);/創(chuàng)建順序表對象while(!alist.isEmpty()如果順序表不為空，繼續(xù)刪除 m=m%alist.getLe ngth();調(diào)整計數(shù)的長度 if(m=0)m=alist.getLe ngth();if(point+m-1alist.getLength()point=point+m-1; / 設(shè)置偏移位置 elsepoi nt=poi

8、 nt+m-alist.getLe ngth()-1;alist.setPos(poi nt);/設(shè)置當前需要刪除的位置 alist.remove(elem);/刪 除元素coutvvelemvv ;/DOS 輸出 foutvvelemvv;/ 文件輸出四、測試結(jié)果（截圖顯示）五、遇到的問題及解決方法1、 初始化部分為循環(huán)賦值，時間復雜度為 (n)。2、處理部分，我為了提高效率沒有采用循環(huán)尋找的方法，直接利用數(shù)學關(guān) 系通過當前位置獲得下一位置，因此對于長度為n的約瑟夫環(huán)，只做了 n次定位， 每次定位的復雜度為 (1)，所以時間復雜度為 (n)。但是用順序表實現(xiàn)時，每次其移除的方法是時間復雜度為 (k)的(k與實際長 度有關(guān))，所以處理部分總的結(jié)果是( 血)的，化簡后時間復雜度仍然為 (n2)。2綜上，該算法的時間代價為 (n2)。(PS:如果是用循環(huán)查找，在 n次定位中每次都使用了 m次的循環(huán)，至少 是(n*m)，然后再用順序表的移除方法，總的復雜度應(yīng)該是(m*n2)的。)事實上要用線性表來完成這道題，其復雜度最好也是 (n2)的，畢竟對于n 個數(shù)據(jù)，每個都要進行時間復雜