山東理工大學本科數據結構課程設計大綱

1、數據結構課程設計教學大綱(051003學院:計算機科學與技術學院專業(yè):計算機科學與技術周數:2周學分:2大綱主撰人:張先偉編寫日期:2004年6月30日一、課程設計的目的和任務1、提高對數據邏輯結構的特點以及存儲表示方式的認識,培養(yǎng)在具體應用中選擇合適的數據結構和存儲結構的能力;2、熟悉軟件開發(fā)的基本過程,初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等階段的基本任務和技能方法;3、培養(yǎng)學生的算法設計和算法分析能力,提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力;4.訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā),培養(yǎng)軟件工作者所應具備的科學的工作方法、作風和相互合作的精神

2、。二、課程設計的主要內容與要求1.課程設計選題(一個題目為一個小組,人數不超過3人1 文章編輯功能:輸入一頁文字,程序可以統(tǒng)計出文字、數字、空格的個數。靜態(tài)存儲一頁文章,每行最多不超過80個字符,共N行;要求(1分別統(tǒng)計出其中英文字母數和空格數及整篇文章總字數;(2統(tǒng)計某一字符串在文章中出現的次數,并輸出該次數;(3刪除某一子串,并將后面的字符前移。存儲結構使用線性表,分別用幾個子函數實現相應的功能;輸入數據的形式和范圍:可以輸入大寫、小寫的英文字母、任何數字及標點符號。輸出形式:(1分行輸出用戶輸入的各行字符;(2分4行輸出"全部字母數"、"數字個數"

3、、"空格個數"、"文章總字數"(3輸出刪除某一字符串后的文章;2通訊錄的制作設計目的:用數據結構中的雙向鏈表作數據結構,結合C/C+語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學數據結構知識應用到實際軟件開發(fā)中去。設計內容:本系統(tǒng)應完成一下幾方面的功能:輸入信息enter(;顯示信息display( ;查找以姓名作為關鍵字search( ;刪除信息delete( ;存盤save ( ;裝入load( ;設計要求:1每條信息至包含:姓名(NAME 街道(STREET城市(CITY郵編(EIP國家(STATE幾項2作為一個完整的系統(tǒng),應具有友好的界面和較強的

4、容錯能力3上機能正常運行,并寫出課程設計報告3宿舍管理查詢軟件任務:為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求:采用交互工作方式建立數據文件,數據文件按關鍵字(姓名、學號、房號進行排序(冒泡、選擇、插入排序等任選一種查詢菜單: (用二分查找實現以下操作按姓名查詢按學號查詢房號查詢打印任一查詢結果(可以連續(xù)操作4順序結構、動態(tài)鏈表結構下的一元多項式的加法、減法、乘法的實現。設有一元多項式A m(x和B n(x.A m(x=A0+A1x1+A2x2+A3x3+ +A m x mB n(x=B0+B1x1+B2x2+B3x3+ +B n x n請實現求M(x= A m(x+B n(x、M

5、(x= A m(x-B n(x和M(x= A m(x×B n(x。要求:1首先判定多項式是否稀疏2分別采用順序和動態(tài)存儲結構實現;3結果M(x中無重復階項和無零系數項;4要求輸出結果的升冪和降冪兩種排列情況5 二叉排序樹的實現用順序和二叉鏈表作存儲結構1回車('n'為輸入結束標志,輸入數列L,生成一棵二叉排序樹T;2對二叉排序樹T作中序遍歷,輸出結果;3輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2;否則輸出信息“無x”;6學生搭配問題一班有m個女生,有n個男生(m不等于n,現要開一個舞會. 男女生分別編號坐在舞池的兩邊的椅子上

6、.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:1輸出每曲配對情況2計算出任何一個男生(編號為X和任意女生(編號為Y,在第K曲配對跳舞的情況.至少求出K的兩個值.3盡量設計出多種算法及程序,可視情況適當加分提示:用隊列來解決比較方便.7敢死隊問題有M個敢死隊員要炸掉敵人的一碉堡,誰都不想去,排長決定用輪回數數的辦法來決定哪個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務,則要再派一個戰(zhàn)士上去?，F給每個戰(zhàn)士編一個號,大家圍坐成一圈,隨便從某一個戰(zhàn)士開始計數,當數到5時,對應的戰(zhàn)士就去執(zhí)行任務,且此戰(zhàn)士不再參加下一

7、輪計數。如果此戰(zhàn)士沒完成任務,再從下一個戰(zhàn)士開始數數,被數到第5時,此戰(zhàn)士接著去執(zhí)行任務。以此類推,直到任務完成為止。排長是不愿意去的,假設排長為1號,請你設計一程序,求出從第幾號戰(zhàn)士開始計數才能讓排長最后一個留下來而不去執(zhí)行任務。要求:至少采用兩種不同的數據結構的方法實現。8長整數四則運算要求見嚴蔚敏習題集P801.49停車場管理要求見嚴蔚敏習題集P962.110魔王語言解釋要求見嚴蔚敏習題集P972.211車廂調度要求見嚴蔚敏習題集P972.312算術表達式求值演示要求見嚴蔚敏習題集P992.513銀行業(yè)務模擬要求見嚴蔚敏習題集P1002.614電梯模擬要求見嚴蔚敏習題集P1022.815

8、重言式判別要求見嚴蔚敏習題集P1485.116哈夫曼編碼譯碼器要求見嚴蔚敏習題集P1485.217圖遍歷的應用要求見嚴蔚敏習題集P1505.318全國交通咨詢模擬要求見嚴蔚敏習題集P1515.819圖書管理要求見嚴蔚敏習題集P1666.320平衡二叉樹操作的演示要求見嚴蔚敏習題集P1666.42、課程設計調研根據具體題目要求,由學生查閱指導教師提供的參考書目,以設計小組為單位進行需求分析,初步明確所選用的邏輯結構和存儲結構。3、課程設計方案制定根據討論,明確解決問題的基本算法,完成每個部分的算法設計說明(可以是描述算法的流程圖和每個程序中使用的存儲結構設計說明。4、課程設計報告的要求課程設計報

9、告:(保存在word 文檔中,文件名要求按照"姓名-學號-課程設計報告"起名,如文件名為"張三-001-課程設計報告".doc 按照課程設計的具體要求建立的功能模塊,每個模塊要求按照如下幾個內容認真完成;其中包括:a需求分析:在該部分中敘述,每個模塊的功能要求b概要設計在此說明每個部分的算法設計說明(可以是描述算法的流程圖,每個程序中使用的存儲結構設計說明(如果指定存儲結構請寫出該存儲結構的定義。c詳細設計各個算法實現的源程序,對每個題目要有相應的源程序(可以是一組源程序,每個功能模塊采用不同的函數實現源程序要按照寫程序的規(guī)則來編寫。要結構清晰,重點函數

10、的重點變量,重點功能部分要加上清晰的程序注釋。d調試分析測試數據,測試輸出的結果,時間復雜度分析,和每個模塊設計和調試時存在問題的思考(問題是哪些?問題如何解決?,算法的改進設想。e設計總結:課程設計過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調試能力的思考、對數據結構這門課程的思考、在課程設計過程中對數據結構課程的認識等內容三、課程設計的指導在設計的第一周周三之前教師必須完成對學生的設計方案的檢查,保證無原則性的設計錯誤;在第一周后半周和第二周必須保證每天和學生見面,指導學生解決設計和調試中出現的問題。四、課程設計的質量標準與成績考核課程設計結束時,要求學生寫出課程設計報告(附源程序,可運行的軟件系統(tǒng)。課程設計成績分兩部分,設計報告占30%,設計作品占70%。其中設計報告雷同者按不合格處理;設計作品的成績必須由教師親自對學生的程序進行檢查,先由學生對自己的設計框架和實現過程進行介紹，再由教師至少對學生提出 4 個與程序有關的不同層次的問題， 根據學生的對問題的回答和介紹情況并參考設計過程中的表現給予打分。 評分過程要考慮到 不同題目的難度差異性。 成績分為優(yōu)秀、良好、中、及格，不及格五級。 五、課程設計的工作進度安排 課程設計的