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

1、數(shù)據(jù)結(jié)構(gòu)實踐報告 20xx 報 告 匯 編 compilation of reports 數(shù)據(jù)結(jié)構(gòu)實踐報告 學(xué) 號： 150906112 姓 名： 武錦蓉 班 級： net2 班 指導(dǎo)老師： 田喜平 時 間： xx-12-21 報告文檔·借鑒學(xué)習(xí) word 可· 工程名稱 一、 工程構(gòu)思 程序由三個模塊組成： （1）輸入模塊：無提示語句，直接輸入總?cè)藬?shù) n 和報數(shù)次數(shù) m，中間用逗號隔開。 （2）處理模塊：將元素儲存于順序表中。在主函數(shù)中根據(jù)報數(shù)間隔確定需要刪除的元素的位置，在順序表中設(shè)置該位置并刪除該位置，同時輸出該位置的值。反復(fù)設(shè)置并刪除直到表空。 （3）輸出模塊：分別

2、在 dos 下和文件中，按移除元素的順序依次顯示其位置。 約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)是存在“第一元素、最后元素”，并且存在“唯一的前驅(qū)和后繼的”，符合線性表的特點。由于需要模擬約瑟夫環(huán)的出列問題，可以采用順序表來實現(xiàn)線性表，完成出列順序的輸出。 核心算法主要分為兩步： 1、確定需要刪除的位置，2、設(shè)置并刪除該位置。 報數(shù)間隔 m，我們可以把當(dāng)前位置加上 m 獲得需要刪除的位置，如果獲得的位置超過順序表中實際元素的總長度，那么可以通過減去數(shù)組的實際長度來修正（即模擬環(huán)狀計數(shù)）。然后把順序表中的當(dāng)前指向位置設(shè)置為該位置，繼而刪掉該位置。 反復(fù)進行上述確定位置和刪除位置的操作，直

3、到順序表為空。 程序主要功能模塊 1 、輸入的形式和輸入值的范圍： 每一次輸入的值為兩個正整數(shù)，中間用逗號隔開。 假設(shè)分別設(shè)為 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 報告文檔·借鑒

4、學(xué)習(xí) word 可· 輸入：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 7 13 20 26 34 40 8 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ù)關(guān)系：線性關(guān)系，即(0an)。 根本操作： bool

5、remove(int &elem)/移除一個元素，被移除的元素賦給 elem /如果操作成功，返回 true,否那么返回 false bool isempty()/判斷數(shù)組的元素是否清空，空返回 true,否那么返回false bool setpos(int place)/設(shè)置當(dāng)前元素的位置，設(shè)置成功返回 true,否那么返回 false int getlength()/獲取數(shù)組的實際長度 2 、各程序模塊之間的層次（調(diào)用）關(guān)系： 主函數(shù)會按設(shè)計的方法調(diào)用順序表中“獲取實際長度”、“設(shè)置需要刪除元素的位置”、“移除該位置元素”和“判斷是否為空表”四種方法方法，使元素依次出列，并正確結(jié)束

6、程序。 用整形存儲用戶輸入的整數(shù)。 用順序表實現(xiàn)線性表： class alist private: int *listarray;/指向數(shù)組的指針 int realsize;/數(shù)組中含有元素的實際長度 報告文檔·借鑒學(xué)習(xí) word 可· int fence;/指向當(dāng)前元素下標(biāo) public: alist(int s)/構(gòu)造函數(shù)，初始化數(shù)組 listarray=new ints; for(int i=0;i=0&&place<=realsize) fence=place; return true; return false; 報告文檔·借鑒學(xué)習(xí)

7、 word 可· int getlength()/獲取數(shù)組長度 return realsize; ; 在主函數(shù)中調(diào)用上述模塊的方法： ofstream fout;/文件流 fout.open("c:josephus.txt");/設(shè)置文件路徑 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

8、(m=0)m=alist.getlength(); if(point+m-1 報告文檔·借鑒學(xué)習(xí) word 可· 五、遇到的問題及解決方法 1、初始化局部為循環(huán)賦值，時間復(fù)雜度為(n)。 2、處理局部，我為了提高效率沒有采用循環(huán)尋找的方法，直接利用數(shù)學(xué)關(guān)系通過當(dāng)前位置獲得下一位置，因此對于長度為 n 的約瑟夫環(huán)，只做了 n 次定位，每次定位的復(fù)雜度為(1)，所以時間復(fù)雜度為(n)。 但是用順序表實現(xiàn)時，每次其移除的方法是時間復(fù)雜度為(k)的(k 與實際長度有關(guān))，所以處理局部總的結(jié)果是(2) 1 ( n n ?)的，化簡后時間復(fù)雜度仍然為(n 2 )。 綜上，該算法的時間代價為(n 2 )。 （ps：如果是用循環(huán)查找，在 n 次定位中每次都使用了 m 次的循環(huán)，至少是(n*m)，然后再用順序表的移除方法，總的復(fù)雜度應(yīng)該是(m*n 2 )的。） 事實上要用線性表來完成這道題，其復(fù)雜度最好也是(n 2 )的，畢竟對于 n個數(shù)據(jù)，每個都要進行時間復(fù)雜度為(n)的刪除工作。欲到達(n)的效率除非不用線性表來實現(xiàn)。 六、體會 輸入人數(shù) n,報數(shù)間隔 m，創(chuàng)立順序表對象。 報告文檔·借鑒學(xué)習(xí) word 可· 主