數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)習(xí)

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)習(xí)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)習(xí)實(shí)習(xí)步驟實(shí)習(xí)步驟（1）按照每次實(shí)習(xí)的要求選定題目。（2）分析題目要求，明確要實(shí)現(xiàn)的功能；設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)；根據(jù)面向?qū)ο缶幊谭椒?，確定算法的基本思想，主要模塊，各模塊功能及調(diào)用關(guān)系，再用C+語(yǔ)言對(duì)主要算法進(jìn)行細(xì)化。（3）編寫好上機(jī)源程序，并進(jìn)行靜態(tài)檢查，使程序中的邏輯錯(cuò)誤和語(yǔ)法錯(cuò)誤減少到最低程度。（4）準(zhǔn)備好測(cè)試數(shù)據(jù)，考慮好調(diào)試手段，上機(jī)調(diào)試程序；程序通過(guò)后，打印一份源程序清單及對(duì)測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。（5）最后寫好調(diào)試分析報(bào)告及使用說(shuō)明，完成一份完整的實(shí)習(xí)報(bào)告。實(shí)習(xí)報(bào)告的內(nèi)容實(shí)習(xí)報(bào)告的內(nèi)容一 實(shí)習(xí)題目與要求 包括題目與功能要求 二 需求分析 包括問(wèn)題描述、系統(tǒng)環(huán)境、運(yùn)

2、行要求等 三 概要設(shè)計(jì) 包括數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)、算法設(shè)計(jì)、模塊設(shè)計(jì)等 四 詳細(xì)設(shè)計(jì) 包括類的函數(shù)成員和數(shù)據(jù)成員設(shè)計(jì)、界面設(shè)計(jì)及其它模塊設(shè)計(jì)與實(shí)現(xiàn) 五 調(diào)試分析 調(diào)試過(guò)程中遇到的主要問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的回顧討論和分析；算法的時(shí)間和空間復(fù)雜度的分析；算法的進(jìn)一步改進(jìn)等。六 使用說(shuō)明 使用說(shuō)明主要描述如何使用你的程序及使用時(shí)的注意事項(xiàng)。七 測(cè)試結(jié)果 如果題目規(guī)定了測(cè)試數(shù)據(jù)，則結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出，當(dāng)然還可以含其他測(cè)試數(shù)據(jù)及其運(yùn)行輸出（需要多組測(cè)試數(shù)據(jù)）。八 源程序清單 源程序中要添加必要的注釋。實(shí)習(xí)一實(shí)習(xí)一 線性表、棧和線性表、棧和隊(duì)列及應(yīng)用隊(duì)列及應(yīng)用任選一題1 1、一

3、元稀疏多項(xiàng)式運(yùn)算器、一元稀疏多項(xiàng)式運(yùn)算器【問(wèn)題描述問(wèn)題描述】設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器。 【基本要求基本要求】（1）輸入并建立兩個(gè)多項(xiàng)式；（2）多項(xiàng)式a與b相加，建立和多項(xiàng)式c；（3）多項(xiàng)式a與b相減，建立差多項(xiàng)式d；（4）輸出多項(xiàng)式a,b,c,d。輸出格式：比如多項(xiàng)式a為：A(x)=c1xe1+ c2xe2+ cmxem，其中，ci和ei分別為第i項(xiàng)的系數(shù)和指數(shù)，且各項(xiàng)按指數(shù)的升冪排列，即0e1e2em?！緶y(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)】（1）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)（2）(x+x100)+(x100+x200)=(x+2x100+x200)（3）

4、(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)（4）(6x-3-x+4.4x2-1.2x9)-(-6x-3+4.4x2+7.8x15) =(12x-3-x-1.2x9-7.8x15)【實(shí)現(xiàn)提示實(shí)現(xiàn)提示】（1）用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。（2）每個(gè)多項(xiàng)式鏈表中都只存儲(chǔ)非零系數(shù)項(xiàng)。若多項(xiàng)式a與b中指數(shù)相等的兩項(xiàng)相加/減后，系數(shù)為零，則在和/差多項(xiàng)式c中不存儲(chǔ)該指數(shù)項(xiàng)。 【拓展內(nèi)容拓展內(nèi)容】 計(jì)算器的仿真界面。2 2、n(n20)n(n20)的階乘的階乘【問(wèn)題描述問(wèn)題描述】 大數(shù)運(yùn)算計(jì)算n的階乘 (n20)?！净疽蠡疽蟆?（1）數(shù)據(jù)的表示和存儲(chǔ)： 累

5、積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果的數(shù)據(jù)類型要求是整型這是問(wèn)題本身的要求。 試設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)，要求每個(gè)元素或結(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值。（2）數(shù)據(jù)的操作及其實(shí)現(xiàn)： 基于設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)乘法操作，要求從鍵盤上輸入n值；在屏幕上顯示最終計(jì)算結(jié)果?！緶y(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)】 （1）n=20，n!=2432902008176640000（2）n=30，n!=265252859812191058636308480000000【實(shí)現(xiàn)提示實(shí)現(xiàn)提示】（1）設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 介于階乘運(yùn)算的精確性以及實(shí)型數(shù)據(jù)表示的不精確性，本題不能采用實(shí)型表示累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果，而只能用整型。然而由于普通整型和

6、長(zhǎng)整型所能表述數(shù)的范圍受其字長(zhǎng)的限制，不能表示大數(shù)階乘的累積結(jié)果，故必須設(shè)計(jì)一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)，例如可以讓每個(gè)元素或結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的若干位數(shù)值。 從問(wèn)題描述不難看出n值為任意值，故為使程序盡量不受限制，應(yīng)采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（2）實(shí)現(xiàn)兩個(gè)數(shù)的乘法運(yùn)算需考慮： 乘數(shù)的各位數(shù)都要與被乘數(shù)進(jìn)行乘法運(yùn)算； 乘法過(guò)程中的進(jìn)位問(wèn)題及其實(shí)現(xiàn)。 因每個(gè)元素或結(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值，故當(dāng)元素或結(jié)點(diǎn)中的數(shù)值大于999，需向前一個(gè)元素或結(jié)點(diǎn)進(jìn)位。3 3、表達(dá)式的后綴表示、表達(dá)式的后綴表示【問(wèn)題描述】 表達(dá)式中包含運(yùn)算對(duì)象、運(yùn)算符和圓括號(hào)等，習(xí)慣上使用中綴表示（指運(yùn)算符夾在兩運(yùn)算符對(duì)象中間）形式。計(jì)算

7、表達(dá)式的值，涉及到運(yùn)算符的優(yōu)先級(jí)別，如先乘除后加減。括在一對(duì)圓括號(hào)中的子表達(dá)式必須先計(jì)算，因此，圓括號(hào)可視為特殊的運(yùn)算符，具有最高優(yōu)先級(jí)別。圓括號(hào)可以任意嵌套，這意味著左圓括號(hào)后面又是表達(dá)式，形成表達(dá)式的遞歸定義。為了直接指明表達(dá)式中各運(yùn)算對(duì)象的先后計(jì)算順序，可將表達(dá)式的中綴形式轉(zhuǎn)換成后綴（指運(yùn)算符放在二運(yùn)算對(duì)象的后面）形式。例如，表達(dá)式a*b-(c+d)/e，這是通常的中綴形式，其后綴表示是ab*cd+e/-,其中圓括號(hào)在后綴形式中已不見了。 設(shè)計(jì)一轉(zhuǎn)換程序，將輸入的任一表達(dá)式轉(zhuǎn)換成相應(yīng)的后綴形式后輸出。【基本要求】 為簡(jiǎn)單起見，假定運(yùn)算對(duì)象只含變量，且每個(gè)變量名以單字母表示；運(yùn)算符僅含+、

8、-、*、/和圓括號(hào)；表達(dá)式以分號(hào)“；”結(jié)尾。在轉(zhuǎn)換過(guò)程中，要求作必要的語(yǔ)法檢查，例如圓括號(hào)是否配對(duì)，單詞是否合法等。 要求分別編寫轉(zhuǎn)換程序的非遞歸與遞歸算法?！緶y(cè)試數(shù)據(jù)】（1）A*B*C（2）a+b*(c-d)-e/f（3）(A+B)*D+E/(F+A*D)+C實(shí)習(xí)二實(shí)習(xí)二 樹和二叉樹樹和二叉樹及應(yīng)用及應(yīng)用任選一題1 1、實(shí)現(xiàn)、實(shí)現(xiàn)WindowsWindows資源管理器資源管理器【問(wèn)題描述問(wèn)題描述】 Windows資源管理器是用來(lái)管理計(jì)算機(jī)資源的窗口，電腦里所有的文件都可以在資源管理器里找到，可以在資源管理器里查看文件夾的分層結(jié)構(gòu)，可以利用資源管理器快速進(jìn)行文件和文件夾的操作。例如，磁盤（根）

9、、目錄、不同類型的文件。 其中，文件信息包括文件名、類型、創(chuàng)建時(shí)間、文件大小等；磁盤信息包括磁盤名稱、總大小、可用空間等；目錄信息包括目錄名稱、修改日期、大小、對(duì)象數(shù)等。【基本要求基本要求】（1）構(gòu)造一個(gè)空的資源管理器（2）新建/刪除磁盤（3）在當(dāng)前選擇目錄下新建/刪除目錄（4）在當(dāng)前選擇目錄下新建/刪除文件（5）以目錄樹的形式輸出當(dāng)前目錄下的文件以及文件夾信息，并統(tǒng)計(jì)目錄數(shù)和文件數(shù) （6）回上一級(jí)：當(dāng)前目錄為當(dāng)前目錄的上一級(jí)目錄，并以目錄樹的形式輸出當(dāng)前目錄下的文件以及文件夾信息，并統(tǒng)計(jì)目錄數(shù)和文件數(shù) （7）模糊查找目錄/文件信息，并顯示查找結(jié)果 （8）撤銷一個(gè)資源管理器2 2、樹的遍歷、樹

10、的遍歷【問(wèn)題描述】（1）一棵有n個(gè)結(jié)點(diǎn)的有根樹，結(jié)點(diǎn)從1到n標(biāo)號(hào)，不同的點(diǎn)標(biāo)號(hào)不同。對(duì)于每一個(gè)結(jié)點(diǎn)，求在它的子孫結(jié)點(diǎn)中，有多少個(gè)結(jié)點(diǎn)的標(biāo)號(hào)比它的標(biāo)號(hào)小。（2）已知一棵樹上的邊的長(zhǎng)度，那么有多少對(duì)結(jié)點(diǎn)的距離小于等于K，可自定義K值，及構(gòu)建自己的樹?！緮U(kuò)展內(nèi)容擴(kuò)展內(nèi)容】一棵有n個(gè)結(jié)點(diǎn)的樹，以及定義在邊上的權(quán)值w，選出一個(gè)最多有p個(gè)結(jié)點(diǎn)的集合S。定義di=mindisi,j，j是S中的結(jié)點(diǎn)，要求這樣的S，使得給定d1+d2+dn最小。3 3、唯一的確定一棵二叉樹、唯一的確定一棵二叉樹【問(wèn)題描述問(wèn)題描述】 如果給出了遍歷二叉樹的前序序列和中序序列，則可以構(gòu)造出唯一的一棵二叉樹。試編寫實(shí)現(xiàn)上述功能的程序

11、。 【基本要求基本要求】 已知一棵二叉樹的前序和中序序列，試設(shè)計(jì)完成下列任務(wù)的一個(gè)算法：（1）構(gòu)造一棵二叉樹；（2）證明構(gòu)造正確（即分別以前序和中序遍歷該樹，將得到的結(jié)果與給出的序列進(jìn)行比較）。（3）對(duì)該二叉樹進(jìn)行后序遍歷，輸出后序遍歷序列。（4）用凹入法輸出該二叉樹。【測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)】 （1）前序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC。 （2）前序序列為-+ a b c / d e，中序序列為a+bc-d/e ?！就卣箖?nèi)容拓展內(nèi)容】 已知后序和中序序列構(gòu)造二叉樹。實(shí)習(xí)三實(shí)習(xí)三 搜索及應(yīng)用搜索及應(yīng)用任選一題1 1、實(shí)現(xiàn)對(duì)字典的實(shí)現(xiàn)對(duì)字典的查找查找【問(wèn)題描述問(wèn)題描述】 采用

12、分塊查找、二叉搜索樹查找、哈希表查找等不同的查找方法實(shí)現(xiàn)對(duì)字典的查找，并分析不同查找方法的效率，統(tǒng)計(jì)查找花費(fèi)的時(shí)間。2 2、電話號(hào)碼查詢系統(tǒng)、電話號(hào)碼查詢系統(tǒng)【問(wèn)題描述問(wèn)題描述】 設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)。【基本要求基本要求】（1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)： 電話號(hào)碼、用戶名、地址；（2）從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表；（3）采用合適的方法解決沖突；（4）查找并顯示給定電話號(hào)碼的記錄；（5）查找并顯示給定用戶名的記錄。【實(shí)現(xiàn)提示實(shí)現(xiàn)提示】 構(gòu)造哈希函數(shù)時(shí)，要注意使其分布均勻。用戶名的長(zhǎng)度均不超過(guò)20個(gè)字符。字符的取碼方法可直接利用ord函數(shù)?？上葘?duì)過(guò)長(zhǎng)的用戶名作

13、折疊處理。【選作內(nèi)容選作內(nèi)容】（1）從幾種哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計(jì)幾個(gè)不同的哈希函數(shù)，比較它們的地址沖突率。（2）在哈希函數(shù)確定的前提下，嘗試各種不同的處理沖突的方法，并比較平均查找長(zhǎng)度的變化。實(shí)習(xí)四實(shí)習(xí)四 圖及其應(yīng)用圖及其應(yīng)用任選一題1 1、求無(wú)向連通圖的生成樹求無(wú)向連通圖的生成樹 【問(wèn)題描述問(wèn)題描述】 若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條路線即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題。 【基本要求基本要求】 (1)利用克魯斯卡爾算法求網(wǎng)的最小生成樹，其中，以課本中的等價(jià)類表示構(gòu)造生成樹過(guò)程中的連通分量。 (2)利用普里姆算法求網(wǎng)的最小生成樹。 (3)以文本文件形式輸出生成樹中各條邊以及他們的權(quán)值。2 2、圖的遍歷圖的遍歷【問(wèn)題描述問(wèn)題描述】 有一個(gè)長(zhǎng)方形的房間，房間里的地面上布滿了正方形的瓷磚，瓷磚要么是紅色的，要么是黑色的。一個(gè)人站在其中一塊黑色的瓷磚上，他可以向四周的瓷磚上移動(dòng)，但是不能移動(dòng)