在日常學(xué)習(xí)、工作或生活中，大家總少不了接觸作文或者范文吧，通過(guò)文章可以把我們那些零零散散的思想，聚集在一塊。寫(xiě)范文的時(shí)候需要注意什么呢？有哪些格式需要注意呢？以下是小編為大家收集的優(yōu)秀范文，歡迎大家分享閱讀。
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇一
data structure course design
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、設(shè)計(jì)要點(diǎn)
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。① 需求分析
將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。
2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)2-3人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末前兩周完成。
三．設(shè)計(jì)要求
學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上6-8小時(shí)的機(jī)來(lái)調(diào)試c語(yǔ)言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。
四．設(shè)計(jì)題目
1、校園導(dǎo)游程序
[問(wèn)題描述]
用無(wú)向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問(wèn)題。
[基本要求]（1）查詢(xún)各景點(diǎn)的相關(guān)信息；
（2）查詢(xún)圖中任意兩個(gè)景點(diǎn)間的最短路徑。
（3）查詢(xún)圖中任意兩個(gè)景點(diǎn)間的所有路徑。
（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。
[選作內(nèi)容]
（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。
（2）區(qū)分機(jī)動(dòng)車(chē)道和人行道。
（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。
2、算術(shù)表達(dá)式求值
[問(wèn)題描述]
一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。
[基本要求]
（1）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。
（2）顯示輸入序列和棧的變化過(guò)程。
[選作內(nèi)容]
擴(kuò)充運(yùn)算符集合。
引入變量操作數(shù)。
操作數(shù)類(lèi)型擴(kuò)充到實(shí)數(shù)。
3、文學(xué)研究助手
[問(wèn)題描述]
文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為“文學(xué)研究助手”。[基本要求]
英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]
以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]
設(shè)小說(shuō)中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。
如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把kmp算法改寫(xiě)成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]
（1）模式匹配要基于kmp算法。
（2）整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。
（3）假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序，與kmp算法統(tǒng)計(jì)程序進(jìn)行效率比較。
（4）推廣到更一般的模式集匹配問(wèn)題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）
4.迷宮求解
[問(wèn)題描述]
可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；
[基本要求]
含有兩個(gè)以上的迷宮圖，由用戶(hù)選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
[實(shí)現(xiàn)提示]
可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹(shù)的深度優(yōu)先和廣度優(yōu)先算法。
5.括號(hào)匹配的檢驗(yàn)
[問(wèn)題描述]
假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即cc或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來(lái)描述。例如：考慮下列的括號(hào)序列：
[([ ] [ ])]
8
當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類(lèi)似的，因只等來(lái)了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿(mǎn)足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類(lèi)推?？梢?jiàn)這個(gè)處理過(guò)程正好和棧的特點(diǎn)相吻合。
[基本要求]
設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，若是右括號(hào)，則或者是和當(dāng)前棧頂?shù)睦ㄌ?hào)相匹配，或者是不合法的情況，輸出“此串括號(hào)匹配不合法”。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。
[測(cè)試數(shù)據(jù)]
輸入 #（[ ]（））#，結(jié)果“匹配”
輸入 #[（）]#，結(jié)果“此串括號(hào)匹配不合法”
#為起始和結(jié)束標(biāo)志。
6.停車(chē)場(chǎng)管理
[問(wèn)題描述]
設(shè)停車(chē)場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在車(chē)場(chǎng)的最北端），若車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛汽車(chē)，則后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后開(kāi)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其它車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[測(cè)試數(shù)據(jù)]
設(shè)n=2,輸入數(shù)據(jù)為：（‘a(chǎn)’，1，5），（‘a(chǎn)’，2，10），（‘d’，1，15），（‘a(chǎn)’，3，20），（‘a(chǎn)’，4，25），（‘a(chǎn)’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘a(chǎn)’表示到達(dá)；‘d’表示離去，‘e’表示輸入結(jié)束。[基本要求]
以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)離去；則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。[實(shí)現(xiàn)提示]
需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車(chē)讓路而從停車(chē)場(chǎng)退出來(lái)的汽車(chē)，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車(chē)，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的牌照號(hào)碼和進(jìn)入停車(chē)場(chǎng)的時(shí)刻。[選作內(nèi)容]
（1）兩個(gè)棧共享空間，思考應(yīng)開(kāi)辟數(shù)組的空間是多少？
（2）汽車(chē)可有不同種類(lèi)，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車(chē)和1.5輛小汽車(chē)的占地面積相同，1輛十輪卡車(chē)占地面積相當(dāng)于3輛小汽車(chē)的占地面積。
（3）汽車(chē)可以直接從便道上開(kāi)走，此時(shí)排在它前面的汽車(chē)要先開(kāi)走讓路，然后再依次排到隊(duì)尾。
（4）停放在便道上的汽車(chē)也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車(chē)場(chǎng)的車(chē)低，請(qǐng)思考如何修改結(jié)構(gòu)以滿(mǎn)足這種要求。
7.簡(jiǎn)單行編輯程序
[問(wèn)題描述]
文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱(chēng)為行編輯程序。
被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，稱(chēng)為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè)文件每行不超過(guò)320個(gè)字符，很少超過(guò)80字符。[基本要求]
實(shí)現(xiàn)以下4條基本編輯命令：
（1）行插入。格式：i<行號(hào)><回車(chē)><文本><回車(chē)>
將<文本>插入活區(qū)中第<行號(hào)>行之后
（2）行刪除。格式：d<行號(hào)1>[□<行號(hào)2>]<回車(chē)>
刪除活區(qū)中第<行號(hào)1>行（到第<行號(hào)2>行）。兩種格式的例子是：“d10↙”和“d10□14↙”
（3）活區(qū)切換。格式：n<回車(chē)>
將活區(qū)寫(xiě)入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。
（4）活區(qū)顯示。格式：p<回車(chē)>
逐頁(yè)地（每頁(yè)20行）顯示活區(qū)內(nèi)容，每顯示一頁(yè)之后請(qǐng)用戶(hù)決定是否繼續(xù)顯示以后各頁(yè)（如果存在）。印出的每一行要前置以行號(hào)和一個(gè)空格符，行號(hào)固定占4位，增量為1。
各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。[測(cè)試數(shù)據(jù)]
由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如首行、尾行。[實(shí)現(xiàn)提示]
（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來(lái)描述?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布，且峰值在60到70之間，用320×activemaxlen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ)，每個(gè)標(biāo)準(zhǔn)行塊含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài) 8 鏈表連接起來(lái)。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ascii字符（如(012)8）標(biāo)識(shí)。此外，還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。
（2）初始化過(guò)程包括：請(qǐng)用戶(hù)提供輸入文件名（空串表示無(wú)輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過(guò)activemaxlen-x。x的值可以自定，例如20。
（3）在執(zhí)行行插入命令的過(guò)程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過(guò)activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。
（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。
（5）可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。[選作內(nèi)容]
（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。
（2）加入更復(fù)雜的編輯操作，如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為s<行號(hào)>@<串1>@<串2><回車(chē)>和m<串><回車(chē)>。
8.圖遍歷的演示
[問(wèn)題描述]
很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫(xiě)一個(gè)程序，演示無(wú)向圖的遍歷操作。[基本要求]
以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶(hù)指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪(fǎng)問(wèn)序列和相應(yīng)生成樹(shù)的邊集。[測(cè)試數(shù)據(jù)]
由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。[實(shí)現(xiàn)提示]
設(shè)圖的結(jié)點(diǎn)不超過(guò)30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。通過(guò)輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。
[選作內(nèi)容]
（1）借助于棧類(lèi)型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。
（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)，再按凹入表或樹(shù)形打印生成樹(shù)
（3）實(shí)現(xiàn)有向圖的遍歷操作。
9、赫夫曼樹(shù)的建立
*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
*要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
10、圖的建立及輸出
*問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
11、各種排序
*問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。
*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?
12、圖的遍歷
*問(wèn)題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
13、線(xiàn)性表的操作
*問(wèn)題描述：利作鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
14、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問(wèn)題描述：
1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。
2）根據(jù)用戶(hù)界面提示，用鍵盤(pán)輸入。home鍵設(shè)置迷宮起點(diǎn)，end鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，enter鍵添加墻，del鍵刪除墻，完成后按f9鍵演示，esc鍵退出。
3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)mazepath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在maze_text中實(shí)現(xiàn)）。
5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“error： you must set startplace.”；未輸入終點(diǎn)時(shí)，顯示“error： you must set endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)path found，否則消去足跡，顯示path not found.15．一元稀疏多項(xiàng)式計(jì)算器
*問(wèn)題描述：一元多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。
16．算術(shù)表達(dá)式求值演示
*問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。
*基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。
*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類(lèi)型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。
17．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。18．圖書(shū)管理
*問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。
*基本要求：（1）每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用b樹(shù)對(duì)書(shū)號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫(kù)：新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)后登記到圖書(shū)帳目中去。如果這種書(shū)在帳目中已有，則只將總庫(kù)存量增加。②清除庫(kù)存：某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)帳目中注銷(xiāo)。③某種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。④歸還：注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。⑤顯示：以凹入表的形式顯示b樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列b樹(shù)的打印格式如下所示：
19、文章編輯
*問(wèn)題描述：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行。
*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
*存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。
*輸出形式：（1）分行輸出用戶(hù)輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
50，52 70，72
20、回文判斷
[問(wèn)題描述]
試寫(xiě)一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。[實(shí)現(xiàn)提示]
首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。
21、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問(wèn)題描述：
要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
五、參考書(shū)目
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社
《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社
《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社
計(jì)算機(jī)軟件教研室 2004年1月7日
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇二
綜合課程設(shè)計(jì)1 ——《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門(mén)課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能
二、設(shè)計(jì)要點(diǎn)
1、通過(guò)這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。
2、學(xué)生必須仔細(xì)研讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)(實(shí)習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨(dú)立地完成課程設(shè)計(jì)的任務(wù)，有問(wèn)題及時(shí)主動(dòng)與指導(dǎo)教師溝通。
3、本次課程設(shè)計(jì)按照教學(xué)要求需要獨(dú)立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)地向指導(dǎo)教師匯報(bào)。
4、編程語(yǔ)言任選。
三、設(shè)計(jì)題目
1、集合的并、交和算差運(yùn)
任務(wù)：編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。要求:(1)集合的元素限定為小寫(xiě)字母字符 [‘a(chǎn)’..’z’]。(2)演示程序以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式執(zhí)行。實(shí)現(xiàn)提示:以鏈表表示集合。
選作內(nèi)容:(1)集合的元素判定和子集判定運(yùn)算。
(2)求集合的補(bǔ)集。
(3)集合的混合運(yùn)算表達(dá)式求值。
(4)集合的元素類(lèi)型推廣到其他類(lèi)型，甚至任意類(lèi)型。
2、停車(chē)場(chǎng)管理
任務(wù)：設(shè)停車(chē)場(chǎng)是一個(gè)可以停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次有北向南排列（大門(mén)在最南端，最先到達(dá)的第一車(chē)停放在車(chē)場(chǎng)的最北端），若車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛車(chē)，那么后來(lái)的車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其他車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。
要求：以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停車(chē)不收費(fèi)）。棧以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。
3、哈夫曼碼的編/譯碼系統(tǒng) 【問(wèn)題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能：
（1）i:初始化（initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmtree中。
（2）e:編碼（encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree中讀入），對(duì)文件tobetran中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中。（3）d:譯碼（decoding）。利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。
（4）p:打印代碼文件（print）。將文件codefile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件codeprin中。
（5）t:打印哈夫曼樹(shù)（tree printing）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀(guān)的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。【測(cè)試數(shù)據(jù)】
（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。
（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“this program is my favorite”。
字符 空格 a b c d e f g h i j k l m 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
【實(shí)現(xiàn)提示】
（1）編碼結(jié)果以文本方式存儲(chǔ)在文件codefile中。
（2）用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“q”，表示退出運(yùn)行quit。請(qǐng)用戶(hù)鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶(hù)選擇了“q”為止。
（3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行i，d或e命令之后，哈夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行i命令，因?yàn)槲募fmtree可能早已建好。
4、校園導(dǎo)游咨詢(xún)
任務(wù)：設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪(fǎng)的客人提供各種信息查詢(xún)服務(wù)。
要求：
（1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。
（2）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。
（3）為來(lái)訪(fǎng)客人提供景點(diǎn)的問(wèn)路查詢(xún)，即已知一個(gè)景點(diǎn)，查詢(xún)到某景點(diǎn)之間的一條最短路徑及長(zhǎng)度。
5、散列表的設(shè)計(jì)與實(shí)現(xiàn)
任務(wù)：設(shè)計(jì)散列表實(shí)現(xiàn)電話(huà)號(hào)碼查找系統(tǒng)。要求：
（1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：用戶(hù)名、電話(huà)號(hào)碼、地址；
2（2）從鍵盤(pán)輸入各記錄，以用戶(hù)名（漢語(yǔ)拼音形式）為關(guān)鍵字建立散列表；（3）采用一定的方法解決沖突；
（4）查找并顯示給定電話(huà)號(hào)碼的記錄； 選作內(nèi)容：
（1）系統(tǒng)功能的完善；
（2）設(shè)計(jì)不同的散列函數(shù)，比較沖突率；
（3）在散列函數(shù)確定的前提下，嘗試各種不同類(lèi)型處理沖突的方法，考察平均查找長(zhǎng)度的變化。
6、文章編輯
功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行； 要求:（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：
（1）分行輸出用戶(hù)輸入的各行字符；
（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
四、參考書(shū)目
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社
《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社
《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社
《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇三
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程設(shè)計(jì)教學(xué)大綱
course design of data structure
課程代碼：
適用專(zhuān)業(yè)：信息計(jì)算、信息安全 總學(xué)時(shí)數(shù)：1周編寫(xiě)年月：2004年7月
執(zhí) 筆：劉科峰、李小英、高學(xué)軍
課程性質(zhì)：設(shè)計(jì)（論文）/必修 開(kāi)課學(xué)期：5 總學(xué)分?jǐn)?shù)：1 修訂年月：2007年7月
一、課程設(shè)計(jì)的性質(zhì)和目的
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是本學(xué)院本科專(zhuān)業(yè)的集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合應(yīng)用練習(xí)。其目的就是要達(dá)到理論與實(shí)際相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。
二、課程設(shè)計(jì)內(nèi)容及學(xué)時(shí)分配
寫(xiě)出不少于3000字的課程設(shè)計(jì)說(shuō)明書(shū)。說(shuō)明書(shū)中除了在封面中應(yīng)有題目、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期以外，其正文一般有如下幾個(gè)方面的內(nèi)容：
1.需求分析 2.概要設(shè)計(jì) 3.詳細(xì)設(shè)計(jì) 4.調(diào)試分析 5.測(cè)試結(jié)果 6.附錄或參考資料
三、課程設(shè)計(jì)教學(xué)基本要求
四、課程設(shè)計(jì)選題
根據(jù)教材《數(shù)據(jù)結(jié)構(gòu)題集（c語(yǔ)言版）》（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，或選擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過(guò)設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。
1． 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)系統(tǒng)； 2． 停車(chē)場(chǎng)管理系統(tǒng)； 3． 民航售票系統(tǒng)； 4． 有理數(shù)四則運(yùn)算器； 5． 文本格式化器； 6． 哈夫曼編/譯碼器； 7． 教學(xué)計(jì)劃編制； 8． 計(jì)算機(jī)輔助考核系統(tǒng)；
9． 學(xué)籍管理系統(tǒng)； 10． 圖書(shū)管理系統(tǒng)。
五、本課程與其它課程的聯(lián)系與分工
本課程是《數(shù)據(jù)結(jié)構(gòu)》的配套課程，學(xué)完《數(shù)據(jù)結(jié)構(gòu)》后進(jìn)行的綜合性課程設(shè)計(jì)。
六、成績(jī)?cè)u(píng)定
由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計(jì)說(shuō)明書(shū)的質(zhì)量和課程設(shè)計(jì)過(guò)程中的工作態(tài)度等綜合打分。課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫(xiě)出課程設(shè)計(jì)報(bào)告，可運(yùn)行的軟件系統(tǒng)（包括源程序）。課程設(shè)計(jì)成績(jī)：上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占40％。
成績(jī)?cè)u(píng)定實(shí)行優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。優(yōu)秀者人數(shù)一般不得超過(guò)總?cè)藬?shù)的20%。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計(jì)，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。有關(guān)的考查相關(guān)材料（文字材料以及磁盤(pán)或光盤(pán)）統(tǒng)一妥善保管。
七、建議教材與教學(xué)參考書(shū)
[1] 《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社
[2] 《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏 吳偉民 米寧 編著，清華大學(xué)出版社
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇四
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
data structure course design
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、設(shè)計(jì)要點(diǎn)
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。① 需求分析
將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。
2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)3-4人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。
三．設(shè)計(jì)要求
學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天至少要上3-4小時(shí)的機(jī)來(lái)調(diào)試c語(yǔ)言設(shè)計(jì)的成成，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。
四．設(shè)計(jì)題目
1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)
*問(wèn)題描述：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）*功能要求：
1).可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)； 2)．能統(tǒng)計(jì)各學(xué)?？偡?，3)．可以按學(xué)校編號(hào)、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；
4).可以按學(xué)校編號(hào)查詢(xún)學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢(xún)?nèi)〉们叭蚯拔迕膶W(xué)校。
規(guī)定：輸入數(shù)據(jù)形式和范圍：20以?xún)?nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱(chēng)，運(yùn)動(dòng)項(xiàng)目的名稱(chēng)）
輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形
界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。
*存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫(xiě)方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書(shū)上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；
測(cè)試數(shù)據(jù)：要求使用
1、全部合法數(shù)據(jù)；
2、整體非法數(shù)據(jù)；
3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫(xiě)明；
2、一元多項(xiàng)式計(jì)算
*問(wèn)題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式； 能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過(guò)程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
3、訂票系統(tǒng)
*問(wèn)題描述：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢(xún)：
可以查詢(xún)某個(gè)航線(xiàn)的情況（如，輸入航班號(hào)，查詢(xún)起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿(mǎn)倉(cāng)）； 可以輸入起飛抵達(dá)城市，查詢(xún)飛機(jī)航班情況；
3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班； 4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；
客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 *要求：
根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；
4、迷宮求解
*問(wèn)題描述：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
5、文章編輯
*問(wèn)題描述：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行。
*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
*存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。
*輸出形式：（1）分行輸出用戶(hù)輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
6、joseph環(huán)
*問(wèn)題描述：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。
*測(cè)試數(shù)據(jù)：
m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？
*輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。
*輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列
7、猴子選大王
*問(wèn)題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n
8、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問(wèn)題描述：
要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
9、赫夫曼樹(shù)的建立
*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
*要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
10、紙牌游戲
*問(wèn)題描述：編號(hào)為1-52張牌，正面向上，從第2張開(kāi)始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過(guò)。輸出：這時(shí)正面向上的牌有哪些？
11、圖的建立及輸出
*問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
12、拓?fù)渑判?BR> *問(wèn)題描述：編寫(xiě)函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?BR> 13、各種排序
*問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。
*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?
14、圖的遍歷
*問(wèn)題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
15、線(xiàn)性表的操作
*問(wèn)題描述：利作鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
16、長(zhǎng)整數(shù)四則運(yùn)算
*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是-(2^151)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。*測(cè)試數(shù)據(jù)：
（1）0；0；應(yīng)輸出“0”。
（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；-1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1”。
（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。
（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。
*實(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位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。
（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)
點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。
17、馬踏棋盤(pán)
*問(wèn)題描述：將馬隨機(jī)放在國(guó)際象棋的8 8棋盤(pán)bord[8ⅱ8]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線(xiàn)，并按求出的行走路線(xiàn)，將數(shù)字1，2，?，64依次填入個(gè)8 8的方陣，輸出之。*測(cè)試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。
*實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過(guò)的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。
18、校園導(dǎo)游咨詢(xún) *問(wèn)題描述：
（1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。
（2）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)的問(wèn)路查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。
（3）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。
*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。
19、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問(wèn)題描述：
1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。
2）根據(jù)用戶(hù)界面提示，用鍵盤(pán)輸入。home鍵設(shè)置迷宮起點(diǎn)，end鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，enter鍵添加墻，del鍵刪除墻，完成后按f9 鍵演示，esc鍵退出。
3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)mazepath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在maze_text中實(shí)現(xiàn)）。
5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“error： you must set startplace.”；未輸入終點(diǎn)時(shí)，顯示“error： you must set endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)path found，否則消去足跡，顯示path not found.20．一元稀疏多項(xiàng)式計(jì)算器
*問(wèn)題描述：一元多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。
21．算術(shù)表達(dá)式求值演示
*問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。
*基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。
*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類(lèi)型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。
22．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。23．圖書(shū)管理
*問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。
*基本要求：（1）每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用b樹(shù)對(duì)書(shū)號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫(kù)：新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)后登記到圖書(shū)帳目中去。如果這種書(shū)在帳目中已有，則只將總庫(kù)存量增加。②清除庫(kù)存：某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)帳目中注銷(xiāo)。③某種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。④歸還：注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。⑤顯示：以凹入表的形式顯示b樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列b樹(shù)的打印格式如下所示：
50，52 70，72
8
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇五
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
課程名稱(chēng)： 課程編號(hào)： 適用專(zhuān)業(yè)： 總 學(xué) 分： 總 學(xué) 時(shí)： 其中實(shí)驗(yàn)學(xué)時(shí) 主 撰 人： 撰寫(xiě)日期：
一、目的與任務(wù)
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、教學(xué)基本要求
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化
需求分析：將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目
數(shù)據(jù)結(jié)構(gòu) 408104 計(jì)算機(jī)科學(xué)與技術(shù) 72 30 2012．6
436104 軟件工程
審 核 人：
②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)3-4人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。
4．答辯：課題的論述、測(cè)試及問(wèn)題回答
三、課程設(shè)計(jì)內(nèi)容
1、背包問(wèn)題的求解：
假設(shè)有一個(gè)能裝入總體積為t的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿(mǎn)背包，即使w1 +w2 + … + wn=t，要求找出所有滿(mǎn)足上述條件的解。例如：當(dāng)t=10，各件物品的體積{1，8，4，3，5，2}時(shí)，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。
提示：可利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒(méi)有裝滿(mǎn)，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿(mǎn)為止。但如果在剩余的物品中找不到合適的物品以填滿(mǎn)背包，則說(shuō)明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再?gòu)摹八蟆钡奈锲分羞x取，如此重復(fù)，直至求得滿(mǎn)足條件的解，或者無(wú)解。
由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。
2、訂票系統(tǒng)（1）問(wèn)題描述
通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢(xún)： 可以查詢(xún)某個(gè)航線(xiàn)的情況（如，輸入航班號(hào)，查詢(xún)起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿(mǎn)倉(cāng)）；
可以輸入起飛抵達(dá)城市，查詢(xún)飛機(jī)航班情況；
3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；
4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。
5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件（2）要求
根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；
3、迷宮求解（1）問(wèn)題描述
可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
4、dijkstra算法求最短路徑
問(wèn)題描述：從鍵盤(pán)上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）
1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊
3）程序所能達(dá)到的功能：輸出用dijkstra算法求出的一條最短路徑。
5、joseph環(huán)（1）問(wèn)題描述
編號(hào)是1，2，??,n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。（3）測(cè)試數(shù)據(jù)：
m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？
（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。
（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列
6、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問(wèn)題描述：建立二叉樹(shù)，并實(shí)行層序、先序遍歷等算法
（2）要求：能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
7、赫夫曼樹(shù)的建立
（1）問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
（2）要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
8、圖的建立及輸出
（1）問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型）
（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
9、拓?fù)渑判?BR> （1）問(wèn)題描述：編寫(xiě)函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判?。?）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)
10、各種排序
（1）問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。（2）要求：輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。
輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列
11、圖的遍歷 對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
12、線(xiàn)性表的操作
利用鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
13、長(zhǎng)整數(shù)四則運(yùn)算
*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是-(2^151)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。*測(cè)試數(shù)據(jù)：
（1）0；0；應(yīng)輸出“0”。
（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；-1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1”。
（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*實(shí)現(xiàn)提示：
（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。
（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)
點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。
14、克魯斯?fàn)査惴ㄇ笞钚∩蓸?shù)
問(wèn)題描述：從鍵盤(pán)上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）
1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊
3)程序所能達(dá)到的功能：能夠輸出這個(gè)圖的一棵最小生成樹(shù)
15、算術(shù)表達(dá)式求值演示
（1）問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。（2）基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
16．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。
四、時(shí)間安排
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時(shí)間2周（17-18周）。
五、組織管理
1．由院、系指派經(jīng)驗(yàn)豐富的專(zhuān)業(yè)教師擔(dān)任指導(dǎo)教師。
2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。
六、成績(jī)考核與評(píng)定
學(xué)生課程設(shè)計(jì)結(jié)束后寫(xiě)出總結(jié)報(bào)告，對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對(duì)每位學(xué)生寫(xiě)出評(píng)語(yǔ)和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績(jī)，課程設(shè)計(jì)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。
課程設(shè)計(jì)成績(jī)?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評(píng)分標(biāo)準(zhǔn)：
① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真，積極 主動(dòng)，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。撰寫(xiě)了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。
② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù)，成績(jī)較突出，表現(xiàn)良好；撰寫(xiě)了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。
③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開(kāi)展工作 并完成一定的設(shè)計(jì)任務(wù)，無(wú)大的違紀(jì)違規(guī)現(xiàn)象；撰寫(xiě)了實(shí)習(xí)報(bào)告。通過(guò)了答辯。
④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過(guò)失?；驘o(wú)實(shí)習(xí)報(bào)告，沒(méi)有通過(guò)答辯。
2．成績(jī)?cè)u(píng)定
依據(jù)上述考核內(nèi)容，最后采用優(yōu)（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五級(jí)記分制評(píng)定學(xué)生課程設(shè)計(jì)成績(jī)。
七、主要參考資料
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 2006.2 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 2010.8 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 2006.4 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 2006.2 《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 2010.6 《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社2006.4
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇一
data structure course design
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、設(shè)計(jì)要點(diǎn)
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。① 需求分析
將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。
2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)2-3人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末前兩周完成。
三．設(shè)計(jì)要求
學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上6-8小時(shí)的機(jī)來(lái)調(diào)試c語(yǔ)言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。
四．設(shè)計(jì)題目
1、校園導(dǎo)游程序
[問(wèn)題描述]
用無(wú)向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問(wèn)題。
[基本要求]（1）查詢(xún)各景點(diǎn)的相關(guān)信息；
（2）查詢(xún)圖中任意兩個(gè)景點(diǎn)間的最短路徑。
（3）查詢(xún)圖中任意兩個(gè)景點(diǎn)間的所有路徑。
（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。
[選作內(nèi)容]
（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。
（2）區(qū)分機(jī)動(dòng)車(chē)道和人行道。
（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。
2、算術(shù)表達(dá)式求值
[問(wèn)題描述]
一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。
[基本要求]
（1）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。
（2）顯示輸入序列和棧的變化過(guò)程。
[選作內(nèi)容]
擴(kuò)充運(yùn)算符集合。
引入變量操作數(shù)。
操作數(shù)類(lèi)型擴(kuò)充到實(shí)數(shù)。
3、文學(xué)研究助手
[問(wèn)題描述]
文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為“文學(xué)研究助手”。[基本要求]
英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]
以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]
設(shè)小說(shuō)中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。
如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把kmp算法改寫(xiě)成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]
（1）模式匹配要基于kmp算法。
（2）整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。
（3）假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序，與kmp算法統(tǒng)計(jì)程序進(jìn)行效率比較。
（4）推廣到更一般的模式集匹配問(wèn)題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）
4.迷宮求解
[問(wèn)題描述]
可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；
[基本要求]
含有兩個(gè)以上的迷宮圖，由用戶(hù)選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
[實(shí)現(xiàn)提示]
可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹(shù)的深度優(yōu)先和廣度優(yōu)先算法。
5.括號(hào)匹配的檢驗(yàn)
[問(wèn)題描述]
假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即cc或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來(lái)描述。例如：考慮下列的括號(hào)序列：
[([ ] [ ])]
8
當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類(lèi)似的，因只等來(lái)了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿(mǎn)足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類(lèi)推?？梢?jiàn)這個(gè)處理過(guò)程正好和棧的特點(diǎn)相吻合。
[基本要求]
設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，若是右括號(hào)，則或者是和當(dāng)前棧頂?shù)睦ㄌ?hào)相匹配，或者是不合法的情況，輸出“此串括號(hào)匹配不合法”。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。
[測(cè)試數(shù)據(jù)]
輸入 #（[ ]（））#，結(jié)果“匹配”
輸入 #[（）]#，結(jié)果“此串括號(hào)匹配不合法”
#為起始和結(jié)束標(biāo)志。
6.停車(chē)場(chǎng)管理
[問(wèn)題描述]
設(shè)停車(chē)場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在車(chē)場(chǎng)的最北端），若車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛汽車(chē)，則后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后開(kāi)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其它車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[測(cè)試數(shù)據(jù)]
設(shè)n=2,輸入數(shù)據(jù)為：（‘a(chǎn)’，1，5），（‘a(chǎn)’，2，10），（‘d’，1，15），（‘a(chǎn)’，3，20），（‘a(chǎn)’，4，25），（‘a(chǎn)’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘a(chǎn)’表示到達(dá)；‘d’表示離去，‘e’表示輸入結(jié)束。[基本要求]
以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)離去；則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。[實(shí)現(xiàn)提示]
需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車(chē)讓路而從停車(chē)場(chǎng)退出來(lái)的汽車(chē)，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車(chē)，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)的牌照號(hào)碼和進(jìn)入停車(chē)場(chǎng)的時(shí)刻。[選作內(nèi)容]
（1）兩個(gè)棧共享空間，思考應(yīng)開(kāi)辟數(shù)組的空間是多少？
（2）汽車(chē)可有不同種類(lèi)，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車(chē)和1.5輛小汽車(chē)的占地面積相同，1輛十輪卡車(chē)占地面積相當(dāng)于3輛小汽車(chē)的占地面積。
（3）汽車(chē)可以直接從便道上開(kāi)走，此時(shí)排在它前面的汽車(chē)要先開(kāi)走讓路，然后再依次排到隊(duì)尾。
（4）停放在便道上的汽車(chē)也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車(chē)場(chǎng)的車(chē)低，請(qǐng)思考如何修改結(jié)構(gòu)以滿(mǎn)足這種要求。
7.簡(jiǎn)單行編輯程序
[問(wèn)題描述]
文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱(chēng)為行編輯程序。
被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，稱(chēng)為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè)文件每行不超過(guò)320個(gè)字符，很少超過(guò)80字符。[基本要求]
實(shí)現(xiàn)以下4條基本編輯命令：
（1）行插入。格式：i<行號(hào)><回車(chē)><文本><回車(chē)>
將<文本>插入活區(qū)中第<行號(hào)>行之后
（2）行刪除。格式：d<行號(hào)1>[□<行號(hào)2>]<回車(chē)>
刪除活區(qū)中第<行號(hào)1>行（到第<行號(hào)2>行）。兩種格式的例子是：“d10↙”和“d10□14↙”
（3）活區(qū)切換。格式：n<回車(chē)>
將活區(qū)寫(xiě)入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。
（4）活區(qū)顯示。格式：p<回車(chē)>
逐頁(yè)地（每頁(yè)20行）顯示活區(qū)內(nèi)容，每顯示一頁(yè)之后請(qǐng)用戶(hù)決定是否繼續(xù)顯示以后各頁(yè)（如果存在）。印出的每一行要前置以行號(hào)和一個(gè)空格符，行號(hào)固定占4位，增量為1。
各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。[測(cè)試數(shù)據(jù)]
由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如首行、尾行。[實(shí)現(xiàn)提示]
（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來(lái)描述?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布，且峰值在60到70之間，用320×activemaxlen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ)，每個(gè)標(biāo)準(zhǔn)行塊含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài) 8 鏈表連接起來(lái)。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ascii字符（如(012)8）標(biāo)識(shí)。此外，還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。
（2）初始化過(guò)程包括：請(qǐng)用戶(hù)提供輸入文件名（空串表示無(wú)輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過(guò)activemaxlen-x。x的值可以自定，例如20。
（3）在執(zhí)行行插入命令的過(guò)程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過(guò)activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。
（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。
（5）可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。[選作內(nèi)容]
（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。
（2）加入更復(fù)雜的編輯操作，如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為s<行號(hào)>@<串1>@<串2><回車(chē)>和m<串><回車(chē)>。
8.圖遍歷的演示
[問(wèn)題描述]
很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫(xiě)一個(gè)程序，演示無(wú)向圖的遍歷操作。[基本要求]
以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶(hù)指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪(fǎng)問(wèn)序列和相應(yīng)生成樹(shù)的邊集。[測(cè)試數(shù)據(jù)]
由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。[實(shí)現(xiàn)提示]
設(shè)圖的結(jié)點(diǎn)不超過(guò)30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。通過(guò)輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。
[選作內(nèi)容]
（1）借助于棧類(lèi)型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。
（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)，再按凹入表或樹(shù)形打印生成樹(shù)
（3）實(shí)現(xiàn)有向圖的遍歷操作。
9、赫夫曼樹(shù)的建立
*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
*要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
10、圖的建立及輸出
*問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
11、各種排序
*問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。
*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?
12、圖的遍歷
*問(wèn)題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
13、線(xiàn)性表的操作
*問(wèn)題描述：利作鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
14、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問(wèn)題描述：
1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。
2）根據(jù)用戶(hù)界面提示，用鍵盤(pán)輸入。home鍵設(shè)置迷宮起點(diǎn)，end鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，enter鍵添加墻，del鍵刪除墻，完成后按f9鍵演示，esc鍵退出。
3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)mazepath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在maze_text中實(shí)現(xiàn)）。
5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“error： you must set startplace.”；未輸入終點(diǎn)時(shí)，顯示“error： you must set endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)path found，否則消去足跡，顯示path not found.15．一元稀疏多項(xiàng)式計(jì)算器
*問(wèn)題描述：一元多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。
16．算術(shù)表達(dá)式求值演示
*問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。
*基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。
*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類(lèi)型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。
17．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。18．圖書(shū)管理
*問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。
*基本要求：（1）每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用b樹(shù)對(duì)書(shū)號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫(kù)：新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)后登記到圖書(shū)帳目中去。如果這種書(shū)在帳目中已有，則只將總庫(kù)存量增加。②清除庫(kù)存：某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)帳目中注銷(xiāo)。③某種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。④歸還：注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。⑤顯示：以凹入表的形式顯示b樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列b樹(shù)的打印格式如下所示：
19、文章編輯
*問(wèn)題描述：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行。
*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
*存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。
*輸出形式：（1）分行輸出用戶(hù)輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
50，52 70，72
20、回文判斷
[問(wèn)題描述]
試寫(xiě)一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。[實(shí)現(xiàn)提示]
首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。
21、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問(wèn)題描述：
要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
五、參考書(shū)目
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社
《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社
《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社
計(jì)算機(jī)軟件教研室 2004年1月7日
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇二
綜合課程設(shè)計(jì)1 ——《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門(mén)課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能
二、設(shè)計(jì)要點(diǎn)
1、通過(guò)這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。
2、學(xué)生必須仔細(xì)研讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)(實(shí)習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨(dú)立地完成課程設(shè)計(jì)的任務(wù)，有問(wèn)題及時(shí)主動(dòng)與指導(dǎo)教師溝通。
3、本次課程設(shè)計(jì)按照教學(xué)要求需要獨(dú)立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)地向指導(dǎo)教師匯報(bào)。
4、編程語(yǔ)言任選。
三、設(shè)計(jì)題目
1、集合的并、交和算差運(yùn)
任務(wù)：編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。要求:(1)集合的元素限定為小寫(xiě)字母字符 [‘a(chǎn)’..’z’]。(2)演示程序以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式執(zhí)行。實(shí)現(xiàn)提示:以鏈表表示集合。
選作內(nèi)容:(1)集合的元素判定和子集判定運(yùn)算。
(2)求集合的補(bǔ)集。
(3)集合的混合運(yùn)算表達(dá)式求值。
(4)集合的元素類(lèi)型推廣到其他類(lèi)型，甚至任意類(lèi)型。
2、停車(chē)場(chǎng)管理
任務(wù)：設(shè)停車(chē)場(chǎng)是一個(gè)可以停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次有北向南排列（大門(mén)在最南端，最先到達(dá)的第一車(chē)停放在車(chē)場(chǎng)的最北端），若車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛車(chē)，那么后來(lái)的車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其他車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。
要求：以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車(chē)輛到達(dá)，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)或便道上的停車(chē)位置；若是車(chē)輛離去，則輸出汽車(chē)在停車(chē)場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停車(chē)不收費(fèi)）。棧以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。
3、哈夫曼碼的編/譯碼系統(tǒng) 【問(wèn)題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能：
（1）i:初始化（initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmtree中。
（2）e:編碼（encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmtree中讀入），對(duì)文件tobetran中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中。（3）d:譯碼（decoding）。利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。
（4）p:打印代碼文件（print）。將文件codefile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件codeprin中。
（5）t:打印哈夫曼樹(shù)（tree printing）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀(guān)的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。【測(cè)試數(shù)據(jù)】
（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。
（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“this program is my favorite”。
字符 空格 a b c d e f g h i j k l m 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
【實(shí)現(xiàn)提示】
（1）編碼結(jié)果以文本方式存儲(chǔ)在文件codefile中。
（2）用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“q”，表示退出運(yùn)行quit。請(qǐng)用戶(hù)鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶(hù)選擇了“q”為止。
（3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行i，d或e命令之后，哈夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行i命令，因?yàn)槲募fmtree可能早已建好。
4、校園導(dǎo)游咨詢(xún)
任務(wù)：設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪(fǎng)的客人提供各種信息查詢(xún)服務(wù)。
要求：
（1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。
（2）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。
（3）為來(lái)訪(fǎng)客人提供景點(diǎn)的問(wèn)路查詢(xún)，即已知一個(gè)景點(diǎn)，查詢(xún)到某景點(diǎn)之間的一條最短路徑及長(zhǎng)度。
5、散列表的設(shè)計(jì)與實(shí)現(xiàn)
任務(wù)：設(shè)計(jì)散列表實(shí)現(xiàn)電話(huà)號(hào)碼查找系統(tǒng)。要求：
（1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：用戶(hù)名、電話(huà)號(hào)碼、地址；
2（2）從鍵盤(pán)輸入各記錄，以用戶(hù)名（漢語(yǔ)拼音形式）為關(guān)鍵字建立散列表；（3）采用一定的方法解決沖突；
（4）查找并顯示給定電話(huà)號(hào)碼的記錄； 選作內(nèi)容：
（1）系統(tǒng)功能的完善；
（2）設(shè)計(jì)不同的散列函數(shù)，比較沖突率；
（3）在散列函數(shù)確定的前提下，嘗試各種不同類(lèi)型處理沖突的方法，考察平均查找長(zhǎng)度的變化。
6、文章編輯
功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行； 要求:（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：
（1）分行輸出用戶(hù)輸入的各行字符；
（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
四、參考書(shū)目
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)》 高教出版社
《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社
《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社
《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇三
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程設(shè)計(jì)教學(xué)大綱
course design of data structure
課程代碼：
適用專(zhuān)業(yè)：信息計(jì)算、信息安全 總學(xué)時(shí)數(shù)：1周編寫(xiě)年月：2004年7月
執(zhí) 筆：劉科峰、李小英、高學(xué)軍
課程性質(zhì)：設(shè)計(jì)（論文）/必修 開(kāi)課學(xué)期：5 總學(xué)分?jǐn)?shù)：1 修訂年月：2007年7月
一、課程設(shè)計(jì)的性質(zhì)和目的
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是本學(xué)院本科專(zhuān)業(yè)的集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合應(yīng)用練習(xí)。其目的就是要達(dá)到理論與實(shí)際相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。
二、課程設(shè)計(jì)內(nèi)容及學(xué)時(shí)分配
寫(xiě)出不少于3000字的課程設(shè)計(jì)說(shuō)明書(shū)。說(shuō)明書(shū)中除了在封面中應(yīng)有題目、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期以外，其正文一般有如下幾個(gè)方面的內(nèi)容：
1.需求分析 2.概要設(shè)計(jì) 3.詳細(xì)設(shè)計(jì) 4.調(diào)試分析 5.測(cè)試結(jié)果 6.附錄或參考資料
三、課程設(shè)計(jì)教學(xué)基本要求
四、課程設(shè)計(jì)選題
根據(jù)教材《數(shù)據(jù)結(jié)構(gòu)題集（c語(yǔ)言版）》（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，或選擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過(guò)設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。
1． 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)系統(tǒng)； 2． 停車(chē)場(chǎng)管理系統(tǒng)； 3． 民航售票系統(tǒng)； 4． 有理數(shù)四則運(yùn)算器； 5． 文本格式化器； 6． 哈夫曼編/譯碼器； 7． 教學(xué)計(jì)劃編制； 8． 計(jì)算機(jī)輔助考核系統(tǒng)；
9． 學(xué)籍管理系統(tǒng)； 10． 圖書(shū)管理系統(tǒng)。
五、本課程與其它課程的聯(lián)系與分工
本課程是《數(shù)據(jù)結(jié)構(gòu)》的配套課程，學(xué)完《數(shù)據(jù)結(jié)構(gòu)》后進(jìn)行的綜合性課程設(shè)計(jì)。
六、成績(jī)?cè)u(píng)定
由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計(jì)說(shuō)明書(shū)的質(zhì)量和課程設(shè)計(jì)過(guò)程中的工作態(tài)度等綜合打分。課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫(xiě)出課程設(shè)計(jì)報(bào)告，可運(yùn)行的軟件系統(tǒng)（包括源程序）。課程設(shè)計(jì)成績(jī)：上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占40％。
成績(jī)?cè)u(píng)定實(shí)行優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。優(yōu)秀者人數(shù)一般不得超過(guò)總?cè)藬?shù)的20%。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計(jì)，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。有關(guān)的考查相關(guān)材料（文字材料以及磁盤(pán)或光盤(pán)）統(tǒng)一妥善保管。
七、建議教材與教學(xué)參考書(shū)
[1] 《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社
[2] 《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏 吳偉民 米寧 編著，清華大學(xué)出版社
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇四
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
data structure course design
一、課程的性質(zhì)、教學(xué)目的和要求
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、設(shè)計(jì)要點(diǎn)
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。① 需求分析
將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。
2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)3-4人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。
三．設(shè)計(jì)要求
學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天至少要上3-4小時(shí)的機(jī)來(lái)調(diào)試c語(yǔ)言設(shè)計(jì)的成成，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。
四．設(shè)計(jì)題目
1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)
*問(wèn)題描述：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）*功能要求：
1).可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)； 2)．能統(tǒng)計(jì)各學(xué)?？偡?，3)．可以按學(xué)校編號(hào)、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；
4).可以按學(xué)校編號(hào)查詢(xún)學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢(xún)?nèi)〉们叭蚯拔迕膶W(xué)校。
規(guī)定：輸入數(shù)據(jù)形式和范圍：20以?xún)?nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱(chēng)，運(yùn)動(dòng)項(xiàng)目的名稱(chēng)）
輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形
界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。
*存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫(xiě)方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書(shū)上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；
測(cè)試數(shù)據(jù)：要求使用
1、全部合法數(shù)據(jù)；
2、整體非法數(shù)據(jù)；
3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫(xiě)明；
2、一元多項(xiàng)式計(jì)算
*問(wèn)題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式； 能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過(guò)程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
3、訂票系統(tǒng)
*問(wèn)題描述：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢(xún)：
可以查詢(xún)某個(gè)航線(xiàn)的情況（如，輸入航班號(hào)，查詢(xún)起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿(mǎn)倉(cāng)）； 可以輸入起飛抵達(dá)城市，查詢(xún)飛機(jī)航班情況；
3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班； 4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；
客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 *要求：
根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；
4、迷宮求解
*問(wèn)題描述：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
5、文章編輯
*問(wèn)題描述：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共n行。
*要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。
*存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；
*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。
*輸出形式：（1）分行輸出用戶(hù)輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；
6、joseph環(huán)
*問(wèn)題描述：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。
*測(cè)試數(shù)據(jù)：
m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？
*輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。
*輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列
7、猴子選大王
*問(wèn)題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n
8、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問(wèn)題描述：
要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
9、赫夫曼樹(shù)的建立
*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
*要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
10、紙牌游戲
*問(wèn)題描述：編號(hào)為1-52張牌，正面向上，從第2張開(kāi)始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過(guò)。輸出：這時(shí)正面向上的牌有哪些？
11、圖的建立及輸出
*問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
12、拓?fù)渑判?BR> *問(wèn)題描述：編寫(xiě)函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?BR> 13、各種排序
*問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。
*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?
14、圖的遍歷
*問(wèn)題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
15、線(xiàn)性表的操作
*問(wèn)題描述：利作鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
16、長(zhǎng)整數(shù)四則運(yùn)算
*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是-(2^151)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。*測(cè)試數(shù)據(jù)：
（1）0；0；應(yīng)輸出“0”。
（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；-1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1”。
（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。
（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。
*實(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位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。
（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)
點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。
17、馬踏棋盤(pán)
*問(wèn)題描述：將馬隨機(jī)放在國(guó)際象棋的8 8棋盤(pán)bord[8ⅱ8]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線(xiàn)，并按求出的行走路線(xiàn)，將數(shù)字1，2，?，64依次填入個(gè)8 8的方陣，輸出之。*測(cè)試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。
*實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過(guò)的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。
18、校園導(dǎo)游咨詢(xún) *問(wèn)題描述：
（1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。
（2）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)的問(wèn)路查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。
（3）為來(lái)訪(fǎng)客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。
*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。
19、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問(wèn)題描述：
1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。
2）根據(jù)用戶(hù)界面提示，用鍵盤(pán)輸入。home鍵設(shè)置迷宮起點(diǎn)，end鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，enter鍵添加墻，del鍵刪除墻，完成后按f9 鍵演示，esc鍵退出。
3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)mazepath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在maze_text中實(shí)現(xiàn)）。
5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“error： you must set startplace.”；未輸入終點(diǎn)時(shí)，顯示“error： you must set endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)path found，否則消去足跡，顯示path not found.20．一元稀疏多項(xiàng)式計(jì)算器
*問(wèn)題描述：一元多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,cn,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。
21．算術(shù)表達(dá)式求值演示
*問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。
*基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。
*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類(lèi)型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。
22．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。23．圖書(shū)管理
*問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。
*基本要求：（1）每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用b樹(shù)對(duì)書(shū)號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫(kù)：新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)后登記到圖書(shū)帳目中去。如果這種書(shū)在帳目中已有，則只將總庫(kù)存量增加。②清除庫(kù)存：某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)帳目中注銷(xiāo)。③某種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。④歸還：注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。⑤顯示：以凹入表的形式顯示b樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列b樹(shù)的打印格式如下所示：
50，52 70，72
8
數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱篇五
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱
課程名稱(chēng)： 課程編號(hào)： 適用專(zhuān)業(yè)： 總 學(xué) 分： 總 學(xué) 時(shí)： 其中實(shí)驗(yàn)學(xué)時(shí) 主 撰 人： 撰寫(xiě)日期：
一、目的與任務(wù)
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。
二、教學(xué)基本要求
1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化
需求分析：將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。
給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。
對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。
如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）
源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。
程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式
① 設(shè)計(jì)題目
數(shù)據(jù)結(jié)構(gòu) 408104 計(jì)算機(jī)科學(xué)與技術(shù) 72 30 2012．6
436104 軟件工程
審 核 人：
②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式
可設(shè)3-4人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。
4．答辯：課題的論述、測(cè)試及問(wèn)題回答
三、課程設(shè)計(jì)內(nèi)容
1、背包問(wèn)題的求解：
假設(shè)有一個(gè)能裝入總體積為t的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿(mǎn)背包，即使w1 +w2 + … + wn=t，要求找出所有滿(mǎn)足上述條件的解。例如：當(dāng)t=10，各件物品的體積{1，8，4，3，5，2}時(shí)，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。
提示：可利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒(méi)有裝滿(mǎn)，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿(mǎn)為止。但如果在剩余的物品中找不到合適的物品以填滿(mǎn)背包，則說(shuō)明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再?gòu)摹八蟆钡奈锲分羞x取，如此重復(fù)，直至求得滿(mǎn)足條件的解，或者無(wú)解。
由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。
2、訂票系統(tǒng)（1）問(wèn)題描述
通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢(xún)： 可以查詢(xún)某個(gè)航線(xiàn)的情況（如，輸入航班號(hào)，查詢(xún)起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿(mǎn)倉(cāng)）；
可以輸入起飛抵達(dá)城市，查詢(xún)飛機(jī)航班情況；
3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；
4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。
5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件（2）要求
根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；
3、迷宮求解（1）問(wèn)題描述
可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
4、dijkstra算法求最短路徑
問(wèn)題描述：從鍵盤(pán)上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）
1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊
3）程序所能達(dá)到的功能：輸出用dijkstra算法求出的一條最短路徑。
5、joseph環(huán)（1）問(wèn)題描述
編號(hào)是1，2，??,n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。（3）測(cè)試數(shù)據(jù)：
m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？
（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。
（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列
6、建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問(wèn)題描述：建立二叉樹(shù)，并實(shí)行層序、先序遍歷等算法
（2）要求：能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；
7、赫夫曼樹(shù)的建立
（1）問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)
（2）要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)
在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；
8、圖的建立及輸出
（1）問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類(lèi)型）
（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。
9、拓?fù)渑判?BR> （1）問(wèn)題描述：編寫(xiě)函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判?。?）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)
10、各種排序
（1）問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。（2）要求：輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。
輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列
11、圖的遍歷 對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。
12、線(xiàn)性表的操作
利用鏈表的插入運(yùn)算建立線(xiàn)性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。
13、長(zhǎng)整數(shù)四則運(yùn)算
*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是-(2^151)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。*測(cè)試數(shù)據(jù)：
（1）0；0；應(yīng)輸出“0”。
（2）-2345,6789；-7654,3211；應(yīng)輸出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；-1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出“1”。
（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*實(shí)現(xiàn)提示：
（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。
（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)
點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。
14、克魯斯?fàn)査惴ㄇ笞钚∩蓸?shù)
問(wèn)題描述：從鍵盤(pán)上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）
1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊
3)程序所能達(dá)到的功能：能夠輸出這個(gè)圖的一棵最小生成樹(shù)
15、算術(shù)表達(dá)式求值演示
（1）問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。（2）基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。
16．稀疏矩陣運(yùn)算器
*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。
*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。
*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。
四、時(shí)間安排
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時(shí)間2周（17-18周）。
五、組織管理
1．由院、系指派經(jīng)驗(yàn)豐富的專(zhuān)業(yè)教師擔(dān)任指導(dǎo)教師。
2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。
六、成績(jī)考核與評(píng)定
學(xué)生課程設(shè)計(jì)結(jié)束后寫(xiě)出總結(jié)報(bào)告，對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對(duì)每位學(xué)生寫(xiě)出評(píng)語(yǔ)和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績(jī)，課程設(shè)計(jì)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。
課程設(shè)計(jì)成績(jī)?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評(píng)分標(biāo)準(zhǔn)：
① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真，積極 主動(dòng)，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。撰寫(xiě)了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。
② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù)，成績(jī)較突出，表現(xiàn)良好；撰寫(xiě)了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。
③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開(kāi)展工作 并完成一定的設(shè)計(jì)任務(wù)，無(wú)大的違紀(jì)違規(guī)現(xiàn)象；撰寫(xiě)了實(shí)習(xí)報(bào)告。通過(guò)了答辯。
④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過(guò)失?；驘o(wú)實(shí)習(xí)報(bào)告，沒(méi)有通過(guò)答辯。
2．成績(jī)?cè)u(píng)定
依據(jù)上述考核內(nèi)容，最后采用優(yōu)（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五級(jí)記分制評(píng)定學(xué)生課程設(shè)計(jì)成績(jī)。
七、主要參考資料
《數(shù)據(jù)結(jié)構(gòu) c語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 2006.2 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 2010.8 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 2006.4 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 2006.2 《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 2010.6 《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社2006.4