【正文】 輔相成，構(gòu)成一個(gè)完整的課程教學(xué)體系。2． 程序質(zhì)量（50%）3． 實(shí)習(xí)報(bào)告（30%）七、成果形式除要求提供正確的程序源代碼文件及相關(guān)數(shù)據(jù)文件可供演示檢查外，應(yīng)強(qiáng)調(diào)文檔的分量、完善性和規(guī)范性要求，文檔應(yīng)有相當(dāng)?shù)恼挤直壤?。本環(huán)節(jié)主要突出實(shí)際應(yīng)用，尤其要強(qiáng)調(diào)學(xué)生自主設(shè)計(jì)，獨(dú)立思考。4．利用適當(dāng)形式的命題，加深體會(huì)結(jié)構(gòu)化程序設(shè)計(jì)的方法, 培養(yǎng)自頂而下、逐步細(xì)化的編程思維方式。本課程設(shè)計(jì)的目標(biāo)就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能以及合作能力。第一篇：《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱201112《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱一、課程基本信息課程英文名稱：Data Structure Course Designing課程類別：專業(yè)基礎(chǔ)課程課程學(xué)時(shí)：2周學(xué)分：2先修課程：《C語言程序設(shè)計(jì)基礎(chǔ)》、《離散數(shù)學(xué)》、《數(shù)據(jù)結(jié)構(gòu)》適用專業(yè)：信息計(jì)算大綱執(zhí)筆：計(jì)算機(jī)科學(xué)與技術(shù)教研室 楊先鳳大綱審批：計(jì)算機(jī)科學(xué)學(xué)院學(xué)術(shù)委員會(huì)制定(修訂)時(shí)間：2011年12 一．課程設(shè)計(jì)性質(zhì)本實(shí)踐性教學(xué)環(huán)節(jié)為信息計(jì)算專業(yè)所開設(shè)的專業(yè)基礎(chǔ)必修課。1．通過本環(huán)節(jié)的充分編程實(shí)踐和實(shí)際應(yīng)用，進(jìn)一步熟悉與鞏固C語言語法知識(shí)和程序設(shè)計(jì)的基本方法。5．通過一定的文檔要求，培養(yǎng)學(xué)生良好的程序設(shè)計(jì)風(fēng)格,包括程序結(jié)構(gòu)形式,行文格式和程序正文格式等。五、課程設(shè)計(jì)內(nèi)容每個(gè)同學(xué)從下面題目中隨機(jī)抽取2—5個(gè)題目（具體選幾個(gè)，由同學(xué)依據(jù)自己的能力確定，至少有2個(gè)），認(rèn)真完成，要求程序能運(yùn)行，將運(yùn)行結(jié)果截圖附在課程設(shè)計(jì)報(bào)告里，源程序代碼要一同打印附在報(bào)告后面。實(shí)習(xí)報(bào)告的開頭應(yīng)給出題目、班級(jí)、姓名、學(xué)號(hào)和完成日期，并包括課題分析、方案確定、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、調(diào)試分析、用戶使用說明、測(cè)試結(jié)果、附錄（帶注釋的源程序，或文件名清單）等幾個(gè)主要方面內(nèi)容。（二）主要先修課程和后續(xù)課程 ：《C語言程序設(shè)計(jì)》 ：《計(jì)算機(jī)組成原理》、《操作系統(tǒng)》、《數(shù)據(jù)庫系統(tǒng)原理》二、課程設(shè)計(jì)目的及基本要求《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性強(qiáng)的課程，其中對(duì)算法設(shè)計(jì)和程序編寫的掌握尤為重要。三、課程設(shè)計(jì)內(nèi)容及安排矩陣的轉(zhuǎn)置、加減和相乘問題描述：采用十字鏈表存儲(chǔ)的稀疏矩陣，完成矩陣轉(zhuǎn)置、加減和相乘功能。根據(jù)哈夫曼樹的原理求n個(gè)自然數(shù)相加減后結(jié)果最小（中間結(jié)果、最后結(jié)果不能負(fù)）。要求：1）先生成一個(gè)網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲(chǔ)來完成； 3）最后打印輸出最小生成樹；4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）先生成一個(gè)帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成狄杰斯特算法；3）打印輸出最后的該頂點(diǎn)到其它頂點(diǎn)的路徑，并打印最短路徑。4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）建立一個(gè)AOE圖，并輸出結(jié)果確保創(chuàng)建成功；2）判斷AOE圖是一個(gè)拓?fù)溆行蛐蛄?，如果不是拓?fù)溆行騽t報(bào)錯(cuò)； 3）編寫函數(shù)求AOE圖的關(guān)鍵路徑； 4）打印輸出關(guān)鍵路徑；5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）創(chuàng)建一顆B樹，并打印輸出；2）分別編寫函數(shù)完成B的查找、插入和刪除；3）測(cè)試B樹的查找、插入和刪除，分別打印測(cè)試結(jié)果； 4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。五、課程設(shè)計(jì)考核方法及成績?cè)u(píng)定程序清單：代碼應(yīng)具有詳細(xì)注釋，用來說明程序的功能、結(jié)構(gòu)；設(shè)計(jì)報(bào)告：報(bào)告中應(yīng)包含上機(jī)時(shí)遇到的問題及解決辦法，觀察到的現(xiàn)象及其分析，對(duì)程序設(shè)計(jì)技巧的總結(jié)及分析等；程序的輸出結(jié)果及對(duì)結(jié)果的分析；實(shí)驗(yàn)的心得體會(huì)，以及其它信息；提交時(shí)，須向指導(dǎo)教師說明：程序的使用方法，調(diào)用方法、操作步驟等；要求輸入信息的類型及格式；出錯(cuò)信息的含義及程序的適用范圍等。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問題的能力。對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天至少要上34小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的成成，總共至少要上機(jī)調(diào)試程序30小時(shí)。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。*存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 *要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；迷宮求解*問題描述：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；joseph環(huán)*問題描述：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。輸出：這時(shí)正面向上的牌有哪些？1圖的建立及輸出*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?1圖的遍歷*問題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。任何整形變量的范圍是(2^151)。（3）9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；1,0001,0001；應(yīng)輸出“0”。*實(shí)現(xiàn)提示：（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768 5 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入個(gè)8 8的方陣，輸出之。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。2）根據(jù)用戶界面提示，用鍵盤輸入。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在Maze_text中實(shí)現(xiàn)）。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評(píng)判成績的標(biāo)準(zhǔn)之一。（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。引入變量操作數(shù)。[基本要求]英文小說存于一個(gè)文本文件中。[實(shí)現(xiàn)提示]設(shè)小說中的詞匯一律不跨行。如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來描述。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。[問題描述]文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。格式：i將插入活區(qū)中第行之后（2）行刪除。（4）活區(qū)顯示。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ)，每個(gè)標(biāo)準(zhǔn)行塊含81個(gè)字符。此外，還應(yīng)記住活區(qū)起始行號(hào)。x的值可以自定，例如20。（5）可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。試寫一個(gè)程序，演示無向圖的遍歷操作。注意測(cè)試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。[選作內(nèi)容]（1）借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*問題描述：1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)MazePath稍加更改即可求得全部路徑。16．算術(shù)表達(dá)式求值演示*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。17．稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。注意研究教科書中的算法，以便提高計(jì)算效率。*基本要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、作者、現(xiàn)存量和總庫存量等五4。如果這種書在帳目中已有，則只將總庫存量增加。⑤顯示：以凹入表的形式顯示B樹。*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。其中序列1和序列2 中都不含字符‘a(chǎn)mp。３－１’則不是。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問題的能力。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。提示：可利用回溯法的設(shè)計(jì)思想來解決背包問題。訂票系統(tǒng)（1）問題描述通過此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有