【正文】 9] i=[43] t=[12] i=[44] t=[2] i=[45] t=[1] i=[46] t=[6] i=[47] t=[4] i=[48] t=[7] i=[49] t=[1]第三篇：數(shù)據(jù)結構課程設計教學大綱《數(shù)據(jù)結構課程設計》教學大綱Data Structure Course Design一、課程的性質(zhì)、教學目的和要求《數(shù)據(jù)結構》是計算機軟件的一門基礎課程，計算機科學各領域及有關的應用軟件都要用到各種類型的數(shù)據(jù)結構。學好數(shù)據(jù)結構對掌握實際編程能力是很有幫助的。為了學好《數(shù)據(jù)結構》，必須編寫一些在特定數(shù)據(jù)結構上的算法，通過上機調(diào)試，才能更好地掌握各種數(shù)據(jù)結構及其特點，同時提高解決計算機應用實際問題的能力。二、設計要點1．設計和調(diào)試過程要規(guī)范化。① 需求分析將題目中要求的功能進行敘述分析，并且設計解決此問題的數(shù)據(jù)存儲結構，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進行測試的結果列出來。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規(guī)則來編寫。要結構清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。程序能夠運行，要有基本的容錯功能。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。2．課程設計實習報告的書寫格式① 設計題目（任選其一）②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式可設34人一題，安排在《數(shù)據(jù)結構》課程開課學期布置題目，然后在期末兩周時間內(nèi)完成。三．設計要求學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。課程設計按照教學要求需要兩周時間完成，兩周中每天至少要上34小時的機來調(diào)試C語言設計的成成，總共至少要上機調(diào)試程序30小時。為保證質(zhì)量，需要每個學生將每天的上機調(diào)試程序的時間記錄下來，作為評判成績的標準之一。四．設計題目運動會分數(shù)統(tǒng)計*問題描述：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學生自己設定。（m1).可以輸入各個項目的前三名或前五名的成績； 2)．能統(tǒng)計各學?？偡?，3)．可以按學校編號、學校總分、男女團體總分排序輸出；4).可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學校的名稱，運動項目的名稱）輸出形式：有中文提示，各學校分數(shù)為整形界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。*存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內(nèi)容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；測試數(shù)據(jù)：要求使用全部合法數(shù)據(jù)；整體非法數(shù)據(jù)；局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明；一元多項式計算*問題描述：能夠按照指數(shù)降序排列建立并輸出多項式； 能夠完成兩個多項式的相加、相減，并將結果輸入；在上交資料中請寫明：存儲結構、多項式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；訂票系統(tǒng)*問題描述：通過此系統(tǒng)可以實現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結構、具體數(shù)據(jù)自定）2）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結構自己設定）可以訂票，如果該航班已經(jīng)無票，可以提供相關可選擇航班； 4）退票： 可退票，退票后修改相關數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。5）修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件 *要求：根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；迷宮求解*問題描述：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。*要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。*存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；joseph環(huán)*問題描述：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。*要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。*測試數(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ù)，將正確的輸出序列猴子選大王*問題描述：一堆猴子都有編號，編號是1，2，3...m ,這群猴子（m個）按照1m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結構的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數(shù)*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；紙牌游戲*問題描述：編號為152張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過。輸出：這時正面向上的牌有哪些？1圖的建立及輸出*問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。1拓撲排序*問題描述：編寫函數(shù)實現(xiàn)圖的拓撲排序。1各種排序*問題描述：對30000個隨機整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。*輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個遞增的數(shù)列?1圖的遍歷*問題描述：對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。1線性表的操作*問題描述：利作鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數(shù)、輸出等運算反復實現(xiàn)鏈表的這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結果。1長整數(shù)四則運算*問題描述：設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結點含一個整形變量。任何整形變量的范圍是(2^151)。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。*測試數(shù)據(jù)：（1）0；0；應輸出“0”。（2）2345,6789；7654,3211；應輸出“1,0000,0000”。（3）9999,9999；1,0000,0000,0000；應輸出“999（4）1,0001,0001；1,0001,0001；應輸出“0”。（5）1,0001,0001；1,0001,0000；應輸出“1”。（6）9999,9999,9999；9999,9999,9999；應輸出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；應輸出“1,0001,0000,0000”。*實現(xiàn)提示：（1）每個結點中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當于按32768進制存放，在十進制與32768 5 進制數(shù)之間的轉換十分不方便，故可以在每個結點中僅存十進制的4位，即不超過9999的非負整數(shù)，整個鏈表表示為萬進制。（2）可以利用頭結點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結構的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。1馬踏棋盤*問題描述：將馬隨機放在國際象棋的8 8棋盤Bord[8Ⅱ8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格上只進入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入個8 8的方陣，輸出之。*測試數(shù)據(jù)：由讀者指定,可自行指定一個馬的初始位置。*實現(xiàn)提示：每次在多個可走位置中選擇一個進行試探，其余未曾試探過的可走位置必須用適當結構妥善管理，以備試探失敗時的“回溯”(悔棋)使用。1校園導游咨詢 *問題描述：（1）設計你的學校的校園平面圖，所含景點不少于10個。以圖中頂點表示學校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。（3）為來訪客人提供圖中任意景點相關信息的查詢。*測試數(shù)據(jù)：由讀者根據(jù)實際情況指定。*實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關信息。1編制一個求解迷宮通路的圖形界面演示程序。*問題描述：1）輸入一個任意大小的迷宮，任設起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。2）根據(jù)用戶界面提示，用鍵盤輸入。Home鍵設置迷宮起點，End鍵