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

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

一、課程說(shuō)明

課程編號(hào)：090166X11

課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)/CourseExerciseinDatastructure

課程類別：專業(yè)教育課程（集中實(shí)踐環(huán)節(jié)）

學(xué)時(shí)/學(xué)分：2周/2學(xué)分

先修課程：高級(jí)語(yǔ)言程序設(shè)計(jì)、離散數(shù)學(xué)

適用專業(yè)：智能科學(xué)與技術(shù)

教材、教學(xué)參考書：

⑴《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，嚴(yán)蔚敏，吳偉民，清華大學(xué)出版社,2011

[2]《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版）》，嚴(yán)蔚敏等，人民郵電出版社，2015

二、課程設(shè)置的目的意義

本課程設(shè)計(jì)是為了配合《數(shù)據(jù)結(jié)構(gòu)》課程而開設(shè)的，通過(guò)設(shè)計(jì)完整的大型程

序，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語(yǔ)言的算法轉(zhuǎn)換成程序并

用上機(jī)調(diào)試的基本方法。課程的目的是使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種

基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械?/p>

使用方法；使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化

軟件設(shè)計(jì)的能力；使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)

行程序設(shè)計(jì)的基本能力；

三、課程的基本要求

知識(shí)：了解各類常用數(shù)據(jù)結(jié)構(gòu)，包括線性表、隊(duì)列、棧、樹、圖等的構(gòu)成與

特點(diǎn)；了解各類數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建、插入、刪除、遍歷、銷毀等各種操作；了解各

類數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，掌握經(jīng)典算法的實(shí)現(xiàn)，如：模式匹配算法、算符優(yōu)先法、快

速矩陣相乘算法、各類排序算法等。鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)基本知識(shí)的理解和掌

握。

能力：通過(guò)利用各種數(shù)據(jù)結(jié)構(gòu)綜合解決問(wèn)題，加深對(duì)各類數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)

構(gòu)和物理結(jié)構(gòu)的認(rèn)識(shí)，初步體會(huì)和理解如何通過(guò)相應(yīng)的結(jié)構(gòu)和算法來(lái)解決問(wèn)題，

培養(yǎng)根據(jù)具體問(wèn)題來(lái)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法的能力；學(xué)會(huì)將理論知識(shí)與實(shí)際應(yīng)用結(jié)

合，學(xué)會(huì)根據(jù)提出的問(wèn)題去分析問(wèn)題和解決問(wèn)題，提高綜合運(yùn)用課程知識(shí)的能力；

培養(yǎng)學(xué)生自學(xué)參考書籍，查閱手冊(cè)、圖表和文獻(xiàn)資料的能力。

素質(zhì)：通過(guò)實(shí)際課程設(shè)計(jì)，初步掌握簡(jiǎn)單軟件的分析方法和設(shè)計(jì)方法，了解

與課程有關(guān)的工程技術(shù)規(guī)范，培養(yǎng)軟件設(shè)計(jì)和系統(tǒng)設(shè)計(jì)素質(zhì)。

四、實(shí)驗(yàn)方式與基本要求

1.學(xué)生可以在指導(dǎo)老師給出的課題中選擇設(shè)計(jì)課題，也可以由學(xué)生自行提

出設(shè)計(jì)課題，經(jīng)指導(dǎo)老師認(rèn)可后確定設(shè)計(jì)課題。

2.根據(jù)題目的人數(shù)要求學(xué)生可自由分組，并確定組內(nèi)成員的分工，進(jìn)行課程

設(shè)計(jì)課題的資料搜集。所有學(xué)生根據(jù)所選課題學(xué)會(huì)找參考書籍、查閱手冊(cè)、圖表

和文獻(xiàn)資料等。通過(guò)獨(dú)立思考，深入鉆研有關(guān)問(wèn)題，學(xué)會(huì)自己分析解決問(wèn)題的方

法。

3.根據(jù)搜集的資料，進(jìn)行程序功能與數(shù)據(jù)結(jié)構(gòu)分析，并選擇合適的數(shù)據(jù)結(jié)構(gòu)、

并在此基礎(chǔ)上進(jìn)行實(shí)現(xiàn)程序功能的算法設(shè)計(jì)。

4.運(yùn)用掌握C/C++語(yǔ)言編寫程序，實(shí)現(xiàn)各個(gè)模塊功能，進(jìn)行程序設(shè)計(jì)，并調(diào)

試程序，記錄測(cè)試情況。

5.每組成員根據(jù)自己的工作各自完成課程設(shè)計(jì)報(bào)告。

6.指導(dǎo)教師對(duì)每組同學(xué)的開發(fā)的系統(tǒng)進(jìn)行綜合驗(yàn)收，并由學(xué)院考核小組進(jìn)行

隨機(jī)抽查評(píng)分。

五、課程的基本內(nèi)容以及重點(diǎn)難點(diǎn)

本課程基本內(nèi)容為：利用各種數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題。

重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、系統(tǒng)設(shè)計(jì)與調(diào)試、性能與功能測(cè)試。

難點(diǎn)：系統(tǒng)設(shè)計(jì)及調(diào)試。

六、實(shí)驗(yàn)項(xiàng)目的設(shè)置與內(nèi)容提要

驗(yàn)

每組

實(shí)驗(yàn)項(xiàng)實(shí)驗(yàn)實(shí)實(shí)驗(yàn)實(shí)驗(yàn)

型

人數(shù)

類內(nèi)容摘要

目名稱時(shí)數(shù)要求類別

問(wèn)題描述：設(shè)計(jì)一個(gè)學(xué)生作業(yè)管理系

統(tǒng)，實(shí)現(xiàn)對(duì)學(xué)生作業(yè)提交情況的檢查、

查詢、文件名的規(guī)范等操作。

系統(tǒng)運(yùn)行要求：

（1）”學(xué)生信息表'’已經(jīng)存在，初始為

教師的教務(wù)管理系統(tǒng)中導(dǎo)出的點(diǎn)名

裝,是Excel表格,具林表格■見附作一。

（2）學(xué)生提交的作業(yè)文檔已存在，并

保存在同一目錄下，作業(yè)文件名由學(xué)

號(hào)+姓名組成。

系統(tǒng)基本要求：程序采用圖形界面下

學(xué)生作不超技術(shù)進(jìn)行交互的工作方式，完成如下功能：

綜合

礎(chǔ)

01業(yè)管理2周過(guò)5選做基（1）規(guī)范學(xué)生作業(yè)文件名

設(shè)計(jì)

系統(tǒng)人（2）多種方式建立學(xué)生作業(yè)信息

（3）檢查瀏覽學(xué)生作業(yè)提交情況及作

業(yè)文檔

（4）按照學(xué)號(hào)對(duì)所有學(xué)生信息進(jìn)行升

序、降序排列，并輸出

（5）按姓名、學(xué)號(hào)等方式，實(shí)現(xiàn)對(duì)學(xué)

生作業(yè)信息的精確查詢、模糊查詢，

輸出屏幕顯示，并能調(diào)用word等編輯

器打開選中學(xué)生的作業(yè)文檔

（6）學(xué)生作業(yè)信息的插入、刪除、修

改。

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

問(wèn)題描述：設(shè)計(jì)一個(gè)哈希表，實(shí)現(xiàn)個(gè)

個(gè)電

人人電話號(hào)碼查詢系統(tǒng)。

話

碼

號(hào)

不超綜合

技術(shù)

杳基本要求：

系

設(shè)計(jì)

02詢2周過(guò)3選做

基礎(chǔ)設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、

統(tǒng)人

用戶名、用戶住址；

從鍵盤露入各記錄'，分別以電話號(hào)碼

實(shí)驗(yàn)

實(shí)驗(yàn)項(xiàng)實(shí)驗(yàn)每組實(shí)驗(yàn)實(shí)驗(yàn)

人

要求

數(shù)內(nèi)容摘要

目名稱時(shí)數(shù)類型類別

和用戶名為關(guān)鍵字建立哈希表；

可根據(jù)用戶選擇使用不同的哈希函

數(shù)，并輸出各自的沖突率；

b）在哈希函數(shù)確定的前提下，可提供

各種不同類型處理沖突的方法供選

擇，并統(tǒng)計(jì)對(duì)應(yīng)方法的平均查找長(zhǎng)度；

C）能統(tǒng)計(jì)不同哈希函數(shù)的沖突率，及

不同沖突處理策略的平均查找長(zhǎng)度，

列表顯示各種不同方法的比較結(jié)果；

查找并顯示給定電話號(hào)碼/用戶名的記

錄；

問(wèn)題描述：設(shè)計(jì)一個(gè)管理個(gè)人通訊錄

的程序，完成下列基本功能。

錄入和備份通訊錄

通訊錄管理

通訊錄信息瀏覽

技術(shù)

實(shí)用的不超綜合

通訊錄信息添加

礎(chǔ)

基

03小型通2周過(guò)3設(shè)計(jì)選做

通訊錄信息刪除

訊錄人

通訊錄信息查詢：按照姓名、電話號(hào)

碼等字段，進(jìn)行精確、模糊查詢，并

在屏幕上輸出查詢結(jié)果。

通訊錄信息修改

f）通訊錄類別管理

問(wèn)題描述：用一個(gè)字符類型的二維數(shù)

組表示迷宮，數(shù)組中的每個(gè)元素表示

一個(gè)小方格，取值“0”（通道）或“1”

（阻塞物）。設(shè)計(jì)一個(gè)模擬小老鼠走迷

宮的程序，為小老鼠尋找一條從迷宮

入口到迷宮出口的途經(jīng)小方格最少的

綜合最短通路。

迷宮問(wèn)技術(shù)

042周1設(shè)計(jì)選做基本要求：

基礎(chǔ)

題用隨機(jī)函數(shù)設(shè)置迷宮；

選擇合適的數(shù)據(jù)結(jié)構(gòu)表示迷宮。

迷宮入口和出口由鍵盤或鼠標(biāo)輸入。

輸出從入口到出口的最短通路（如存

在）或不存在通路的信息。

設(shè)計(jì)出友好的圖形化界面，做到很好

的人機(jī)交互。

問(wèn)題描述：設(shè)計(jì)一個(gè)動(dòng)畫演示系統(tǒng)動(dòng)

態(tài)演示棧和隊(duì)列的各種操作，幫助理

解這兩種數(shù)據(jù)結(jié)構(gòu)中的插入、刪除、

向上溢出和向下溢出等概念。特別是

關(guān)于兩個(gè)棧共用一塊存儲(chǔ)空間和循環(huán)

隊(duì)列的情況。

基本要求：

對(duì)單個(gè)棧，從鍵盤或文件中輸入入棧

棧與隊(duì)數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)序列，動(dòng)態(tài)演示數(shù)據(jù)

的入棧和出棧過(guò)程，包括棧頂指針的

列結(jié)構(gòu)不超綜合

技術(shù)變化，棧內(nèi)數(shù)據(jù)的變化，溢出的情況

05的操作2周過(guò)4設(shè)計(jì)選做

基礎(chǔ)的演示等，并顯示文字說(shuō)明對(duì)該過(guò)程

動(dòng)畫演人

進(jìn)行講解；

示系統(tǒng)對(duì)兩個(gè)棧共用空間的情況，從鍵盤或

文件中輸入入棧數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)序

歹U，動(dòng)態(tài)演示數(shù)據(jù)的入棧過(guò)程，包括

棧頂指針的變化，棧內(nèi)數(shù)據(jù)的變化，

溢出的情況的演示等，并顯示文字說(shuō)

明對(duì)該過(guò)程進(jìn)行講解；

對(duì)一般隊(duì)列，從鍵盤或文件中輸入入

隊(duì)數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)序列，動(dòng)態(tài)演示入

隊(duì)和出隊(duì)過(guò)程，包括隊(duì)頭、隊(duì)尾指針

實(shí)驗(yàn)

實(shí)驗(yàn)項(xiàng)實(shí)驗(yàn)每組實(shí)驗(yàn)實(shí)驗(yàn)

人

要求

數(shù)內(nèi)容摘要

目名稱時(shí)數(shù)類型類別

值的變化，隊(duì)內(nèi)數(shù)據(jù)的變化，溢出的

情況的演示等，并顯示文字說(shuō)明對(duì)該

過(guò)程進(jìn)行講解；

對(duì)循環(huán)隊(duì)列，從鍵盤或文件中輸入入

隊(duì)數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)序列，動(dòng)態(tài)演示入

隊(duì)和出隊(duì)過(guò)程，包括隊(duì)頭、隊(duì)尾指針

值的變化，隊(duì)內(nèi)數(shù)據(jù)的變化，特別是

隊(duì)列已滿情況的判定條件演示等，并

顯示文字說(shuō)明對(duì)該過(guò)程進(jìn)行講解；

問(wèn)題描述：哈夫曼編碼在通訊、網(wǎng)絡(luò)、

數(shù)據(jù)壓縮、圖像處理中的得到廣泛應(yīng)

用，在一個(gè)通訊系統(tǒng)中，采用圖形界

面設(shè)計(jì)m叉哈夫曼樹（m^2）,對(duì)■通訊褚

息進(jìn)行編碼和解碼。

基本要求：

從終端讀入字符文件，統(tǒng)計(jì)文件中字

符的出現(xiàn)頻率作為每個(gè)字符的權(quán)值，

哈夫曼建立叉哈夫曼樹，并將哈夫曼樹以

不超m

樹編碼/綜合技術(shù)直觀的方式（如樹形）顯示在終端上，

062周過(guò)3選做

譯碼系設(shè)計(jì)基礎(chǔ)同時(shí)將字符及其對(duì)應(yīng)的編碼寫入文件

人

統(tǒng)CodePrint中；

利用編碼結(jié)果，對(duì)文件中的正文進(jìn)行

編碼，然后將結(jié)果存入文件CodeFile

中,并輸出結(jié)果,將文件CodeFile以

緊湊格式顯示在終端上，每行50個(gè)代

碼。

將土件CodeFile中的代碼進(jìn)行譯碼，

結(jié)果存入文件TextFile中，并輸出結(jié)

果。

問(wèn)題描述：設(shè)計(jì)一個(gè)校園導(dǎo)游程序，

完成校園信息的維護(hù)以及為來(lái)訪的客

人提供信息查詢等服務(wù)功能。

基本要求：

根據(jù)新校區(qū)的校園平面圖設(shè)計(jì)帶權(quán)無(wú)

向網(wǎng)絡(luò)，所含景點(diǎn)不少于10個(gè)，以圖

中頂點(diǎn)表示校內(nèi)各景點(diǎn)，頂點(diǎn)的信息

包括：景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等，以

邊表示道路，邊上信息包括：兩點(diǎn)距

不超技術(shù)

校園導(dǎo)綜合離、所需時(shí)間等相關(guān)信息。（注：數(shù)據(jù)

礎(chǔ)

072周過(guò)2選做基

游系統(tǒng)設(shè)計(jì)的輸入可以是鍵盤輸入或文件輸入兩

人

種方式）建立相應(yīng)的圖結(jié)構(gòu)。

提供對(duì)校園景點(diǎn)信息的編輯（如：添

力口、刪除、修改等）的功能；為來(lái)訪

客人提供圖中任意景點(diǎn)相關(guān)信息的查

詢（可提供多種查詢方式）；

為來(lái)訪客人提供從校門口到圖中任意

景點(diǎn)的問(wèn)路查詢（最短路徑）；

為來(lái)訪客人提供圖中任意景點(diǎn)間的問(wèn)

路查詢。

問(wèn)題描述：已知一個(gè)無(wú)向連通網(wǎng)表示n

個(gè)城市以及城市間可能設(shè)置的通信線

路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示

最小生不超綜合兩個(gè)城市之間的線路，賦于邊上的權(quán)

技術(shù)

成樹問(wèn)周過(guò)設(shè)計(jì)選做值表示相應(yīng)的代價(jià)。對(duì)于個(gè)點(diǎn)的連

0822基礎(chǔ)n

題人通網(wǎng)可以建立許多不同的生成樹，每

一棵生成樹都可以是一個(gè)通信網(wǎng)。現(xiàn)

在，我們要選擇這樣一棵生成樹，使

總的耗費(fèi)最小。即構(gòu)造連通網(wǎng)的最小

一每組實(shí)驗(yàn)實(shí)驗(yàn)實(shí)驗(yàn)

序

實(shí)驗(yàn)

實(shí)驗(yàn)項(xiàng)人數(shù)類型要求類別

要

摘

容

號(hào)內(nèi)

時(shí)數(shù)

稱

目名

。

問(wèn)題

樹的

生成

：

要求

基本

。

結(jié)構(gòu)

存儲(chǔ)

網(wǎng)的

交通

城市

建立

（1）

文

入或

盤輸

是鍵

可以

輸入

數(shù)據(jù)

（注：

式）

種方

入兩

件輸

l算法

uska

和Kr

算法

Prim

別用

（2）分

成樹

小生

出最

并輸

樹，

生成

最小

構(gòu)造