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

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

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

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

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

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

總學(xué)時(shí)40學(xué)時(shí)學(xué)分?jǐn)?shù)2.5

一、課程簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)掌握常見的順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、棧與隊(duì)列的基本算法及簡(jiǎn)單應(yīng)用；

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

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

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

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

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

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

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

序號(hào)教學(xué)模塊知識(shí)點(diǎn)學(xué)時(shí)

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

項(xiàng)目一

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

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

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

介

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

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

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

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

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

作和按值查找的算法；

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

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

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

本運(yùn)算；

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

3隊(duì)列的基本運(yùn)算的實(shí)現(xiàn)；6

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

基本運(yùn)算；

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

本運(yùn)算的實(shí)現(xiàn)

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

項(xiàng)目四串的(2)掌握用順序存儲(chǔ)串及堆存儲(chǔ)串時(shí)的特點(diǎn)及

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

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

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

項(xiàng)目五數(shù)組儲(chǔ)方式；

53

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

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

法；

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

項(xiàng)目二叉樹點(diǎn)結(jié)構(gòu)和類型定義；

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

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

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

用問題。

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

(2)掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接

表)方法；

(3)熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍

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

76

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

得到的序列；

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

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

(5)領(lǐng)會(huì)拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算

法思想

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

的概念；

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

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

查找長(zhǎng)度；

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

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

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

項(xiàng)目九內(nèi)排

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

序

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

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

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

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

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

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

鏈?zhǔn)皆俚綏Ｅc列、隊(duì)列、二叉樹，由易到難，在指導(dǎo)學(xué)生的過程中要注重啟發(fā)學(xué)生的思

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

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

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

評(píng)分依據(jù)

(均為100分制)的比重

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

期末考試成績(jī)70%

七、選用教材

⑴嚴(yán)蔚敏,吳偉民.