《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)任務(wù)書

1、《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)任務(wù)書課程代碼：B03203課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：DataStructures設(shè)計(jì)周數(shù)：2學(xué)分：1課程類別：必修課程性質(zhì)：專業(yè)基礎(chǔ)課先修課程：計(jì)算機(jī)導(dǎo)論、Java語言程序設(shè)計(jì)面向?qū)I(yè)：軟件技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)開課單位：軟件工程系課程設(shè)計(jì)題目一課程設(shè)計(jì)題目一迷宮問題迷宮問題一設(shè)計(jì)的目的和要求一設(shè)計(jì)的目的和要求1設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。要求學(xué)生在設(shè)計(jì)中

2、逐步提高程序設(shè)計(jì)能力，培養(yǎng)科學(xué)的軟件工作方法。學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)在下述各方面得到鍛煉：（1）能根據(jù)實(shí)際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出解決問題的有效算法。（2）提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。（3）培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)

3、雜度，進(jìn)一步提高程序設(shè)計(jì)水平。2設(shè)計(jì)的要求：迷宮問題在一個(gè)二維陣列構(gòu)成的迷宮里，有許多由1構(gòu)成的墻壁0表示的走道其中左上角是迷宮的入口右下角是迷宮的出口迷宮出口有一塊乳酪請(qǐng)幫這只老鼠找到一條路徑可以走出迷宮去享受乳酪在迷宮里面只允許上下左右四個(gè)方向行走。=011111101010100001000101101101001101100011100=Inputfilefmat：011001000011010111010000Outputfi

4、lefmat：請(qǐng)輸出到螢?zāi)簧险?qǐng)把你找到的任一條路徑用符號(hào)列印在螢?zāi)簧?編輯、編譯、調(diào)試源程序15撰寫課程設(shè)計(jì)報(bào)告1總計(jì)5課程設(shè)計(jì)題目二課程設(shè)計(jì)題目二內(nèi)部排序算法比較內(nèi)部排序算法比較一一設(shè)計(jì)的目的和要求設(shè)計(jì)的目的和要求（一）設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力，培養(yǎng)科學(xué)的軟件工

5、作方法。學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)在下述各方面得到鍛煉：1能根據(jù)實(shí)際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出解決問題的有效算法。2提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。3培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。4在教科書中，各種內(nèi)

6、部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)，以取得直觀感受。（二）設(shè)計(jì)的要求1對(duì)以下6種常用的內(nèi)部排序算法進(jìn)行比較：起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序。2待排序表的表長(zhǎng)不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）

7、。3統(tǒng)計(jì)在完全正序、完全逆序情況下的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。4最后對(duì)結(jié)果作出簡(jiǎn)單分析，包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。二設(shè)計(jì)內(nèi)容及步驟二設(shè)計(jì)內(nèi)容及步驟1分析問題，給出數(shù)學(xué)模型，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。（1）分析問題的特點(diǎn)，用數(shù)學(xué)表達(dá)式或其它形式描述其數(shù)學(xué)模型。（2）選擇能夠體現(xiàn)問題本身特點(diǎn)的邏輯結(jié)構(gòu)。（3）在邏輯結(jié)構(gòu)確定的情況下，為算法的設(shè)計(jì)選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)的不同存儲(chǔ)方式，其對(duì)應(yīng)的算法也不相同。2算法

8、設(shè)計(jì)在已經(jīng)選擇好數(shù)據(jù)結(jié)構(gòu)的前提下，為解決問題設(shè)計(jì)算法。（1）確定所需模塊對(duì)于稍復(fù)雜的程序設(shè)計(jì)，要充分利用模塊化程序設(shè)計(jì)方法，自頂向下，逐步細(xì)化，在整體思路確定的情況下，考慮所需模塊數(shù)，各模塊完成功能以及模塊之間的數(shù)據(jù)聯(lián)系和調(diào)用關(guān)系。（2）各子模塊功能描述給出主要模塊的算法描述，用流程圖或偽代碼表示。（3）模塊之間的調(diào)用關(guān)系給出算法各模塊之間的關(guān)系圖示3源程序清單為了提高工作效率，充分利用上機(jī)調(diào)試程序的時(shí)間，要求學(xué)生在上機(jī)之前給出源程序清