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

1、作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 數(shù)據(jù)結(jié)構(gòu)復習數(shù)據(jù)結(jié)構(gòu)復習選擇選擇填空填空解答題（問答題）解答題（問答題）算法題算法題作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 數(shù)據(jù)結(jié)構(gòu)復習數(shù)據(jù)結(jié)構(gòu)復習復習原則復習原則1 理解理解各章基本概念（選擇、填空）各章基本概念（選擇、填空）2 存儲結(jié)構(gòu)：存儲結(jié)構(gòu)： 1）掌握基本存儲結(jié)構(gòu)（）掌握基本存儲結(jié)構(gòu)（ 表、棧、隊列、二叉表、棧、隊列、二叉樹（順序結(jié)構(gòu)、鏈式結(jié)構(gòu)（動態(tài)、靜態(tài)）；樹（順序結(jié)構(gòu)、鏈式結(jié)構(gòu)（動態(tài)、靜態(tài)）；存儲信息、含義及存儲信息、含義及C 語言描述）語言描述） 2）理解復雜存儲結(jié)構(gòu)（圖

2、、樹）理解復雜存儲結(jié)構(gòu)（圖、樹）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 數(shù)據(jù)結(jié)構(gòu)復習數(shù)據(jù)結(jié)構(gòu)復習3 算法算法 1）掌握基本算法及應用）掌握基本算法及應用 如：構(gòu)造、銷毀、插入、刪除、遍歷、查找、如：構(gòu)造、銷毀、插入、刪除、遍歷、查找、排序等，主要步驟、基本思想、主要操作的實現(xiàn)排序等，主要步驟、基本思想、主要操作的實現(xiàn)（C語言描述）語言描述） 2）復雜算法）復雜算法 掌握方法，能讀懂程序（能填空；能寫出主掌握方法，能讀懂程序（能填空；能寫出主要數(shù)據(jù)結(jié)構(gòu)的變化狀態(tài)）要數(shù)據(jù)結(jié)構(gòu)的變化狀態(tài)）4 會計算基本（簡單）算法的時間復雜度。會計算基本（簡單）算法的時間復雜度。作

3、者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第一章第一章 題型題型選擇選擇填空填空解答解答作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 數(shù)據(jù)結(jié)構(gòu)和算法的有關概念數(shù)據(jù)結(jié)構(gòu)和算法的有關概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)及分類數(shù)據(jù)的邏輯結(jié)構(gòu)及分類數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（ADT）算法算法算法的時間復雜度算法的時間復雜度 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。帶

4、有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)操作的定義（功能）數(shù)據(jù)操作的定義（功能）數(shù)據(jù)操作的實現(xiàn)數(shù)據(jù)操作的實現(xiàn)( (在計算機上在計算機上) ) 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈式存儲鏈式存儲 線性表線性表棧、隊列棧、隊列樹結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)圖結(jié)構(gòu) 散列存儲散列存儲索引存儲索引存儲串及數(shù)組串及數(shù)組結(jié)構(gòu)結(jié)構(gòu)操作操作集合結(jié)構(gòu)集合結(jié)構(gòu)作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第二章 題型選擇選擇填空填空解答解答算法算法作

5、者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 線性表 線性表的概念、線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 線性表的存儲和實現(xiàn)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)- -類型定義類型定義基本操作算法基本操作算法 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 線性表的存儲和實現(xiàn)線性鏈表線性鏈表循環(huán)鏈表循環(huán)鏈表雙向鏈表雙向鏈表實現(xiàn)方式實現(xiàn)方式動態(tài)鏈表、靜態(tài)鏈表動態(tài)鏈表、靜態(tài)鏈表鏈表的類型定義鏈表的類型定義鏈表的基本操作算法鏈表的基本操作算法鏈表其它操作算法鏈表其它操作算法作者 (時間 2000

6、年）北京理工大學計算機科學工程系 秦懷青email typedef struct Lnode ElemType data; Struct Lnode *next;LNode, *LinkList;頭指針頭指針a ai ia a1 1a ai+1i+1a ai i-1 1a an nL L線性鏈表的類型定義線性鏈表的類型定義作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第三章第三章 題型題型 選擇選擇填空填空解答解答算法算法作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email

7、 3.1 3.1 棧棧棧的概念、特點棧的概念、特點棧的順序存儲結(jié)構(gòu)和實現(xiàn)棧的順序存儲結(jié)構(gòu)和實現(xiàn)棧的鏈式存儲結(jié)構(gòu)和實現(xiàn)棧的鏈式存儲結(jié)構(gòu)和實現(xiàn) 順序棧、鏈式棧的類型定義順序棧、鏈式棧的類型定義 順序棧、鏈式棧的順序棧、鏈式棧的基本操作算法基本操作算法作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 表達式求值（算符優(yōu)先算法）表達式求值（算符優(yōu)先算法）(方法方法)理解棧在遞歸函數(shù)執(zhí)行過程中的作用理解棧在遞歸函數(shù)執(zhí)行過程中的作用編寫遞歸算法編寫遞歸算法 棧的應用棧的應用作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 隊列隊列隊列的概念、特點隊列的概念、

8、特點循環(huán)隊列循環(huán)隊列鏈式隊列鏈式隊列 循環(huán)隊列、鏈式隊列的類型定義循環(huán)隊列、鏈式隊列的類型定義 循環(huán)隊列、鏈式隊列的循環(huán)隊列、鏈式隊列的基本操作算法基本操作算法作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第五章第五章 題型題型選擇選擇填空填空解答解答算法算法作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 5.1 5.1 數(shù)數(shù) 組組 ( (選擇、填空、解答選擇、填空、解答) )數(shù)組的邏輯結(jié)構(gòu)數(shù)組的邏輯結(jié)構(gòu)數(shù)組的基本操作數(shù)組的基本操作數(shù)組的存儲方法數(shù)組的存儲方法多維數(shù)組

9、元素存儲地址的計算多維數(shù)組元素存儲地址的計算(低下標優(yōu)先低下標優(yōu)先)0 1 n-1 n n+1 2n-1 mn-10 1 n-1 n n+1 2n-1 mn-1a a00 00 a a01 01 a a0n-1 0n-1 a a10 10 a a11 11 a a1n-1 1n-1 a am-10 m-10 a am-11 m-11 a am-1n-1m-1n-1作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 5.2. 5.2.矩陣的壓縮存儲矩陣的壓縮存儲特殊矩陣的概念特殊矩陣的概念特殊矩陣的壓縮存儲方法（對稱矩陣）特殊矩陣的壓縮存儲方法（對稱矩陣）稀疏矩陣的概念稀疏

10、矩陣的概念稀疏矩陣的壓縮存儲方法稀疏矩陣的壓縮存儲方法三元組順序表三元組順序表作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 矩陣快速轉(zhuǎn)置算法矩陣快速轉(zhuǎn)置算法numcol： 存儲存儲M第第col列非零元個數(shù)列非零元個數(shù)cpotcol： 存儲存儲M第第col列第一個非零元在列第一個非零元在T.data中中的位置的位置作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 5.3 5.3 廣義表廣義表廣義表的概念廣義表的概念廣義表的存儲廣義表的存儲（方法）方法） 頭尾鏈表頭尾鏈表存儲結(jié)構(gòu)存儲結(jié)構(gòu)廣義表的遞歸算法廣義表的遞歸算法 復制廣義表復制廣義表 Co

11、pyGList(T,L)CopyGList(T,L) 求廣義表的深度求廣義表的深度GListDepth(L)GListDepth(L) 判廣義表相等判廣義表相等作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第六章第六章 題型題型選擇選擇填空填空解答解答算法算法作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 二叉樹二叉樹 ( (選擇、填空、問答選擇、填空、問答) )二叉樹的二叉樹的概念概念二叉樹的性質(zhì)二叉樹的性質(zhì)作者 (時間 2000年）北京理工大學計算機科學工程系 秦

12、懷青email 二叉樹存儲二叉樹存儲 二叉樹的的順序存儲二叉樹的的順序存儲 (方法方法)二叉樹的鏈式存儲二叉樹的鏈式存儲 (方法、類型定義方法、類型定義)作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 二叉樹的遍歷（方法、算法）二叉樹的遍歷（方法、算法） 先序、中序、后序遍歷（方法）先序、中序、后序遍歷（方法） 按層遍歷（方法、算法）按層遍歷（方法、算法） 二叉樹的遞歸算法二叉樹的遞歸算法 1 1、查詢二叉樹中某個結(jié)點、查詢二叉樹中某個結(jié)點2 2、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)3 3、求二叉樹的深度、求二叉樹的深度4 4、復制二叉樹、復制二叉樹

13、作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 線索二叉樹線索二叉樹概念概念 使用使用 (遍歷方法）遍歷方法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 樹樹基本概念基本概念 ( (選擇、填空選擇、填空) )作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 樹的存儲和樹的遍歷樹的存儲和樹的遍歷雙親表示法雙親表示法 (方法）方法）孩子鏈表表示法孩子鏈表表示法 (方法）方法）孩子兄弟表示法孩子兄弟表示法 (方法）方法）森林與二叉樹的對應關系森林與二叉樹的對應關系 (方法）方法）先根（序）遍歷：先訪問樹的根結(jié)點，然后依次

14、先根遍先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。歷根的每棵子樹。后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點。根結(jié)點。按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，二層，第第h層的結(jié)點層的結(jié)點。(方法）方法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 哈夫曼樹與哈夫曼編碼（方法）哈夫曼樹與哈夫曼編碼（方法）哈夫曼樹（最優(yōu)二叉樹）的概念哈夫曼樹（最優(yōu)二叉樹）的概念構(gòu)造哈夫曼樹構(gòu)造哈夫曼樹( (方法、讀懂算法）方法、讀懂算法）哈夫曼編

15、碼哈夫曼編碼( (方法）方法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 第七章第七章 題型題型選擇選擇填空填空解答解答算法算法注意注意: 關鍵路徑不考關鍵路徑不考,以以ppt為準為準作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 圖的概念與術(shù)語圖的概念與術(shù)語圖的存儲結(jié)構(gòu)及特點圖的存儲結(jié)構(gòu)及特點圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲表示（方法）存儲表示（方法）圖的鄰接表存儲表示（方法）圖的鄰接表存儲表示（方法）圖的遍歷（能讀懂算法、方法）圖的遍歷（能讀懂算

16、法、方法）圖的深度遍歷（圖的深度遍歷（DFSDFS）圖的廣度遍歷（圖的廣度遍歷（BFSBFS）圖的最小生成樹（方法）圖的最小生成樹（方法）普里姆算法普里姆算法克魯斯卡爾算法克魯斯卡爾算法有向無環(huán)圖有向無環(huán)圖拓撲排序（讀懂算法、方法）拓撲排序（讀懂算法、方法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 基本概念（選擇、填空、問答）基本概念（選擇、填空、問答）靜態(tài)查找表、動態(tài)查找表靜態(tài)查找表、動態(tài)查找表查找查找也叫檢索，是根據(jù)給定的某個值，在也叫檢索，是根據(jù)給定的某個值，在表中確定一個關鍵字等于

17、給定值的記錄。表中確定一個關鍵字等于給定值的記錄。查找方法評價查找方法評價查找速度查找速度占用存儲空間多少占用存儲空間多少平均查找長度平均查找長度 ASL(Average Search Length)1niASLPiCi作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 順序表的查找：順序查找順序表的查找：順序查找算法算法有序表的查找：折半查找有序表的查找：折半查找算法算法靜態(tài)查找表（選擇、填空、靜態(tài)查找表（選擇、填空、算法）算法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 概念概念查找算法查找算法（編程）（編程）插入操作插入操作（方法）（方

18、法）刪除操作刪除操作（方法）（方法） 動態(tài)查找表動態(tài)查找表二叉排序樹二叉排序樹作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 概念概念平衡二叉樹的構(gòu)造平衡二叉樹的構(gòu)造平衡處理平衡處理（方法）（方法）平衡二叉排序樹平衡二叉排序樹作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 概念概念查找操作查找操作（方法）（方法）插入操作插入操作結(jié)點分裂結(jié)點分裂（方法）（方法）刪除操作刪除操作結(jié)點合并結(jié)點合并（方法）（方法） B- B-樹（方法）樹（方法）作者 (時間 2000年）北京理工大學計算機科學工程系 秦懷青email 概念（哈希函數(shù)、哈希地址、沖突）概念（哈希函數(shù)、哈希地址、沖突）處理沖突的處理沖突的方法方法哈希表構(gòu)造與查找哈希表構(gòu)造與查找（方法）（方法） 哈希表（散列表）哈希表（散列表） （方法）（方法）作者 (時間 2000年）