大數(shù)據(jù)結(jié)構(gòu)實踐報告材料

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

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

3、格式為：“n,m ”。 不對非法輸入做處理，即假設輸入都是合法的。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 3237 41 7 13 20 26 34 40 8

4、17 29 38 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ù)關系：線性關系，即 <ai,ai+1>(0 a<n) ?；静僮鳎篵ool remove(int &elem)/ 移除一個元素，被移除的元素賦給 elem/ 如果操作成功，返回 true, 否則返回 falsebool isEmpty()/ 判斷數(shù)組的元素是否清空，

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

6、nt fence;/ 指向當前元素下標public:AList(int s)/ 構(gòu)造函數(shù)，初始化數(shù)組listArray=new ints;for(int i=0;i<s;i+)listArrayi=i+1;/ 數(shù)組值等于數(shù)組下標 +1realSize=s;fence=0;/ 指向首元素bool remove(int &elem)/ 移除一個元素if(isEmpty()return false;/ 如果數(shù)組為空返回 false elem = listArrayfence;從當前位置開始循環(huán)向前賦值for(int i=fence;i<realSize-1;i+)/ listAr

7、rayi=listArrayi+1;realSize-;return true;bool isEmpty()/ 判斷數(shù)組的元素是否清空if(realSize=0)return true;else return false;bool setPos(int place)/ 設置當前元素的位置if(place>=0&&place<=realSize)fence=place;return true;return false;int getLength()/ 獲取數(shù)組長度return realSize;在主函數(shù)中調(diào)用上述模塊的方法：ofstream fout;/ 文件流 fo

8、ut.open("C:Josephus.txt");/ 設置文件路徑 int n,m,elem,point=0;scanf("%d,%d",&n,&m);/ 獲得用戶輸入AList alist(n);/ 創(chuàng)建順序表對象while(!alist.isEmpty()/ 如果順序表不為空，繼續(xù)刪除 m=m%alist.getLength();/ 調(diào)整計數(shù)的長度/ 設置偏移if(m=0)m=alist.getLength();if(point+m-1<alist.getLength()point=point+m-1;位置elsepoint=

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