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

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

（CurriculumDesignofDataStructures）

課程代碼：06460044

學(xué)分：1.5

周數(shù)：1.5周（其中：講課2學(xué)時(shí)；設(shè)計(jì)學(xué)時(shí)；上機(jī)30學(xué)時(shí)；答辯學(xué)

時(shí)）

先修課程：程序設(shè)計(jì)基礎(chǔ)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)A

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

教材：無

一、課程性質(zhì)與目標(biāo)

（一）課程性質(zhì)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是必修的實(shí)踐性教學(xué)環(huán)節(jié)之一，是學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)A》

課程后的綜合性實(shí)驗(yàn)課程，是對(duì)該課程所學(xué)知識(shí)進(jìn)行的一次全面的綜合訓(xùn)練。《數(shù)據(jù)結(jié)

構(gòu)課程設(shè)計(jì)》著眼于原理與應(yīng)用結(jié)合點(diǎn)，使學(xué)生學(xué)會(huì)如何把書上學(xué)到的知識(shí)用于解決實(shí)

際問題，培養(yǎng)軟件工作所需要的動(dòng)手能力；另一方面，能使書本上的知識(shí)變“活”，起

到深化理解和靈活掌握教學(xué)內(nèi)容的目的。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是軟件設(shè)計(jì)的綜合訓(xùn)

練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧、以至一

整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。

（二）課程目標(biāo)

課程目標(biāo)L知識(shí)方面

1.1全面梳理所學(xué)的數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，進(jìn)一步深入理解數(shù)據(jù)結(jié)構(gòu)的基本概念、

邏輯特性、存儲(chǔ)表示方法、算法描述及其性能分析方法。

1.2熟悉軟件開發(fā)的基本過程，初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、

程序編碼、測(cè)試等基本方法和技能。

課程目標(biāo)2.能力與素質(zhì)方面

2.1具備利用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)解決實(shí)際問題的初步的獨(dú)立分析和設(shè)計(jì)能力。

2.2具有針對(duì)實(shí)際問題的特點(diǎn)選用合適的數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)相應(yīng)的算法并加以實(shí)現(xiàn)

的能力。

2.3具有撰寫比較完善的課程設(shè)計(jì)報(bào)告進(jìn)行論述的能力。

二、課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點(diǎn)的對(duì)應(yīng)關(guān)系

本課程支撐專業(yè)培養(yǎng)計(jì)劃中畢業(yè)要求指標(biāo)點(diǎn)1.4、3.3、3.4、6.3、12.2。

畢業(yè)要求指標(biāo)點(diǎn)L4能夠應(yīng)用專業(yè)知識(shí)解決工程計(jì)算問題；

畢業(yè)要求指標(biāo)點(diǎn)3.3能夠針對(duì)特定軟件需求、可復(fù)用模塊或組件完成數(shù)據(jù)結(jié)構(gòu)和

算法的設(shè)計(jì)；

畢業(yè)要求指標(biāo)點(diǎn)3.4能夠在設(shè)計(jì)中體現(xiàn)創(chuàng)新意識(shí)；

畢業(yè)要求指標(biāo)點(diǎn)6.3能夠撰寫各類軟件工程文檔并進(jìn)行評(píng)價(jià);

畢業(yè)要求指標(biāo)點(diǎn)12.2能夠養(yǎng)成主動(dòng)慣并表現(xiàn)出不斷探索的成效，能夠自我評(píng)價(jià)。

畢業(yè)要求

指標(biāo)點(diǎn)1.4指標(biāo)點(diǎn)3.3指標(biāo)點(diǎn)3.4指標(biāo)點(diǎn)6.3指標(biāo)點(diǎn)12.2

課程目標(biāo)

課程目標(biāo)1.1VV

課程目標(biāo)L2V

課程目標(biāo)2.1VVV

課程目標(biāo)2.2VVV

課程目標(biāo)2.3VV

二、內(nèi)容與進(jìn)度安排

1.內(nèi)容及要求

a.設(shè)計(jì)內(nèi)容

課程設(shè)計(jì)選題和一般要求參見附錄1,課程設(shè)計(jì)選題可以由任課教師根據(jù)實(shí)際情

況適當(dāng)安排。

要求通過設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算

法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。

b.其他要求：

（1）認(rèn)真上機(jī)編程，不得從事與課程設(shè)計(jì)無關(guān)的活動(dòng)。

⑵課程設(shè)計(jì)報(bào)告包括封面、目錄、報(bào)告正文、參考文獻(xiàn)。報(bào)告正文中要給出對(duì)課程

項(xiàng)目功能的簡(jiǎn)要介紹、總體設(shè)計(jì)（功能模塊結(jié)構(gòu)）、詳細(xì)設(shè)計(jì)（采用的邏輯結(jié)構(gòu)

和存儲(chǔ)結(jié)構(gòu)的分析與設(shè)計(jì)）、算法設(shè)計(jì)以及關(guān)鍵算法的描述或流程圖、程序測(cè)試

（測(cè)試用例和程序運(yùn)行結(jié)果）。報(bào)告需打印提交，代碼無需打印。

（3）報(bào)告提交要求。每位學(xué)生需將報(bào)告和代碼程序代碼壓縮，文件名命名格式為：學(xué)

號(hào)+姓名+專業(yè)班級(jí).rar,如：3140602026+張三+計(jì)算機(jī)1401.rar,并上傳到指定的

ftp服務(wù)器，班長(zhǎng)收齊所有同學(xué)的課程設(shè)計(jì)報(bào)告后一起提交給指導(dǎo)教師。

c.實(shí)驗(yàn)環(huán)境

普通PC機(jī)，軟件要求安裝VS.net開發(fā)環(huán)境。

2.進(jìn)度安排

本課程設(shè)計(jì)為1.5周，共7天，上機(jī)為30學(xué)時(shí)，學(xué)生需在上機(jī)前做好準(zhǔn)備工作,

最后兩天為現(xiàn)場(chǎng)檢查時(shí)間，每位學(xué)生需現(xiàn)場(chǎng)演示并回答老師提出的問題。

序號(hào)設(shè)計(jì)內(nèi)容時(shí)間支撐的課程目標(biāo)

1環(huán)境搭建和系統(tǒng)需求1天1.1,1.2,2.1,2.2

分析

2系統(tǒng)數(shù)據(jù)結(jié)構(gòu)分析選1天1.1,1.2,2.1,2.2

擇與設(shè)計(jì)

3系統(tǒng)數(shù)據(jù)結(jié)構(gòu)相關(guān)算1天1.1,1.2,2.1,2.2

法功能設(shè)計(jì)與實(shí)現(xiàn)

（一）

4系統(tǒng)數(shù)據(jù)結(jié)構(gòu)相關(guān)算1天1.1,1.2,2.1,2.2

法功能設(shè)計(jì)與實(shí)現(xiàn)

（-）

5系統(tǒng)數(shù)據(jù)結(jié)構(gòu)相關(guān)算1天1.1,1.2,2.1,2.2

法功能設(shè)計(jì)與實(shí)現(xiàn)

（三）

6系統(tǒng)聯(lián)調(diào)與測(cè)試1天1.1,1.2,2.1,2.2

7系統(tǒng)總結(jié)及演示以及1天1.1,1,2,1.3,2.1,2.2,2.3

對(duì)指導(dǎo)教師提出的關(guān)

鍵問題進(jìn)行分析匯報(bào)

三'考核與成績(jī)?cè)u(píng)定

1.考核材料

平時(shí)考勤情況，預(yù)習(xí)準(zhǔn)備情況，程序?qū)崿F(xiàn)與演示情況，回答問題情況，課程設(shè)

計(jì)報(bào)告、程序。

2.考核要求及權(quán)重

考核內(nèi)容考核要求考核權(quán)重備注

平時(shí)考勤共考勤5次，每缺勤1次扣1分5%

預(yù)習(xí)準(zhǔn)備情況根據(jù)上機(jī)前的準(zhǔn)備情況評(píng)分25%

功能實(shí)現(xiàn)與演示根據(jù)現(xiàn)場(chǎng)演示功能情況評(píng)分50%

根據(jù)現(xiàn)場(chǎng)演示對(duì)提問問題的回答情況

回答問題10%

評(píng)分

課程設(shè)計(jì)報(bào)告根據(jù)設(shè)計(jì)報(bào)告格式和內(nèi)容情況評(píng)分10%

注：具體評(píng)分細(xì)則詳見附錄2

四、大綱說明

1.學(xué)生在本課程設(shè)計(jì)前應(yīng)學(xué)習(xí)了《程序設(shè)計(jì)基礎(chǔ)》、《離散數(shù)學(xué)》、《數(shù)據(jù)結(jié)構(gòu)A》

等課程，時(shí)間上可安排在《數(shù)據(jù)結(jié)構(gòu)A》課程學(xué)習(xí)結(jié)束之后。

2.參考文獻(xiàn)

[1]《數(shù)據(jù)結(jié)構(gòu):C++實(shí)現(xiàn)》，繆淮扣，科學(xué)出版社，2014年第2版。

[2]《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏，清華大學(xué)出版社，1997年第1版。

[3]《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）》，殷人昆，清華大學(xué)出版

社，2007年第2版。

[4]《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用:C++語言描述數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：C++語言描

述（DataStructures,Algorithms,andApplicationinC++）^>（美）Sartaj,Sahni

著，王立柱等譯，機(jī)械工業(yè)出版社，2015年第2版。

2017年8月

附錄1課程設(shè)計(jì)建議選題

選題一、學(xué)生信息管理系統(tǒng)

問題描述：

設(shè)計(jì)一個(gè)學(xué)生信息管理系統(tǒng)，實(shí)現(xiàn)對(duì)學(xué)生基本信息的添加、刪除、修改和查詢等操作。

要求：

程序采用文本界面或圖形界面下進(jìn)行交互的工作方式，完成如下功能：

(1)多種方式建立學(xué)生信息

?每個(gè)學(xué)生信息由學(xué)號(hào)、姓名、數(shù)學(xué)、英語和語文組成；

?可以通過手工錄入每個(gè)學(xué)生信息，并在C盤下以StudentFile.txt保存；

?也可以導(dǎo)入某個(gè)路徑下存放學(xué)生信息的文本文件。

(2)瀏覽所有學(xué)生信息。

(3)按照學(xué)號(hào)對(duì)所有學(xué)生信息進(jìn)行升序、降序排列，并輸出

?可選用冒泡、選擇等算法；

?不僅輸出屏幕顯示，還需要寫入存放學(xué)生信息的文件。

(4)按姓名、學(xué)號(hào)等方式，實(shí)現(xiàn)對(duì)學(xué)生信息精確查詢、模糊查詢，并輸出屏幕顯示

?精確查詢結(jié)果演示

查詢“姓名是王五”同學(xué)信息，則輸出

學(xué)號(hào)姓名高數(shù)英語離散數(shù)學(xué).......

2007112011王五889078...........

?模糊查詢結(jié)果演示

查詢姓“劉”的同學(xué)信息(輸入“劉”)，則輸出

學(xué)號(hào)姓名高數(shù)英語離散數(shù)學(xué)

2007112011劉梅889078........

2007112011劉強(qiáng)878098........

2007112011劉星867058........

?能夠?qū)崿F(xiàn)連續(xù)多次查詢

(5)學(xué)生信息的插入、刪除、修改。

?通過插入、刪除和修改后，保持所有學(xué)生信息的有序性；

?插入、刪除和修改后，對(duì)存放所有學(xué)生信息的文件及時(shí)更新。

(6)數(shù)據(jù)的統(tǒng)計(jì)功能

?統(tǒng)計(jì)每個(gè)學(xué)生的平均分和總分；

?統(tǒng)計(jì)每個(gè)科目的平均分和最高分、最低分；

?將上述統(tǒng)計(jì)結(jié)果，寫入存放學(xué)生信息的文件。

選題二'銀行業(yè)務(wù)的模擬系統(tǒng)

問題描述：

設(shè)計(jì)一個(gè)銀行業(yè)務(wù)模擬系統(tǒng)，模擬銀行的業(yè)務(wù)運(yùn)行并計(jì)算一天中客戶在銀行逗留的平均時(shí)間。

銀行有N(N的取值自己定義)個(gè)窗口對(duì)外接待客戶，從早晨銀行開門起不斷有客戶進(jìn)入銀行。由

于每個(gè)窗口在某個(gè)時(shí)刻只能接待一個(gè)客戶，因此在客戶人數(shù)眾多時(shí)需在每個(gè)窗口前順次排隊(duì)，對(duì)于

剛進(jìn)入銀行的客戶，如果某個(gè)窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若N個(gè)窗口均有客

戶所占，他便會(huì)排在人數(shù)最少的隊(duì)伍后面。

要求：

(1)在界面上可以設(shè)定銀行的對(duì)外營(yíng)業(yè)時(shí)間(銀行的開門時(shí)間以及銀行的關(guān)門時(shí)間)。

(2)用人機(jī)交互的方式來輸入客戶的到達(dá)時(shí)間以及客戶的離開時(shí)間，用隊(duì)列來存儲(chǔ)客戶的到

達(dá)事件和客戶的離開事件。

(3)可以友好的顯示出在某一天中整個(gè)銀行系統(tǒng)中客戶在銀行逗留的平均時(shí)間。

選題三'停車場(chǎng)管理系統(tǒng)

問題描述：

設(shè)計(jì)一個(gè)停車場(chǎng)管理系統(tǒng)，模擬停車場(chǎng)的運(yùn)作。

要求：

(1)要求以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行

模擬管理；

(2)要求處理的數(shù)據(jù)元素包括如下數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照及“到

達(dá)”或“離去”的時(shí)刻；

(3)若是車輛到達(dá)，就輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去，就輸出汽車

在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用(在便道上停留的時(shí)間不收費(fèi))。

(4)完成該停車場(chǎng)的一些信息統(tǒng)計(jì)功能(如每天到達(dá)/離開的車次，停車總時(shí)數(shù)、每天的停

車費(fèi)用等)。

選題四'哈夫曼編碼/譯碼器

問題描述：

設(shè)計(jì)一個(gè)哈夫曼編碼/譯碼系統(tǒng)，對(duì)一個(gè)文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件(后

綴名.cod)；反過來，可將一個(gè)編碼文件還原為一個(gè)文本文件(.txt)。

要求：

(1)輸入一個(gè)待壓縮的文本文件名，統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值，生成哈夫曼樹;

(2)將文本文件利用哈夫曼樹進(jìn)行編碼，生成編碼文件(后綴名cod)；

(3)輸入一個(gè)待解壓的壓縮文件名稱，并利用相應(yīng)的哈夫曼樹將編碼序列譯碼；

(4)顯示指定的編碼文件和文本文件；

選題五'最小生成樹問題

問題描述：

已知一個(gè)無向連通網(wǎng)表示n個(gè)城市以及城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，

邊表示兩個(gè)城市之間的線路，賦于邊上的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)點(diǎn)的連通網(wǎng)可以建立許多

不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)。現(xiàn)在，我們要選擇這樣一棵生成樹，使總的耗

費(fèi)最小。即構(gòu)造連通網(wǎng)的最小生成樹的問題。

要求：

(1)建立城市交通網(wǎng)的存儲(chǔ)結(jié)構(gòu)。(注：數(shù)據(jù)輸入可以是鍵盤輸入或文件輸入兩種方式)

(2)分別用Prim算法和Kruskal算法構(gòu)造最小生成樹，并輸出最小生成樹的代價(jià)及生成樹的

邊。(注：結(jié)果的輸出可以是屏幕輸出和文件輸出兩種方式)

選題六、二叉排序樹的操作演示

問題描述：

設(shè)計(jì)一個(gè)二叉排序樹的各種操作的演示系統(tǒng)，完成對(duì)二叉排序樹的建立、插入、刪除和查找操

作的演示。

要求：

(1)給出一組關(guān)鍵值，建立相應(yīng)的二叉排序樹，并顯示建立的二叉排序樹；

(2)刪除一個(gè)結(jié)點(diǎn)的操作。要求可以實(shí)現(xiàn)刪除根結(jié)點(diǎn)、葉子結(jié)點(diǎn)以及其它任意結(jié)點(diǎn)的功能，

并顯示操作前、后的二叉排序樹；

(3)插入一個(gè)新結(jié)點(diǎn)的操作，并顯示操作前、后的二叉排序樹；

(4)對(duì)給定的值在二叉排序樹進(jìn)行查找，并給出查找結(jié)果。

選題七、內(nèi)部排序算法的性能分析

問題描述：

設(shè)計(jì)一個(gè)測(cè)試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感受。

要求：

(1)對(duì)起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法進(jìn)行比較；

(2)待排序表的表長(zhǎng)不小于1000,表中數(shù)據(jù)隨機(jī)產(chǎn)生，至少用3組不同數(shù)據(jù)作比較，比較指

標(biāo)有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換記為3次移動(dòng))；

(3)輸出比較結(jié)果。

附錄2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)分細(xì)則(按100分計(jì)算)

項(xiàng)目?jī)?yōu)秀良好中等及格不及格

(100-90)(80-89)(70-79)(60-69)(60以下)

預(yù)習(xí)準(zhǔn)備情況預(yù)習(xí)準(zhǔn)備內(nèi)預(yù)習(xí)準(zhǔn)備內(nèi)預(yù)習(xí)準(zhǔn)備內(nèi)有一定的預(yù)預(yù)習(xí)準(zhǔn)備內(nèi)容

25%容很充分容充分容較充分習(xí)準(zhǔn)備內(nèi)容沒有或極少

實(shí)現(xiàn)所有功實(shí)現(xiàn)所有功有1個(gè)必須有2個(gè)必須有2個(gè)功能未實(shí)

能，并有所增能；提示清實(shí)現(xiàn)的功能實(shí)現(xiàn)的功能現(xiàn)；基本沒有提

功能實(shí)現(xiàn)與演