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

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

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

3、到順序表為空。 程序主要功能模塊 1 、輸入的形式和輸入值的范圍： 每一次輸入的值為兩個(gè)正整數(shù)，中間用逗號(hào)隔開。 假設(shè)分別設(shè)為 n,m，那么輸入格式為：“n,m”。 不對(duì)非法輸入做處理，即假設(shè)輸入都是合法的。 2 、輸出的形式： 輸出格式 1：在字符界面上輸出這 n 個(gè)數(shù)的輸出序列 輸出格式 2：將這 n 個(gè)數(shù)的輸出序列寫入到文件中 3 、程序所能到達(dá)的功能： 對(duì)于輸入的約瑟夫環(huán)長(zhǎng)度 n 和間隔 m，輸出約瑟夫環(huán)的出列順序。 4 、測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 正確： 輸入：10,3 輸出：3 6 9 2 7 1 8 5 10 4 報(bào)告文檔·借鑒

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 錯(cuò)誤： 輸入：10 3 輸出：6 8 7 1 3 4 2 9 5 10 二、 程序清單 1 、 抽象數(shù)據(jù)類型的定義： 為實(shí)現(xiàn)上述程序的功能，可以用整數(shù)存儲(chǔ)用戶的輸入。并將用戶輸入的值存儲(chǔ)于線性表中。線性表 adt 定義如下： adt list 數(shù)據(jù)對(duì)象：整形 數(shù)據(jù)關(guān)系：線性關(guān)系，即(0an)。 根本操作： bool

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

6、程序。 用整形存儲(chǔ)用戶輸入的整數(shù)。 用順序表實(shí)現(xiàn)線性表： class alist private: int *listarray;/指向數(shù)組的指針 int realsize;/數(shù)組中含有元素的實(shí)際長(zhǎng)度 報(bào)告文檔·借鑒學(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; 報(bào)告文檔·借鑒學(xué)習(xí)

7、 word 可· int getlength()/獲取數(shù)組長(zhǎng)度 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)立順序表對(duì)象 while(!alist.isempty()/如果順序表不為空，繼續(xù)刪除 m=m%alist.getlength();/調(diào)整計(jì)數(shù)的長(zhǎng)度 if

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