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

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

（CurriculumDesignofDataStructures）

課程代碼：06460044

學(xué)分：1.5

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

時）

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

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

教材：無

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

（一）課程性質(zhì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

的能力。

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

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

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

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

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

算法的設(shè)計；

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

畢業(yè)要求指標(biāo)點6.3能夠撰寫各類軟件工程文檔并進行評價;

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

畢業(yè)要求

指標(biāo)點1.4指標(biāo)點3.3指標(biāo)點3.4指標(biāo)點6.3指標(biāo)點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)容與進度安排

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

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

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

況適當(dāng)安排。

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

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

b.其他要求：

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

⑵課程設(shè)計報告包括封面、目錄、報告正文、參考文獻。報告正文中要給出對課程

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

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

（測試用例和程序運行結(jié)果）。報告需打印提交，代碼無需打印。

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

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

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

c.實驗環(huán)境

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

2.進度安排

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

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

序號設(shè)計內(nèi)容時間支撐的課程目標(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è)計

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

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

（一）

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

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

（-）

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

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

（三）

6系統(tǒng)聯(lián)調(diào)與測試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

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

鍵問題進行分析匯報

三'考核與成績評定

1.考核材料

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

計報告、程序。

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

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

平時考勤共考勤5次，每缺勤1次扣1分5%

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

功能實現(xiàn)與演示根據(jù)現(xiàn)場演示功能情況評分50%

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

回答問題10%

評分

課程設(shè)計報告根據(jù)設(shè)計報告格式和內(nèi)容情況評分10%

注：具體評分細則詳見附錄2

四、大綱說明

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

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

2.參考文獻

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

[2]《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴蔚敏，清華大學(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

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

2017年8月

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

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

問題描述：

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

要求：

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

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

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

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

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

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

(3)按照學(xué)號對所有學(xué)生信息進行升序、降序排列，并輸出

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

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

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

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

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

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

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

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

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

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

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

2007112011劉強878098........

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

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

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

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

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

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

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

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

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

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

問題描述：

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

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

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

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

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

要求：

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

(2)用人機交互的方式來輸入客戶的到達時間以及客戶的離開時間，用隊列來存儲客戶的到

達事件和客戶的離開事件。

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

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

問題描述：

設(shè)計一個停車場管理系統(tǒng)，模擬停車場的運作。

要求：

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

模擬管理；

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

達”或“離去”的時刻；

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

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

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

車費用等)。

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

問題描述：

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

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

要求：

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

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

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

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

選題五'最小生成樹問題

問題描述：

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

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

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

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

要求：

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

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

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

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

問題描述：

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

作的演示。

要求：

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

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

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

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

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

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

問題描述：

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

要求：

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

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

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

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

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

項目優(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)容沒有或極少

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

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

功能實現(xiàn)與演