數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)一、設(shè)計(jì)目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會(huì)使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實(shí)際問(wèn)題。二、設(shè)計(jì)要求在本課程設(shè)計(jì)過(guò)程中要求：（1）重視課程設(shè)計(jì)環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實(shí)的工作態(tài)度對(duì)待課程設(shè)計(jì)的每一項(xiàng)任務(wù)；（2）按照課程設(shè)計(jì)的題目要求，獨(dú)立地完成各項(xiàng)任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計(jì)入本課程設(shè)計(jì)成績(jī)。凡發(fā)現(xiàn)實(shí)驗(yàn)報(bào)告或源程序雷同，涉及的全部人員皆以零分計(jì)入本課程設(shè)計(jì)成績(jī)。（3）認(rèn)真編寫(xiě)課程設(shè)計(jì)報(bào)告。課程設(shè)計(jì)報(bào)告的書(shū)寫(xiě)格式及要求見(jiàn)附錄2。三、設(shè)計(jì)步驟1、問(wèn)題分析和任務(wù)定義；2、數(shù)據(jù)類(lèi)型和系統(tǒng)設(shè)計(jì)；3、編碼實(shí)現(xiàn)和靜態(tài)檢查；4、上機(jī)調(diào)試；5、總結(jié)和整理課程設(shè)計(jì)報(bào)告。四、考核方式和成績(jī)?cè)u(píng)定考核分為兩個(gè)部分：程序運(yùn)行情況：按規(guī)定時(shí)間到機(jī)房運(yùn)行程序，由老師檢查運(yùn)行情況。學(xué)生能對(duì)自己的程序面對(duì)教師提問(wèn)并能熟練地解釋清楚。實(shí)驗(yàn)報(bào)告：是否按規(guī)定書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告的各項(xiàng)內(nèi)容。課程設(shè)計(jì)成績(jī)采用五級(jí)分制。100%=上機(jī)檢查（50%）+課程設(shè)計(jì)報(bào)告（50%）五、上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可1上交源程序：學(xué)生按照課程設(shè)計(jì)的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；2上交程序的說(shuō)明文件：（保存在.doc中）在說(shuō)明文檔中應(yīng)該寫(xiě)明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；3課程設(shè)計(jì)報(bào)告：（保存在word文檔中，文件名要求按照姓名-學(xué)號(hào)-課程設(shè)計(jì)報(bào)告起名，如文件名為張三-101-課程設(shè)計(jì)報(bào)告.doc）按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成；1、需求分析1程序的功能；2輸入輸出的要求；3測(cè)試數(shù)據(jù)。2、概要設(shè)計(jì)包括程序設(shè)計(jì)組成框圖，程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義）。3、詳細(xì)設(shè)計(jì)包括模塊功能說(shuō)明（如函數(shù)功能、入口及出口參數(shù)說(shuō)明，函數(shù)調(diào)用關(guān)系描述等），每個(gè)模塊的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖）。源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。4、調(diào)試分析測(cè)試數(shù)據(jù)，測(cè)試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題的思考（問(wèn)題是哪些？問(wèn)題如何解決？），算法的改進(jìn)設(shè)想。5、核心源程序清單和執(zhí)行結(jié)果源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。附錄1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的具體內(nèi)容本次課程設(shè)計(jì)完成如下模塊（共36個(gè)模塊，抽簽決定自己所做題目的序號(hào)）1、一元多項(xiàng)式乘法1)問(wèn)題描述已知A(x)=a0+a1x+a2x2+anxn和B(x)=b0+b1x+b2x2+bmxm，并且在A(yíng)(x)和B(x)中指數(shù)相差很多，求A(x)=A(x)*B(x)。2)基本要求(1)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示一元多項(xiàng)式；(2)設(shè)計(jì)算法實(shí)現(xiàn)一元多項(xiàng)式乘法；(3)分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2、迷宮問(wèn)題1)問(wèn)題描述迷宮求解是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問(wèn)題，心理學(xué)家把一只老鼠從一個(gè)無(wú)頂蓋的大盒子的入口處趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。例如，圖2所示為一個(gè)迷宮示意圖，其中雙邊矩形表示迷宮，1代表有障礙，0代表無(wú)障礙。2)基本要求(1)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)迷宮；(2)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)保存從入口到出口的通路；(3)設(shè)計(jì)算法完成迷宮問(wèn)題的求解；(4)分析算法的時(shí)間復(fù)雜度。3)設(shè)計(jì)思想可以采用回溯法實(shí)現(xiàn)該問(wèn)題的求解。回溯法是一種不斷試探及時(shí)糾正錯(cuò)誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過(guò)的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向；若所有的方向均沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都搜索到，或01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111入口(1,1)出口(6,8)圖2迷宮示意圖，其中1代表有障礙，0代表無(wú)障礙前進(jìn)的方向有八個(gè)，分別是上、下、左、右、左上、左下、右上、右下找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。在求解過(guò)程中，為了保證在任何位置上都能沿原路退回，需要一個(gè)后進(jìn)先出的棧來(lái)保存從入口到當(dāng)前位置的路徑?？梢詫⒚詫m定義成一個(gè)二維數(shù)組，則每個(gè)點(diǎn)有8個(gè)試探方向，如當(dāng)前點(diǎn)的坐標(biāo)是(x,y)，與其相鄰的8個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，規(guī)定試探順序?yàn)轫槙r(shí)針?lè)较?，將這8個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move8中，在move數(shù)組中，每個(gè)元素由兩個(gè)域組成：x表示橫坐標(biāo)增量，y表示縱坐標(biāo)增量。這樣會(huì)很方便地求出從某點(diǎn)(x，y)按某一方向v(0v7)到達(dá)新點(diǎn)（i，j）的坐標(biāo)：i=x+movev.x；j=y+movev.y。算法用偽代碼描述如下：1.棧初始化；2.將入口點(diǎn)坐標(biāo)(x,y)及該點(diǎn)的方向d（設(shè)為-1）入棧；3.當(dāng)棧不空時(shí)循環(huán)執(zhí)行下述操作：3.1(x,y,d)容忍值，則在j處放置放大器；2.2否則D(i)=maxD(i)，D(j)+d(j)；【思考題】本題假設(shè)分布網(wǎng)絡(luò)是一棵二叉樹(shù)結(jié)構(gòu)，如果是樹(shù)結(jié)構(gòu)應(yīng)如何設(shè)計(jì)算法？5、哈夫曼編碼1)問(wèn)題描述設(shè)某編碼系統(tǒng)共有n個(gè)字符，使用頻率分別為w1,w2,wn，設(shè)計(jì)一個(gè)不等長(zhǎng)的編碼方案，使得該編碼系統(tǒng)的空間效率最好。2)基本要求(1)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)；(2)設(shè)計(jì)編碼算法；(3)分析時(shí)間復(fù)雜度和空間復(fù)雜度。3)設(shè)計(jì)思想利用Huffman編碼樹(shù)求得最佳的編碼方案。根據(jù)哈夫曼算法