【正文】 大學出版社計算機軟件教研室 2004年1月7日第五篇：《數(shù)據(jù)結(jié)構(gòu)課程設計》教學大綱《數(shù)據(jù)結(jié)構(gòu)課程設計》教學大綱課程名稱： 課程編號： 適用專業(yè)： 總 學 分： 總 學 時： 其中實驗學時 主 撰 人： 撰寫日期：一、目的與任務《數(shù)據(jù)結(jié)構(gòu)》是計算機軟件的一門基礎課程，計算機科學各領(lǐng)域及有關(guān)的應用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。為了學好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點，同時提高解決計算機應用實際問題的能力。二、教學基本要求1．設計和調(diào)試過程要規(guī)范化需求分析：將題目中要求的功能進行敘述分析，并且設計解決此問題的數(shù)據(jù)存儲結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關(guān)鍵語句的時間復雜度。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進行測試的結(jié)果列出來。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。程序能夠運行，要有基本的容錯功能。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。2．課程設計實習報告的書寫格式① 設計題目數(shù)據(jù)結(jié)構(gòu) 408104 計算機科學與技術(shù) 72 30 2012．6436104 軟件工程審 核 人：②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結(jié)果分析 ⑧收獲及體會 3．實施方式可設34人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學期布置題目，然后在期末兩周時間內(nèi)完成。4．答辯：課題的論述、測試及問題回答三、課程設計內(nèi)容背包問題的求解：假設有一個能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。例如：當T=10，各件物品的體積{1，8，4，3，5，2}時，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。提示：可利用回溯法的設計思想來解決背包問題。首先將物品排成一列，然后順序選取物品裝入背包，假設已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復，直至求得滿足條件的解，或者無解。由于回溯求解的規(guī)則規(guī)則是“后進先出”因此自然要用到棧。訂票系統(tǒng)（1）問題描述通過此系統(tǒng)可以實現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。5）修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件（2）要求根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結(jié)構(gòu)，設計程序完成功能；迷宮求解（1）問題描述可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復雜度、另外可以提出算法的改進方法；dijkstra算法求最短路徑問題描述：從鍵盤上輸入一個圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點數(shù)num 2)依次輸入圖的各條邊3）程序所能達到的功能：輸出用dijkstra算法求出的一條最短路徑。joseph環(huán)（1）問題描述編號是1，2，??,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。（2）要求 利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。（3）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個人的密碼，建立單循環(huán)鏈表。（5）輸出形式：建立一個輸出函數(shù)，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立（1）問題描述：建立建立最優(yōu)二叉樹函數(shù)（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復雜度、另外可以提出算法的改進方法；圖的建立及輸出（1）問題描述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型）（2）要求：能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。拓撲排序（1）問題描述：編寫函數(shù)實現(xiàn)圖的拓撲排序。（2）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點各種排序（1）問題描述：對30000個隨機整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。（2）要求：輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個遞增的數(shù)列1圖的遍歷 對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。1線性表的操作利用鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數(shù)、輸出等運算反復實現(xiàn)鏈表的這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。1長整數(shù)四則運算*問題描述：設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。任何整形變量的范圍是(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）每個結(jié)點中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當于按32768進制存放，在十進制與32768進制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個結(jié)點中僅存十進制的4位，即不超過9999的非負整數(shù)，整個鏈表表示為萬進制。（2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。1克魯斯爾算法求最小生成樹問題描述：從鍵盤上輸入一個圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點數(shù)num 2)依次輸入圖的各條邊3)程序所能達到的功能：能夠輸出這個圖的一棵最小生成樹1算術(shù)表達式求值演示（1）問題描述：表達式求值是實現(xiàn)程序設計語言的基本問題之一，也是棧的應用的一個典型例子。設計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達式。利用教材中給出的算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值，并仿照教材例31演示在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。16．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本原酸的運算器。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實現(xiàn)兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*實現(xiàn)提示：（1）首先應輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否匹配。可設矩陣的行數(shù)和列數(shù)均不超過20。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計算效率。（3）在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應該另生成，乘積矩陣也可以用二維數(shù)組存放。四、時間安排《數(shù)據(jù)結(jié)構(gòu)課程設計》安排在第三學期進行，時間2周（1718周）。五、組織管理1．由院、系指派經(jīng)驗豐富的專業(yè)教師擔任指導教師。2．課程設計實行指導教師負責制，由指導教師全面負責課程設計的指導與管理工作。六、成績考核與評定學生課程設計結(jié)束后寫出總結(jié)報告，對設計的內(nèi)容和效果進行總結(jié)，按照學生在設計期間的表現(xiàn)，指導老師對每位學生寫出評語和鑒定，系課程設計領(lǐng)導小組組織答辯，最后確定每位學生課程設計成績，課程設計成績分為優(yōu)、良、中、及格和不及格五個等級。課程設計成績?yōu)槠綍r表現(xiàn)30%、設計報告50%、答辯20%。評分標準：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學校的各項紀律。工作認真，積極 主動，吃苦耐勞，能出色的完成設計任務。撰寫了高質(zhì)量的總結(jié)報告。答辯準確流利。② 良好：目的明確，態(tài)度端正，能遵守學校的各項紀律，工作比較積極主動。能較好地完成設計任務，成績較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實習報告。答辯較準確流利。③ 及格：目的明確，態(tài)度基本端正，能遵守學校紀律，在督促下能開展工作 并完成一定的設計任務，無大的違紀違規(guī)現(xiàn)象；撰寫了實習報告。通過了答辯。④ 不及格：實習態(tài)度端正，不能遵守實習單位的紀律，不服從領(lǐng)導，自由散漫，工作消極被動，不能完成實習任務，實習期間有失職、曠工、打架、酗酒等大的過失?；驘o實習報告，沒有通過答辯。2．成績評定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴蔚敏 清華大學出版社 《c語言程序設計》 譚浩強 清華大學出版社 《數(shù)據(jù)結(jié)構(gòu)習題》 李春保 清華大學出版社 《數(shù)據(jù)結(jié)構(gòu)習題》 嚴蔚敏 清華大學出版社 《c語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學出版社 《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習題與解析》李春葆