數(shù)據(jù)結(jié)構(gòu)理論(二)課程教學(xué)大綱

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

課程性質(zhì)專業(yè)必修課

課程編號xx882034-2課程名稱數(shù)據(jù)結(jié)構(gòu)

適用專業(yè)物聯(lián)網(wǎng)工程、計算機科學(xué)與技術(shù)、軟件工程

先修課程C語言程序設(shè)計

總學(xué)時40學(xué)時學(xué)分數(shù)2.5

一、課程簡介

《數(shù)據(jù)結(jié)構(gòu)》是計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程專業(yè)的核心課程，作為學(xué)

科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。通過本課程的學(xué)習(xí)，使學(xué)生理解、掌握基

本數(shù)據(jù)結(jié)構(gòu)的特點，了解數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，著重培養(yǎng)學(xué)生的算法設(shè)計與分析的基本

理論知識和技能,提高學(xué)生設(shè)計算法、設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)的能力。本課程強調(diào)理論和實

踐的結(jié)合，突出對學(xué)生的動手能力的培養(yǎng)。在對學(xué)生進行基本數(shù)據(jù)結(jié)構(gòu)的技術(shù)、理論、

設(shè)計等各種技能培養(yǎng)的同時，培養(yǎng)學(xué)生將實際問題轉(zhuǎn)化為基本數(shù)據(jù)結(jié)構(gòu)的問題的分析能

力，鼓勵學(xué)生學(xué)以致用，將學(xué)到的知識用以解決實際問題，從而提高學(xué)生算法設(shè)計能力

和軟件開發(fā)能力。

二、課程教學(xué)目標(biāo)

通過本課程的學(xué)習(xí)，學(xué)生應(yīng)實現(xiàn)如下目標(biāo)：

1、知識目標(biāo)：

了解：數(shù)據(jù)結(jié)構(gòu)的基本概念、算法的時間復(fù)雜度的概念、串的基本操作、多維數(shù)組、

廣度表、二叉樹的相關(guān)遞歸與非遞歸算法、圖的相關(guān)算法、外排序的相關(guān)算法思想等。

掌握：簡單的時間復(fù)雜度的計算、順序表的相關(guān)操作用插入、刪除算法、單鏈表的

相關(guān)操作與插入刪除算法、棧與隊列的相關(guān)操作與插入刪除算法、二叉樹的基本性質(zhì)及

二叉樹的遍歷及二叉樹的簡單的遞歸算法、哈夫曼樹、樹到二叉樹的轉(zhuǎn)換、圖的基本概

念及圖的最小生樹、圖的關(guān)鍵路徑、最短路徑等基本算法思想應(yīng)用、查找的基本概念、

平均查找長度、折半查找樹的生成、二叉排序樹的生成、哈希表的生成及簡單的內(nèi)排序

（快速排序、堆排序、歸并排序等）的應(yīng)用等。

2、能力目標(biāo):

(1)對數(shù)據(jù)結(jié)構(gòu)的分類與經(jīng)典算法初步的認識和了解；

(2)掌握常見的順序結(jié)構(gòu)、鏈式結(jié)構(gòu)、棧與隊列的基本算法及簡單應(yīng)用；

(3)掌握樹型結(jié)構(gòu)基本算法中的遞歸與非遞歸算法及簡單應(yīng)用；

(4)在實訓(xùn)中，培養(yǎng)和鍛煉學(xué)生運用相關(guān)算法解決問題、進行應(yīng)用開發(fā)的能力,

為將來從事計算機方面的開發(fā)或計算機類管理奠定堅實的基礎(chǔ)。

三、課程教學(xué)基本要求

為了更好地掌握本課程的知識，必須先修《C語言程序設(shè)計》、《離散數(shù)學(xué)》等課程,

要求同學(xué)們教室上課，課后按要求完成給定的習(xí)題或思考題。

四、課程教學(xué)模塊(或教學(xué)內(nèi)容)與學(xué)時分配

序號教學(xué)模塊知識點學(xué)時

(1)掌握數(shù)據(jù)結(jié)構(gòu)的基本概念

項目一

(2)了解抽象數(shù)據(jù)類型

1數(shù)據(jù)結(jié)構(gòu)簡3

(3)了解算法時間復(fù)雜度和空間復(fù)雜度的分析

介

(4)了解算法的描述方法。

(1)理解線性表的定義及其運算；

(2)理解順序表和鏈表的定義、組織形式、結(jié)

項目二線性構(gòu)特征和類型說明；

2表的基本操(3)掌握在順序表和鏈表上實現(xiàn)的插入、刪除6

作和按值查找的算法；

(4)了解循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點

和在其上施加的插入、刪除等操作。

(1)理解棧的定義、特征及在其上所定義的基

本運算；

項目三棧與(2)掌握在兩種存儲結(jié)構(gòu)上對棧所施加的基本

3隊列的基本運算的實現(xiàn)；6

操作(3)理解隊列的定義、特征及在其上所定義的

基本運算；

(4)掌握在兩種存儲結(jié)構(gòu)上對隊列所施加的基

本運算的實現(xiàn)

(1)了解串的邏輯定義；

項目四串的(2)掌握用順序存儲串及堆存儲串時的特點及

4基本操作在這兩種存儲方式下基本操作的實現(xiàn)；2

(3)了解改進的模式匹配算法；

(1)掌握數(shù)組的順序存儲結(jié)構(gòu)及特殊矩陣的存

項目五數(shù)組儲方式；

53

及稀疏矩陣(2)了解稀疏矩陣的壓縮存儲方式一三元組表

(1)深刻理解二叉樹的定義、性質(zhì)及其存儲方

法；

(2)熟練掌握二叉樹的二叉鏈表存儲方式、結(jié)

項目二叉樹點結(jié)構(gòu)和類型定義；

6的性質(zhì)及基(3)理解并掌握二叉樹的三種遍歷算法；掌握8

本操作二叉樹的線索化方法；

(4)靈活運用二叉樹的遍歷方法解決相關(guān)的應(yīng)

用問題。

(1)理解圖的基本概念及術(shù)語；

(2)掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接

表)方法；

(3)熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍

項目七圖的歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并

76

基本操作能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法

得到的序列；

(4)理解最小生成樹的概念，能按Prim算法

構(gòu)造最小生成樹；

(5)領(lǐng)會拓撲排序、關(guān)鍵路徑、最短路徑的算

法思想

(1)了解查找的基本思想及查找成功和不成功

的概念；

(2)掌握在順序表、有序表、索引表、散列表

8項目八查找等上的查找方法和算法，并能求出相應(yīng)的平均4

查找長度；

(3)理解并掌握二叉排序樹的各種算法

1)領(lǐng)會排序的基本思想和基本概念；

(2)理解并掌握插入排序、冒泡排序、快速排

項目九內(nèi)排

9序、直接選擇排序、堆排序、歸并排序和基數(shù)2

序

排序的基本思想、步驟和時空效率分析

五、教學(xué)方法與策略

1、講授法：從數(shù)據(jù)結(jié)構(gòu)的基本概念及數(shù)據(jù)應(yīng)用與組織入手，講授數(shù)據(jù)的四種結(jié)構(gòu)

及四種結(jié)構(gòu)的表示方式及在內(nèi)存的組織方法及各種方法的具體實現(xiàn)。在程序設(shè)計中注意

培養(yǎng)學(xué)生的獨立編寫程序的能力，注意培養(yǎng)學(xué)生的創(chuàng)新能力和進取精神。

2、實驗課：掌握線性結(jié)構(gòu)與樹型結(jié)構(gòu)的典型算法。在程序設(shè)計訓(xùn)練中，由順序到

鏈式再到棧與列、隊列、二叉樹，由易到難，在指導(dǎo)學(xué)生的過程中要注重啟發(fā)學(xué)生的思

維與培養(yǎng)學(xué)生的創(chuàng)新意識扎扎實實練好基本功。

六、學(xué)生學(xué)習(xí)成效考核方式

考核環(huán)節(jié)構(gòu)成占總成績

評分依據(jù)

(均為100分制)的比重

上課出勤與作業(yè)上課缺席一次扣2分，缺課達1/3取消資格。30%

期末考試成績70%

七、選用教材

⑴嚴蔚敏,吳偉民.