第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱計(jì)科

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》

教學(xué)大綱

哈爾濱師范大學(xué)

計(jì)算機(jī)學(xué)與信息工程學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》

一、課程設(shè)置的有關(guān)說明 1.課程性質(zhì)

本課程屬于集中實(shí)踐教學(xué)環(huán)節(jié)，是在學(xué)習(xí)了C語言、面向?qū)ο蟪绦蛟O(shè)計(jì)（C++）和數(shù)據(jù)結(jié)構(gòu)后開設(shè)的。數(shù)據(jù)結(jié)構(gòu)是一門較為抽象的課程，在學(xué)習(xí)完該課程后，學(xué)生往往會(huì)覺得其實(shí)際應(yīng)用難以理解。通過安排相應(yīng)的實(shí)踐，可以讓學(xué)生認(rèn)識(shí)到該課程的實(shí)用性和重要性。

2.課程定義

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是計(jì)算機(jī)科學(xué)專業(yè)本科學(xué)生必修的實(shí)踐課程，本課程設(shè)計(jì)旨在培養(yǎng)學(xué)生的將理論應(yīng)用于實(shí)踐的能力?？倢W(xué)分1學(xué)分，在第5學(xué)期4周集中進(jìn)行，主要訓(xùn)練學(xué)生綜合運(yùn)用C語言、C++、面向?qū)ο蟪绦蛟O(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問題，使學(xué)生能熟練的設(shè)計(jì)算法并有效的實(shí)現(xiàn)。3.設(shè)置課程的目的和教學(xué)基本要求 設(shè)置課程的目的：

通過對(duì)本課程的學(xué)習(xí)，培養(yǎng)學(xué)生進(jìn)一步理解和掌握所學(xué)的各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛟O(shè)計(jì)中的使用方法，使學(xué)生具備初步的獨(dú)立分析和設(shè)計(jì)能力； 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能； 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力； 訓(xùn)練用系統(tǒng)的觀點(diǎn)進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。

基本要求：

1）設(shè)計(jì)和調(diào)試過程要規(guī)范化。①需求分析

將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方。

②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）

源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。

2）課程設(shè)計(jì)報(bào)告的書寫格式 ①設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析

⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3）實(shí)施方式

可設(shè)一人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末4周時(shí)間內(nèi)完成。（或在下學(xué)期開學(xué)4周時(shí)間內(nèi)完成）。4）考核方式

課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫出課程設(shè)計(jì)報(bào)告（附源程序），可運(yùn)行的軟件系統(tǒng) 課程設(shè)計(jì)成績(jī)分兩部分，設(shè)計(jì)報(bào)告占30％，設(shè)計(jì)作品占70％。按照優(yōu)秀、良好、中、及格，不及格五級(jí)給予成績(jī)。4.教學(xué)內(nèi)容簡(jiǎn)介

通過指導(dǎo)教師命題或?qū)W生自擬題目的方式，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。最終按要求上交一份3000字左右數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（附源程序）。

二、設(shè)計(jì)參考題目

1、一元多項(xiàng)式計(jì)算 *問題描述：

能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

2、迷宮求解 *問題描述：

可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

3、joseph環(huán) *問題描述：

編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。*要求：

利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(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ù)，將正確的輸出序列

4、建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；

5、赫夫曼樹的建立 *問題描述：

建立建立最優(yōu)二叉樹函數(shù) *要求：

可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

6、圖的建立及輸出 *問題描述：

建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣

7、拓?fù)渑判?*問題描述：

編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?/p>

8、圖的遍歷 *問題描述：

對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。

三、時(shí)間進(jìn)度

學(xué)生課程設(shè)計(jì)時(shí)間安排如下： 第1周初，布置題目 第2周末，中期檢查

第3周末，個(gè)別指導(dǎo)難度突破 第4周末，驗(yàn)收

四、閱讀參考書目：

《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 2007年3月

《《數(shù)據(jù)結(jié)構(gòu)》算法實(shí)現(xiàn)及解析》（第二版）高一凡 西安電子科技大學(xué)出版社 2004年10月

《c語言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》 李春保 清華大學(xué)出版社 2004年2月 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 1999年2月 《c/c++與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 2008年3月

《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社 2005年4月

第二篇：《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱

適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 課程周數(shù)：2周

一、大綱說明

本大綱根據(jù)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)人才培養(yǎng)方案制訂。

（一）課程設(shè)計(jì)性質(zhì)

課程設(shè)計(jì)是學(xué)生對(duì)課程所學(xué)知識(shí)的綜合運(yùn)用，它與課堂聽講、上機(jī)實(shí)驗(yàn)、課外練習(xí)、自學(xué)研究相輔相成，構(gòu)成一個(gè)完整的課程教學(xué)體系。

（二）主要先修課程和后續(xù)課程 1.先修課程：《C語言程序設(shè)計(jì)》 2.后續(xù)課程：《計(jì)算機(jī)組成原理》、《操作系統(tǒng)》、《數(shù)據(jù)庫系統(tǒng)原理》

二、課程設(shè)計(jì)目的及基本要求

《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性強(qiáng)的課程，其中對(duì)算法設(shè)計(jì)和程序編寫的掌握尤為重要。學(xué)生雖然可以通過與課堂教學(xué)同步的上機(jī)實(shí)驗(yàn)完成相關(guān)內(nèi)容的練習(xí)，但卻往往局限于一些功能簡(jiǎn)單、彼此之間關(guān)系獨(dú)立的算法和程序。課程設(shè)計(jì)是一種綜合訓(xùn)練，致力于培養(yǎng)學(xué)生全面、靈活的算法設(shè)計(jì)思想和較高的編程能力，為今后從事計(jì)算機(jī)開發(fā)與應(yīng)用打下基礎(chǔ)。新世紀(jì)需要具有豐富科學(xué)知識(shí)、獨(dú)立解決實(shí)際問題、有創(chuàng)造能力的新型人才，這也是該課程設(shè)計(jì)的最終目的。

三、課程設(shè)計(jì)內(nèi)容及安排

1、矩陣的轉(zhuǎn)置、加減和相乘

問題描述：采用十字鏈表存儲(chǔ)的稀疏矩陣，完成矩陣轉(zhuǎn)置、加減和相乘功能。要求：

1）采用函數(shù)形式完成轉(zhuǎn)置、相加、相減和相乘； 2）有輸入數(shù)據(jù)合法性檢查； 3）矩陣的存儲(chǔ)采用動(dòng)態(tài)數(shù)組；

4）兩個(gè)矩陣產(chǎn)生后要分別打印出來，完成相應(yīng)處理后結(jié)果要打印出來； 5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

2、線索二叉樹

問題描述：實(shí)現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。要求：

1）各功能模塊必須是單獨(dú)的函數(shù)； 2）線索二叉樹是動(dòng)態(tài)生存的； 3）輸入數(shù)據(jù)進(jìn)行必要的合法性檢查；

4）執(zhí)行每一個(gè)功能后，按二叉樹廣義表的表達(dá)方式打印輸出，檢查結(jié)果是否正確； 5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

3、根據(jù)哈夫曼樹的原理求n個(gè)自然數(shù)相加減后結(jié)果最小（中間結(jié)果、最后結(jié)果不能負(fù)）。

問題描述：實(shí)現(xiàn)線索二叉樹的生成、遍歷、查找、插入和刪除操作。要求：

1）可以循環(huán)測(cè)試，可以選擇退出程序；

2）打印這n個(gè)自然數(shù)進(jìn)行加減的表達(dá)式（注意：中間結(jié)果不能為負(fù)）； 例如：輸入1,2,3，最后打印出3-2-1=0 3）輸入數(shù)據(jù)要進(jìn)行合法性檢查；

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

4、普里姆算法求最小生成樹

問題描述：用普里姆算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。要求：

1）先生成一個(gè)網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲(chǔ)來完成； 3）最后打印輸出最小生成樹；

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

5、克魯斯卡爾算法求最小生成樹

問題描述：用克魯斯卡爾算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。要求：

1）先生成一個(gè)網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲(chǔ)來完成； 3）最后打印輸出最小生成樹；

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

6、狄杰斯特算法求最短路徑

問題描述：采用狄杰斯特算法求一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑。要求：

1）先生成一個(gè)帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成狄杰斯特算法；

3）打印輸出最后的該頂點(diǎn)到其它頂點(diǎn)的路徑，并打印最短路徑。4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

7、佛洛依德算法求最短路徑

問題描述：采用佛洛依德算法求每對(duì)頂點(diǎn)到其它頂點(diǎn)的最短路徑。要求：

1）先生成一個(gè)帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成佛洛依德算法； 3）打印輸出每對(duì)頂點(diǎn)的最短路徑。

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

8、分塊查找

問題描述：采用分塊查找的方法查找指定的關(guān)鍵碼。要求：

1）可以循環(huán)查找，可以選擇退出；

2）分別采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)完成分塊查找，其中在順序存儲(chǔ)結(jié)果下，索引表的查找采用二分查找；

3）分別用函數(shù)完成索引表查找和塊中查找；

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

9、關(guān)鍵路徑

問題描述：建立AOE圖，確定其拓?fù)溆行蚝笄箨P(guān)鍵路徑。要求：

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ì)論文中有流程圖。

10、二叉排序樹

問題描述：完成二叉排序樹的創(chuàng)建、查找、插入和刪除操作。要求：

1）創(chuàng)建一顆二叉排序樹，并打印輸出；

2）分別編寫函數(shù)完成二叉排序樹的查找、插入和刪除； 3）測(cè)試二叉排序樹的查找、插入和刪除，分別打印測(cè)試結(jié)果； 4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

11、B-樹

問題描述：完成B-樹的創(chuàng)建、查找、插入和刪除。要求：

1）創(chuàng)建一顆B-樹，并打印輸出；

2）分別編寫函數(shù)完成B-的查找、插入和刪除；

3）測(cè)試B-樹的查找、插入和刪除，分別打印測(cè)試結(jié)果； 4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

12、哈希表查找

問題描述：定義一個(gè)哈希表和對(duì)哈希表進(jìn)行插入、查找和刪除、打印。要求：

1）定義一個(gè)哈希表，并打印輸出結(jié)果； 2）分別編寫函數(shù)完成查找、插入和刪除； 3）測(cè)試查找、插入和刪除，分別打印測(cè)試結(jié)果；

4）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。

四、指導(dǎo)方式

集體輔導(dǎo)與個(gè)別輔導(dǎo)相結(jié)合。

五、課程設(shè)計(jì)考核方法及成績(jī)?cè)u(píng)定

1、程序清單：代碼應(yīng)具有詳細(xì)注釋，用來說明程序的功能、結(jié)構(gòu)；

2、設(shè)計(jì)報(bào)告：報(bào)告中應(yīng)包含上機(jī)時(shí)遇到的問題及解決辦法，觀察到的現(xiàn)象及其分析，對(duì)程序設(shè)計(jì)技巧的總結(jié)及分析等；程序的輸出結(jié)果及對(duì)結(jié)果的分析；實(shí)驗(yàn)的心得體會(huì)，以及其它信息；

3、提交時(shí)，須向指導(dǎo)教師說明：程序的使用方法，調(diào)用方法、操作步驟等；要求輸入信息的類型及格式；出錯(cuò)信息的含義及程序的適用范圍等。

成績(jī)?cè)u(píng)定：課程設(shè)計(jì)成績(jī)分兩部分，設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占60％。

六、課程設(shè)計(jì)教材及主要參考資料 教學(xué)參考書

[1]李素若.《數(shù)據(jù)結(jié)構(gòu)》.北京：化學(xué)工業(yè)出版社，2009.參考資料：

[1] 朱蓉，《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書》

[2]嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)(C語言版)，1999，清華大學(xué)出版社； [3]嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)，1999，清華大學(xué)出版社； [4]徐孝凱，數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)，2002，清華大學(xué)出版社；

[5]孟佳娜 胡瀟琨，算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與習(xí)題，2004，機(jī)械工業(yè)出版社；

七、其他 i=[1] t=[12] i=[2] t=[4] i=[3] t=[10] i=[4] t=[12] i=[5] t=[1] i=[6] t=[2] i=[7] t=[2] i=[8] t=[11] i=[9] t=[5] i=[10] t=[10] i=[11] t=[11] i=[12] t=[8] i=[13] t=[2] i=[14] t=[3] i=[15] t=[9] i=[16] t=[7] i=[17] t=[5] i=[18] t=[6] i=[19] t=[12] i=[20] t=[7] i=[21] t=[3] i=[22] t=[7] i=[23] t=[8] i=[24] t=[6] i=[25] t=[7] i=[26] t=[8] i=[27] t=[3] i=[28] t=[2] i=[29] t=[7] i=[30] t=[4] i=[31] t=[3] i=[32] t=[8] i=[33] t=[9] i=[34] t=[1] i=[35] t=[1] i=[36] t=[3] i=[37] t=[8] i=[38] t=[1] i=[39] t=[10] i=[40] t=[12] i=[41] t=[10] i=[42] t=[9] i=[43] t=[12] i=[44] t=[2] i=[45] t=[1] i=[46] t=[6] i=[47] t=[4] i=[48] t=[7] i=[49] t=[1]

第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱

Data Structure Course Design

一、課程的性質(zhì)、教學(xué)目的和要求

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(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í)際問題的能力。

二、設(shè)計(jì)要點(diǎn)

1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。① 需求分析

將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。

給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。

對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。

如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）

源程序要按照寫程序的規(guī)則來編寫。要結(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è)計(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)》課程開課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。

三．設(shè)計(jì)要求

學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天至少要上3-4小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的成成，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。

四．設(shè)計(jì)題目

1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)

*問題描述：參加運(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é)?？偡郑?)．可以按學(xué)校編號(hào)、學(xué)校總分、男女團(tuán)體總分排序輸出；

4).可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。

規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xià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ù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計(jì)的書上，請(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料中寫明；

2、一元多項(xiàng)式計(jì)算

*問題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式； 能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

3、訂票系統(tǒng)

*問題描述：通過此系統(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ù)文件；

客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 *要求：

根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；

4、迷宮求解

*問題描述：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

5、文章編輯

*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過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)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。

*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；

6、joseph環(huán)

*問題描述：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(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、猴子選大王

*問題描述：一堆猴子都有編號(hào)，編號(hào)是1，2，3...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n

8、建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；

9、赫夫曼樹的建立

*問題描述：建立建立最優(yōu)二叉樹函數(shù)

*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

10、紙牌游戲

*問題描述：編號(hào)為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過。輸出：這時(shí)正面向上的牌有哪些？

11、圖的建立及輸出

*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

12、拓?fù)渑判?/p>

*問題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?/p>

13、各種排序

*問題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。

*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?

14、圖的遍歷

*問題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。

15、線性表的操作

*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。

16、長(zhǎng)整數(shù)四則運(yù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)隔開。*測(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位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。

（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)

點(diǎn)數(shù)目。相加過程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。

17、馬踏棋盤

*問題描述：將馬隨機(jī)放在國(guó)際象棋的8 8棋盤Bord[8Ⅱ8]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入�個(gè)8 8的方陣，輸出之。*測(cè)試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。

*實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。

18、校園導(dǎo)游咨詢 *問題描述：

（1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。

（2）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。

（3）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。

*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。

19、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問題描述：

1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。

2）根據(jù)用戶界面提示，用鍵盤輸入。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ì)算器

*問題描述：一元多項(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á)式求值演示

*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。

*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。

*實(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ù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。

22．稀疏矩陣運(yù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ù)均不超過20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。23．圖書管理

*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。

*基本要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、作者、現(xiàn)存量和總庫存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用B樹對(duì)書號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。④歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。⑤顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列B樹的打印格式如下所示：

50，52 70，72

8

第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱

Data Structure Course Design

一、課程的性質(zhì)、教學(xué)目的和要求

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(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í)際問題的能力。

二、設(shè)計(jì)要點(diǎn)

1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。① 需求分析

將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。

給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。

對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。

如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）

源程序要按照寫程序的規(guī)則來編寫。要結(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è)計(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)》課程開課學(xué)期布置題目，然后在期末前兩周完成。

三．設(shè)計(jì)要求

學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上6-8小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。

四．設(shè)計(jì)題目

1、校園導(dǎo)游程序

[問題描述]

用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。

[基本要求]（1）查詢各景點(diǎn)的相關(guān)信息；

（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。

（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。

（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。

[選作內(nèi)容]

（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。

（2）區(qū)分機(jī)動(dòng)車道和人行道。

（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。

2、算術(shù)表達(dá)式求值

[問題描述]

一個(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）從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。

（2）顯示輸入序列和棧的變化過程。

[選作內(nèi)容]

擴(kuò)充運(yùn)算符集合。

引入變量操作數(shù)。

操作數(shù)類型擴(kuò)充到實(shí)數(shù)。

3、文學(xué)研究助手

[問題描述]

文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。[基本要求]

英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]

以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]

設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。

如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]

（1）模式匹配要基于KMP算法。

（2）整個(gè)統(tǒng)計(jì)過程中只對(duì)小說文字掃描一遍以提高效率。

（3）假設(shè)小說中的每個(gè)單詞或者從行首開始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。

（4）推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）

4.迷宮求解

[問題描述]

可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；

[基本要求]

含有兩個(gè)以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

[實(shí)現(xiàn)提示]

可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。

5.括號(hào)匹配的檢驗(yàn)

[問題描述]

假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來描述。例如：考慮下列的括號(hào)序列：

[([ ] [ ])]

8

當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類似的，因只等來了第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)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類推?？梢娺@個(gè)處理過程正好和棧的特點(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ǎng)管理

[問題描述]

設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[測(cè)試數(shù)據(jù)]

設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。[基本要求]

以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(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)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。[實(shí)現(xiàn)提示]

需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。[選作內(nèi)容]

（1）兩個(gè)棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。

（3）汽車可以直接從便道上開走，此時(shí)排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾。

（4）停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低，請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。

7.簡(jiǎn)單行編輯程序

[問題描述]

文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè)文件每行不超過320個(gè)字符，很少超過80字符。[基本要求]

實(shí)現(xiàn)以下4條基本編輯命令：

（1）行插入。格式：i<行號(hào)><回車><文本><回車>

將<文本>插入活區(qū)中第<行號(hào)>行之后

（2）行刪除。格式：d<行號(hào)1>[□<行號(hào)2>]<回車>

刪除活區(qū)中第<行號(hào)1>行（到第<行號(hào)2>行）。兩種格式的例子是：“d10↙”和“d10□14↙”

（3）活區(qū)切換。格式：n<回車>

將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。

（4）活區(qū)顯示。格式：p<回車>

逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請(qǐng)用戶決定是否繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置以行號(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）來描述。考慮到文本文件行長(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 鏈表連接起來。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ASCII字符（如(012)8）標(biāo)識(shí)。此外，還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。

（2）初始化過程包括：請(qǐng)用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlen-x。x的值可以自定，例如20。

（3）在執(zhí)行行插入命令的過程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過activemaxlen，應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。

（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個(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><回車>和m<串><回車>。

8.圖遍歷的演示

[問題描述]

很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個(gè)程序，演示無向圖的遍歷操作。[基本要求]

以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。[測(cè)試數(shù)據(jù)]

由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。[實(shí)現(xiàn)提示]

設(shè)圖的結(jié)點(diǎn)不超過30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。

[選作內(nèi)容]

（1）借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。

（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹

（3）實(shí)現(xiàn)有向圖的遍歷操作。

9、赫夫曼樹的建立

*問題描述：建立建立最優(yōu)二叉樹函數(shù)

*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

10、圖的建立及輸出

*問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

11、各種排序

*問題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。

*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?

12、圖的遍歷

*問題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。

13、線性表的操作

*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。

14、編制一個(gè)求解迷宮通路的圖形界面演示程序。*問題描述：

1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。

2）根據(jù)用戶界面提示，用鍵盤輸入。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ì)算器

*問題描述：一元多項(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á)式求值演示

*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。

*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。

*實(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ù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。

17．稀疏矩陣運(yù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ù)均不超過20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。18．圖書管理

*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。

*基本要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、作者、現(xiàn)存量和總庫存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用B樹對(duì)書號(hào)盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。④歸還：注銷對(duì)借閱者的登記，改變?cè)摃默F(xiàn)存量。⑤顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列B樹的打印格式如下所示：

19、文章編輯

*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁文章，每行最多不超過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)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。

*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；

50，52 70，72

20、回文判斷

[問題描述]

試寫一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘１+３&３－１’則不是。[實(shí)現(xiàn)提示]

首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。

21、建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；

五、參考書目

《數(shù)據(jù)結(jié)構(gòu) C語言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語言程序設(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語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社

《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社

計(jì)算機(jī)軟件教研室 2004年1月7日

第五篇：《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱

課程名稱： 課程編號(hào)： 適用專業(yè)： 總 學(xué) 分： 總 學(xué) 時(shí)： 其中實(shí)驗(yàn)學(xué)時(shí) 主 撰 人： 撰寫日期：

一、目的與任務(wù)

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(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í)際問題的能力。

二、教學(xué)基本要求

1．設(shè)計(jì)和調(diào)試過程要規(guī)范化

需求分析：將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。

給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。

對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。

如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）

源程序要按照寫程序的規(guī)則來編寫。要結(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è)計(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)》課程開課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。

4．答辯：課題的論述、測(cè)試及問題回答

三、課程設(shè)計(jì)內(nèi)容

1、背包問題的求解：

假設(shè)有一個(gè)能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。例如：當(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ì)思想來解決背包問題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復(fù)，直至求得滿足條件的解，或者無解。

由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。

2、訂票系統(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ù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。

5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件（2）要求

根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；

3、迷宮求解（1）問題描述

可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

4、dijkstra算法求最短路徑

問題描述：從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）

1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊

3）程序所能達(dá)到的功能：輸出用dijkstra算法求出的一條最短路徑。

5、joseph環(huán)（1）問題描述

編號(hào)是1，2，??,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(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、建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實(shí)行層序、先序遍歷等算法

（2）要求：能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；

7、赫夫曼樹的建立

（1）問題描述：建立建立最優(yōu)二叉樹函數(shù)

（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹

在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；

8、圖的建立及輸出

（1）問題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型）

（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

9、拓?fù)渑判?/p>

（1）問題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉＃?）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)

10、各種排序

（1）問題描述：對(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、線性表的操作

利用鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。

13、長(zhǎng)整數(shù)四則運(yù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)隔開。*測(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位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。

（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)

點(diǎn)數(shù)目。相加過程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。

14、克魯斯?fàn)査惴ㄇ笞钚∩蓸?/p>

問題描述：從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）

1)首先輸入圖的結(jié)點(diǎn)數(shù)->num 2)依次輸入圖的各條邊

3)程序所能達(dá)到的功能：能夠輸出這個(gè)圖的一棵最小生成樹

15、算術(shù)表達(dá)式求值演示

（1）問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例3-1演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。

16．稀疏矩陣運(yù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ù)均不超過20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(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)豐富的專業(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é)束后寫出總結(jié)報(bào)告，對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對(duì)每位學(xué)生寫出評(píng)語和鑒定，系課程設(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ù)。撰寫了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。

② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù)，成績(jī)較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。

③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。通過了答辯。

④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失。或無實(shí)習(xí)報(bào)告，沒有通過答辯。

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án)蔚敏 清華大學(xué)出版社 2006.2 《c語言程序設(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語言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 2010.6 《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析》李春葆 清華大學(xué)出版社2006.4