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

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

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

英文名稱：DataStructures

課程編號：

學(xué)時(shí)數(shù)：80

其中實(shí)驗(yàn)（實(shí)訓(xùn)）學(xué)時(shí)數(shù)：24課外學(xué)時(shí)數(shù)：0

學(xué)分?jǐn)?shù)：5.0

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

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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科各專業(yè)本科學(xué)生必修的一門專業(yè)基礎(chǔ)課是計(jì)算機(jī)程序設(shè)計(jì)的重

要理論和實(shí)踐基礎(chǔ)，是培養(yǎng)學(xué)生軟件設(shè)計(jì)能力的一門重要課程，在計(jì)算機(jī)學(xué)科的本科教學(xué)中，

起著非常重要的作用。

本課程研究計(jì)算機(jī)系統(tǒng)中常用的線性表、二叉樹、圖等典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法，研究

各種典型排序和查找算法的設(shè)計(jì)方法和性能指標(biāo)，并介紹這些數(shù)據(jù)結(jié)構(gòu)和算法在實(shí)際工程中

的應(yīng)用。通過學(xué)習(xí)本課程，使學(xué)生深入理解軟件設(shè)計(jì)的基本要素和基本結(jié)構(gòu)，培養(yǎng)邏輯思維

能力，提高程序設(shè)計(jì)能力。

數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，上機(jī)實(shí)驗(yàn)、課程設(shè)計(jì)等實(shí)踐性環(huán)節(jié)必不

可少。

二'課程教學(xué)內(nèi)容的基本要求、重點(diǎn)和難點(diǎn)

本課程是理論與實(shí)踐并重的課程，要求學(xué)生既要掌握數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)理論知識，又要掌

握操作計(jì)算機(jī)和運(yùn)行、調(diào)試程序的基本技能；能夠熟練運(yùn)用C/C++語言或其它計(jì)算機(jī)語言

編制具有中等難度的應(yīng)用程序，在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。

本課程的基本要求如下。

理解線性表、棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等基本的數(shù)據(jù)邏輯結(jié)構(gòu)，掌握描述

這些數(shù)據(jù)結(jié)構(gòu)、選擇合適的存儲結(jié)構(gòu)和實(shí)現(xiàn)各種操作的方法。

熟練運(yùn)用C/C++語言或其它計(jì)算機(jī)語言表達(dá)鏈?zhǔn)酱鎯Y(jié)構(gòu)；熟練運(yùn)用遞歸函數(shù)表達(dá)遞

歸定義、遞歸算法和遞歸結(jié)構(gòu)。

理解插入、交換、選擇、歸并等多種典型排序算法的思想，掌握在線性表、樹等各種不

同數(shù)據(jù)結(jié)構(gòu)中的查找算法。

掌握在計(jì)算機(jī)語言環(huán)境中編輯、編譯、運(yùn)行程序的方法，以及單步運(yùn)行、設(shè)置斷點(diǎn)、查

看變量運(yùn)行時(shí)值等調(diào)試程序的方法。

具體設(shè)置如下：

（一）緒論

了解和掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，這些概念包括:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、抽象數(shù)據(jù)類

型、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)上的操作集合、算法及算法特點(diǎn)等。了解和

掌握算法效率分析的意義和方法。

重點(diǎn)：抽象數(shù)據(jù)類型表示。

難點(diǎn)：抽象數(shù)據(jù)類型的概念和表示形式。

（二）線性表

了解線性表的邏輯結(jié)構(gòu)和基本操作；理解線性表的順序存儲結(jié)構(gòu)和實(shí)現(xiàn)方法；理解線性表的

鏈?zhǔn)酱鎯Y(jié)構(gòu)和實(shí)現(xiàn)方法；了解單循環(huán)鏈表和雙向鏈表的概念和基本設(shè)計(jì)方法。

重點(diǎn)：順序存儲結(jié)構(gòu)和順序表的設(shè)計(jì)方法。

難點(diǎn)：單鏈表的存儲結(jié)構(gòu)設(shè)計(jì)及算法的實(shí)現(xiàn)。

（三）棧和隊(duì)列

理解棧的概念、順序棧和鏈?zhǔn)綏５脑O(shè)計(jì)方法；理解隊(duì)列的概念、順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的

設(shè)計(jì)方法；了解優(yōu)先級隊(duì)列以及優(yōu)先級隊(duì)列和一般隊(duì)列的差別；了解堆棧和隊(duì)列的應(yīng)用方法。

重點(diǎn)：棧和隊(duì)列的基本概念及其各種操作算法的設(shè)計(jì)和實(shí)現(xiàn)。

難點(diǎn)：棧的應(yīng)用算法和循環(huán)隊(duì)列的實(shí)現(xiàn)。

（四）字符串

理解串的概念和串的基本操作；理解串的靜態(tài)存儲結(jié)構(gòu)、動(dòng)態(tài)存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)；了

解串基本操作的實(shí)現(xiàn)方法：了解串的BE模式匹配方法和KMP模式匹配方法。

重點(diǎn)：字符串操作算法的設(shè)計(jì)和實(shí)現(xiàn)。

難點(diǎn)：串的模式匹配算法。

（五）廣義線性表

熟練掌握數(shù)組的概念和數(shù)組的靜態(tài)、動(dòng)態(tài)存儲結(jié)構(gòu)；了解特殊矩陣的壓縮存儲方法；了解稀

疏矩陣的基本壓縮存儲方法，包括稀疏矩陣的三元組概念，以及稀疏矩陣三元組的順序表、

單鏈表和十字鏈表存儲結(jié)構(gòu)。

重點(diǎn)：特殊矩陣和稀疏矩陣的壓縮存儲方法。

難點(diǎn)：特殊矩陣和稀疏矩陣的存儲結(jié)構(gòu)設(shè)計(jì)及其算法設(shè)計(jì)。

（六）遞歸算法

正確理解遞歸的概念、遞推公式的歸納方法和遞歸算法的執(zhí)行過程：熟練掌握遞歸算法的問

題分析和算法設(shè)計(jì)方法；了解遞歸算法時(shí)間效率低的原因。

重點(diǎn)：遞推公式的歸納；遞歸算法的執(zhí)行過程；遞歸算法的設(shè)計(jì)方法。

難點(diǎn)：遞歸技術(shù)的原理、實(shí)現(xiàn)和運(yùn)用。

（七）樹與二叉樹

了解樹的定義、表示方法及其典型存儲結(jié)構(gòu)；理解二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)和操作的

實(shí)現(xiàn)方法；掌握二叉樹的遍歷算法及其應(yīng)用實(shí)現(xiàn)；理解哈夫曼樹的概念及其應(yīng)用；了解樹與

二叉樹的關(guān)系。

重點(diǎn)：二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)；二叉樹的遍歷算法和二叉樹遍歷算法的應(yīng)用：哈

夫曼樹在編碼方面的應(yīng)用方法。

難點(diǎn)：有關(guān)樹和二叉樹的各種遞歸算法。

（八）圖

了解圖的基本概念和術(shù)語；掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)以及圖操作的實(shí)現(xiàn)方法；理

解圖的深度和廣度優(yōu)先遍歷方法和算法設(shè)計(jì)方法;理解最小生成樹的概念以及普里姆算法和

單源最短路徑的狄克斯特拉算法。

重點(diǎn)：圖的鄰接矩陣和圖的鄰接表存儲結(jié)構(gòu)；圖的深度和廣度遍歷方法；普里姆算法和狄克

斯特拉算法。

難點(diǎn)：圖的兩種遍歷算法以及各應(yīng)用問題的求解算法。

（九）排序

了解排序的基本概念和排序算法的評判標(biāo)準(zhǔn)；掌握直接插入排序、希爾排序、直接選擇排序、

堆排序、快速排序、二路歸并排序、基數(shù)排序的算法思想和算法設(shè)計(jì)方法；理解各種排序方

法的性能特點(diǎn)。

重點(diǎn)：希爾排序、堆排序、快速排序、二路歸并排序和基數(shù)排序的算法思想。

難點(diǎn)：堆排序、快速排序、二路歸并排序和基數(shù)排序的算法設(shè)計(jì)方法。

（十）查找

了解查找的基本概念和查找方法的評判標(biāo)準(zhǔn);理解順序查找,掌握有序查找的算法設(shè)計(jì)方法,

理解索引查找的基本結(jié)構(gòu)；了解二叉排序樹和B-樹的基本結(jié)構(gòu)和插入、刪除方法；掌握哈

希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)造方法。

重點(diǎn)：二叉排序樹和二叉排序樹的插入和刪除方法：哈希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)

造方法。

難點(diǎn)：二分查找，二叉排序樹的構(gòu)造，哈希表的沖突處理。

三'教學(xué)方式及學(xué)時(shí)分配

主要教學(xué)輔導(dǎo)答疑

序號主要內(nèi)容學(xué)時(shí)分配

方式比例

一緒論講授42：1

二線性表講授+實(shí)驗(yàn)12+42：1

三棧和隊(duì)列講授+實(shí)驗(yàn)6+22：1

四字符串講授22：1

五廣義線性表講授+實(shí)驗(yàn)4+22：1

六遞歸算法講授22：1

七樹與二叉樹講授+實(shí)驗(yàn)8+42：1

八圖講授+實(shí)驗(yàn)10+42：1

七排序講授+實(shí)驗(yàn)6+22：1

十查找講授+實(shí)驗(yàn)6+22：1

四'課程其他教學(xué)環(huán)節(jié)要求

數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，不僅僅要注重理解基本知識，更要注重培養(yǎng)

軟件設(shè)計(jì)的基本技能。實(shí)踐性環(huán)節(jié)是鞏固所學(xué)理論知識、使理論與實(shí)際相結(jié)合、提高程序設(shè)

計(jì)能力和計(jì)算機(jī)操作能力的一項(xiàng)必不可少的重要環(huán)節(jié)。因此，課后習(xí)題、上機(jī)實(shí)驗(yàn)和課程設(shè)

計(jì)等都是加強(qiáng)程序設(shè)計(jì)訓(xùn)練所必需的。

本課程安排的上機(jī)實(shí)驗(yàn)學(xué)時(shí)為24學(xué)時(shí)，課內(nèi)開設(shè)的12個(gè)實(shí)驗(yàn)說明如下。

實(shí)驗(yàn)一：線性表操作（一）要求：掌握順序存儲結(jié)構(gòu)的特點(diǎn)和常見算法。

實(shí)驗(yàn)二：線性表操作（二）要求：掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)和常見算法。

實(shí)驗(yàn)三：棧和隊(duì)列操作要求：掌握棧和隊(duì)列操作，設(shè)計(jì)新的成員函數(shù)，并進(jìn)行測試。

實(shí)驗(yàn)四：多維數(shù)組和廣義表操作要求：掌握這兩種操作、及新的成員函數(shù)，并測試。

實(shí)驗(yàn)五：樹和二叉樹（一）要求：掌握二叉樹的存儲實(shí)現(xiàn)、二叉樹的遍歷思想。

實(shí)驗(yàn)六：樹和二叉樹（二）要求：掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。

實(shí)驗(yàn)七：圖的有關(guān)操作（一）要求：掌握圖的存儲思想及其存儲實(shí)現(xiàn)、圖的深度、廣度優(yōu)

先遍歷算法思想及其程序?qū)崿F(xiàn)。

實(shí)驗(yàn)八：圖的有關(guān)操作（二）要求：掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。

實(shí)驗(yàn)九：查找要求：掌握順序查找，折半查找，二快速排序，堆排序等二叉排序樹算

法。

實(shí)驗(yàn)十：排序要求：掌握常見的排序算法的思想及其適用條件、常見的排序算法的程序

實(shí)現(xiàn)。

實(shí)驗(yàn)十一：綜合實(shí)驗(yàn)（一）要求：使用數(shù)據(jù)結(jié)構(gòu)中各種算法編寫系統(tǒng)類結(jié)構(gòu)。

實(shí)驗(yàn)十二：綜合實(shí)驗(yàn)（二）要求：結(jié)合實(shí)驗(yàn)十一的設(shè)計(jì)，完成綜合系統(tǒng)的實(shí)現(xiàn)和調(diào)試。

本課程通過課堂講授例題、課堂練習(xí)、課后習(xí)題、上機(jī)實(shí)驗(yàn)以及課程設(shè)計(jì)等各個(gè)實(shí)踐環(huán)節(jié)，

對學(xué)生進(jìn)行系統(tǒng)的程序設(shè)計(jì)訓(xùn)練。所有例題、課堂練習(xí)題、課后習(xí)題、上機(jī)實(shí)驗(yàn)題都是精心

挑選的，由淺入深，環(huán)環(huán)相扣，步步推進(jìn)，調(diào)動(dòng)學(xué)生的主動(dòng)性和自覺性并培養(yǎng)學(xué)生寫程序的

興趣。

除了課內(nèi)安排的習(xí)題課、課堂討論、期中測驗(yàn)、復(fù)習(xí)課以外，每次課后都要求學(xué)生做至少2

個(gè)完整的程序，并定期檢查學(xué)生做作業(yè)的情況，作業(yè)的數(shù)量和質(zhì)量占平時(shí)成績的一部分。

考核方式說明：

本課程為考試課程，期末考試為閉卷筆試。學(xué)生的課程總評成績由平時(shí)成績（占30%）和期

末考試成績（70%）兩部分構(gòu)成，平時(shí)成績中實(shí)驗(yàn)成績占20%,出勤、作業(yè)、課堂測驗(yàn)、學(xué)習(xí)

主動(dòng)性等占10%。實(shí)驗(yàn)成績根據(jù)實(shí)驗(yàn)報(bào)告質(zhì)量評定，作亞成績根據(jù)習(xí)題的數(shù)量和質(zhì)量評定。

五、本課程與其他課程的聯(lián)系

本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，其先修課程是程序設(shè)計(jì)語言、離散數(shù)學(xué)，后續(xù)課程包括算法設(shè)

計(jì)與分析、編譯技術(shù)、操作系統(tǒng)等課程。

六'教學(xué)參考書目

《數(shù)據(jù)結(jié)構(gòu)（C++版）》，王紅梅編著，清華大學(xué)出版社，2008年。

《數(shù)據(jù)結(jié)構(gòu)（C++版）》，葉核亞編著，機(jī)械工業(yè)出版社，2004年。

《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程》，嚴(yán)蔚敏等編著，清華大學(xué)出版社，2001年。

《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》，殷人昆等編著，清華大學(xué)出版社，1999年