1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)教學(xué)大綱學(xué)分：1周數(shù)：3性質(zhì)：必修形式：分散建議執(zhí)行學(xué)期：4一、課程設(shè)計(jì)教學(xué)的意義和目的（一）意義：課程設(shè)計(jì)是培養(yǎng)和鍛煉學(xué)生綜合運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，是實(shí)踐性教學(xué)的重要環(huán)節(jié)，它具有動(dòng)手，動(dòng)腦，理論聯(lián)系實(shí)際的特點(diǎn)，是培養(yǎng)在校大學(xué)生理論聯(lián)系實(shí)際，敢于動(dòng)手，善于動(dòng)腦，獨(dú)立自主解決各種問(wèn)題的一種較好的方法。數(shù)據(jù)結(jié)構(gòu)與算法是一門應(yīng)用性、實(shí)踐性較強(qiáng)的課程，忽視了實(shí)踐性教學(xué)的環(huán)節(jié)，學(xué)生就會(huì)對(duì)該門課程的掌握不扎實(shí)。（二）本教學(xué)環(huán)節(jié)的實(shí)施目的：通過(guò)課程設(shè)計(jì)，使學(xué)生學(xué)會(huì)系統(tǒng)地運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法等課程的知識(shí)和技能解決實(shí)際問(wèn)題的本領(lǐng)。通過(guò)設(shè)計(jì)實(shí)驗(yàn)，培養(yǎng)學(xué)生查閱專業(yè)資料，工具書或參

2、考書，掌握現(xiàn)代設(shè)計(jì)手段和軟件工具，并掌握以圖紙和說(shuō)明書的方式表達(dá)設(shè)計(jì)思想和計(jì)算結(jié)果的能力。通過(guò)數(shù)學(xué)建模與軟件開(kāi)發(fā)，不但要培養(yǎng)和提高學(xué)生解決具體問(wèn)題，而且應(yīng)建立正確的設(shè)計(jì)和科研思想，牢固樹(shù)立事實(shí)求實(shí)和嚴(yán)肅認(rèn)真的科學(xué)工作態(tài)度。、課程設(shè)計(jì)教學(xué)的基本要求學(xué)生必須仔細(xì)閱讀數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)方案，認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。有問(wèn)題及時(shí)主動(dòng)通過(guò)各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要三周時(shí)間完成，三周中每天（按每周5天）至少要上3-4小時(shí)的機(jī)來(lái)調(diào)試C語(yǔ)言設(shè)計(jì)的程序，總

3、共至少要上機(jī)調(diào)試程序45小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)作為核定成績(jī)的參考。數(shù)據(jù)結(jié)構(gòu)是一門涉及多門課程的課程，難度較大，需要較好的C語(yǔ)言的程序設(shè)計(jì)和調(diào)試能力，如果學(xué)生能夠按照要求，從時(shí)間和精力上保證完全的投入，相信能夠有很大的收獲。三、課程設(shè)計(jì)的內(nèi)容及安排（一）主要內(nèi)容：本次課程設(shè)計(jì)完成如下模塊（共12個(gè)模塊，學(xué)生可以在其中至少挑選4個(gè)功能塊完成，但有*號(hào)的模塊是必須要選擇的，多做可以加分）1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)*任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m,女子m+1m+w不同的項(xiàng)目取前五名或前三名積分；取前

4、五名的積分分別為：7、5、3、2、1,前三名的積分分別為：5、3、2;哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）功能要求：1） .可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；2） .能統(tǒng)計(jì)各學(xué)?？偡?；3） .可以按學(xué)校編號(hào)、學(xué)?？偡?、男女團(tuán)體總分排序輸出；4） .可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整型界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根

5、據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；2、一元多項(xiàng)式計(jì)算*任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過(guò)程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；3、訂票系統(tǒng)任務(wù)

6、：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng)）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；4、 迷宮

7、求解任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；5、 文章編輯*功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行；要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、

8、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、”文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；6、 joseph環(huán)任務(wù)：編號(hào)是1,2,n的n個(gè)人按照順時(shí)針?lè)较驀蝗?，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。要求：

9、利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。測(cè)試數(shù)據(jù)：m的初值為20,n=7,7個(gè)人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什么？要求：輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n,輸入每個(gè)人的密碼，建立單循環(huán)鏈表。輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列7、 猴子選大王任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1,2,3.m,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,nm,n為整數(shù)，n<m輸出形式：中文提示按照m

10、個(gè)猴子，數(shù)n個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào)，建立一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能8、建立二叉樹(shù)，后序、先序遍歷（用遞歸或非遞歸的方法都可以）任務(wù)：要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的輸入函數(shù)、輸出后序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；9、赫夫曼樹(shù)的建立任務(wù)：建立建立最優(yōu)二叉樹(shù)函數(shù)要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；10、紙牌游戲任務(wù)：編號(hào)為1-52張牌，正面向上，從第2張開(kāi)始，以2為基數(shù)，是2的倍

11、數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；再依次5的倍數(shù)的牌翻一次，6的，7的，直到以52為基數(shù)的牌翻過(guò)，輸出：這時(shí)正面向上的牌有哪些？11、圖的建立及輸出任務(wù)：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。12、各種排序任務(wù)：用程序?qū)崿F(xiàn)插入法排序、起泡法算法排序；利用插入排序和冒泡法的算法，將用戶隨機(jī)輸入的一列數(shù)按遞增的順序排好。輸入的數(shù)據(jù)形式為任何一個(gè)

12、正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列？（二）、工作進(jìn)度安排1、熟悉設(shè)計(jì)題目。查閱相關(guān)資料2天2、TurboC編程軟件工具的熟悉應(yīng)用1天3、編寫程序及軟件方針調(diào)試3天4、編寫設(shè)計(jì)說(shuō)明書2天5、設(shè)計(jì)答辯及成績(jī)?cè)u(píng)定1天四、學(xué)生應(yīng)提交的設(shè)計(jì)成果上交的設(shè)計(jì)成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可。1、上交源程序：學(xué)生按照課程設(shè)計(jì)的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；2、上交程序的說(shuō)明文件：（保存在.txt中）在說(shuō)明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；3、課程設(shè)計(jì)報(bào)告：（保存在word文檔中，文件名要求按照&qu

13、ot;姓名-學(xué)號(hào)-課程設(shè)1t報(bào)告”起名，如文件名為"張三-001-課程設(shè)1t報(bào)告”.doc）按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成；其中包括：1）需求分析：在該部分中敘述每個(gè)模塊的功能要求2）概要設(shè)計(jì)在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義。3）詳細(xì)設(shè)計(jì)各個(gè)算法實(shí)現(xiàn)的源程序，對(duì)每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)）源程序要按照寫程序的規(guī)則來(lái)編寫。要結(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è)想。4、課程設(shè)計(jì)總結(jié)：（保存在word文檔中）總結(jié)可以包括：課程設(shè)計(jì)過(guò)程中的收獲、遇到的問(wèn)題、遇到問(wèn)題后解決問(wèn)題的思考、程序調(diào)試能力的思考、對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計(jì)過(guò)程中對(duì)數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識(shí)等內(nèi)容；五、課程設(shè)計(jì)考核方法及成績(jī)?cè)u(píng)定設(shè)計(jì)成績(jī)根據(jù)平時(shí)考勤，階段性進(jìn)度檢查，質(zhì)疑，設(shè)計(jì)說(shuō)明書，最終設(shè)計(jì)答辯綜