【正文】 算。*實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。*實現(xiàn)提示：（1）每個結(jié)點中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768 5 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個結(jié)點中僅存十進(jìn)制的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制。輸出：這時正面向上的牌有哪些？1圖的建立及輸出*問題描述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。*存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。對有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點。要求：1）建立一個AOE圖，并輸出結(jié)果確保創(chuàng)建成功；2）判斷AOE圖是一個拓?fù)溆行蛐蛄?，如果不是拓?fù)溆行騽t報錯； 3）編寫函數(shù)求AOE圖的關(guān)鍵路徑； 4）打印輸出關(guān)鍵路徑；5）每一個函數(shù)要有必要的注釋，在課程設(shè)計論文中有流程圖。根據(jù)哈夫曼樹的原理求n個自然數(shù)相加減后結(jié)果最?。ㄖ虚g結(jié)果、最后結(jié)果不能負(fù)）。五、課程設(shè)計內(nèi)容每個同學(xué)從下面題目中隨機抽取2—5個題目（具體選幾個，由同學(xué)依據(jù)自己的能力確定，至少有2個），認(rèn)真完成，要求程序能運行，將運行結(jié)果截圖附在課程設(shè)計報告里，源程序代碼要一同打印附在報告后面。本課程設(shè)計的目標(biāo)就是要達(dá)到理論與實際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力，并培養(yǎng)基本的、良好的程序設(shè)計技能以及合作能力。（一）課程設(shè)計性質(zhì)課程設(shè)計是學(xué)生對課程所學(xué)知識的綜合運用，它與課堂聽講、上機實驗、課外練習(xí)、自學(xué)研究相輔相成，構(gòu)成一個完整的課程教學(xué)體系。狄杰斯特算法求最短路徑問題描述：采用狄杰斯特算法求一個頂點到其它頂點的最短路徑。四、指導(dǎo)方式集體輔導(dǎo)與個別輔導(dǎo)相結(jié)合。三．設(shè)計要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。*存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點符號。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。要求每個方格上只進(jìn)入一次，走遍棋盤上全部64個方格。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。⑤顯示：以凹入表的形式顯示B樹。課程設(shè)計按照教學(xué)要求需要1周時間完成，1周中每天至少要上68小時的機來調(diào)試C語言設(shè)計的程序，總共至少要上機調(diào)試程序30小時。[選作內(nèi)容]擴充運算符集合。（3）假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。[基本要求]以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。[基本要求]實現(xiàn)以下4條基本編輯命令：（1）行插入。行尾可用一個特殊的ASCII字符（如(012)8）標(biāo)識。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。3）橙色的實心小圓圈表示起點，綠色實心圓圈表示終點，空心圓圈表示足跡，紅色方塊表示墻。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實現(xiàn)兩個矩陣相加、相減和相乘的運算。④歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。六、成績考核與評定學(xué)生課程設(shè)計結(jié)束后寫出總結(jié)報告，對設(shè)計的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計期間的表現(xiàn)，指導(dǎo)老師對每位學(xué)生寫出評語和鑒定，系課程設(shè)計領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計成績，課程設(shè)計成績分為優(yōu)、良、中、及格和不及格五個等級?；驘o實習(xí)報告，沒有通過答辯。（3）在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。相加過程中不要破壞兩個操作數(shù)鏈表。（2）要求：輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。例如：當(dāng)T=10，各件物品的體積{1，8，4，3，5，2}時，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。b+a’是屬該模式的字符序列，而‘１+３amp。（3）系統(tǒng)應(yīng)實現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號后登記到圖書帳目中去。*選作內(nèi)容：（1）擴充運算符集，如增加乘方、單目減、賦值等運算；（2）運算量可以是變量；（3）運算量可以是實數(shù)類型；（4）計數(shù)器的功能和仿鎮(zhèn)界面。1編制一個求解迷宮通路的圖形界面演示程序。[問題描述]很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的?？紤]到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320activemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費。一種解決方法是逐段地編輯。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。引入表達(dá)式起始、結(jié)束符是為了方便。程序能夠運行，要有基本的容錯功能。如果這種書在帳目中已有，則只將總庫存量增加。22．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。*問題描述：1）輸入一個任意大小的迷宮，任設(shè)起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。相加過程中不要破壞兩個操作數(shù)鏈表。*輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；一元多項式計算*問題描述：能夠按照指數(shù)降序排列建立并輸出多項式； 能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；在上交資料中請寫明：存儲結(jié)構(gòu)、多項式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進(jìn)方法；訂票系統(tǒng)*問題描述：通過此系統(tǒng)可以實現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達(dá)城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達(dá)城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班； 4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。1B樹問題描述：完成B樹的創(chuàng)建、查找、插入和刪除。普里姆算法求最小生成樹問題描述：用普里姆算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。2． 程序質(zhì)量（50%）3． 實習(xí)報告（30%）七、成果形式除要求提供正確的程序源代碼文件及相關(guān)數(shù)據(jù)文件可供演示檢查外，應(yīng)強調(diào)文檔的分量、完善性和規(guī)范性要求，文檔應(yīng)有相當(dāng)?shù)恼挤直壤?。第一篇：《?shù)據(jù)結(jié)構(gòu)課程設(shè)計》教學(xué)大綱201112《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》教學(xué)大綱一、課程基本信息課程英文名稱：Data Structure Course Designing課程類別：專業(yè)基礎(chǔ)課程課程學(xué)時：2周學(xué)分：2先修課程：《C語言程序設(shè)計基礎(chǔ)》、《離散數(shù)學(xué)》、《數(shù)據(jù)結(jié)構(gòu)》適用專業(yè)：信息計算大綱執(zhí)筆：計算機科學(xué)與技術(shù)教研室 楊先鳳大綱審批：計算機科學(xué)學(xué)院學(xué)術(shù)委員會制定(修訂)時間：2011年12 一．課程設(shè)計性質(zhì)本實踐性教學(xué)環(huán)節(jié)為信息計算專業(yè)所開設(shè)的專業(yè)基礎(chǔ)必修課。實習(xí)報告的開頭應(yīng)給出題目、班級、姓名、學(xué)號和完成日期，并包括課題分析、方案確定、概要設(shè)計、詳細(xì)設(shè)計、調(diào)試分析、用戶使用說明、測試結(jié)果、附錄（帶注釋的源程序，或文件名清單）等幾個主要方面內(nèi)容。要求：1）先生成一個網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲來完成； 3）最后打印輸出最小生成樹；4）每一個函數(shù)要有必要的注釋，在課程設(shè)計論文中有流程圖。要求：1）創(chuàng)建一顆B樹，并打印輸出；2）分別編寫函數(shù)完成B的查找、插入和刪除；3）測試B樹的查找、插入和刪除，分別打印測試結(jié)果； 4）每一個函數(shù)要有必要的注釋，在課程設(shè)計論文中有流程圖。程序能夠運行，要有基本的容錯功能。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 *要求：根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能；迷宮求解*問題描述：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進(jìn)方法；文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。*輸出的形式：數(shù)字大小逐個遞增的數(shù)列?1圖的遍歷*問題描述：對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進(jìn)隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。2）根據(jù)用戶界面提示，用鍵盤輸入。利用“稀疏”特點進(jìn)行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。②清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。試為停車場編制按上述要求進(jìn)行管理的模擬程序。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲，每個標(biāo)準(zhǔn)行塊含81個字符。試寫一個程序，演示無向圖的遍歷操作。*問題描述：1）輸入一個任意大小的迷宮，任設(shè)起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。17．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。如果這種書在帳目中已有，則只將總庫存量增加。３－１’則不是。提示：可利用回溯法的設(shè)計思想來解決背包問題。輸出的形式：數(shù)字大小逐個遞增的數(shù)列1圖的遍歷 對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進(jìn)隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。四、時間安排《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》安排在第三學(xué)期進(jìn)行，時間2周（1718周）。2．成績評定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(shè)計》 譚浩強 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 。2．課程設(shè)計實行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教