復(fù)習(xí)提綱數(shù)據(jù)結(jié)構(gòu)

1、本次課重點(diǎn)：本次課重點(diǎn)：1. 數(shù)據(jù)結(jié)構(gòu)的基本概念；數(shù)據(jù)結(jié)構(gòu)的基本概念；2. 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以 及二者之間的關(guān)系；及二者之間的關(guān)系；3. 算法及特性。算法及特性。本次課重點(diǎn)：本次課重點(diǎn)：1. 估算算法時(shí)間復(fù)雜度的基本方法；估算算法時(shí)間復(fù)雜度的基本方法；2. 大大記號的意義；記號的意義；3.問題規(guī)模、基本語句；問題規(guī)模、基本語句；4. 線性表的定義；線性表的定義；5. 線性表的邏輯特征；線性表的邏輯特征；6. 順序表的存儲要點(diǎn)及存儲特點(diǎn)；順序表的存儲要點(diǎn)及存儲特點(diǎn)；7. 順序表的隨機(jī)存取特性；順序表的隨機(jī)存取特性；本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 順序表類的構(gòu)

2、造函數(shù)；（了解）順序表類的構(gòu)造函數(shù)；（了解）2. 2. 順序表插入、刪除、查找操作的實(shí)現(xiàn)；順序表插入、刪除、查找操作的實(shí)現(xiàn)；3.3.順序表插入、刪除、查找操作的時(shí)間性能。順序表插入、刪除、查找操作的時(shí)間性能。本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 單鏈表的存儲要點(diǎn)及存儲特點(diǎn)；單鏈表的存儲要點(diǎn)及存儲特點(diǎn)；2. 2. 單鏈表的順序存取特性；單鏈表的順序存取特性；3. 3. 單鏈表的插入、刪除操作；單鏈表的插入、刪除操作；4. 4. 單鏈表的插入、刪除操作操作的時(shí)間性能。單鏈表的插入、刪除操作操作的時(shí)間性能。本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 單鏈表類的構(gòu)造函數(shù)和析構(gòu)函數(shù)（了解）；單鏈表類的構(gòu)造函數(shù)和析

3、構(gòu)函數(shù)（了解）；2. 2. 順序表和單鏈表的比較；順序表和單鏈表的比較；3. 3. 循環(huán)鏈表的存儲結(jié)構(gòu)；循環(huán)鏈表的存儲結(jié)構(gòu)；4. 4. 循環(huán)鏈表的操作。循環(huán)鏈表的操作。本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 雙鏈表的存儲結(jié)構(gòu)；雙鏈表的存儲結(jié)構(gòu)；2. 2. 雙鏈表的插入、刪除操作；雙鏈表的插入、刪除操作；3. 3. 靜態(tài)鏈表的存儲結(jié)構(gòu)；（了解）靜態(tài)鏈表的存儲結(jié)構(gòu)；（了解）本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 棧的定義及操作特性；棧的定義及操作特性；2. 2. 順序棧及實(shí)現(xiàn)；順序棧及實(shí)現(xiàn)；3. 3. 鏈棧及實(shí)現(xiàn)；鏈棧及實(shí)現(xiàn)；4. 4. 順序棧和鏈棧的比較；順序棧和鏈棧的比較；5. 5. 隊(duì)列的定義及操作

4、特性；隊(duì)列的定義及操作特性；6. 6. 循環(huán)隊(duì)列及實(shí)現(xiàn)；循環(huán)隊(duì)列及實(shí)現(xiàn)；7. 7. 順序隊(duì)列的假溢出現(xiàn)象。順序隊(duì)列的假溢出現(xiàn)象。本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 循環(huán)隊(duì)列及實(shí)現(xiàn)；循環(huán)隊(duì)列及實(shí)現(xiàn)； 2. 2. 鏈隊(duì)列及實(shí)現(xiàn)；鏈隊(duì)列及實(shí)現(xiàn)；本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 遞歸的定義；（課本上沒有，講課時(shí)有講）遞歸的定義；（課本上沒有，講課時(shí)有講） 2. 2. 樹的定義；樹的定義；3. 3. 樹的基本術(shù)語；樹的基本術(shù)語；4. 4. 樹的遍歷操作；樹的遍歷操作；本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 樹的雙親表示法；（了解）樹的雙親表示法；（了解）2. 2. 樹的孩子鏈表表示法；（了解）樹的孩子鏈表

5、表示法；（了解）3. 3. 樹的雙親孩子表示法；（了解）樹的雙親孩子表示法；（了解）4. 4. 樹的孩子兄弟表示法。樹的孩子兄弟表示法。本次課重點(diǎn)：本次課重點(diǎn)：1.1.二叉樹的基本術(shù)語和定義二叉樹的基本術(shù)語和定義2.2.二叉樹的性質(zhì)（課本上的二叉樹的性質(zhì)（課本上的5 5個(gè)性質(zhì)，個(gè)性質(zhì)，不僅要掌握，而且要會靈活運(yùn)用）不僅要掌握，而且要會靈活運(yùn)用）3.3.二叉樹的各種遍歷操作二叉樹的各種遍歷操作本次課重點(diǎn)：本次課重點(diǎn)：* *已知一棵二叉樹的前序序列和中序序列，如已知一棵二叉樹的前序序列和中序序列，如何確定這棵二叉樹（要求會操作，不是會講何確定這棵二叉樹（要求會操作，不是會講理論）理論）1.1.二叉

6、樹的順序存儲結(jié)構(gòu)。二叉樹的順序存儲結(jié)構(gòu)。2.2.二叉鏈表存儲結(jié)構(gòu)。（熟練掌握）二叉鏈表存儲結(jié)構(gòu)。（熟練掌握）3.3.二叉樹遍歷算法的遞歸實(shí)現(xiàn)。（熟練掌握）二叉樹遍歷算法的遞歸實(shí)現(xiàn)。（熟練掌握）4.4.二叉樹前序遍歷的非遞歸算法。（了解）二叉樹前序遍歷的非遞歸算法。（了解）本次課重點(diǎn)：本次課重點(diǎn)：1.1.二叉樹的二叉鏈表存儲結(jié)構(gòu)二叉樹的二叉鏈表存儲結(jié)構(gòu)2.2.二叉樹中序線索鏈表的建立二叉樹中序線索鏈表的建立本次課重點(diǎn)：本次課重點(diǎn)：1.1.在中序線索鏈表上查找某個(gè)結(jié)點(diǎn)的后繼。在中序線索鏈表上查找某個(gè)結(jié)點(diǎn)的后繼。（了解）（了解）2. 2. 樹轉(zhuǎn)換為二叉樹。（熟練掌握樹轉(zhuǎn)換為二叉樹。（熟練掌握) )3

7、. 3. 森林轉(zhuǎn)換為二叉樹。（熟練掌握森林轉(zhuǎn)換為二叉樹。（熟練掌握) )4. 4. 二叉樹轉(zhuǎn)換為樹（或森林）。（熟練掌握二叉樹轉(zhuǎn)換為樹（或森林）。（熟練掌握) )本次課重點(diǎn)：本次課重點(diǎn)：1.1.哈夫曼樹的構(gòu)造方法。（熟練掌握哈夫曼樹的構(gòu)造方法。（熟練掌握) )2. 2. 哈夫曼編碼與解碼方法。哈夫曼編碼與解碼方法。本次課重點(diǎn)：本次課重點(diǎn)：1.1.圖的定義和若干基本術(shù)語。（熟練掌握圖的定義和若干基本術(shù)語。（熟練掌握) )2. 2. 圖的深度優(yōu)先遍歷。（熟練掌握）圖的深度優(yōu)先遍歷。（熟練掌握）本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 圖的廣度優(yōu)先遍歷。（熟練掌握）圖的廣度優(yōu)先遍歷。（熟練掌握）2.2.圖

8、的鄰接矩陣存儲結(jié)構(gòu)。（熟練掌握圖的鄰接矩陣存儲結(jié)構(gòu)。（熟練掌握) )3.3.鄰接矩陣存儲類的構(gòu)造函數(shù)。（熟練掌握鄰接矩陣存儲類的構(gòu)造函數(shù)。（熟練掌握) )本次課重點(diǎn)：本次課重點(diǎn)：1.1.圖的鄰接表存儲結(jié)構(gòu)。（熟練掌握圖的鄰接表存儲結(jié)構(gòu)。（熟練掌握) )2.2.鄰接表存儲類的構(gòu)造函數(shù)。（熟練掌握鄰接表存儲類的構(gòu)造函數(shù)。（熟練掌握) )3.3.基于鄰接表的深度優(yōu)先遍歷算法。（了解）基于鄰接表的深度優(yōu)先遍歷算法。（了解）4.4.基于鄰接表的廣度優(yōu)先遍歷算法。（了解）基于鄰接表的廣度優(yōu)先遍歷算法。（了解）5.5.無向圖的連通性。無向圖的連通性。上次課重點(diǎn)：上次課重點(diǎn)： PrimPrim算法的求解思想、

9、過程及使用的最有利條算法的求解思想、過程及使用的最有利條件（稠密圖）。（熟練掌握件（稠密圖）。（熟練掌握) ) PrimPrim算法的偽代碼描述。（了解）算法的偽代碼描述。（了解） KruskalKruskal算法的求解思想、過程算法的求解思想、過程及使用的最有利及使用的最有利條件（稀疏圖）條件（稀疏圖）。（熟練掌握。（熟練掌握) )4. Kruskal4. Kruskal算法的偽代碼描述。（了解）算法的偽代碼描述。（了解）5. Dijkstra5. Dijkstra算法的求解思想、過程。（熟練掌握算法的求解思想、過程。（熟練掌握) )6. Dijkstra6. Dijkstra算法的偽代碼描述。（了解）算法的偽代碼描述。（了解）本次課重點(diǎn)：本次課重點(diǎn)：1. 1. 拓?fù)湫蛄械亩x。（掌握）拓?fù)湫蛄械亩x。（掌握）2. 2. 拓?fù)渑判蛩惴ǖ那蠼馑枷爰斑^程。（掌握拓?fù)渑判蛩惴ǖ那蠼馑枷爰斑^程。（掌握) )3. 3. 排序的基本術(shù)語，如內(nèi)部排序、外部排序等。排序的基本術(shù)語，如內(nèi)部排序、外部排序等。4. 4. 直接插入排序，起泡排序，快速排序算法思想，直接插入排序，起泡排序，快速排序算法思想，針對具體實(shí)例的操作過程，