第一篇：《數據結構》課程教學大綱

《數據結構》課程教學大綱

Data Structure 執筆人：

編寫日期：

一、課程基本信息

1.課程編號：

2.課程性質/類別： 必修課 / 專業主干課

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

4.適用專業：計算機科學與技術、軟件工程、網絡工程、信息管理與信息系統等專業

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

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

三、課程教學內容與基本要求

（一）緒論（3 學時）1．主要內容：

（1）介紹什么是數據結構；

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

（3）抽象數據類型的表示與實現；

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

（1）了解學習數據結構的重要性；

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

類C語言的書寫規范。

（二）線性表（6 學時）1．主要內容：

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

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

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

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

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

3．自學內容：

靜態鏈表。

（三）棧和隊列（5 學時）1．主要內容：

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

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

（2）掌握棧的兩種存儲表示和實現，特別注意棧滿棧空的條件；（3）掌握隊列的兩種存儲表示和實現，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關系。3．自學內容：

鏈棧，離散事件模擬

（四）串（3 學時）1．主要內容：

（1）串的抽象數據類型定義；

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

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

串操作的應用實例。

（五）數組和廣義表（4 學時）1．主要內容：

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

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

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

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

采用十字鏈表存儲結構創建稀疏矩陣。

（六）樹和二叉樹（10 學時）1．主要內容：

（1）樹的抽象數據類型定義和基本術語；

（2）二叉樹的抽象數據類型定義、性質和存儲結構；（3）二叉樹的遍歷；

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

（5）樹的存儲結構、樹和森林的遍歷以及與二叉樹的轉換；（6）Huffman樹及其應用。2．基本要求

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

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

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

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

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

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

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

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

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

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

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

（5）了解有向無環圖、AOV網、AOE網及其在實際中的應用，熟悉拓撲排序算法和關鍵路徑算法；

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

樹的先根遍歷算法與圖的深度優先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優先遍歷算法比較。

（八）查找（4 學時）1．主要內容：

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

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

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

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

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

平衡二叉樹。

（九）內部排序（4 學時）1．主要內容：

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

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

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

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

3．自學內容：

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

四、教學安排建議

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

2.案例分析

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

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

4.實驗安排

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

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

實驗1 線性表的順序存儲結構的實現(2學時)

實驗2 線性表的鏈式存儲結構的實現(2學時)

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

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

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

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

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

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

五、課程考核

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

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

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

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

平時作業10%：根據上交次數及完成情況進行評定。

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

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

六、本課程與其它課程的先行后續關系

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

后續課程：《操作系統》、《編譯原理》、《數據庫理論》、《算法分析與設計》等

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

1.教材：

嚴蔚敏，吳偉民編著，《數據結構（C語言版）》，清華大學出版，2012.5 嚴蔚敏，吳偉民編著，《數據結構題集（C語言版）》，清華大學出版，2012.5 2.參考書：

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

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

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

第二篇：數據結構課程教學大綱

數據結構課程教學大綱

一、課程基本概況

課程名稱：數據結構

課程名稱（英文）： Data Structures

課程編號：B09042

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

課程學分：3

課程分類：專業選修課

開設學期：4

適用專業：計算機網絡工程本科

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

后續課程：數據庫，編譯原理，操作系統等

二、課程的性質、目的和任務

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

三、主要內容、重點及深度

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

第一章

緒論

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

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

（三）重點與難點

重點：數據結構的定義；算法的描述方法。

難點：數據結構的定義；算法與程序的區別；時間復雜度及其計算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結構；線性表的存儲結構及操作的實現；理解一元多項式的表示；

（二）教學內容 本章知識點：

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

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

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

（三）重點與難點

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

第三章 棧和隊列

（一）目的要求

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

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

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

（三）重點與難點

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

第四章 串

（一）目的要求

了解串的邏輯結構，存儲結構；掌握串操作的實現(重點難點BF和KMP算法)串的應用。

（二）教學內容 本章知識點：

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

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

4.KMP算法，熟悉NEXT函數和改進NEXT函數的定義和計算(掌握)； 5.串名的存儲映象和在堆存儲結構實現串操作的方法(理解)。

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

第五章 數組和廣義表

（一）目的要求

掌握數組的存儲結構；稀疏矩陣的表示及操作的實現；廣義表的定義和存儲結構；廣義表的遞歸算法。

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

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

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

（三）重點與難點

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

第六章 樹和二叉樹

（一）目的要求

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

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

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

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

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

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

第七章 圖

（一）目的要求

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

（二）教學內容 本章知識點： 1.熟悉圖的各種存儲結構；

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

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

（三）重點與難點

重點：圖的存儲結構；圖的遍歷 難點：圖遍歷的算法；

第八章

動態存儲管理

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

（三）重點與難點

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

第九章

查找

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

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

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

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

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

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

（三）重點與難點

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

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

第十章

內部排序

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

（三）重點與難點

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

十一章

外部排序

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

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

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

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

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

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

（三）重點與難點

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

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

實驗一

停車場管理系統

（一）實驗內容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。棧以順序結構實現，隊列以鏈表結構實現。

（二）實驗過程 編程實現實驗內容。

（三）實驗教學基本要求

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

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

（五）實驗學時 4學時

實驗二

教學計劃編制問題

（一）實驗內容

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

（二）實驗過程編程實現實驗內容。

（三）實驗教學基本要求

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

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

（五）實驗學時 2學時

實驗三

最小生成樹問題

（一）實驗內容

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

（二）實驗過程 編程實現實驗內容

（三）實驗教學基本要求

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

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

（五）實驗學時 2學時

實驗四

哈希表設計

（一）實驗內容

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

（二）實驗過程 編程實現實驗內容

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

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

（五）實驗學時 4學時

五、課程教學的基本要求和主要環節

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

考試采用閉卷方式。總成績由平時成績和考試成績組成。平時成績占30%，考試成績占70%。

六、本課程與其它課程的聯系與分工

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

后續課包括：數據庫，編譯原理，操作系統等。

七、建議教材與參考教材

《數據結構》（C語言版）

嚴蔚敏等

清華大學出版社

1997 《數據結構題集》

嚴蔚敏等

清華大學出版社

1999

《數據結構習題與解析》

李春葆

清華大學出版社

2004

八、負責人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領導：

第三篇：《數據結構 A》課程教學大綱

《數據結構 A》課程教學大綱

Data Structure A

課程代碼：

適用專業：信息計算、信息安全 總學時數：72

編寫年月：2003年7月

執

筆：高學軍、劉科峰、李小英



一、課程的性質和目的

數據結構是信息與計算科學專業的一門重要專業基礎課程。當用計算機來解決實際問題時，就要涉及到數據的表示及數據的處理，而數據表示及數據處理正是數據結構課程的主要研究對象，通過這兩方面內容的學習，為后續課程，特別是軟件方面的課程打下了厚實的知識基礎，同時也提供了必要的技能訓練。因此，數據結構課程在信息與計算科學專業中具有舉足輕重的作用。

課程性質：專業基礎理論課/必修 開課學期：5 總學分數：4.5 修訂年月：2007年7月

二、課程教學內容及學時分配

第1章 緒論（4學時）

理解數據、數據元素和數據項的概念及其相互間的關系。理解數據結構的邏輯結構、存儲結構的聯系與區別，以及在數據結構上施加的運算及其實現。掌握簡單的算法分析方法。

本章知識點為：數據、數據元素、數據對象、數據結構、存儲結構和數據類型等概念術語的確定含義；抽象數據類型的定義、表示和實現方法；描述算法的類C語言；算法設計的基本要求以及從時間和空間角度分析算法的方法。

第2章 線性表（10學時，2個學時實驗上機）

理解線性表的定義及其運算。理解順序表和鏈表的定義、組織形式、結構特征和類型說明，掌握在這兩種表上實現的插入、刪除和按值查找的算法。了解循環鏈表、雙向(循環)鏈表的結構特點和在其上施加的插入、刪除等操作。掌握稀疏多項式在線性表的兩種存儲結構上的實現方法。

本章知識點為：線性表的邏輯結構定義、抽象數據類型定義和各種存儲結構的描述方法；在線性表的兩類存儲結構(順序的和鏈式的)上實現基本操作；稀疏多項式的抽象數據類型定義、表示和加法的實現。

第3章 棧和隊列（6學時，2個學時實驗上機）

理解棧和隊列的定義、特征及在其上所定義的基本運算。掌握在兩種存儲結構上對棧和隊列所施加的基本運算的實現。熟練掌握循環隊列和鏈隊列的基本操作實現算法，尤其是隊滿和隊空的描述方法。

本章知識點為：抽象數據類型棧的定義；棧的表示和實現；棧的應用；抽象數據類型隊列的定義；鏈隊列；循環隊列。第4章 串（4學時，2個學時實驗上機）

熟悉串的七種基本操作的定義，并能利用這些基本操作來實現串的其它各種操作的方法。熟練掌握在串的定長順序存儲結構上實現串的各種操作的方法。掌握串的堆存儲結構以及在其上實現串操作的基本方法。

本章知識點為：串的數據類型定義；串的三種存儲表示：定長順序存儲結構、塊鏈存儲結構和堆分配存儲結構；串的各種基本操作的實現及其應用；

第5章 數組和廣義表（6學時，2個學時實驗上機）

了解數組的兩種存儲表示方法，并掌握數組在以行為主的存儲結構中的地址計算方法。掌握對特殊矩陣進行壓縮存儲時的下標變換公式。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，領會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法。掌握廣義表的結構特點及其存儲表示方法。

本章知識點為：數組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲方法及運算的實現；廣義表的邏輯結構和存儲結構和廣義表的操作。

第6章 樹和二叉樹（12學時，2個學時實驗上機）

深刻理解樹的定義、性質及其存儲方法，熟練掌握二叉樹的二叉鏈表存儲方式、結點結構和類型定義，并能畫出給定二叉樹的二叉鏈表的結構示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會完成樹、森林與二叉樹間的相互轉換；理解哈夫曼樹的構造方法，并能對給定的數據集合構造出哈夫曼樹。

本章知識點為：二叉樹的定義、性質和存儲結構；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲結構、與二叉樹的轉換、遍歷；樹的多種應用。

第7章 圖（12學時，2個學時實驗上機）

理解圖的基本概念及術語，掌握圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優先搜索遍歷和廣度優先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結構上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構造最小生成樹；了解并掌握拓撲排序、關鍵路徑、最短路徑的算法思想。

本章知識點為：圖的定義和術語；圖的四種存儲結構：數組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優先搜索和廣度優先搜索；圖的連通性：連通分量和最小生成樹；拓撲排序和關鍵路徑；兩類求最短路徑問題的解法。

第8章 查找（10學時，2個學時實驗上機）

了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應的平均查找長度。

本章知識點為：討論查找表(包括靜態查找表和動態查找表)的各種實現方法：順序表、有序表、樹表和哈希表；平均查找長度的討論。

第9章 內部排序（8學時，2個學時實驗上機）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數排序的基本思想、步驟及算法。

本章知識點為：討論比較各種內部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數排序的基本思想、算法特點、排序過程以及它們的時間復雜度分析。在每類排序方法中，又從簡單方法入手，重點討論性能先進的高效方法。

三、課程教學的基本要求

本課程是信息與計算科學專業的重要專業基礎課，計算機科學各領域及有關的系統和應用軟件都要用到各種數據結構。在教學方法上采用課堂講授，課后自學，課堂討論等教學形式。

(一)課堂講授

本課程屬于基礎理論課程。在傳授知識原理的前提下，配合實際應用例子，由淺入深善于誘導，使學生從被動吸收知識的狀態下，轉化到主動索取知識的狀態中來，并采用多媒體輔助教學，加大課堂授課的知識含量。注重培養學生的學習興趣，提高學生的基本素質。

（二）課后自學

為了培養學生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內容，課上教師只給出自學提綱，不作詳細講解，課后學生自學。

（三）課堂討論

課堂討論的目的是活躍學習氣氛，開拓思路。教師應認真組織，安排重點發言，充分調動每一名同學的學習積極性，做好總結。

（四）課外作業

為了讓學生鞏固所學的知識，每章都布置一定數量課外作業。

（五）實驗

用C語言或C++語言完成一些算法設計題。培養學生的算法設計能力和程序設計能力。總評成績：平時作業占30%，閉卷考試占70%。

四、本課程與其它課程的聯系與分工

先修課程：離散數學，C++面向對象程序設計等。后續課程：操作系統，數據庫原理等。

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

[1] 嚴蔚敏 吳偉民編著，數據結構(C語言版)，北京:清華大學出版社, 2004 [2] 嚴蔚敏 吳偉民編著，數據結構題集(C語言版)，北京:清華大學出社，2004 [3] Willan Ford,Willian Topp.Data Structures with C++.New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company，1996(數據結構——C++語言描述.北京:清華大學出版社，1997)

[4] 徐孝凱，數據結構實用教程（C/C++描述），北京:清華大學出版社，1999 [5] 陳慧南.數據結構（使用C++語言描述），南京:東南大學出版社，2001 [6] 殷人昆,陶永雷,謝若陽等.數據結構（用面向對象方法與C++描述），北京:清華大學出版社，1999

第四篇：數據結構與算法課程教學大綱

教學大綱

數據結構與算法（Data Structures）

計算機技術已成為現代化發展的重要支柱和標志，并逐步滲透到人類生活的各個領域。隨著計算機硬件的發展，對計算機軟件的發展也提出了越來越高的要求。由于軟件的核心是算法，而算法實際上是對加工數據過程的描述，所以研究數據結構對提高編程能力和設計高性能的算法是至關重要的。

非數值計算問題的數學模型不再是傳統的數學方程問題，而是諸如表、樹、圖之類的數據結構。因此，簡單地說，數據結構是一門研究非數值計算的程序設計問題的學科，主要研究數據的邏輯結構、存儲結構和算法。

一、教學目的與要求---了解數據的邏輯結構和物理結構；

教學要求在每章教學內容給出，大體上為三個層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學會所學知識，熟練掌握就是運用所學知識解決實際問題。

教學目的為：了解算法對于程序設計的重要性 ； 學習掌握基本數據結構的描述與實現方法，熟練掌握典型數據結構及其應用算法的設計。了解算法分析方法。

二、教學重點與難點--數據結構中基本概念和術語，算法描述和分析方法。

1、鏈表插入、刪除運算的算法。算法時間復雜度

2、后綴表達式的算法，數制的換算

利用本章的基本知識設計相關的應用問題

3、循環隊列的特點及判斷溢出的條件

利用隊列的特點設計相關的應用問題

4、串的模式匹配運算算法

5、二叉樹遍歷算法的設計

利用二叉樹遍歷算法，解決簡單應用問題 哈夫曼樹的算法

6、圖的遍歷

最小生成樹

最短路徑

7、二叉排序樹查找

平衡樹二叉樹

8、堆排序

快速排序 歸并排序

三、教學方法與手段-充分利用多媒體教學工具，配合黑板上的教學內容較難部分的算法實現過程演義

四、教學內容、目標與學時分配

教學內容 教學目標 課時分配

1、緒論

數據結構的內容

邏輯結構與存儲結構

算法和算法分析

2、線性表

線性表的定義與運算

線性表的順序存儲

線性表的鏈式存儲

3、棧

棧的定義與運算

棧存儲和實現

棧的應用舉例

4、隊列

隊列的定義與基本運算

隊列的存儲與實現

隊列的應用舉例

5、串

串的定義與基本運算

串的表示與實現

串的基本運算

6、樹和二叉樹

樹的定義和術語

二叉樹樹的基本概念和術語 遍歷二叉數和線索二叉樹

二叉樹的轉換

二叉樹的應用

哈夫曼樹及其應用

7、圖

圖的定義和術語

圖的存儲結構

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態查找 動態查找

哈希表

了解

了解

掌握

熟練掌握順序表存儲地址的計算

掌握單鏈表的結構特點和基本運算

掌握雙鏈表的結構特點和基本運算

掌握棧的定義與運算

掌握棧的存儲與實現

熟練掌握棧的各種實際應用

掌握隊列的定義與基本運算

熟練掌握隊列的存儲與實現

掌握循環隊列的特征和基本運算

了解串的邏輯結構

掌握串的存儲結構

熟練掌握串的基本運算

了解

了解二叉樹

熟練掌握二叉樹定義和存儲結構

了解二叉樹的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

了解

熟練掌握

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學時

1學時

1學時

2學時

8學時

2學時

2學時

4學時

8學時

2學時

2學時

4學時

6學時

2學時

2學時

2學時

6學時

2學時

2學時

2學時

12學時

2學時

2學時

2學時

2學時

2學時

2學時

8學時

2學時

2學時

2學時

2學時

8學時

4學時

2學時

2學時

9、排序

12學時 插入排序

熟練掌握基本思想

3學時 快速排序

了解各種內部排序方法和特點

3學時 選擇排序

掌握

2學時 各種排序方法比較

掌握

2學時

實驗內容 實驗目標 課時分配 算法編程實驗：

1、用指針方式編寫程序 復習C（C++）語言指針、結構體等的用法

2、對單鏈表進行遍歷

鏈表的描述與操作實現

3、棧及其操作

描述方法及操作

4、編寫串子系統1 串的特點及順序定長存儲、操作、查找

5、編寫串子系統 2 串的特點及順序定長存儲、操作、查找

6、編寫樹子系統1 二叉樹的特點及存儲方式、創建、顯示、遍歷等

7、編寫樹子系統2 二叉樹的特點及存儲方式、創建、顯示、遍歷等

8、圖子系統

圖的鄰接矩陣的存儲、遍歷、廣度/深度優先搜索

9、查找子系統

理解查找基本算法、平均查找長度、靜態、動態查找等

五、考試范圍與題型

1、考試范圍與分數比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊列

6% 5)串

4% 6)樹和二叉樹

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分數比例

1)名詞解釋

18% 2)判斷對錯

16% 3)填空

16% 4)單項選擇

18% 5)應用

32%

六、教材與參考資料

1、教材： 實用數據結構基礎（譚浩強）中國鐵道出版社

2、參考資料： 數據結構（嚴蔚敏）清華大學出版社

數據結構實用教程（徐孝凱）清華大學出版社

（撰寫人：

，審核人： 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時）

第五篇：數據結構教學大綱(參考)

數據結構 Data Structure 課程代碼：

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

學 分 數：

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

開課學期：4 主講教師：

編寫日期： 2011年7月1日

一、課程性質和目的課程性質：數據結構A是計算機科學與技術、數字媒體藝術、信息管理與信息系統專業的一門重要學科基礎課，是必修課。

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

二、課程教學內容、學時分配和課程教學基本要求

1.緒論（理論2學時）

教學內容：

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

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

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

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

教學內容：

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

(4)線性表的應用，包括無序表和有序表的合并、多項式的加法運算等。基本要求：

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

實驗：

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

教學內容：

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

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

(4)隊列的類型，隊列的順序存儲(循環隊)和鏈接存儲的表示和實現。(5)隊列的應用舉例，如打印楊暉三角形，模擬汽車加油站等問題。基本要求：

掌握棧和隊列的特點，并能在相應的應用問題中正確選用。熟練掌握棧的順序棧和鏈棧的進棧出棧算法，特別應注意棧滿和棧空的條件。掌握利用棧實現表達式求值的算法，了解迷宮求解算法。理解遞歸算法執行過程中棧的狀態變化過程，了解將遞歸程序轉換為非遞歸程序的方法。熟練掌握循環隊列和鏈隊列的進隊出隊算法，特別是循環隊列中隊頭與隊尾指針的變化情況。了解隊列的應用。

實驗：

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

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

教學內容：

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

(3)特殊矩陣和稀疏矩陣的壓縮存儲，稀疏矩陣的轉置運算。(4)廣義表的邏輯結構和存儲結構。基本要求：

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

教學內容：

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

(3)二叉樹的的前序、中序、后序、層次遍歷方法。線索化二叉樹。(4)樹和森林的定義，樹的存儲，樹、森林與二叉樹的轉換。(5)樹的應用，哈夫曼樹及哈夫曼編碼。基本要求：

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

實驗：

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

教學內容：

(1)圖的定義和術語。

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

(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法。基本要求：

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

實驗：

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

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

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

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

基本要求：

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

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

教學內容：

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

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

(7)排序算法分析：各種排序算法的比較和移動次數，時間復雜度和空間復雜度的分析。基本要求：

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

實驗：

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

教學內容：

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

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

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

三、本課程與其它課程的聯系和分工

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

四、本課程的考核方式

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

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

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

建議教材：

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

3.殷人昆主編．數據結構（用面向對象方法與C++描述）．北京：清華大學出版社． 建議教學參考書：

1.[美]Bruno R.Preiss著，胡廣斌，王崧等譯．數據結構與算法－面向對象的C++設計模式．北京：電子工業出版社．

2.殷人昆主編．數據結構與習題解析（用面向對象方法與C++描述）．北京：清華大學出版社．

六、課程簡介

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

執筆人：

審核人：

教學院長：

院學術委員會：

院長：