第一篇：數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱

教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures）

計(jì)算機(jī)技術(shù)已成為現(xiàn)代化發(fā)展的重要支柱和標(biāo)志，并逐步滲透到人類(lèi)生活的各個(gè)領(lǐng)域。隨著計(jì)算機(jī)硬件的發(fā)展，對(duì)計(jì)算機(jī)軟件的發(fā)展也提出了越來(lái)越高的要求。由于軟件的核心是算法，而算法實(shí)際上是對(duì)加工數(shù)據(jù)過(guò)程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對(duì)提高編程能力和設(shè)計(jì)高性能的算法是至關(guān)重要的。

非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是傳統(tǒng)的數(shù)學(xué)方程問(wèn)題，而是諸如表、樹(shù)、圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。因此，簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法。

一、教學(xué)目的與要求---了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；

教學(xué)要求在每章教學(xué)內(nèi)容給出，大體上為三個(gè)層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會(huì)所學(xué)知識(shí)，熟練掌握就是運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題。

教學(xué)目的為：了解算法對(duì)于程序設(shè)計(jì)的重要性 ； 學(xué)習(xí)掌握基本數(shù)據(jù)結(jié)構(gòu)的描述與實(shí)現(xiàn)方法，熟練掌握典型數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用算法的設(shè)計(jì)。了解算法分析方法。

二、教學(xué)重點(diǎn)與難點(diǎn)--數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語(yǔ)，算法描述和分析方法。

1、鏈表插入、刪除運(yùn)算的算法。算法時(shí)間復(fù)雜度

2、后綴表達(dá)式的算法，數(shù)制的換算

利用本章的基本知識(shí)設(shè)計(jì)相關(guān)的應(yīng)用問(wèn)題

3、循環(huán)隊(duì)列的特點(diǎn)及判斷溢出的條件

利用隊(duì)列的特點(diǎn)設(shè)計(jì)相關(guān)的應(yīng)用問(wèn)題

4、串的模式匹配運(yùn)算算法

5、二叉樹(shù)遍歷算法的設(shè)計(jì)

利用二叉樹(shù)遍歷算法，解決簡(jiǎn)單應(yīng)用問(wèn)題 哈夫曼樹(shù)的算法

6、圖的遍歷

最小生成樹(shù)

最短路徑

7、二叉排序樹(shù)查找

平衡樹(shù)二叉樹(shù)

8、堆排序

快速排序 歸并排序

三、教學(xué)方法與手段-充分利用多媒體教學(xué)工具，配合黑板上的教學(xué)內(nèi)容較難部分的算法實(shí)現(xiàn)過(guò)程演義

四、教學(xué)內(nèi)容、目標(biāo)與學(xué)時(shí)分配

教學(xué)內(nèi)容 教學(xué)目標(biāo) 課時(shí)分配

1、緒論

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

算法和算法分析

2、線性表

線性表的定義與運(yùn)算

線性表的順序存儲(chǔ)

線性表的鏈?zhǔn)酱鎯?chǔ)

3、棧

棧的定義與運(yùn)算

棧存儲(chǔ)和實(shí)現(xiàn)

棧的應(yīng)用舉例

4、隊(duì)列

隊(duì)列的定義與基本運(yùn)算

隊(duì)列的存儲(chǔ)與實(shí)現(xiàn)

隊(duì)列的應(yīng)用舉例

5、串

串的定義與基本運(yùn)算

串的表示與實(shí)現(xiàn)

串的基本運(yùn)算

6、樹(shù)和二叉樹(shù)

樹(shù)的定義和術(shù)語(yǔ)

二叉樹(shù)樹(shù)的基本概念和術(shù)語(yǔ) 遍歷二叉數(shù)和線索二叉樹(shù)

二叉樹(shù)的轉(zhuǎn)換

二叉樹(shù)的應(yīng)用

哈夫曼樹(shù)及其應(yīng)用

7、圖

圖的定義和術(shù)語(yǔ)

圖的存儲(chǔ)結(jié)構(gòu)

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態(tài)查找 動(dòng)態(tài)查找

哈希表

了解

了解

掌握

熟練掌握順序表存儲(chǔ)地址的計(jì)算

掌握單鏈表的結(jié)構(gòu)特點(diǎn)和基本運(yùn)算

掌握雙鏈表的結(jié)構(gòu)特點(diǎn)和基本運(yùn)算

掌握棧的定義與運(yùn)算

掌握棧的存儲(chǔ)與實(shí)現(xiàn)

熟練掌握棧的各種實(shí)際應(yīng)用

掌握隊(duì)列的定義與基本運(yùn)算

熟練掌握隊(duì)列的存儲(chǔ)與實(shí)現(xiàn)

掌握循環(huán)隊(duì)列的特征和基本運(yùn)算

了解串的邏輯結(jié)構(gòu)

掌握串的存儲(chǔ)結(jié)構(gòu)

熟練掌握串的基本運(yùn)算

了解

了解二叉樹(shù)

熟練掌握二叉樹(shù)定義和存儲(chǔ)結(jié)構(gòu)

了解二叉樹(shù)的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

了解

熟練掌握

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學(xué)時(shí)

1學(xué)時(shí)

1學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

4學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

4學(xué)時(shí)

6學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

6學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

12學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

4學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

9、排序

12學(xué)時(shí) 插入排序

熟練掌握基本思想

3學(xué)時(shí) 快速排序

了解各種內(nèi)部排序方法和特點(diǎn)

3學(xué)時(shí) 選擇排序

掌握

2學(xué)時(shí) 各種排序方法比較

掌握

2學(xué)時(shí)

實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)?zāi)繕?biāo) 課時(shí)分配 算法編程實(shí)驗(yàn)：

1、用指針?lè)绞骄帉?xiě)程序 復(fù)習(xí)C（C++）語(yǔ)言指針、結(jié)構(gòu)體等的用法

2、對(duì)單鏈表進(jìn)行遍歷

鏈表的描述與操作實(shí)現(xiàn)

3、棧及其操作

描述方法及操作

4、編寫(xiě)串子系統(tǒng)1 串的特點(diǎn)及順序定長(zhǎng)存儲(chǔ)、操作、查找

5、編寫(xiě)串子系統(tǒng) 2 串的特點(diǎn)及順序定長(zhǎng)存儲(chǔ)、操作、查找

6、編寫(xiě)樹(shù)子系統(tǒng)1 二叉樹(shù)的特點(diǎn)及存儲(chǔ)方式、創(chuàng)建、顯示、遍歷等

7、編寫(xiě)樹(shù)子系統(tǒng)2 二叉樹(shù)的特點(diǎn)及存儲(chǔ)方式、創(chuàng)建、顯示、遍歷等

8、圖子系統(tǒng)

圖的鄰接矩陣的存儲(chǔ)、遍歷、廣度/深度優(yōu)先搜索

9、查找子系統(tǒng)

理解查找基本算法、平均查找長(zhǎng)度、靜態(tài)、動(dòng)態(tài)查找等

五、考試范圍與題型

1、考試范圍與分?jǐn)?shù)比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊(duì)列

6% 5)串

4% 6)樹(shù)和二叉樹(shù)

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分?jǐn)?shù)比例

1)名詞解釋

18% 2)判斷對(duì)錯(cuò)

16% 3)填空

16% 4)單項(xiàng)選擇

18% 5)應(yīng)用

32%

六、教材與參考資料

1、教材： 實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（譚浩強(qiáng)）中國(guó)鐵道出版社

2、參考資料： 數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）清華大學(xué)出版社

數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（徐孝凱）清華大學(xué)出版社

（撰寫(xiě)人：

，審核人： 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí)）

第二篇：數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱

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

一、課程基本信息

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

總學(xué)時(shí)：64(理論課內(nèi)學(xué)時(shí)48，上機(jī)課內(nèi)學(xué)時(shí)16)課程設(shè)計(jì)：24 課程類(lèi)型：必修課

考試形式：半開(kāi)卷考試 講課對(duì)象：計(jì)算機(jī)本科

建議教材：《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)陳明 編著 清華大學(xué)出版社

課程簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊(duì)列、串、樹(shù)與森林、圖、排序、查找、索引與散列結(jié)構(gòu)等。課程以結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言C語(yǔ)言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和結(jié)構(gòu)化程序設(shè)計(jì)基本能力的雙基訓(xùn)練。為后續(xù)計(jì)算機(jī)專(zhuān)業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。

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

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的一門(mén)重要專(zhuān)業(yè)基礎(chǔ)課，是計(jì)算機(jī)學(xué)科的公認(rèn)主干課。課程內(nèi)容由數(shù)據(jù)結(jié)構(gòu)和算法分析初步兩部分組成。

數(shù)據(jù)結(jié)構(gòu)是針對(duì)處理大量非數(shù)值性程序問(wèn)題而形成的一門(mén)學(xué)科，內(nèi)涵豐富、應(yīng)用范圍廣。它既有完整的學(xué)科體系和學(xué)科深度，又有較強(qiáng)的實(shí)踐性。通過(guò)課程的學(xué)習(xí)，應(yīng)使學(xué)生理解和掌握各種數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu)和邏輯結(jié)構(gòu))的概念及其有關(guān)的算法；熟悉并了解目前常用數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)諸多領(lǐng)域中的基本應(yīng)用。

算法分析強(qiáng)調(diào)最基本的算法設(shè)計(jì)技術(shù)和分析方法。要求學(xué)生從算法和數(shù)據(jù)結(jié)構(gòu)的相互依存關(guān)系中把握應(yīng)用算法設(shè)計(jì)的藝術(shù)和技能。

經(jīng)過(guò)上機(jī)實(shí)習(xí)和課程設(shè)計(jì)的訓(xùn)練，使學(xué)生能夠編制、調(diào)試具有一定難度的中型程序；以培養(yǎng)良好的軟件工程習(xí)慣和面向?qū)ο蟮能浖季S方法。

“數(shù)據(jù)結(jié)構(gòu)”的前序課是《離散數(shù)學(xué)》、《C語(yǔ)言程序設(shè)計(jì)與算法初步》。

三、理論教學(xué)內(nèi)容的基本要求及學(xué)時(shí)分配

1、序論(2學(xué)時(shí))學(xué)習(xí)目標(biāo)：熟悉各類(lèi)文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。

重點(diǎn)與難點(diǎn)：本章無(wú)。

知識(shí)點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型、算法及其設(shè)計(jì)原則、時(shí)間復(fù)雜度、空間復(fù)雜度。

2、線性表(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類(lèi)不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱(chēng)為順序表，用后者表示的線性表簡(jiǎn)稱(chēng)為鏈表；

(2)熟練掌握這兩類(lèi)存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；

(3)能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合；

(4)結(jié)合線性表類(lèi)型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類(lèi)型的理解。

重點(diǎn)與難點(diǎn)：鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。

知識(shí)點(diǎn)：線性表、順序表、鏈表、有序表。

3、棧和隊(duì)列(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類(lèi)型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；

(2)熟練掌握棧類(lèi)型的兩種實(shí)現(xiàn)方法；

(3)熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法；(4)理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。

重點(diǎn)與難點(diǎn)：棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問(wèn)題中正確使用。

知識(shí)點(diǎn)：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列。

4、串(2學(xué)時(shí))

學(xué)習(xí)目標(biāo)：(1)理解串類(lèi)型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作；

(2)理解串類(lèi)型的各種存儲(chǔ)表示方法；(3)理解串匹配的各種算法。

重點(diǎn)和難點(diǎn)：相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型，因此本章重點(diǎn)僅在于了解串類(lèi)型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作。本章的難點(diǎn)是理解實(shí)現(xiàn)串匹配的KMP算法的思想。

知識(shí)點(diǎn)：串的類(lèi)型定義、串的存儲(chǔ)表示、串匹配、KMP算法。

5、數(shù)組和廣義表(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解數(shù)組類(lèi)型的特點(diǎn)及其在高級(jí)編程語(yǔ)言中的存儲(chǔ)表示和實(shí)現(xiàn)方法，并掌握數(shù)組在“以行為主”的存儲(chǔ)表示中的地址計(jì)算方法；

(2)掌握特殊矩陣的存儲(chǔ)壓縮表示方法；

(3)理解稀疏矩陣的兩類(lèi)存儲(chǔ)壓縮方法的特點(diǎn)及其適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算所采用的處理方法。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)是學(xué)習(xí)數(shù)組類(lèi)型的定義及其存儲(chǔ)表示。

知識(shí)點(diǎn)：數(shù)組的類(lèi)型定義、數(shù)組的存儲(chǔ)表示、特殊矩陣的壓縮存儲(chǔ)表示方法、隨機(jī)稀疏矩陣的壓縮存儲(chǔ)表示方法。

6、樹(shù)和二叉樹(shù)(8學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類(lèi)型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別；(2)熟記二叉樹(shù)的主要特性，并掌握它們的證明方法；

(3)熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作；

(4)理解二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；

(5)熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法；(6)學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法；

(7)了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫曼編碼的方法。

重點(diǎn)和難點(diǎn)：二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點(diǎn)，而編寫(xiě)實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸算法也恰是本章的難點(diǎn)所在。

知識(shí)點(diǎn)：樹(shù)的類(lèi)型定義、二叉樹(shù)的類(lèi)型定義、二叉樹(shù)的存儲(chǔ)表示、二叉樹(shù)的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹(shù)、樹(shù)和森林的存儲(chǔ)表示、樹(shù)和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹(shù)和赫夫曼編碼。

7、圖(8學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)領(lǐng)會(huì)圖的類(lèi)型定義；

(2)熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則；

(3)熟練掌握?qǐng)D的兩種遍歷算法；(4)理解各種圖的應(yīng)用問(wèn)題的算法。

重點(diǎn)和難點(diǎn)：圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問(wèn)題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場(chǎng)合。

知識(shí)點(diǎn)：圖的類(lèi)型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無(wú)向網(wǎng)的最小生成樹(shù)、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑。

8、查找(6學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解“查找表”的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時(shí)的查找方法；

(3)熟悉靜態(tài)查找樹(shù)的構(gòu)造方法和查找算法，理解靜態(tài)查找樹(shù)和折半查找的關(guān)系；

(4)熟練掌握二叉查找樹(shù)的構(gòu)造和查找方法；(5)理解二叉平衡樹(shù)的構(gòu)造過(guò)程；

(6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別；

(7)掌握描述查找過(guò)程的判定樹(shù)的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于理解查找表的結(jié)構(gòu)特點(diǎn)及其各種表示方法的特點(diǎn)和適用場(chǎng)合。

知識(shí)點(diǎn)：順序表、有序表、索引順序表、靜態(tài)查找樹(shù)、二叉查找樹(shù)、二叉平衡樹(shù)、哈希表。

9、內(nèi)部排序(6學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。排序方法有不同的分類(lèi)方法，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過(guò)程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序等五類(lèi)；

(2)掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類(lèi)：O(n2)的簡(jiǎn)單排序方法，O(n*logn)的高效排序方法和O(d*n)的基數(shù)排序方法；

(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。

重點(diǎn)和難點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法是本章的學(xué)習(xí)重點(diǎn)和難點(diǎn)。

知識(shí)點(diǎn)：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、2-路歸并排序、基數(shù)排序、排序方法的綜合比較。

10、文件(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：熟悉各類(lèi)文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。知識(shí)點(diǎn)：順序文件、索引文件、B-樹(shù)、B+樹(shù)、索引順序文件、VSAM文件、散列文件、多關(guān)鍵字文件。

四、實(shí)驗(yàn)教學(xué)內(nèi)容的基本要求及學(xué)時(shí)分配

1、線性表(1學(xué)時(shí))實(shí)驗(yàn)一 順序表的應(yīng)用 實(shí)驗(yàn)二 鏈表的應(yīng)用

要求：理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義，組織形式，結(jié)構(gòu)特征和類(lèi)型說(shuō)明；掌握在這兩種表上實(shí)現(xiàn)的插入，刪除和按值查找的算法；了解循環(huán)鏈表，雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入，刪除等操作。

2、棧(0.5學(xué)時(shí))實(shí)驗(yàn)三 棧的應(yīng)用

要求：理解棧的定義，特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)。

3、隊(duì)列(0.5學(xué)時(shí))實(shí)驗(yàn)四 隊(duì)列的應(yīng)用

要求：理解隊(duì)列的定義，特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。

4、串(0.5學(xué)時(shí))實(shí)驗(yàn)五 串的應(yīng)用

要求：了解串的定義；理解和領(lǐng)會(huì)串的存儲(chǔ)方式；掌握常用的串運(yùn)算。

5、數(shù)組和廣義表(0.5學(xué)時(shí))實(shí)驗(yàn)六 稀疏矩陣的應(yīng)用

要求：理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式；理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算；領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算；了解廣義表的定義和基本運(yùn)算。

6、樹(shù)與二叉樹(shù)(4學(xué)時(shí))實(shí)驗(yàn)七 樹(shù)與二叉樹(shù)的應(yīng)用

要求：理解樹(shù)的定義，術(shù)語(yǔ)；領(lǐng)會(huì)并掌握樹(shù)的各種存儲(chǔ)結(jié)構(gòu)；熟練掌握森林與二叉樹(shù)間的相互轉(zhuǎn)換；領(lǐng)會(huì)樹(shù)和森林的遍歷；了解樹(shù)的簡(jiǎn)單應(yīng)用。深刻理解二叉樹(shù)的定義，性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹(shù)的二叉鏈表存儲(chǔ)方式，結(jié)點(diǎn)結(jié)構(gòu)和類(lèi)型定義；理解并掌握二叉樹(shù)的三種遍歷算法；掌握二叉樹(shù)的線索化方法；靈活運(yùn)用二叉樹(shù)的遍歷方法解決相關(guān)的應(yīng)用問(wèn)題。

7、圖(3學(xué)時(shí))實(shí)驗(yàn)八 圖的應(yīng)用

要求：理解圖的基本概念及術(shù)語(yǔ)；掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想，步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹(shù)的概念，能按Prim算法構(gòu)造最小生成樹(shù)；領(lǐng)會(huì)并掌握拓?fù)渑判颍P(guān)鍵路徑，最短路徑的算法思想。

8、查找(3學(xué)時(shí))實(shí)驗(yàn)九 順序查找 實(shí)驗(yàn)十 折半查找 實(shí)驗(yàn)十一 哈希表的應(yīng)用 實(shí)驗(yàn)十二 二叉排序樹(shù)的綜合練習(xí)要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹(shù)，平衡二叉樹(shù)B-樹(shù)的各種算法。

9、排序(3學(xué)時(shí))實(shí)驗(yàn)十三 插入排序 實(shí)驗(yàn)十四 選擇排序 實(shí)驗(yàn)十五 排序綜合練習(xí)

要求：領(lǐng)會(huì)排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接選擇排序，堆排序，歸并排序和基數(shù)排序的基本思想，步驟，算法及時(shí)空效率分析；了解外排序的定義和基本方法。

五、大綱說(shuō)明

1、課堂講述的論題只是核心或有特色的知識(shí)內(nèi)容，還有相當(dāng)數(shù)量的篇章內(nèi)容留給學(xué)生自學(xué)，所確定的自學(xué)部分內(nèi)容亦屬考查范圍。

2、“數(shù)據(jù)結(jié)構(gòu)”課注重上機(jī)訓(xùn)練，所有作業(yè)都必須配有規(guī)范的文檔。上機(jī)訓(xùn)練由平時(shí)的上機(jī)訓(xùn)練和小學(xué)期的實(shí)訓(xùn)課程設(shè)計(jì)兩部分組成。

3、課內(nèi)學(xué)時(shí)安排說(shuō)明：前8周每周4學(xué)時(shí)全為理論課，從第9周開(kāi)始理論和上機(jī)為1：1，也即2學(xué)時(shí)理論，2學(xué)時(shí)上機(jī)訓(xùn)練。

4、本課強(qiáng)調(diào)能力的培養(yǎng)，期末采用半開(kāi)卷考試(允許同學(xué)攜帶一頁(yè)A4紙的總結(jié)資料)。本課成績(jī)由平時(shí)作業(yè)、上機(jī)成績(jī)(30%)和期末考試(70%)合成得到，有獨(dú)到見(jiàn)解的作業(yè)予以適當(dāng)加分。

5、主要參考書(shū)：

[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽(yáng) 楊劍勇 編著 機(jī)械工業(yè)出版社

[2]《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》(含CD)嚴(yán)蔚敏 吳為民 編著 清華大學(xué)出版社

[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》嚴(yán)蔚敏 編著 清華大學(xué)出版社

[4]《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)》張世和 編著 清華大學(xué)出版社

第三篇：《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱（Data Structures & Algorithms）

一、基本信息

課程編號(hào)：E1132107 課程類(lèi)別：學(xué)科基礎(chǔ)課必修課 適用層次：本科

適用專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程等 開(kāi)課學(xué)期：3 學(xué) 分：2學(xué)分 學(xué) 時(shí)：2周 考核方式：考查

二、教學(xué)目的

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)不僅是數(shù)據(jù)結(jié)構(gòu)與算法課程的實(shí)踐教學(xué)環(huán)節(jié)，而且是一門(mén)綜合性實(shí)驗(yàn)項(xiàng)目。通過(guò)這個(gè)實(shí)驗(yàn)，培養(yǎng)學(xué)生綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和程序設(shè)計(jì)基本知識(shí)，解決實(shí)際問(wèn)題，提高程序設(shè)計(jì)的能力和團(tuán)隊(duì)協(xié)作精神。

本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。

1．學(xué)生通過(guò)實(shí)踐掌握線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)； 2．培養(yǎng)學(xué)生利用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問(wèn)題的能力;3．使學(xué)生初步具備查閱資料、分析設(shè)計(jì)、上機(jī)實(shí)現(xiàn)和書(shū)寫(xiě)科技 報(bào)告的能力。

三、基本要求

1.指導(dǎo)教師要在選題、設(shè)計(jì)、上機(jī)實(shí)現(xiàn)等諸環(huán)節(jié)上投入精力，加強(qiáng)指導(dǎo)、討論和答疑的力度。尤其在選題上，要充分考慮學(xué)生目前所具有的知識(shí)水平、掌握的開(kāi)發(fā)工具、以及綜合設(shè)計(jì)能力的現(xiàn)狀，使題目取材合理、大小適中、難易適度，使學(xué)生在完成設(shè)計(jì)工作后，能有所收獲。2.參加課程設(shè)計(jì)的學(xué)生要珍惜機(jī)會(huì)、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實(shí)踐，虛心向指導(dǎo)教師請(qǐng)教，向同學(xué)學(xué)習(xí)，獨(dú)立完成設(shè)計(jì)任務(wù)。

3.學(xué)生需保質(zhì)、保量、保時(shí)間進(jìn)度地提交規(guī)范的課程設(shè)計(jì)報(bào)告，審查由指導(dǎo)教師負(fù)責(zé)。

四、教學(xué)內(nèi)容

1.主要內(nèi)容：應(yīng)用所掌握的線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問(wèn)題。2.軟件開(kāi)發(fā)工具：C/C++、JAVA。

3.課程設(shè)計(jì)題目：指導(dǎo)教師擬定（參考題目見(jiàn)附錄1）

4.具體步驟：指導(dǎo)教師擬定設(shè)計(jì)題目，學(xué)生研究具體問(wèn)題、進(jìn)行需求分析、選擇合適的數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法、編寫(xiě)并調(diào)試代碼、書(shū)寫(xiě)文檔材料、提交設(shè)計(jì)報(bào)告，最后，由指導(dǎo)教師驗(yàn)收并評(píng)定成績(jī)。

5.設(shè)計(jì)內(nèi)容及時(shí)間安排：第1-3天，選定題目，明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，并分析算法復(fù)雜度；第4-8天，編寫(xiě)程序、調(diào)試程序、測(cè)試程序；第9-10天，撰寫(xiě)設(shè)計(jì)報(bào)告，準(zhǔn)備答辯（上機(jī)演示，回答教師提問(wèn)）。6.設(shè)計(jì)報(bào)告書(shū)寫(xiě)要求：按照軟件開(kāi)發(fā)規(guī)范的要求書(shū)寫(xiě)設(shè)計(jì)報(bào)告（參見(jiàn)附錄三報(bào)告書(shū)寫(xiě)格式）；要求報(bào)告層次結(jié)構(gòu)清晰、圖表完整、語(yǔ)言通順、字跡工整。7.驗(yàn)收要求：1）運(yùn)行所設(shè)計(jì)的程序；2）回答有關(guān)問(wèn)題；3）提交課程設(shè)計(jì)報(bào)告（打印或手寫(xiě)在實(shí)習(xí)報(bào)告冊(cè)上）；4）提交軟盤(pán)（源程序）。（鼓勵(lì)學(xué)生創(chuàng)新。對(duì)內(nèi)容有創(chuàng)新者，成績(jī)?cè)u(píng)定將適當(dāng)提高）。

五、考核方法

學(xué)習(xí)成績(jī)的評(píng)定方式：考查。

課程設(shè)計(jì)成績(jī)?cè)u(píng)定 =平時(shí)出勤（20%）+設(shè)計(jì)報(bào)告（40%）+答辯（40%）通過(guò)設(shè)計(jì)答辯方式，并結(jié)合學(xué)生的動(dòng)手能力，獨(dú)立分析解決問(wèn)題的能力和創(chuàng)新精神，總結(jié)報(bào)告和答辯水平以及學(xué)習(xí)態(tài)度綜合考評(píng)。成績(jī)分為優(yōu)、良、中、及格和不及格五等。

六、教材與參考資料 1.建議教材：

[1] 數(shù)據(jù)結(jié)構(gòu)(C++)版，王紅梅、胡明、王濤編著，清華大學(xué)出版社，2005.7 [2] 自編教材

2.建議參考書(shū)目：

[1] 許卓群，楊冬青，唐世渭，張銘.數(shù)據(jù)結(jié)構(gòu)與算法.高等教育出版社，2004.7 [2] 嚴(yán)蔚敏, 陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程.清華大學(xué)出版社, 2001.2 [3] 朱晉蜀.數(shù)據(jù)結(jié)構(gòu)(第一版).成都: 電子科技大學(xué)出版社, 2000.1 [4] Clifford A.Shaffer著.張銘，劉曉丹譯.數(shù)據(jù)結(jié)構(gòu)與算法分析.電子工業(yè)出版社，1998.8 [5] 殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）.清華大學(xué)出版社，1999.7 [6] Ford W., Topp W.DATA STRUCTURES with C++.清華大學(xué)出版社（影印版），1997.3

附錄一

參考題目（可分若干組，每個(gè)學(xué)生選擇其中一個(gè)題目）

1．商廈家電庫(kù)存管理 2.排序算法的時(shí)間比較

3．使用哈希表技術(shù)判斷兩個(gè)源程序的相似性 4．以隊(duì)列實(shí)現(xiàn)的仿真技術(shù)預(yù)測(cè)理發(fā)館的經(jīng)營(yíng)狀況 5.某公園導(dǎo)游圖

6．用樹(shù)型結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢(xún) 7．管道鋪設(shè)施工的最佳方案選擇 8．表達(dá)式分析與求值程序 9．安排教學(xué)計(jì)劃

10.設(shè)計(jì)Huffman 編碼器與解碼器 11．在國(guó)際象棋盤(pán)上馬遍歷問(wèn)題 12．八皇后問(wèn)題 13．民航售票系統(tǒng) 14．模擬旅館管理系統(tǒng)中的床位分配和加收 15．銀行業(yè)務(wù)活動(dòng)的模擬

16．文字統(tǒng)計(jì)系統(tǒng)—文字研究助手 17．修道士野人問(wèn)題 18．考試問(wèn)題

19．計(jì)算機(jī)輔助考核系統(tǒng) 20．學(xué)籍管理系統(tǒng)

注：學(xué)生可以自選題目或選擇指導(dǎo)老師擬定的題目。

附錄二

開(kāi)發(fā)步驟

1.分析題目的要求、目的； 2.選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；

3.抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)； 4.抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)； 5.編寫(xiě)代碼、上機(jī)調(diào)試； 6.總結(jié)驗(yàn)收、評(píng)價(jià)。

附錄三 報(bào)告書(shū)寫(xiě)格式

1．問(wèn)題描述

題目?jī)?nèi)容、基本要求 2．需求分析

軟件的基本功能、輸入/輸出形式、測(cè)試數(shù)據(jù)要求 3．概要設(shè)計(jì)

所需的ADT及作用、主程序流程及模塊調(diào)用關(guān)系 4．詳細(xì)設(shè)計(jì)

實(shí)現(xiàn)概要設(shè)計(jì)的數(shù)據(jù)類(lèi)型、每個(gè)操作的偽碼算法、主程序和其它模塊的偽碼算法、函數(shù)調(diào)用關(guān)系圖 5．編碼與調(diào)試分析

編碼與調(diào)試過(guò)程中遇到的問(wèn)題及解決的辦法，還存在哪些沒(méi)有解決的問(wèn)題？ 6．使用說(shuō)明

簡(jiǎn)要說(shuō)明程序運(yùn)行操作步驟 7．測(cè)試結(jié)果

8．課程設(shè)計(jì)心得體會(huì)

第四篇：數(shù)據(jù)結(jié)構(gòu)與算法課程論文

數(shù)據(jù)結(jié)構(gòu)與算法課程小論文

10計(jì)本一班 王曉龍 1004011026 一． 內(nèi)容概要：

如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)是擴(kuò)大計(jì)算機(jī)領(lǐng)域、提高軟件效率的關(guān)鍵。在軟件開(kāi)發(fā)過(guò)程中要求“高效地”組織數(shù)據(jù)和設(shè)計(jì)“好的”算法，并使算法用程序來(lái)實(shí)現(xiàn)，通過(guò)調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計(jì)領(lǐng)域的專(zhuān)門(mén)知識(shí)。

本課程主要學(xué)習(xí)在軟件開(kāi)發(fā)中涉及到的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用的算法，在此基礎(chǔ)上，學(xué)習(xí)如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應(yīng)用問(wèn)題。通過(guò)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本算法和相關(guān)應(yīng)用問(wèn)題來(lái)介紹其基本知識(shí)和應(yīng)用知識(shí)。

二． 關(guān)鍵字：

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、基本算法；算法分析

三． 課程主要內(nèi)容和基本原理：

A．?dāng)?shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

在許多類(lèi)型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴(lài)于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。

（1）.分類(lèi)：

數(shù)據(jù)元素相互之間的關(guān)系稱(chēng)為結(jié)構(gòu)。有四類(lèi)基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)全稱(chēng)為非線性結(jié)構(gòu)。集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類(lèi)型外，別無(wú)其它關(guān)系。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。在圖形結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱(chēng)為數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，由此得到的存儲(chǔ)表示稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類(lèi)型來(lái)實(shí)現(xiàn)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。

數(shù)據(jù)結(jié)構(gòu)中，邏輯上（邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系）可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)都無(wú)關(guān)。（2）.四類(lèi)基本結(jié)構(gòu)：

⑴集合結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。⑵線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。⑶樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。

⑷圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，也稱(chēng)網(wǎng)狀結(jié)構(gòu)。從上面所介紹的數(shù)據(jù)結(jié)構(gòu)的概念中可以知道，一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通常可以采用一個(gè)二元組來(lái)表示。

（3）.常用的數(shù)據(jù)結(jié)構(gòu)：

a.數(shù)組： 在程序設(shè)計(jì)中，為了處理方便，把具有相同類(lèi)型的若干變量按有序的形式組織起來(lái)。這些按序排列的同類(lèi)數(shù)據(jù)元素的集合稱(chēng)為數(shù)組。在C語(yǔ)言中，數(shù)組屬于構(gòu)造數(shù)據(jù)類(lèi)型。一個(gè)數(shù)組可以分解為多個(gè)數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類(lèi)型或是構(gòu)造類(lèi)型。因此按數(shù)組元素的類(lèi)型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、指針數(shù)組、結(jié)構(gòu)數(shù)組等各種類(lèi)別。b.棧：

是只能在某一端插入和刪除的特殊線性表。它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）。c.隊(duì)列：

一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)，稱(chēng)為空隊(duì)列。d.鏈表：

是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。e.樹(shù)：

是包含n（n>0）個(gè)結(jié)點(diǎn)的有窮集合K，且在K中定義了一個(gè)關(guān)系N，N滿足以下條件：

（1）有且僅有一個(gè)結(jié)點(diǎn) k0，他對(duì)于關(guān)系N來(lái)說(shuō)沒(méi)有前驅(qū)，稱(chēng)K0為樹(shù)的根結(jié)點(diǎn)。簡(jiǎn)稱(chēng)為根（root）。（2）除K0外，k中的每個(gè)結(jié)點(diǎn)，對(duì)于關(guān)系N來(lái)說(shuō)有且僅有一個(gè)前驅(qū)。

（3）K中各結(jié)點(diǎn)，對(duì)關(guān)系N來(lái)說(shuō)可以有m個(gè)后繼（m>=0）。f.圖：

圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成。其中，為了與樹(shù)形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱(chēng)為頂點(diǎn)，邊是頂點(diǎn)的有序偶對(duì)，若兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。g.堆： 在計(jì)算機(jī)科學(xué)中，堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有一個(gè)值。通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu)，是指二叉堆。堆的特點(diǎn)是根結(jié)點(diǎn)的值最小（或最大），且根結(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆。h.散列表：

若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù)(Hash function)，按這個(gè)思想建立的表為散列表。B．算法分析：

算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法是解題的步驟，可以把算法定義成解一確定類(lèi)問(wèn)題的任意一種特殊的方法。在計(jì)算機(jī)科學(xué)中，算法要用計(jì)算機(jī)算法語(yǔ)言描述，算法代表用計(jì)算機(jī)解一類(lèi)問(wèn)題的精確、有效的方法。算法+數(shù)據(jù)結(jié)構(gòu)=程序，求解一個(gè)給定的可計(jì)算或可解的問(wèn)題，不同的人可以編寫(xiě)出不同的程序，來(lái)解決同一個(gè)問(wèn)題，這里存在兩個(gè)問(wèn)題：一是與計(jì)算方法密切相關(guān)的算法問(wèn)題；二是程序設(shè)計(jì)的技術(shù)問(wèn)題。算法和程序之間存在密切的關(guān)系。分析算法可以預(yù)測(cè)這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對(duì)解決同一問(wèn)題的不同算法的有效性作出比較。

四．心得體會(huì)：

在做完這次課程論文后，讓我再次加深了對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的理解，對(duì)數(shù)據(jù)結(jié)構(gòu)的構(gòu)建也有更深層次的體會(huì)。算法的每一次改進(jìn)和提高，都凝聚著人類(lèi)的智慧和辛勤勞動(dòng)，每一次創(chuàng)新都給人類(lèi)帶來(lái)了巨大的進(jìn)步。數(shù)據(jù)結(jié)構(gòu)與先進(jìn)的算法能夠合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)，擴(kuò)大計(jì)算機(jī)的應(yīng)用領(lǐng)域，提高軟件的效率。這充分體現(xiàn)了其重要意義。

五． 參考文獻(xiàn)：

數(shù)據(jù)結(jié)構(gòu)與算法王昆侖，李紅

第五篇：《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱

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

一、使用說(shuō)明

（一）課程性質(zhì)

《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)專(zhuān)業(yè)基礎(chǔ)課，在計(jì)算機(jī)軟件的各個(gè)領(lǐng)域中均會(huì)使用到數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。本課程的先修課程為C程序設(shè)計(jì)或C++程序設(shè)計(jì)。

（二）教學(xué)目的

學(xué)會(huì)從問(wèn)題入手，分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的操作算法，并初步掌握時(shí)間和空間分析技術(shù)。另一方面，本課程的學(xué)習(xí)過(guò)程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)生會(huì)書(shū)寫(xiě)符合軟件工程規(guī)范的文件，編寫(xiě)的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀，能上機(jī)調(diào)試并排除錯(cuò)誤。

（三）教學(xué)時(shí)數(shù)

課堂講授每周4學(xué)時(shí)，18周，共72學(xué)時(shí)。

（四）教學(xué)方法

本課程將采用課堂講授及課堂討論相結(jié)合的交互式教學(xué)法，同時(shí)輔以必要的上機(jī)操作實(shí)踐。

（五）面向?qū)I(yè)

計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)。

二、教學(xué)內(nèi)容

第一章 緒論

（一）教學(xué)目的要求

介紹數(shù)據(jù)結(jié)構(gòu)的一些基本概念，算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法，抽象數(shù)據(jù)類(lèi)型的定義和使用以及算法的描述方法。掌握數(shù)據(jù)結(jié)構(gòu)的一些基本概念，掌握算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法，了解抽象數(shù)據(jù)類(lèi)型的定義和使用，了解算法的描述方法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、算法等。抽象數(shù)據(jù)類(lèi)型。算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。

教學(xué)重點(diǎn)：有關(guān)數(shù)據(jù)結(jié)構(gòu)的各個(gè)名詞和術(shù)語(yǔ)的含義，以及語(yǔ)句頻度和時(shí)間復(fù)雜度、空間復(fù)雜度的估算。

教學(xué)難點(diǎn)：算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。

第一節(jié)

一、非數(shù)值計(jì)算

二、數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容的歷史演變

三、數(shù)據(jù)結(jié)構(gòu)研究范圍

第二節(jié)

一、數(shù)據(jù)

二、數(shù)據(jù)結(jié)構(gòu)

三、數(shù)據(jù)類(lèi)型

四、抽象數(shù)據(jù)類(lèi)型

五、多型數(shù)據(jù)類(lèi)型

第三節(jié)

一、固有數(shù)據(jù)類(lèi)型

抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)

基本概念和術(shù)語(yǔ) 什么是數(shù)據(jù)結(jié)構(gòu)

二、數(shù)據(jù)抽象

三、抽象數(shù)據(jù)類(lèi)型的描述語(yǔ)言

第四節(jié)

一、算法

二、算法設(shè)計(jì)的要求

三、算法效率的度量

四、算法的存儲(chǔ)空間需求

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

4學(xué)時(shí)。

第二章 線性表

（一）教學(xué)目的與要求

介紹線性表的基本概念和類(lèi)型定義，對(duì)順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)，循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。掌握線性表的基本概念和類(lèi)型定義；熟練掌握對(duì)順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)；掌握循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：線性表的基本概念和類(lèi)型定義，線性表的順序存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)：（1）單鏈表的查找、插入和刪除；（2）循環(huán)鏈表；（3）雙向鏈表。

教學(xué)重點(diǎn)：在順序表和鏈表上各種基本算法的實(shí)現(xiàn)及相關(guān)的時(shí)間性能分析。

教學(xué)難點(diǎn)：用所學(xué)的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問(wèn)題。鏈表要分清鏈表中指針p和結(jié)點(diǎn)*p之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。

第一節(jié)

一、線性表的定義

二、線性表的基本操作

第二節(jié)

一、順序表

二、順序表上基本運(yùn)算的實(shí)現(xiàn)

三、順序表應(yīng)用舉例

第三節(jié)

一、線性鏈表

二、循環(huán)鏈表

三、雙向鏈表

四、靜態(tài)鏈表

第四節(jié) 一、一元多項(xiàng)式的數(shù)學(xué)表示 二、一元多項(xiàng)式的計(jì)算機(jī)表示

三、抽象數(shù)據(jù)類(lèi)型：一元多項(xiàng)式的定義

四、抽象數(shù)據(jù)類(lèi)型：一元多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)

五、抽象數(shù)據(jù)類(lèi)型：一元多項(xiàng)式的基本操作算法實(shí)現(xiàn)

（三）教學(xué)方法與形式

一元多項(xiàng)式的表示及相加 線性表的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn) 線性表的順序存儲(chǔ)表示和實(shí)現(xiàn)

線性表的類(lèi)型定義 算法和算法分析 課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

8學(xué)時(shí)。

第三章 棧和隊(duì)列

（一）教學(xué)目的與要求

介紹棧和隊(duì)列的定義，順序和鏈接存儲(chǔ)的棧和隊(duì)列的各種運(yùn)算的方法及其程序?qū)崿F(xiàn)。掌握棧和隊(duì)列的定義，熟練掌握順序和鏈接存儲(chǔ)的棧和隊(duì)列的各種運(yùn)算的方法及其程序?qū)崿F(xiàn)。

（二）教學(xué)內(nèi)容

主要內(nèi)容：棧的類(lèi)型定義，棧的順序存儲(chǔ)和鏈接存儲(chǔ)的表示，在棧的順序存儲(chǔ)和鏈接存儲(chǔ)上進(jìn)行各種棧操作的算法，棧的應(yīng)用舉例，隊(duì)列的類(lèi)型定義，隊(duì)列的順序存儲(chǔ)(循環(huán)隊(duì))和鏈接存儲(chǔ)表示及各種操作的實(shí)現(xiàn)算法。

教學(xué)重點(diǎn)：棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。教學(xué)難點(diǎn)：遞歸的實(shí)現(xiàn)、循環(huán)隊(duì)列中對(duì)邊界條件的處理。

第一節(jié)

一、抽象數(shù)據(jù)類(lèi)型棧的定義

二、棧的表示和實(shí)現(xiàn)

第二節(jié)

一、數(shù)制轉(zhuǎn)換

二、括號(hào)匹配的檢驗(yàn)

三、表達(dá)式求值

第三節(jié)

一、函數(shù)調(diào)用與棧

二、遞歸調(diào)用棧的變化

第四節(jié)

一、抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義

二、鏈隊(duì)列--隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

三、循環(huán)隊(duì)列--隊(duì)列的順序表示和實(shí)現(xiàn)

第五節(jié)

一、優(yōu)先級(jí)隊(duì)列的概念

二、優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示和實(shí)現(xiàn)

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

4學(xué)時(shí)。

第四章 串

（一）教學(xué)目的與要求

介紹串的基本概念和操作，串的存儲(chǔ)結(jié)構(gòu)以及基本操作的算法實(shí)現(xiàn)。掌握串的基本概念和操作，掌握串的存儲(chǔ)結(jié)構(gòu)以及基本操作的算法實(shí)現(xiàn)。

（二）教學(xué)內(nèi)容

主要內(nèi)容：串的類(lèi)型定義，串的表示和實(shí)現(xiàn)，正文模式匹配，正文編輯——串操作應(yīng)用舉例串的類(lèi)型定義。

教學(xué)重點(diǎn)：串類(lèi)型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法。教學(xué)難點(diǎn)：利用串的基本操作來(lái)實(shí)現(xiàn)串的其它操作。

優(yōu)先級(jí)隊(duì)列 隊(duì)列 棧與遞歸的實(shí)現(xiàn) 棧的應(yīng)用舉例

棧

第一節(jié)

一、串的定義

二、串的基本操作

第二節(jié)

一、定長(zhǎng)順序存儲(chǔ)表示

二、堆分配存儲(chǔ)表示

三、串的塊鏈存儲(chǔ)表示

四、字符串操作的實(shí)現(xiàn)

第三節(jié)

二、模式匹配的一種改進(jìn)算法

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

4學(xué)時(shí)。

串的類(lèi)型定義

串的表示和實(shí)現(xiàn)

字符串的模式匹配

一、求子串位置的定位函數(shù)Index（S，T，pos）

第五章 數(shù)組和廣義表

（一）教學(xué)目的

介紹數(shù)組的基本概念和基本操作的算法實(shí)現(xiàn)；稀疏矩陣的定義和各種存儲(chǔ)結(jié)構(gòu)，稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；廣義表的定義、存儲(chǔ)結(jié)構(gòu)和求廣義表的長(zhǎng)度及深度的算法，建立廣義表和輸出廣義表的方法并了解其算法。掌握數(shù)組的基本概念和基本操作的算法實(shí)現(xiàn)；掌握稀疏矩陣的定義和各種存儲(chǔ)結(jié)構(gòu)，掌握稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；掌握廣義表的定義、存儲(chǔ)結(jié)構(gòu)和求廣義表的長(zhǎng)度及深度的算法，掌握建立廣義表和輸出廣義表的方法并了解其算法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：稀疏矩陣的定義、存儲(chǔ)和運(yùn)算，廣義表的定義、存儲(chǔ)和運(yùn)算串的類(lèi)型定義。教學(xué)重點(diǎn)：特殊矩陣的壓縮存儲(chǔ)，以及稀疏矩陣的三元組順序表示。教學(xué)難點(diǎn)：特殊矩陣的壓縮存儲(chǔ)，以及稀疏矩陣的三元組順序表示。

第一節(jié) 第二節(jié)

一、數(shù)組的存儲(chǔ)方式

二、數(shù)組元素存儲(chǔ)位置的計(jì)算

三、基本操作的實(shí)現(xiàn)

第三節(jié)

一、特殊矩陣

二、稀疏矩陣

第四節(jié)

一、廣義表的基本概念

二、廣義表的三個(gè)重要結(jié)論

第五節(jié)

一、頭尾鏈表存儲(chǔ)表示

二、擴(kuò)展線性鏈表存儲(chǔ)表示

第六節(jié)

廣義表的遞歸算法 廣義表的存儲(chǔ)表示 廣義表的定義 矩陣的壓縮存儲(chǔ) 數(shù)組類(lèi)型 數(shù)組的順序表示和實(shí)現(xiàn)

一、求廣義表的深度

二、復(fù)制廣義表

三、建立廣義表的存儲(chǔ)結(jié)構(gòu)

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

6學(xué)時(shí)。

第六章 樹(shù)和二叉樹(shù)

（一）教學(xué)目的與要求

介紹樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)及遍歷算法，握二叉樹(shù)的各種遍歷方法及其實(shí)現(xiàn)，二叉樹(shù)的其他操作方法及實(shí)現(xiàn)，樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換方法，哈夫曼樹(shù)的定義和構(gòu)造哈夫曼樹(shù)的方法，哈夫曼樹(shù)編碼的方法。掌握樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)及遍歷算法，熟練掌握二叉樹(shù)的各種遍歷方法及其實(shí)現(xiàn)，掌握二叉樹(shù)的其他操作方法及實(shí)現(xiàn)，掌握樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換方法，掌握哈夫曼樹(shù)的定義和構(gòu)造哈夫曼樹(shù)的方法，了解哈夫曼樹(shù)編碼的方法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：樹(shù)的定義、性質(zhì)和表示方法，二叉樹(shù)的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的各種遍歷方法及實(shí)現(xiàn)，建立二叉樹(shù)、輸出二叉樹(shù)、求二叉樹(shù)深度等的操作方法及實(shí)現(xiàn)，樹(shù)的存儲(chǔ)結(jié)構(gòu)，進(jìn)行先根遍歷、后根遍歷和按層遍歷的方法及實(shí)現(xiàn)，進(jìn)行樹(shù)與二叉樹(shù)的轉(zhuǎn)換方法，哈夫曼樹(shù)的定義、構(gòu)造哈夫曼樹(shù)的方法及哈夫曼編碼的方法。

教學(xué)重點(diǎn)：二叉樹(shù)和樹(shù)的遍歷及其應(yīng)用。

教學(xué)難點(diǎn)：實(shí)現(xiàn)二叉樹(shù)和樹(shù)的各種操作的遞歸算法。

第一節(jié)

一、樹(shù)的定義

二、森林的定義

三、樹(shù)的抽象數(shù)據(jù)類(lèi)型定義

第二節(jié) 一、二叉樹(shù)的定義 二、二叉樹(shù)的性質(zhì) 三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

第三節(jié)

一、遍歷二叉樹(shù)

二、線索二叉樹(shù)

第四節(jié)

一、樹(shù)的存儲(chǔ)結(jié)構(gòu)

二、森林與二叉樹(shù)的轉(zhuǎn)換

三、樹(shù)和森林的遍歷

第五節(jié)

一、最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）

二、赫夫曼編碼

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

10學(xué)時(shí)。

最優(yōu)樹(shù)和赫夫曼編碼

樹(shù)和森林

遍歷二叉樹(shù)和線索二叉樹(shù)

二叉樹(shù)

樹(shù)的定義和基本術(shù)語(yǔ)

第七章 圖

（一）教學(xué)目的與要求

介紹圖的定義和術(shù)語(yǔ)；圖的存儲(chǔ)結(jié)構(gòu)及深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)；圖的生成樹(shù)的概念，求圖的最小生成樹(shù)的普里姆算法和克魯斯卡爾算法并了解其實(shí)現(xiàn)算法；拓?fù)渑判虻姆椒ú⒘私馄鋵?shí)現(xiàn)算法；計(jì)算關(guān)鍵路徑的方法及其實(shí)現(xiàn)算法。掌握?qǐng)D的定義和術(shù)語(yǔ)；熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)；掌握?qǐng)D的生成樹(shù)的概念，掌握求圖的最小生成樹(shù)的普里姆算法和克魯斯卡爾算法并了解其實(shí)現(xiàn)算法；掌握拓?fù)渑判虻姆椒ú⒘私馄鋵?shí)現(xiàn)算法；了解計(jì)算關(guān)鍵路徑的方法并了解其實(shí)現(xiàn)算法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：圖的定義和術(shù)語(yǔ)，圖的鄰接矩陣、鄰接表和邊集數(shù)組表示，圖的深度和廣度優(yōu)先搜索遍歷，圖的生成樹(shù)和最小生成樹(shù)，拓?fù)渑判颉?/p>

教學(xué)重點(diǎn)：圖在鄰接矩陣與鄰接表上實(shí)現(xiàn)的遍歷算法(DFS和BFS)。教學(xué)難點(diǎn)：基于遍歷算法的應(yīng)用。

第一節(jié)

一、圖的定義

二、無(wú)向圖

三、有向圖

四、連通圖

五、生成樹(shù)

第二節(jié)

一、數(shù)組表示法

二、鄰接表 三、十字鏈表

四、鄰接多重表

第三節(jié)

一、深度優(yōu)先搜索

二、廣度優(yōu)先搜索

三、連通分量

第四節(jié)

一、Kruskal算法

二、Prim算法

第五節(jié)

一、拓?fù)渑判?/p>

二、關(guān)鍵路徑

第六節(jié)

一、從某個(gè)源點(diǎn)到其余各項(xiàng)點(diǎn)的最短路徑

二、每一對(duì)頂點(diǎn)之間的最短路徑

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

12學(xué)時(shí)。

最短路徑 有向無(wú)環(huán)圖及其應(yīng)用

最小生成樹(shù) 圖的遍歷 圖的存儲(chǔ)表示 圖的定義和術(shù)語(yǔ)

第八章 查找表

（一）教學(xué)目的與要求

介紹順序表查找和有序表查找的方法及實(shí)現(xiàn)；二叉排序樹(shù)和平衡二叉樹(shù)的定義、對(duì)二叉排序樹(shù)和平衡二叉樹(shù)進(jìn)行插入、刪除和查找的方法和實(shí)現(xiàn)。哈希表的定義，構(gòu)造哈希函數(shù)的多種方法，以及處理沖突的方法；B樹(shù)的定義，查找、插入和刪除元素的方法。熟練掌握順序表查找和有序表查找的方法及實(shí)現(xiàn)；掌握二叉排序樹(shù)和平衡二叉樹(shù)的定義、熟練掌握對(duì)二叉排序樹(shù)和平衡二叉樹(shù)進(jìn)行插入、刪除和查找的方法和實(shí)現(xiàn)。掌握哈希表的定義，構(gòu)造哈希函數(shù)的多種方法，以及處理沖突的方法；了解B樹(shù)的定義，查找、插入和刪除元素的方法。

（二）教學(xué)內(nèi)容

主要內(nèi)容：順序查找和二分查找，索引查找和分塊查找，散列查找，動(dòng)態(tài)查找樹(shù)表。教學(xué)重點(diǎn)：順序查找、二分查找、二叉排序樹(shù)上查找以及散列表上查找的基本思想和算法實(shí)現(xiàn)。

教學(xué)難點(diǎn)：二叉排序樹(shù)的刪除算法。

第一節(jié)

一、順序表的查找

二、有序表的查找

三、靜態(tài)樹(shù)表的查找

四、索引順序表的查找

第二節(jié) 一、二叉排序樹(shù)

二、平衡二叉樹(shù)

三、動(dòng)態(tài)的m路搜索樹(shù)

四、B樹(shù)和B+樹(shù)基本概念

第三節(jié)

一、什么是哈希表

二、哈希函數(shù)的構(gòu)造方法

三、處理沖突的方法

四、哈希表的查找及其分析

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

10學(xué)時(shí)。

第九章 內(nèi)部排序

（一）教學(xué)目的與要求

介紹插入排序、交換排序、選擇排序、快速排序、歸并排序、基數(shù)排序的方法及其實(shí)現(xiàn)，快速排序、堆排序、二路歸并排序的方法及其實(shí)現(xiàn)，各種排序方法的穩(wěn)定性、時(shí)間復(fù)雜度和空間復(fù)雜度。掌握插入排序、交換排序、選擇排序、快速排序、歸并排序、基數(shù)排序的方法及其實(shí)現(xiàn)，熟練掌握快速排序、堆排序、二路歸并排序的方法及其實(shí)現(xiàn)，掌握各種排序方法的穩(wěn)定性、時(shí)間復(fù)雜度和空間復(fù)雜度。

（二）教學(xué)內(nèi)容

主要內(nèi)容：排序的概念，直接插入排序，冒泡排序和快排序，直接選擇排序和堆排序，歸并排序。

哈希表 動(dòng)態(tài)查找表 靜態(tài)查找表 教學(xué)重點(diǎn)：插入排序(直接插入、折半插入)、交換排序（冒泡、快速排序）、選擇排序（直接選擇、堆）、2-路歸并排序。

教學(xué)難點(diǎn)：快速排序partition算法的應(yīng)用和堆的調(diào)整。

第一節(jié)

一、穩(wěn)定的排序方法

二、內(nèi)部/外部排序

三、內(nèi)部排序種類(lèi)

四、排序中的基本操作

五、排序數(shù)據(jù)的存儲(chǔ)方式

第二節(jié)

一、直接插入排序

二、其他插入排序

三、希爾排序

第三節(jié)

一、起泡排序算法

二、快速排序算法

第四節(jié)

一、簡(jiǎn)單選擇排序

二、樹(shù)形選擇排序

三、堆排序

第五節(jié) 第六節(jié)

一、多關(guān)鍵字的排序

二、鏈?zhǔn)交鶖?shù)排序

第七節(jié)

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

10學(xué)時(shí)。

第十章 文件

（一）教學(xué)目的與要求

介紹文件和記錄的基本概念以及基本操作。掌握文件和記錄的基本概念以及基本操作。

（二）教學(xué)內(nèi)容

主要內(nèi)容：基本概念，順序文件，索引文件，索引順序文件，散列文件，多關(guān)鍵碼文件。教學(xué)重點(diǎn)：各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。教學(xué)難點(diǎn)：各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。

第一節(jié)

一、文件及其類(lèi)別

二、記錄的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

三、文件的操作

四、文件的物理結(jié)構(gòu)

第二節(jié)

一、順序文件的定義

順序文件 基本概念

各種排序方法的綜合比較

歸并排序法 基數(shù)排序 選擇排序法 交換排序法 插入排序 排序的定義和方法

二、順序文件的優(yōu)缺點(diǎn)

第三節(jié)

一、索引文件的定義

二、索引文件的特點(diǎn)

第四節(jié)

一、ISAM文件

二、VSAM文件

第五節(jié)

一、散列文件的定義

二、散列文件的特點(diǎn)

第六節(jié)

一、多重表文件

二、倒排文件

（三）教學(xué)方法與形式

課堂講授、多媒體課件。

（四）教學(xué)時(shí)數(shù)

4學(xué)時(shí)。

三、考核方式

本課程的考核采用閉卷考試的方式，課程的總評(píng)成績(jī)由平時(shí)成績(jī)、實(shí)驗(yàn)成績(jī)和期末考試成績(jī)?nèi)糠纸M成，其中平時(shí)成績(jī)占總評(píng)成績(jī)的10%，實(shí)驗(yàn)成績(jī)占總評(píng)成績(jī)的30%，期末考試成績(jī)占總評(píng)成績(jī)的60%。

四、教材選用

1、殷人昆，陶永雷，謝若陽(yáng)等：《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述）》，清華大學(xué)出版社，2007.6年第二版。

2、嚴(yán)蔚敏，吳偉民：《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》 及《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》，清華大學(xué)出版社，2003年第一版。

多關(guān)鍵碼文件 散列文件 ISAM文件和VSAM文件

索引文件