每個人都曾試圖在平淡的學習、工作和生活中寫一篇文章。寫作是培養(yǎng)人的觀察、聯(lián)想、想象、思維和記憶的重要手段。范文怎么寫才能發(fā)揮它最大的作用呢？下面是小編幫大家整理的優(yōu)質(zhì)范文，僅供參考，大家一起來看看吧。

數(shù)據(jù)結(jié)構課程實驗教學大綱 數(shù)據(jù)結(jié)構課程大綱篇一

《數(shù)據(jù)結(jié)構》課程教學大綱

第一部分 大綱說明

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

《數(shù)據(jù)結(jié)構》是計算機科學與技術專業(yè)本科生的一門必修課程。本課程介紹如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊列、遞歸、樹與森林、圖、堆與優(yōu)先級隊列、集合與搜索結(jié)構、排序、索引與散列結(jié)構等。課程采用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構技術，并以兼有面向過程和面向?qū)ο箅p重特色的c++語言作為算法的描述工具，強化數(shù)據(jù)結(jié)構基本知識和面向?qū)ο蟪绦蛟O計基本能力的雙基訓練。為后續(xù)計算機專業(yè)課程的學習打下堅實的基礎。

二、先修課要求

面向?qū)ο蟪绦蛟O計、計算機數(shù)學(離散數(shù)學)。

三、課程的教學基本要求

1、掌握重要數(shù)據(jù)結(jié)構的概念、使用方法及實現(xiàn)技術；

2、學會做簡單的算法分析，包括算法的時間代價和空間代價。

四、教學方法和教學形式建議

電視授課為主，結(jié)合面授輔導、面授或電子郵件答疑，進行必要的上機實驗。

五、課程教學要求的層次

1、熟練掌握：要求學生能夠全面、深入理解和熟練掌握所學內(nèi)容，并能夠用其知識分析、設計和解答相關的應用問題。

2、掌握：要求學生能夠較好地理解和掌握，并且能夠做簡單的分析。

3、了解：要求學生能夠一般地了解的所學內(nèi)容。

六、課程實驗

實驗內(nèi)容和要求由省級電大作出具體規(guī)定，從2004年春開始按該課程實驗教材規(guī)定進行。

第二部分 多種媒體教材一體化總體設計初步方案

一、學時分配

課程教學總學時數(shù)為 72學時，4學分，其中講授學時48，實驗24

教 學 內(nèi) 容

講授學時

實驗學時

一、數(shù)據(jù)結(jié)構基本概念及算法分析

3學時

2學時

二、數(shù)組

3學時

2學時

三、鏈表

3學時

3學時

四、棧和隊列

3學時

2學時

五、遞歸

3學時

2學時

六、樹與森林

9學時

4學時

七、集合與搜索

5學時

2學時

八、圖

7學時

4學時

九、排序

7學時

3學時

十、索引與散列結(jié)構

5學時

二、教學環(huán)節(jié)

1、電視教學

本課程是計算機專業(yè)基礎課，內(nèi)容多且?guī)в幸欢ǖ某橄笮裕瑢W習起來有一定難度。為保證教學效果，采取電視集中授課方式。聘請有經(jīng)驗的教師擔任主講教師，盡可能利用多種媒體進行教學，使學生能夠很快掌握課程的主要知識和解決問題的方法。

2、面授輔導或答疑

本課程教學過程中，面授輔導和答疑是必不可少的教學環(huán)節(jié)。各地方電大應聘請有經(jīng)驗、認真負責的教師任教，以習題課、專題討論或答疑的方式，對課程中的重要概念和典型問題的解決方法進行總結(jié)和深入討論，鞏固和加深課堂內(nèi)學到的知識。面授輔導或答疑安排兩周一次為宜。必要時可采用電子郵件方式直接與主講教師聯(lián)系進行答疑。

3、自學與練習

自學是獲取知識的重要手段。教師講課只是起到拋磚引玉的作用，關鍵還在于學生的自學。為達到自學的效果，除讀懂教科書中所講內(nèi)容外，還需大量做題。其目的是要通過做題弄懂、加深對概念的理解，提高程序設計，解決問題的能力。為此，安排一定的實驗上機學時。要求學生珍惜實驗機時，真正做到學有所獲。

學生在上機做實驗前，應事先將程序、調(diào)試數(shù)據(jù)、上機操作順序準備好，并提前使用這些調(diào)試數(shù)據(jù)人工執(zhí)行過。目的是提高上機的效率和成功率，嚴禁抄襲或拷貝他人的成果，自覺培養(yǎng)科學、嚴謹?shù)淖黠L。

除學校提供的時間外，要求課外學生利用自己可能擁有的計算機條件，完成更多的練習，不通過大量的實踐，能力和知識水平得不到有效得提高。

4、考試

考試是對學生掌握知識水平的檢驗。本著多練多考的原則，各地方電大可以再平時多做一些小考。要求考試內(nèi)容緊扣大綱要求，既要能夠檢驗學生的掌握情況，又要體現(xiàn)水平。因此，不要出難題、怪題，但也不要過于簡單，適當有一些編程題。

課程考試具體規(guī)定請參看該課程考核說明。

第三部分 教學內(nèi)容和教學要求

一、數(shù)據(jù)結(jié)構基本概念及簡單的算法分析 3學時

1、教學內(nèi)容：

什么是數(shù)據(jù)結(jié)構

抽象數(shù)據(jù)類型及面向?qū)ο蟾拍睿簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構的語言

數(shù)據(jù)結(jié)構的抽象層次

算法定義

性能分析與度量：算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜度

2、教學要求：

了解：什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構、數(shù)據(jù)的邏輯結(jié)構與物理結(jié)構、邏輯結(jié)構與物理結(jié)構間的關系

了解：什么是數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什么是面向?qū)ο?/p>

了解：算法的定義、算法的特性、算法的時間代價、算法的空間代價

掌握：用c++語言描述算法的方法，能夠使用c++語言編寫程序

二、數(shù)組 3學時

1、教學內(nèi)容：

作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義和初始化；作為抽象數(shù)據(jù)類型的數(shù)組；數(shù)組的順序存儲方式

順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例

字符串：字符串的抽象數(shù)據(jù)類型；字符串操作的實現(xiàn)；字符串的模式匹配

2、教學要求：

了解：線性表的邏輯結(jié)構特性，以及線性表的兩種存儲實現(xiàn)方式

了解：作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序存儲與按列順序存儲

熟練掌握：順序表的定義與實現(xiàn)，包括搜索、插入、刪除算法的實現(xiàn)及其平均比較次數(shù)的計算，掌握應用順序表作為集合的簡單操作

了解：稀疏矩陣的定義及其數(shù)組實現(xiàn)

熟練掌握：字符串的定義及實現(xiàn)

三、鏈表 3學時

1、教學內(nèi)容：

單鏈表：單鏈表的結(jié)構；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點的單鏈表；用模板定義的單鏈表類；靜態(tài)鏈表

循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；

多項式及其相加：多項式的類定義；多項式的加法

雙向鏈表

2、教學要求：

了解：鏈表與數(shù)組一樣，是一種實現(xiàn)級結(jié)構。有動態(tài)鏈表和靜態(tài)鏈表之分

了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分

了解：單鏈表的結(jié)構、特點

掌握：單鏈表的類定義、構造函數(shù)、單鏈表的插入與刪除算法

了解：帶表頭結(jié)點的單鏈表的優(yōu)點和類定義及相應操作的實現(xiàn)

熟練掌握：用模板定義的單鏈表類

了解：循環(huán)鏈表的特點，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法

掌握：雙向鏈表的特點，雙向鏈表的類定義及相關操作的實現(xiàn)，用雙向鏈表解決問題的方法。

四、棧和隊列 3學時

1、教學內(nèi)容：

棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈接存儲表示

表達式求值：中綴表達式求值；中綴表示到后綴表示的轉(zhuǎn)換

隊列 ：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示；隊列的應用舉例

優(yōu)先級隊列：優(yōu)先級隊列的定義；優(yōu)先級隊列的存儲表示

2、教學要求：

熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應操作的實現(xiàn)。特別注意?？蘸蜅M的條件

了解：在表達式計算時棧是如何使用的，重點了解用后綴表示計算表達式及中綴表示改后綴表示的方法和算法思路

熟練掌握：隊列的定義、特性和隊列的抽象數(shù)據(jù)類型，隊列的順序表示、鏈表表示以及相應操作的實現(xiàn)。特別是循環(huán)隊列中隊頭與隊尾指針的變化情況

掌握：優(yōu)先級隊列的定義、特性和優(yōu)先級隊列的抽象數(shù)據(jù)類型，優(yōu)先級隊列的插入與刪除算法

五、遞歸 3學時

1、教學內(nèi)容：

遞歸的概念：遞歸問題的求解

遞歸過程與遞歸工作棧：單向遞歸和尾遞歸的迭代實現(xiàn)；一般遞歸問題利用棧實現(xiàn)非遞歸解法

廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結(jié)構的實現(xiàn)；廣義表的訪問算法；廣義表的遞歸算法

2、教學要求：

掌握：遞歸的概念。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法

掌握：遞歸過程的機制與利用遞歸工作棧實現(xiàn)遞歸的方法

了解：迷宮問題的遞歸求解思路及如何利用棧實現(xiàn)迷宮問題的非遞歸解法

掌握：利用遞歸解決問題的分治法和回溯法

掌握：廣義表的定義及其實現(xiàn)方法

掌握：廣義表的遞歸算法

六、樹與森林 9學時

1、教學內(nèi)容：

樹和森林的概念：樹的定義；樹的術語；樹的抽象數(shù)據(jù)類型

二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型

二叉樹的表示：順序表示；二叉鏈表表示

遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應用二叉樹遍歷的事例；二叉樹的計數(shù)

線索化二叉樹：線索；中序線索化二叉樹

堆：堆的定義；堆的建立；堆的插入與刪除；堆的調(diào)整算法

樹與森林：樹的存儲表示；森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林

霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼

2、教學要求：

了解：樹和森林的概念。包括樹的定義、樹的術語、樹的抽象數(shù)據(jù)類型

掌握：二叉樹的概念、性質(zhì)及二叉樹的表示

熟練掌握：二叉樹的遍歷方法

掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法

熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實現(xiàn)優(yōu)先級隊列的方法

掌握：樹與森林的實現(xiàn)，重點在用二叉樹實現(xiàn)

掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法

掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法

掌握：霍夫曼樹的實現(xiàn)方法、構造霍夫曼編碼的方法及帶權路徑長度的計算

七、集合與搜索 5學時

1、教學內(nèi)容：

集合及其表示：集合基本概念；以集合為基礎的抽象數(shù)據(jù)類型；用位向量實現(xiàn)集合抽象據(jù)類型；用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型

并查集：并查集的定義；并查集的實現(xiàn)

簡單的搜索結(jié)構：搜索的概念；靜態(tài)搜索結(jié)構；順序搜索；基于有序順序表的順序搜索和折半搜索

二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除

avl樹：avl樹定義；平衡化旋轉(zhuǎn)；avl樹的插入和刪除；avl樹高度

2、教學要求：

掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關操作的實現(xiàn)算法

掌握：利用并查集實現(xiàn)集合的方法

熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法

熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法

掌握：avl樹的平衡化旋轉(zhuǎn)、構造、插入、刪除時的調(diào)整方法及其性能分析

八、圖 7學時

1、教學內(nèi)容：

圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型

圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表

圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關節(jié)點與重連通分量

最小生成樹：kruskul算法；prim算法

單源最短路徑問題：dijkstra算法

活動網(wǎng)絡：aov網(wǎng)絡與拓撲排序；aoe網(wǎng)絡與關鍵路徑

2、教學要求：

理解：圖的基本概念和圖的抽象數(shù)據(jù)類型

掌握：圖的3種存儲表示：鄰接矩陣、鄰接表和鄰接多重表。對于前兩種，要求掌握典型操作，如構造、求根、找第一個鄰接頂點、找下一個鄰接頂點等操作的實現(xiàn)算法

熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)

理解：求解關節(jié)點及構造重連通圖的方法(不要求算法)

掌握：構造最小生成樹的prim算法和kruskal算法，要求理解算法

理解：如何用dijkstra方法求解單源最短路徑問題(不要求算法)

熟練掌握：活動網(wǎng)絡的拓撲排序算法

掌握：求解關鍵路徑的方法

九、排序 7學時

1、教學內(nèi)容：

概述

插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序

交換排序：起泡排序；快速排序

選擇排序：直接選擇排序；錦標賽排序；堆排序

歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序

基數(shù)排序：多關鍵碼排序；鏈式基數(shù)排序

外排序：外排序的基本過程；k路平衡歸并；初始歸并段的生成；最佳歸并樹

2、教學要求：

掌握：排序的基本概念和性能分析方法

掌握：插入排序、交換排序、選擇排序、歸并排序等內(nèi)排序的方法及其性能分析方法

了解：基數(shù)排序方法及其性能分析方法

掌握：多路平衡歸并等外排序方法及敗者樹構造方法

掌握：生成初始歸并段及敗者樹構造方法

掌握：最佳歸并樹的建立方法

十、索引與散列結(jié)構 5學時

1、教學內(nèi)容：

靜態(tài)索引結(jié)構：線性索引；倒排索引；m路靜態(tài)查找樹

動態(tài)索引結(jié)構：動態(tài)的m路查找樹；b樹的定義；b樹的插入；b樹的刪除；b+樹

散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析

2、教學要求：

熟練掌握：靜態(tài)索引結(jié)構，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構造方法

熟練掌握：動態(tài)索引結(jié)構，包括b樹、b+樹的搜索和構造方法

熟練掌握：散列法，包括散列函數(shù)的構造、解決沖突的方法

數(shù)據(jù)結(jié)構課程實驗教學大綱 數(shù)據(jù)結(jié)構課程大綱篇二

數(shù)據(jù)結(jié)構 data structure 課程代碼：

學 時 數(shù)：64（講課50 實驗14 研討0 實習實踐1周）

學 分 數(shù)：

3、4 課程類別：學科基礎課

開課學期：4 主講教師：

編寫日期： 2011年7月1日

一、課程性質(zhì)和目的課程性質(zhì)：數(shù)據(jù)結(jié)構a是計算機科學與技術、數(shù)字媒體藝術、信息管理與信息系統(tǒng)專業(yè)的一門重要學科基礎課，是必修課。

教學目的：通過本課程的學習，一方面，使學生學會分析研究計算機加工的數(shù)據(jù)結(jié)構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構、存儲結(jié)構及相應的算法，并初步了解對算法的時間分析和空間分析技術。另一方面，通過對本課程算法設計和上機實踐的訓練，還應培養(yǎng)學生的數(shù)據(jù)抽象能力和程序設計的能力。

二、課程教學內(nèi)容、學時分配和課程教學基本要求

1.緒論（理論2學時）

教學內(nèi)容：

(1)數(shù)據(jù)結(jié)構的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構、物理結(jié)構等。(2)抽象數(shù)據(jù)類型的表示和實現(xiàn)。(3)算法的概念和特性。

(4)算法時間復雜度和空間復雜度的分析。基本要求：

掌握數(shù)據(jù)結(jié)構的基本概念，了解抽象數(shù)據(jù)類型，掌握算法時間復雜度和空間復雜度的分析方法。

2.線性表（理論8學時，實驗4學時）

教學內(nèi)容：

(1)線性表的類型定義。(2)線性表的順序表示和實現(xiàn)。(3)線性表的鏈式表示和實現(xiàn)。

(4)線性表的應用，包括無序表和有序表的合并、多項式的加法運算等?；疽螅?/p>

理解線性表的邏輯結(jié)構特性是數(shù)據(jù)元素之間存在著線性關系，在計算機中表示這種關系的兩類不同的存儲結(jié)構是順序存儲結(jié)構（順序表）和鏈式存儲結(jié)構（鏈表）。熟練掌握這兩類存儲結(jié)構的描述方法，掌握鏈表中的頭結(jié)點、頭指針和首元結(jié)點的區(qū)別及循環(huán)鏈表、雙向鏈表的特點等。掌握順序表的查找、插入和刪除算法，掌握鏈表的查找、插入和刪除算法。能夠從時間和空間復雜度的角度比較兩種存儲結(jié)構的不同特點及其適用場合。掌握無序表和有序表的合并算法，了解多項式的加法運算。

實驗：

實驗內(nèi)容：單鏈表的基本操作。實驗要求：以單鏈表形式創(chuàng)建一個學生表或圖書表，并能實現(xiàn)相關的查找、插入和刪除等算法。3.棧和隊列（理論6學時，實驗4學時）

教學內(nèi)容：

(1)棧的類型定義，棧的順序存儲和鏈接存儲的表示和實現(xiàn)。(2)棧的應用舉例，如迷宮求解和表達式求值。

(3)棧與遞歸的實現(xiàn)，遞歸程序轉(zhuǎn)換為非遞歸程序的方法。

(4)隊列的類型，隊列的順序存儲(循環(huán)隊)和鏈接存儲的表示和實現(xiàn)。(5)隊列的應用舉例，如打印楊暉三角形，模擬汽車加油站等問題?；疽螅?/p>

掌握棧和隊列的特點，并能在相應的應用問題中正確選用。熟練掌握棧的順序棧和鏈棧的進棧出棧算法，特別應注意棧滿和?？盏臈l件。掌握利用棧實現(xiàn)表達式求值的算法，了解迷宮求解算法。理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程，了解將遞歸程序轉(zhuǎn)換為非遞歸程序的方法。熟練掌握循環(huán)隊列和鏈隊列的進隊出隊算法，特別是循環(huán)隊列中隊頭與隊尾指針的變化情況。了解隊列的應用。

實驗：

實驗內(nèi)容：棧的應用。實驗要求：借助棧來解決某些實際應用問題，如表達式求值、迷宮問題等。

4.串、數(shù)組和廣義表（理論2學時）

教學內(nèi)容：

(1)串的表示和實現(xiàn)，包括順序存儲和鏈式存儲表示。古典的模式匹配算法。(2)數(shù)組的存儲方法。

(3)特殊矩陣和稀疏矩陣的壓縮存儲，稀疏矩陣的轉(zhuǎn)置運算。(4)廣義表的邏輯結(jié)構和存儲結(jié)構?；疽螅?/p>

了解串的順序存儲結(jié)構和堆存儲結(jié)構。掌握串的古典的模式匹配算法。掌握數(shù)組的地址計算方法。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍。了解廣義表的結(jié)構特點及其存儲方法。5.樹和二叉樹（理論8學時，實驗2學時）

教學內(nèi)容：

(1)二叉樹的定義和術語，二叉樹的性質(zhì)，特殊的二叉樹。(2)二叉樹的存儲結(jié)構，順序存儲和二叉鏈表。

(3)二叉樹的的前序、中序、后序、層次遍歷方法。線索化二叉樹。(4)樹和森林的定義，樹的存儲，樹、森林與二叉樹的轉(zhuǎn)換。(5)樹的應用，哈夫曼樹及哈夫曼編碼?；疽螅?/p>

了解樹和森林的概念，包括樹的定義、樹的術語。掌握二叉樹的概念、性質(zhì)及二叉樹的表示。熟練掌握二叉樹的遍歷算法，并且能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作。掌握線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法。了解樹的存儲、樹和森林與二叉樹的轉(zhuǎn)換方法。掌握哈夫曼樹的實現(xiàn)方法、構造哈夫曼編碼的方法及帶權路徑長度的計算。

實驗：

實驗內(nèi)容：二叉樹的基本算法。實驗要求：利用二叉鏈表方法建立二叉樹，實現(xiàn)二叉樹的前、中、后序三種遍歷算法，并運用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結(jié)點個數(shù)、葉子結(jié)點個數(shù)、二叉樹的高度等。6.圖（理論8學時，實驗2學時）

教學內(nèi)容：

(1)圖的定義和術語。

(2)圖的存儲結(jié)構兩種存儲結(jié)構：鄰接矩陣和鄰接表表示法。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。(4)構造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓撲排序和關鍵路徑。

(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法?；疽螅?/p>

掌握圖的基本概念及相關術語和性質(zhì)，掌握圖的鄰接矩陣和鄰接表表示法，了解實際問題的求解效率與采用何種存儲結(jié)構和算法有密切聯(lián)系。熟練掌握圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。掌握構造最小生成樹的兩種算法及拓撲排序算法的思想，掌握迪杰斯特拉算法。了解關鍵路徑的概念和求解方法，了解弗洛伊德算法。

實驗：

實驗內(nèi)容：圖的建立和搜索。實驗要求：使用鄰接矩陣或鄰接表表示法存儲一個圖，實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。7.查找（理論6學時）

教學內(nèi)容：(1)查找的基本概念，平均查找長度。(2)基于線性表的查找：順序查找、折半查找。

(3)基于樹表的查找：二叉排序樹、平衡二叉樹、b-樹和b+樹。

(4)散列表：散列表的基本概念，散列函數(shù)的構造方法、處理沖突的方法、散列表的查找與分析。

基本要求：

熟練掌握順序表和有序表的查找方法及其實現(xiàn)，掌握二叉排序樹的插入和查找算法及其實現(xiàn)，了解平衡二叉樹、b-樹和b+樹的各種操作。熟練掌握散列表的構造方法、處理沖突的方法，深刻理散列表與其他結(jié)構的表的實質(zhì)性的差別，了解各種散列函數(shù)的特點。掌握描述折半查找過程的判定樹的構造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。

8.排序（理論8學時，實驗2學時）

教學內(nèi)容：

(1)排序的基本概念，包括正序，逆序，穩(wěn)定性，排序方法的分類。(2)插入排序：直接插入排序、折半插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡單選擇排序和堆排序。(5)歸并排序：2-路歸并排序。

(6)基數(shù)排序：多關鍵字的排序和鏈數(shù)基數(shù)排序。

(7)排序算法分析：各種排序算法的比較和移動次數(shù)，時間復雜度和空間復雜度的分析?；疽螅?/p>

明確排序的基本概念，排序方法的分類。深刻理解排序算法的過程、特點及其依據(jù)的原則，并能加以靈活應用。掌握各種排序方法的時間和空間復雜度的分析方法。能從關鍵字間的比較次數(shù)和移動次數(shù)分析算法的平均情況和最壞情況的時間性能。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的?？焖倥判?、堆排序和歸并排序等高效排序方法是本章的學習重點和難點。

實驗：

實驗內(nèi)容：綜合性實驗。實驗要求：選取一個合適的數(shù)據(jù)結(jié)構存儲數(shù)據(jù)，能對數(shù)據(jù)進行插入、刪除，用不同查找算法進行查找、用不同的排序算法進行排序等。9.實習（1周）

教學內(nèi)容：

(1)設計準備：理解實習任務，明確相關算法，搜集可用資源，熟悉實習環(huán)境。(2)方案設計：完成設計目標、設計路線的確定，并進行模塊設計和任務分工。(3)代碼編寫：各模塊代碼編寫，模塊測試。(4)代碼測試：模塊組裝，整體測試。(5)設計報告：完成設計文檔，制作設計報告?；疽螅?/p>

能將數(shù)據(jù)結(jié)構課程中所學的基本知識融會貫通，綜合運用所學的知識解決相關的實際問題，能夠把所學知識（包括算法和結(jié)構）在計算機上用編程語言加以實現(xiàn)，并且能夠根據(jù)實際需求創(chuàng)建自己的數(shù)據(jù)結(jié)構和實現(xiàn)自己的算法。

本課程的教學環(huán)節(jié)包括：課堂講授、實驗、實習、作業(yè)、答疑、小測驗等。其中，課堂講授以教師講授為主，授課時將電子教案和板書相結(jié)合，充分發(fā)揮各自的優(yōu)點。采用啟發(fā)式教學，鼓勵學生自學，培養(yǎng)學生的自學能力，以“少而精”為原則，精選教學內(nèi)容，調(diào)動學生學習的主觀能動性。實驗針對相應單元所學的內(nèi)容，能夠采取合適的數(shù)據(jù)結(jié)構和算法解決有關問題。實驗重點培養(yǎng)學生的動手能力。實習針對較為復雜的應用問題，能夠綜合運用所學的各種數(shù)據(jù)結(jié)構進行算法設計和實現(xiàn)，注重學生數(shù)據(jù)抽象能力和算法設計能力的培養(yǎng)。

三、本課程與其它課程的聯(lián)系和分工

本課程的先修課為程序設計基礎和離散數(shù)學，本課程可以c/c++或java語言作為算法描述和上機實踐的工具。同時，本課程又是軟件開發(fā)與設計等方面課程的基礎，如數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、軟件工程等課程。

四、本課程的考核方式

期末考試采用筆試形式，考試題型為：選擇、填空、判斷、應用題和算法設計題?？傇u成績由平時成績和期末成績組成，其中平時成績占30%--40%，期末考試占70%--60%。

課程實習的成績由平時成績和實習作業(yè)兩部分組成，其中平時成績占30%，實習作業(yè)占70%。

五、建議教材與教學參考書

建議教材：

1.嚴蔚敏，李冬梅，吳偉民．數(shù)據(jù)結(jié)構（c語言版）．北京：人民郵電出版社． 2.嚴蔚敏主編．數(shù)據(jù)結(jié)構（c語言版）．北京：清華大學出版社．

3.殷人昆主編．數(shù)據(jù)結(jié)構（用面向?qū)ο蠓椒ㄅcc++描述）．北京：清華大學出版社． 建議教學參考書：

1.[美]bruno 著，胡廣斌，王崧等譯．數(shù)據(jù)結(jié)構與算法－面向?qū)ο蟮腸++設計模式．北京：電子工業(yè)出版社．

2.殷人昆主編．數(shù)據(jù)結(jié)構與習題解析（用面向?qū)ο蠓椒ㄅcc++描述）．北京：清華大學出版社．

六、課程簡介

數(shù)據(jù)結(jié)構是一門專業(yè)基礎課，是學習其他軟件開發(fā)與設計等方面課程的基礎。主要內(nèi)容包括：線性表、棧和隊列、串、數(shù)組和廣義表、樹、圖、查找算法和排序算法。數(shù)據(jù)結(jié)構研究數(shù)據(jù)的組織方式，內(nèi)容豐富、學習量大，隱含在各部分內(nèi)容中的方法和技術多，旨在讓學生掌握計算機軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構的算法。要求學生掌握貫穿全課程的動態(tài)鏈表存儲結(jié)構，掌握算法設計的動態(tài)性和抽象性。要求學生學會分析研究計算機加工的數(shù)據(jù)對象的特征，以便在實際應用中選擇適當?shù)臄?shù)據(jù)結(jié)構、存儲結(jié)構和相應算法，初步掌握算法的時間與空間性能分析技巧，并培養(yǎng)復雜程序設計的技能。

執(zhí)筆人：

審核人：

教學院長：

院學術委員會：

院長：

數(shù)據(jù)結(jié)構課程實驗教學大綱 數(shù)據(jù)結(jié)構課程大綱篇三

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

課程編號：030816 適用專業(yè)：教育技術學 總學時數(shù)：64

學 分：4 編制單位：茂名學院理學院教育與信息技術系 編制時間：2008年6月20日

一、課程地位、性質(zhì)和任務

《數(shù)據(jù)結(jié)構與算法》課程是計算機相關學科專業(yè)的基礎課程中的一門重要的核心課程。通過本課程的教學，使學生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據(jù)問題設計和選擇好的算法，為學習后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設計應用程序打下基礎。

本課程以提高學生的計算機應用能力和綜合素質(zhì)為目標，通過課程教學，為學生構建數(shù)據(jù)結(jié)構與算法方面的知識體系，使學生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構，設計高效的算法，提高程序設計能力，另一方面，在工程應用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學生的程序設計能力。

二、與其他課程的關系

先修課：程序設計基礎、離散數(shù)學、計算機組成原理、計算機文化基礎

三、教學內(nèi)容、課時安排和基本要求

（一）教學部分 第1章 緒論（2學時）1.1什么是數(shù)據(jù)結(jié)構 1.2 基本概念和術語

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

1.4 算法和算法分析（算法及其設計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解

基本要求：

了解：抽象數(shù)據(jù)類型，算法設計方法與算法分析。

掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構、算法的基本概念；問題求解的方法與步驟 重點：數(shù)據(jù)結(jié)構和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標準和評價方法，最壞情況和平均情況的區(qū)分。

第2章 線性表（8學時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)

2.3 線性表的鏈式表示和實現(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表）2.4 一元多項式的表示及相加

基本要求：

了解：兩種存儲結(jié)構（順序存儲結(jié)構和鏈式存儲結(jié)構）及一元多項式的表示及相加。

掌握：要求熟練掌握處理線性表的各種算法。為后繼章節(jié)的學習打基礎。重點：各種算法。難點：鏈表的理解。

第3章 棧與隊列（4學時）

3.1 棧（定義，棧的表示和實現(xiàn)）

3.2 棧的應用舉例（數(shù)制轉(zhuǎn)換，括號匹配的檢驗，行編輯程序，迷宮求解，表達式求值）

3.3 棧與遞歸的實現(xiàn)

3.4 隊列及其實現(xiàn)（定義，鏈隊列，循環(huán)隊列）3.5 *離散事件模擬

教學要求：熟練掌握棧和隊列的特性和在不同存儲結(jié)構前提下的算法實現(xiàn)。棧和隊列是表最基本和重要的數(shù)據(jù)結(jié)構，是數(shù)據(jù)結(jié)構課程的基礎。

基本要求：

了解： 棧和隊列的定義及其實現(xiàn)。

掌握： 熟練掌握棧和隊列的特性和在不同存儲結(jié)構前提下的算法實現(xiàn)。重點： 棧和隊列的算法實現(xiàn)。難點： 棧和隊列的算法實現(xiàn)。

第4章 串（2學時）4.1 串類型的定義

4.2 串的表示和實現(xiàn)（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進算法）4.4 串操作應用舉例（文本編輯，建立詞索引表）

基本要求：

了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應用。

第5章 數(shù)組（2學時）5.1 數(shù)組的定義

5.2 數(shù)組的順序表示和實現(xiàn)

5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結(jié)構 5.6 m元多項式的表示

5.7 廣義表的遞歸算法（求廣義表的深度，復制廣義表，建立廣義表的存儲結(jié)構）

基本要求：

了解：了解作為抽象數(shù)據(jù)類型的數(shù)組和c語言的數(shù)組。認識到數(shù)組可以作為順序存儲結(jié)構用于順序表、字符串和稀疏矩陣的實現(xiàn)。也可以采用鏈式存儲結(jié)構。

掌握：掌握基本概念和算法。重點：算法。

難點：廣義表的遞歸算法。

第6章 樹與二叉樹（15學時）6.1 樹的定義和基本術語

6.2 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲結(jié)構）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）

6.4 樹和森林（樹的存儲結(jié)構，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷）6.5 樹與等價問題

6.6 赫夫曼樹及其應用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數(shù)

基本要求：

了解：理解樹與森林的定義與術語。

掌握：熟練掌握二叉樹性質(zhì)和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構造的方法和算法。重點： 樹的存儲結(jié)構和遍歷算法。難點：哈夫曼樹構造的方法和算法

第7章 圖（11學時）7.1 圖的定義和術語

7.2 圖的存儲結(jié)構（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索）

7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關節(jié)點和重連通分量）

7.5 有向無環(huán)圖及其應用（拓撲排序，關鍵路徑）

7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：

了解：圖的基本概念和相關術語。

掌握：圖的兩種主要存儲結(jié)構及遍歷算法。掌握最小生成樹、最短路徑和活動網(wǎng)算法的思想。

重點：圖的兩種主要存儲結(jié)構及遍歷算法。難點：圖的遍歷算法，最短路徑算法。

第8章 查找（8學時）

9.1 靜態(tài)查找表（順序表，有序表，靜態(tài)樹表，索引順序表）9.2 動態(tài)查找表（二叉排序樹和平衡二叉樹，b_樹和b+樹，鍵樹）9.3 哈希表（定義，構造方法，處理沖突的方法，查找及其分析）

基本要求：

了解： 各種查找法的基本概念及實現(xiàn)的基本思想。

掌握：熟練掌握搜索結(jié)構的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現(xiàn)。難點：哈希表查找算法。

第9章 內(nèi)部排序（8學時）10.1 概述

10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序

10.6 基數(shù)排序（多關鍵字，鏈式）10.7 排序算法分析

基本要求：

了解：基數(shù)排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內(nèi)部排序算法

難點：基數(shù)排序（多關鍵字，鏈式）

第10章 *外部排序（2學時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現(xiàn) 11.4 置換-選擇排序 11.5 最佳歸并樹

基本要求：

了解：外部排序的基本概念和相關術語。

掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現(xiàn) 第11章 算法設計的一般方法（2學時）

1．重點

（1）有效算法的概念，問題固有難度的概念；

（2）遞歸法；分治法；平衡原則；貪心法；動態(tài)規(guī)劃的基本原理；（3）搜索-回溯法的基本原理和本質(zhì).2．難點

（1）問題固有難度的概念；

（2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。

（二）實驗、實習部分

課程安排五個類別的實驗，實驗時數(shù)為12課時，其中： 實驗

一、線性鏈表及運算 2課時 實驗

二、棧和隊列 2課時 實驗

三、樹和二叉樹 4課時 實驗

四、圖及其應用 2課時 實驗

五、查找與排序 2課時

四、課程考核方式

閉卷考試70%、平時作業(yè)與實驗30%

五、建議教材和教學參考書 參考教材：

1、《數(shù)據(jù)結(jié)構》（c語言描述）高等教育出版社 耿國華主編

2、《數(shù)據(jù)結(jié)構》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

3、《數(shù)據(jù)結(jié)構題集》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

4、《數(shù)據(jù)結(jié)構》算法實現(xiàn)及解析（第二版）西安電子科技大學出版社 高一凡

六、說明

1、因課時安排少，教學內(nèi)容多。建議采用多媒體教學。

2、由于本課程內(nèi)容較多，在實際教學中可根據(jù)大綱內(nèi)容，進行適當調(diào)整。

數(shù)據(jù)結(jié)構課程實驗教學大綱 數(shù)據(jù)結(jié)構課程大綱篇四

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

一、課程基本概況

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

課程名稱（英文）： data structures

課程編號：b09042

課程總學時：60（其中，講課48，實驗12）

課程學分：3

課程分類：專業(yè)選修課

開設學期：4

適用專業(yè)：計算機網(wǎng)絡工程本科

先修課程：集合論，圖論，高級語言（結(jié)構或記錄，指針）

后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等

二、課程的性質(zhì)、目的和任務

數(shù)據(jù)結(jié)構是計算機專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學中占有十分重要的地位，是一門理論性非常強的課程。通過課堂教學、課外練習和上機實習，使學生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力以及培養(yǎng)良好的程序設計技能，為后續(xù)課程的學習和科研工作的參與打下良好的基礎。

三、主要內(nèi)容、重點及深度

本門課程共60學時，其中理論教學48學時，實驗教學12學時。其中，理論教學部分：

第一章

緒論

（一）目的要求

了解數(shù)據(jù)結(jié)構的意義與發(fā)展過程、數(shù)據(jù)結(jié)構在計算機科學中的作用、學習本課程的目的、任務及要求。理解數(shù)據(jù)結(jié)構的基本概念；算法設計；掌握算法的時間和空間復雜度。

（二）教學內(nèi)容 本章知識點：

1.相關的基本概念(掌握)；

2.算法五大要素(掌握)；

3.計算語句頻度和估算算法時間復雜度的方法（掌握）。

（三）重點與難點

重點：數(shù)據(jù)結(jié)構的定義；算法的描述方法。

難點：數(shù)據(jù)結(jié)構的定義；算法與程序的區(qū)別；時間復雜度及其計算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結(jié)構；線性表的存儲結(jié)構及操作的實現(xiàn)；理解一元多項式的表示；

（二）教學內(nèi)容 本章知識點：

1.線性表的邏輯結(jié)構(掌握)；2.線性表的存儲結(jié)構(掌握)；

3.線性表在順序結(jié)構和鏈式結(jié)構上實現(xiàn)基本操作的方法(掌握)；

4.從時間和空間復雜度的角度比較線性表兩種存儲結(jié)構的不同特點及其適用場合(掌握)。

（三）重點與難點

重點：線性表的概念；線性表的順序存儲結(jié)構、鏈式存儲結(jié)構及其常用算法。難點：鏈式存儲結(jié)構及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊列

（一）目的要求

掌握棧的定義，表示及實現(xiàn)；表達式求值；棧與遞歸過程；隊列的定義、表示及實現(xiàn)。

（二）教學內(nèi)容 本章知識點： 1.棧和隊列的特點(掌握)；

2.在兩種存儲結(jié)構上棧的基本操作的實現(xiàn)(掌握)； 3.循環(huán)隊列和鏈隊列的基本運算(熟練掌握)； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程(掌握)。

（三）重點與難點

重點：堆棧和隊列的概念；遞歸的定義；循環(huán)隊列和鏈隊列的基本運算。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運算。

第四章 串

（一）目的要求

了解串的邏輯結(jié)構，存儲結(jié)構；掌握串操作的實現(xiàn)(重點難點bf和kmp算法)串的應用。

（二）教學內(nèi)容 本章知識點：

1.串的七種基本運算的定義（了解）；

2.利用這些基本運算來實現(xiàn)串的其它各種運算的方法(掌握)； 3.在順序存儲結(jié)構上實現(xiàn)串的各種操作的方法(掌握)；

算法，熟悉next函數(shù)和改進next函數(shù)的定義和計算(掌握)； 5.串名的存儲映象和在堆存儲結(jié)構實現(xiàn)串操作的方法(理解)。

（三）重點與難點 重點：串定義和存儲方法；串的操作 難點：串操作實現(xiàn)方法

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

（一）目的要求

掌握數(shù)組的存儲結(jié)構；稀疏矩陣的表示及操作的實現(xiàn)；廣義表的定義和存儲結(jié)構；廣義表的遞歸算法。

（二）教學內(nèi)容 本章知識點：1.數(shù)組在以行為主的存儲結(jié)構中的地址計算方法(掌握)； 2.矩陣實現(xiàn)壓縮存儲時的下標變換(掌握)；

3.理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領會以三元組表示稀疏矩陣時進行運算采用的處理方法(掌握)；

4.廣義表的定義及其存儲結(jié)構，學會廣義表的表頭，表尾分析方法(掌握)； 5.學習編制廣義表的遞歸算法(掌握)。

（三）重點與難點

重點：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示；廣義表的存儲定義、操作。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質(zhì)和存儲結(jié)構；遍歷二叉樹和線索二叉樹；理解樹的存儲結(jié)構和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應用；

（二）教學內(nèi)容 本章知識點： 1.二叉樹的結(jié)構特點(理解)；

2.二叉樹的各種存儲結(jié)構的特點及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結(jié)點的前驅(qū)和后繼的方法(掌握)； 5.樹的各種存儲結(jié)構及其特點(掌握)； 6.編寫樹的各種運算的算法(掌握)；

7.建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)。

（三）重點與難點 重點：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構造二叉排序樹。難點：二叉樹的遍歷方式；二叉排序樹的構造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲結(jié)構；掌握圖的遍歷及應用{最小生成樹，最短路徑等}；拓撲排序和關鍵路徑。

（二）教學內(nèi)容 本章知識點： 1.熟悉圖的各種存儲結(jié)構；

2.了解實際問題與采用何種存儲結(jié)構和算法有密切聯(lián)系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)；

4.應用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓撲排序、關鍵路徑等）(掌握)。

（三）重點與難點

重點：圖的存儲結(jié)構；圖的遍歷 難點：圖遍歷的算法；

第八章

動態(tài)存儲管理

（一）目的要求

了解邊界標識法和伙伴系統(tǒng)；無用單元收集和緊縮；

（二）教學內(nèi)容 本章知識點：

1.存儲器分配策略和算法（了解）；

2.無用單元收集時的標志算法（了解）。

（三）重點與難點

存儲器分配策略和算法、無用單元收集時的標志算法

第九章

查找

（一）目的要求

了解靜態(tài)查找表(順序表，有序表，索引順序表)；動態(tài)查找表(二叉排序樹，平衡二叉樹，b-樹和b+樹)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教學內(nèi)容 本章知識點：

1.順序查找、折半查找和索引查找的方法、應用(掌握)；

2.二叉排序樹的構造方法(掌握)；

3.二叉平衡樹的建立方法(掌握)；

4.b-樹，b+樹和鍵樹的特點以及它們的建立過程（理解）；

5.哈希表的構造方法(掌握)；

6.按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度；

7.哈希表在查找不成功時的平均查找長度的計算方法(掌握)。

（三）重點與難點

重點：二叉排序樹的構造方法、二叉平衡樹的建立方法；哈希表的構造、應用；

難點：二叉排序樹的構造及應用；哈希表的構造方法；查找的平均長度。

第十章

內(nèi)部排序

（一）目的要求

掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數(shù)排序等算法。

（二）教學內(nèi)容 本章知識點：

1.各種排序方法的特點并能靈活應用(掌握)； 2.各種方法的排序過程(掌握)；

3.各種排序方法的時間復雜度分析(掌握)。

（三）重點與難點

重點：各種排序方法的特點及其應用；實現(xiàn)排序的各種算法。難點：各種排序算法的時間復雜度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實現(xiàn)；置換--選擇排序；最佳歸并樹。

（二）教學內(nèi)容 本章知識點：

1.外部排序的兩個過程(理解)；

2.外排過程中所需進行外存讀/寫次數(shù)的計算方法(掌握)；

3.敗者樹的建立過程(掌握)；

4.實現(xiàn)多路歸并的算法(掌握)；

5.置換-選擇排序的過程(掌握)；

6.最佳歸并樹的構造方法（熟悉）；

7.按最佳歸并樹的歸并方案進行平衡歸并時，外存讀/寫次數(shù)的計算方法(掌握)。

（三）重點與難點

重點：外部排序過程和實現(xiàn)方法；多路并歸算法及其實現(xiàn)； 難點：最佳并歸樹的構造方法及其應用。

實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。

實驗一

停車場管理系統(tǒng)

（一）實驗內(nèi)容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。棧以順序結(jié)構實現(xiàn)，隊列以鏈表結(jié)構實現(xiàn)。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容。

（三）實驗教學基本要求

通過實例，使學生掌握棧和隊列兩種特殊的線性結(jié)構，掌握棧和隊列的特點。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 4學時

實驗二

教學計劃編制問題

（一）實驗內(nèi)容

假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。編制一個教學計劃程序。

（二）實驗過程編程實現(xiàn)實驗內(nèi)容。

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結(jié)構的特性，掌握如何應用圖結(jié)構解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗三

最小生成樹問題

（一）實驗內(nèi)容

利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權值。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結(jié)構的特性，掌握如何應用圖結(jié)構解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗四

哈希表設計

（一）實驗內(nèi)容

假設人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構造，用偽隨機探測再散列法處理沖突。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容

（三）實驗教學基本要求 掌握索引技術的使用。

（四）實驗設備和材料 計算機

（五）實驗學時 4學時

五、課程教學的基本要求和主要環(huán)節(jié)

本課程可采用課堂講授、課堂討論、習題課等進行課堂教學;條件允許可采用cai、電子教案、幻燈片、參觀等進行輔助教學;每章布置3~6道習題以鞏固教學;在課程后半程，安排3~4個上機實驗，讓學生應用數(shù)據(jù)結(jié)構的理論、方法，分組設計幾個較大的軟件，使理論與實際相結(jié)合。

考試采用閉卷方式?？偝煽冇善綍r成績和考試成績組成。平時成績占30%，考試成績占70%。

六、本課程與其它課程的聯(lián)系與分工

先修課包括：集合論，圖論，高級語言（結(jié)構或記錄，指針）；

后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。

七、建議教材與參考教材

《數(shù)據(jù)結(jié)構》（c語言版）

嚴蔚敏等

清華大學出版社

1997 《數(shù)據(jù)結(jié)構題集》

嚴蔚敏等

清華大學出版社

1999

《數(shù)據(jù)結(jié)構習題與解析》

李春葆

清華大學出版社

2004

八、負責人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領導：

數(shù)據(jù)結(jié)構課程實驗教學大綱 數(shù)據(jù)結(jié)構課程大綱篇五

《數(shù)據(jù)結(jié)構》課程教學大綱

data structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號：

2.課程性質(zhì)/類別： 必修課 / 專業(yè)主干課

3.學時/學分： 48 學時（另實驗16學時）/ 4 學分

4.適用專業(yè)：計算機科學與技術、軟件工程、網(wǎng)絡工程、信息管理與信息系統(tǒng)等專業(yè)

二、課程教學目標及學生應達到的能力

數(shù)據(jù)結(jié)構課程是計算機相關專業(yè)的專業(yè)基礎課、必修課程，主要介紹用計算機解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構的方法以及在各種結(jié)構上執(zhí)行操作的算法。通過本課程的學習，要求學生掌握各種數(shù)據(jù)結(jié)構的特點、存儲表示、運算方法以及在計算機科學中最基本的應用，培養(yǎng)、訓練學生選用合適的數(shù)據(jù)結(jié)構和編寫質(zhì)量高、風格好的應用程序的能力，培養(yǎng)學生分析問題、解決問題的能力，并為后續(xù)課程的學習打下良好的理論基礎和實踐基礎。

三、課程教學內(nèi)容與基本要求

（一）緒論（3 學時）1．主要內(nèi)容：

（1）介紹什么是數(shù)據(jù)結(jié)構；

（2）基本概念和術語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構的定義、邏輯結(jié)構、物理結(jié)構（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；

（3）抽象數(shù)據(jù)類型的表示與實現(xiàn)；

（4）算法和算法分析: 算法的概念、算法設計的要求以及算法效率的度量。2．基本要求

（1）了解學習數(shù)據(jù)結(jié)構的重要性；

（2）掌握數(shù)據(jù)結(jié)構的定義及相關概念和術語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)方法；（4）理解算法的概念、特點并掌握度量其效率的基本方法。3．自學內(nèi)容：

類c語言的書寫規(guī)范。

（二）線性表（6 學時）1．主要內(nèi)容：

（1）線性表的抽象數(shù)據(jù)類型定義和相關概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實現(xiàn)；（3）線性表的鏈式存儲表示和基本操作的實現(xiàn)；

（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。2．基本要求

（1）掌握線性表的定義和特點；

（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現(xiàn)算法；

（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實現(xiàn)算法。

3．自學內(nèi)容：

靜態(tài)鏈表。

（三）棧和隊列（5 學時）1．主要內(nèi)容：

（1）棧和隊列的結(jié)構特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實現(xiàn)；（3）棧和隊列的鏈式存儲表示和實現(xiàn)；（4）棧和隊列在程序設計中的應用。2．基本要求

（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點；

（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿?？盏臈l件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關系。3．自學內(nèi)容：

鏈棧，離散事件模擬

（四）串（3 學時）1．主要內(nèi)容：

（1）串的抽象數(shù)據(jù)類型定義；

（2）串的表示和實現(xiàn): 定長順序存儲結(jié)構和堆分配存儲結(jié)構；（3）串的各種基本操作的實現(xiàn)及其應用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定義，并能利用基本操作實現(xiàn)串的其它操作；（2）掌握串的定長順序存儲結(jié)構以及基本操作的實現(xiàn)；（3）掌握串的堆分配存儲結(jié)構以及基本操作的實現(xiàn)；（4）掌握串的簡單模式匹配算法，理解kmp算法。3．自學內(nèi)容：

串操作的應用實例。

（五）數(shù)組和廣義表（4 學時）1．主要內(nèi)容：

（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構。2．基本要求

（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構中的地址計算方法；（2）掌握對特殊矩陣進行壓縮存儲時的下標變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲結(jié)構下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲結(jié)構；

（4）掌握廣義表的結(jié)構特點、取表頭表尾操作，及其存儲表示方法。3．自學內(nèi)容：

采用十字鏈表存儲結(jié)構創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學時）1．主要內(nèi)容：

（1）樹的抽象數(shù)據(jù)類型定義和基本術語；

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲結(jié)構；（3）二叉樹的遍歷；

（4）線索二叉樹的定義、遍歷及線索化二叉樹；

（5）樹的存儲結(jié)構、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）huffman樹及其應用。2．基本要求

（1）掌握樹型結(jié)構的特點和基本術語；

（2）熟練掌握二叉樹的性質(zhì)，了解相應的證明方法；

（3）了解二叉樹的順序存儲結(jié)構和鏈式存儲結(jié)構，熟練掌握二叉鏈表存儲結(jié)構；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點的前驅(qū)與后繼的方法；

（6）熟悉樹的各種存儲結(jié)構及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解huffman樹的特性，掌握建立huffman樹和huffman編碼的方法。3．自學內(nèi)容：

先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（9 學時）1．主要內(nèi)容：（1）圖的定義和術語；

（2）圖的四種存儲結(jié)構：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；

（5）有向無環(huán)圖及其應用：拓撲排序和關鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術語；

（2）了解圖的存儲結(jié)構，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權圖的最小生成樹求解算法；

（5）了解有向無環(huán)圖、aov網(wǎng)、aoe網(wǎng)及其在實際中的應用，熟悉拓撲排序算法和關鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學內(nèi)容：

樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。

（八）查找（4 學時）1．主要內(nèi)容：

（1）查找的基本概念和相關術語；

（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相關術語；

（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構造和查找方法；

（4）熟練掌握哈希表的構造方法，特別是哈希函數(shù)和處理沖突方法的選取；（5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學內(nèi)容：

平衡二叉樹。

（九）內(nèi)部排序（4 學時）1．主要內(nèi)容：

（1）排序的基本概念和相關術語；

（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈式基數(shù)排序；（7）各種內(nèi)部排序方法的比較討論。2．基本要求

（1）了解排序作用，熟悉相關術語；

（2）掌握多種排序的基本思想、算法特點和排序過程，分析它們的時間復雜度、空間復雜度和穩(wěn)定性。

3．自學內(nèi)容：

二路插入排序、表插入排序和樹形選擇排序。

四、教學安排建議

1.作業(yè)練習 完成每章的教學后進行布置習題，使用教材配套的《數(shù)據(jù)結(jié)構題集（c語言版）》。盡量選擇基礎的并且加注了標記的題，應注重于精，而不要求多。要求積極獨立完成所布置的習題，建議安排至少六次。

2.案例分析

可參考選擇以下一些案例：（1）學生通訊錄管理系統(tǒng)，（2）表達式求值問題（3）交通咨詢系統(tǒng)，等。3.專題研討

可參考選擇以下一些：（1）最小生成樹問題（2）航班信息查詢與檢索系統(tǒng)，（3）內(nèi)部排序算法比較，等。

4.實驗安排

為了達到理論與實際應用的結(jié)合，讓學生能將所學知識應用于實際問題的求解中，培養(yǎng)學生的實際動手能力，從而加深對概念及所學知識的理解，靈活、牢固掌握教材內(nèi)容，提高程序設計及解決實際問題的能力，實驗環(huán)節(jié)的安排非常重要。

建議實驗安排為八次，共16學時，分別如下：

實驗1 線性表的順序存儲結(jié)構的實現(xiàn)(2學時)

實驗2 線性表的鏈式存儲結(jié)構的實現(xiàn)(2學時)

實驗3 棧的算法實現(xiàn)(2學時)

實驗4 隊列的算法實現(xiàn)(2學時)

實驗5 串類型及操作(2學時)

實驗6 二叉樹的建立與遍歷(2學時)

實驗7 圖的建立與遍歷(2學時)

實驗8 查找與排序(2學時)注：教師可根據(jù)教學實際情況（如：學生情況及學時情況等），適當調(diào)整實踐教學內(nèi)容及學時分配。

五、課程考核

1.考核形式及成績評定辦法

本課程考核形式為：平時成績占40%，期末考試成績占60%。其中平時成績的結(jié)構分包括：課堂表現(xiàn)10%、平時作業(yè)10%和實驗20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。

2.本課程考核的基本要求

課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達到本課程教學時數(shù)的1/3，則取消考試資格。

平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進行評定。

實驗20%：根據(jù)各次實驗完成情況及實驗報告成績進行評定。

期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點。

六、本課程與其它課程的先行后續(xù)關系

先行課程：《高級程序設計語言》、《離散數(shù)學》

后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設計》等

七、建議教材及教學參考書

1.教材：

嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構（c語言版）》，清華大學出版，2012.5 嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構題集（c語言版）》，清華大學出版，2012.5 2.參考書：

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構簡明教程》，清華大學出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構與算法》，機械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構》（c語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構》，西安電子科技大學出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構》，大連理工大學出版社，1989

[7] aho a v, hopcroft j e, ullman j structures and n-wesley publishing company,inc.,1983

[8] baron r j, shapiro l structures and their nostrand reinhold company, 1980

[9] esakov j, weiss structures: an advanced approach using ce-hall, inc.,1989

[10] [美]s巴斯《計算機算法：設計和分析引論》朱洪等譯，復旦大學出版社，1985