《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計教學大綱

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

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

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

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

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

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

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

8、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、”文章總字數(shù)”（3）輸出刪除某一字符串后的文章；6、 joseph環(huán)任務(wù)：編號是1,2,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。要求：

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

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

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

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

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