《數(shù)據(jù)結(jié)構(gòu)》實驗大綱

數(shù)據(jù)結(jié)構(gòu)實驗教學(xué)大綱

課程名稱:數(shù)據(jù)結(jié)構(gòu)課程代碼:

課程類型:專業(yè)必修

學(xué)分:3學(xué)分總學(xué)時：48理論學(xué)時：32

先修課程：《C語言》/《Python》適用專業(yè)：大數(shù)據(jù)技術(shù)

一、課程的性質(zhì)、目的和任務(wù)

本課程是計算機專業(yè)的必修課。本課程系統(tǒng)地介紹線性表、棧、隊列、字符串、數(shù)組、

廣義表、樹、二叉樹、圖、查找表、排序等幾種數(shù)據(jù)結(jié)構(gòu)的基本概念，操作及其典型應(yīng)用的

例子。

數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機硬件的研究范圍，而且和軟件的研究有著更密切的

關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信

息檢索時也必須考慮如何組織數(shù)據(jù)，以便查找和存儲數(shù)據(jù)元素更為方便。因此，數(shù)據(jù)結(jié)構(gòu)是

介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程。

通過課堂教學(xué)、課外練習(xí)，使學(xué)生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備

分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力，以及培養(yǎng)良好的數(shù)據(jù)抽象能力

和程序設(shè)計技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。

二、實驗教學(xué)的目的與要求

教學(xué)目的：

從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算三個方面去掌握線性表、棧、隊列、

串、數(shù)組、廣義表、樹、圖和文件等常用的數(shù)據(jù)結(jié)構(gòu)。

掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)的排列和查找運算。

對算法的時間和空間復(fù)雜性有一定的分析能力。

針對簡單的應(yīng)用問題，應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計有效的算法解決之。

基本要求：

必須仔細理解《數(shù)據(jù)結(jié)構(gòu)》實驗內(nèi)容，認真主動完成實驗的要求。有問題及時主動通過各

種方式與教師聯(lián)系溝通。

1.要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好實驗的時間計劃，并在實驗過程中

不斷檢測自己的計劃完成情況，及時的向教師匯報。

二、實驗內(nèi)容及學(xué)時分配

序試驗項目名稱內(nèi)容提要學(xué)每組實驗屬

號時人數(shù)性

1線性表的應(yīng)用結(jié)合線性表的基本操作，完成線21設(shè)計性

一線性表運算性表的插入，查找等運算

2用棧模擬隊列用棧模擬隊列的設(shè)計與實現(xiàn)基本21設(shè)計性

的設(shè)計與實現(xiàn)操作

3字符串的模式通過字符串的模式匹配程序21設(shè)計性

匹配

4矩陣運算的設(shè)應(yīng)用數(shù)組結(jié)構(gòu)實現(xiàn)矩陣的轉(zhuǎn)置等21設(shè)計性

計與實現(xiàn)運算

5二叉樹的遍歷根據(jù)遍歷規(guī)則采用遞歸或非遞歸21設(shè)計性

的方法實現(xiàn)二叉樹的遍歷

6最短路徑問題實現(xiàn)圖的鄰接矩陣存儲和鄰接表21設(shè)計性

表示

7二叉排序樹構(gòu)造一個二叉樹，執(zhí)行查找操作21設(shè)計性

8排序的設(shè)計實給定一系列關(guān)鍵字，利用快速排21

現(xiàn)序方法將其排列

六、推薦教材和教學(xué)參考書

教材：

《數(shù)據(jù)結(jié)構(gòu)》劉暢等著,上海交通大學(xué)出版社,2016年

參考書：

1.《數(shù)據(jù)結(jié)構(gòu)習(xí)題集》嚴蔚敏等著，北京:清華大學(xué)出版社，1997年

2.《數(shù)據(jù)結(jié)構(gòu)與實訓(xùn)》張紅霞等著，北京：電子工業(yè)出版社,2007年。

3.《C程序設(shè)計》譚浩強著.北京：清華大學(xué)出版社，2006年。

數(shù)據(jù)結(jié)構(gòu)實驗教學(xué)大綱

實驗課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗

英語譯名：ExperimentsofDataStructures

課程性質(zhì)：專業(yè)基礎(chǔ)課

適用學(xué)生層次：本科

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

試驗項目數(shù)：8

試驗設(shè)計時數(shù)：16

試驗總學(xué)時數(shù)：16

課程學(xué)分數(shù)：2

教材：無

考核方式：實驗報告及運行結(jié)果

一、實驗教學(xué)的目的與要求

教學(xué)目的：

1.從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算三個方面去掌握線性表、

棧、隊列、串、數(shù)組、廣義表、樹、圖和文件等常用的數(shù)據(jù)結(jié)構(gòu)。

2.掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)的排列和查找運算。

3.對算法的時間和空間復(fù)雜性有一定的分析能力。

4.針對簡單的應(yīng)用問題，應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計有效的算法解決

之。

基本要求：

2.必須仔細理解《數(shù)據(jù)結(jié)構(gòu)》實驗內(nèi)容，認真主動完成實驗的要求。有問

題及時主動通過各種方式與教師聯(lián)系溝通。

3.要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好實驗的時間計劃，并在

實驗過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。

二、實驗內(nèi)容及學(xué)時分配

序號試驗項目名稱學(xué)時內(nèi)容提要

1一元多項式計算4能夠按照指數(shù)降序排列建立并輸出多項

式；能夠完成兩個多項式的相加、相減，

并將結(jié)果輸出；

2迷宮求解4可以輸入一個任意大小的迷宮數(shù)據(jù)，用非

遞歸的方法求出一條走出迷宮的路徑，并

將路徑輸出；

3銀行業(yè)務(wù)模擬4編制程序模擬銀行的業(yè)務(wù)活動

4二叉樹構(gòu)造4已知一棵二叉樹的前序、中序序列，試構(gòu)

造此二叉樹

5公園導(dǎo)游圖5給出一張某公園的導(dǎo)游圖（景點不少于

10個），游客通過終端詢問可知：

（1）任一景點的相關(guān)信息（2）從某一景

點到另一景點的最短路徑（3）游客從公

園大門進入，選一條最短路線，使游客可

以游覽各景點，最后回到出口（出口

6各種排序4用程序?qū)崿F(xiàn)插入法排序、起泡法改進算法

排序；

利用插入排序和冒泡法的改進算法