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

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

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

3、該位置，繼而刪掉該位置。 反復(fù)進(jìn)行上述確定位置和刪除位置的操作，直到挨次表為空。 程序主要功能模塊 1 、輸入的形式和輸入值的范圍： 每一次輸入的值為兩個(gè)正整數(shù)，中間用逗號隔開。 若分別設(shè)為 n,m，則輸入格式為："n,m'。 不對非法輸入做處理，即假設(shè)輸入都是合法的。 2 、輸出的形式： 輸出格式 1：在字符界面上輸出這 n 個(gè)數(shù)的輸出序列 輸出格式 2：將這 n 個(gè)數(shù)的輸出序列寫入到文件中 3 、程序所能達(dá)到的功能： 對于輸入的約瑟夫環(huán)長度 n 和間隔 m，輸出約瑟夫環(huán)的出列挨次。 4 、測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 正確： 輸入：1

4、0,3 輸出：3 6 9 2 7 1 8 5 10 4 報(bào)告文檔借鑒學(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ù)存儲用戶的輸入。并將用戶輸入的值存儲于線性表中。線性表 adt 定義如下： adt list 數(shù)據(jù)對

5、象：整形 數(shù)據(jù)關(guān)系：線性關(guān)系，即ai,ai+1(0an)。 基本操作： bool 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í)際長度 2 、各程序模塊之間的層次（調(diào)用）關(guān)系： 主函數(shù)會按設(shè)計(jì)的方法調(diào)用挨次表中"獵取實(shí)際長度'、"設(shè)置需要刪

6、除元素的位置'、"移除該位置元素'和"推斷是否為空表'四種方法方法，使元素依次出列，并正確結(jié)束程序。 用整形存儲用戶輸入的整數(shù)。 用挨次表實(shí)現(xiàn)線性表： class alist private: int *listarray;/指向數(shù)組的指針 int realsize;/數(shù)組中含有元素的實(shí)際長度 報(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;is;i+) listarrayi=i+1;/數(shù)

7、組值等于數(shù)組下標(biāo)+1 realsize=s; fence=0;/指向首元素 bool remove(int elem)/移除一個(gè)元素 if(isempty()return false;/假如數(shù)組為空返回 false elem = listarrayfence; for(int i=fence;irealsize-1;i+)/從當(dāng)前位置開頭循環(huán)向前賦值 listarrayi=listarrayi+1; realsize-; return true; bool isempty()/推斷數(shù)組的元素是否清空 if(realsize=0)return true; else return false; b

8、ool setpos(int place)/設(shè)置當(dāng)前元素的位置 if(place=0place=realsize) fence=place; return true; return false; 報(bào)告文檔借鑒學(xué)習(xí) 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)建挨次表對

9、象 while(!alist.isempty()/假如挨次表不為空，連續(xù)刪除 m=m%alist.getlength();/調(diào)整計(jì)數(shù)的長度 if(m=0)m=alist.getlength(); if(point+m-1alist.getlength()point=point+m-1; /設(shè)置偏移位置 elsepoint=point+m-alist.getlength()-1; alist.setpos(point);/設(shè)置當(dāng)前需要刪除的位置 alist.remove(elem);/刪除元素 coutelem ;/dos 輸出 foutelem ;/文件輸出 四、測試結(jié)果（截圖顯示） 報(bào)告文檔

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