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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)踐報(bào)告學(xué) 號(hào)： 150906112姓 名： 武錦蓉班 級(jí)： NET2 班 指導(dǎo)老師： 田喜平時(shí) 間： 2016-12-21項(xiàng)目名稱項(xiàng)目構(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 ）輸出模塊：分別在 DOS 下和文件中， 按移除元素的順序依次顯示其位 置。約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置， 而這種數(shù)據(jù)是存在 “第一元素、 最后元素”，并且存在“唯

2、一的前驅(qū)和后繼的” ，符合線性表的特點(diǎn)。由于需 要模擬約瑟夫環(huán)的出列問題，可以采用順序表來(lái)實(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)度來(lái)修正（即模擬環(huán)狀計(jì)數(shù)） 。然后把順序表中的當(dāng)前指向位置設(shè)置為該位置，繼而刪掉該位置。反復(fù)進(jìn)行上述確定位置和刪除位置的操作，直到順序表為空 程序主要功能模塊1 、輸入的形式和輸入值的范圍：每一次輸入的值為兩個(gè)正整數(shù)，中間用逗號(hào)隔開 若分別設(shè)為 n,m ，則輸入

3、格式為：“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輸入：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錯(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)系，即 <ai,ai+1>(0 a<n) ?；静僮鳎篵ool remove(int &elem)/ 移除一個(gè)元素，被移除的元素賦給 elem/ 如果操作成功，返回 true, 否則返回 falsebool isEmpty()/ 判斷數(shù)組的元素是否清空，

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

6、nt fence;/ 指向當(dāng)前元素下標(biāo)public:AList(int s)/ 構(gòu)造函數(shù)，初始化數(shù)組listArray=new ints;for(int i=0;i<s;i+)listArrayi=i+1;/ 數(shù)組值等于數(shù)組下標(biāo) +1realSize=s;fence=0;/ 指向首元素bool remove(int &elem)/ 移除一個(gè)元素if(isEmpty()return false;/ 如果數(shù)組為空返回 false elem = listArrayfence;從當(dāng)前位置開始循環(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)/ 設(shè)置當(dāng)前元素的位置if(place>=0&&place<=realSize)fence=place;return true;return false;int getLength()/ 獲取數(shù)組長(zhǎng)度return realSize;在主函數(shù)中調(diào)用上述模塊的方法：ofstream fout;/ 文件流 fo

8、ut.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)度/ 設(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);/ 設(shè)置當(dāng)前需要?jiǎng)h除的位置alist.remove(elem);/ 刪除元素cout<<elem<<" "/DOS輸出fout<<elem<<" "/ 文件輸出四、測(cè)試結(jié)果(截圖顯示)五、遇到的問題及解決方法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é)果是 (1 2n)n )的，化簡(jiǎn)后時(shí)間復(fù)雜度仍然為 (n2)。綜上，該算法的時(shí)間代價(jià)為 (n2)。(PS：如果是用循環(huán)查找，在 n 次定位中每次都使用了 m 次的循環(huán)，至少 是(n*m) ，然后再用順序表的移除方法，總的復(fù)雜度應(yīng)該是 (m*n 2)的。)事實(shí)上要用線性表來(lái)完成這道題，其復(fù)雜度最好也是(n2)的，畢竟對(duì)于 n個(gè)數(shù)據(jù)，每個(gè)都要進(jìn)行時(shí)間復(fù)雜度為 (n) 的刪除工作。欲到達(dá) (n)的效率除