數據結構

數據結構是計算機專業的核心課程，是從事計算機軟件開發、應用人員應當必備的專業基礎。隨着計算機的日益普及，簡單的數據結構知識已經下放到中學的計算機課程中，並已成為計算機軟件考試的必考課程之一。本書是根據作者在北京清華大學及美國密西根州GrandValley州立大學多年教學的經驗，並參考了近年出版的多種國外大學數據結構和麪向對象軟件工程教科書編寫的。內容包括：數組、鏈接表、棧和隊列、遞歸、樹與森林、圖、堆與優先級隊列、集合與搜索結構、排序、索引結構與散列等。書中採用面向對象的觀點討論數據結構技術，並以兼有面向過程和麪向對象雙重特色的C++語言作為算法的描述工具，強化基本知識和基本能力的雙基訓練。全書條理清晰，通俗易懂，圖文並茂，適於自學。

本書適合作大專院校中計算機或軟件專業的教材，也可供計算機軟件人員和計算機用户閲讀。 ^[1] 

第1章 緒論

1.1什麼是數據結構

1.2抽象數據類型及面向對象概念

1.2.1數據類型

1.2.2數據抽象與抽象數據類型

1.2.3 面向對象的概念

1.2.4 用於描述數據結構的語言

1.3數據結構的抽象層次

*1.4 用C＋＋描述面向對象程序

1.4.1C＋＋的函數特徵

1.4.2C＋＋的數據聲明

1.4.3C＋＋的作用域

1.4.4 C＋＋的類

1.4.5C＋＋中的對象

1.4.6C＋＋的輸入輸出

1.4.7C＋＋中的函數

1.4.8C＋＋中的參數傳遞

1.4.9 C＋＋中的函數名重載和操作符重載

1.4.10 C＋＋中的動態存儲分配

1.4.11友元（friend）函數

1.4.12內聯（inline）函數

1.4.13 結構（struct）與類

1.4.14 聯合（Union）與類

1.5算法定義

1.6模板（template）

1.7性能分析與度量

1.7.1算法的性能標準

1.7.2算法的後期測試

1.7.3算法的事前估計

1.7.4 空間複雜度度量

1.7.5時間複雜度度量

1.7.6時間複雜度的漸進表示法

1.7.7漸進的空間複雜度

習題

第2章 數組

2.1作為抽象數據類型的數組

2.1.1在C＋＋中數組的定義和初始化

2.1.2作為抽象數據類型的數組

2.1.3數組的順序存儲方式

2.2 順序表

2.2.1順序表的定義和特點

2.2.2順序表的類定義

2.2.3順序表的查找、插入和刪除

2.2.4作為抽象數據類型，使用順序表的事例

2.3多項式抽象數據類型

2.3.1多項式抽象數據類型

2.3.2 多項式的表示

2.3.3多項式的相加

2.4 稀疏矩陣

2.4.1稀疏矩陣的抽象數據類型

2.4.2稀疏矩陣的壓縮表示

2.4.3稀疏矩陣的轉置

2.4.4 稀疏矩陣相乘

2.5字符串

2.5.1字符串抽象數據類型和類定義

2.5.2字符串操作的實現

2.5.3字符串的模式匹配

2.5.4模式匹配的改進算法——KMP（D.E.Knuth—J.H.Morris—V.R.Pratt）算法

習題

第3章 鏈表

3.1單鏈表（SinglyLinkedList）

3.1.1單鏈表的結構

3.1.2單鏈表的類定義

3.1.3單鏈表中的插入與刪除

3.1.4帶表頭結點的單鏈表

3.1.5用模板定義的單鏈表類

3.1.6單鏈表的遊標（Iterator）類

3.1.7靜態鏈表

3.2循環鏈表

3.2.1循環鏈表的類定義

3.2.2用循環鏈表求解約瑟夫問題

3.3多項式及其相加

3.3.1多項式的類定義

3.3.2多項式的加法 ^[1] 

3.4雙向鏈表

3.5稀疏矩陣

3.5.1稀疏矩陣的類定義

3.5.2稀疏矩陣的建立

3.5.3刪除稀疏矩陣

3.6C＋＋中的虛函數和動態聯編

3.6.1C＋＋中的繼承（inheritance）

3.6.2基類與派生類對象指針的轉換

3.6.3虛函數（virtualfunction）

3.6.4 純虛函數和抽象基類

3.6.5多態性（polymorphism）和動態聯編

習題

第4章 棧和隊列

4.1棧

4.1.1棧的抽象數據類型

4.1.2棧抽象數據類型的順序存儲表示與實現——順序棧

4.1.3棧抽象數據類型的鏈接存儲表示——鏈式棧

4.2表達式的計算

4.2.1表達式

4.2.2應用後綴表示計算表達式的值

4.2.3中綴表達式轉換為後綴表達式

4.3隊列

4.3.1隊列的抽象數據類型

4.3.2隊列的順序存儲表示——循環隊列

4.3.3隊列的鏈接存儲表示——鏈式隊列

4.3.4 隊列的應用舉例——打印二項展開式（a＋b）j的係數

4.4優先級隊列（PriorityQueue）

4.4.1優先級隊列的定義

4.4.2優物級隊列的存儲表示和實現

4.5事件驅動模擬

習題

第5章 遞歸

5.1遞歸的概念

5.2迷宮問題

5.3遞歸過程與遞歸工作棧

5.4利用棧實現的迷宮問題非遞歸解法

5.5廣義表

5.5.1廣義表的概念

5.5.2廣義表的表示及操作

5.5.3廣義表存儲結構的實現

5.5.4 廣義表的訪問算法

5.5.5廣義表的遞歸算法

5.5.6三元多項式的表示

習題

第6章 樹與森林

6.1樹和森林的概念

6.1.1樹的定義

6.1.2樹的術語

6.1.3樹的抽象數據類型

6.2二叉樹

6.2.1二叉樹的定義

6.2.2二叉樹的性質

6.2.3二叉樹的抽象數據類型

6.3二叉樹的表示

6.3.1數組表示

6.3.2鏈表存儲表示

6.4二叉樹遍歷

6.4.1中序遍歷

6.4.2前序遍歷

6.4.3後序遍歷

6.4.4 應用二叉樹遍歷的事例

6.4.5二叉樹遍歷的遊標類

6.4.6 不用棧的二叉樹中序遍歷算法

6.5線索化二叉樹

6.5.1線索

6.5.2中序線索化二叉樹

6.5.3前序與後序的線索化二叉樹

6.6 堆（Heap ）

6.6.1堆的定義

6.6.2堆的建立

6.6.3堆的插入與刪除

6.7樹與森林

6.7.1樹的存儲表示

6.7.2森林與二叉樹的轉換

6.7.3樹的遍歷

6.7.4 森林的遍歷

6.8二叉樹的計數

6.9 霍夫曼樹

6.9.1路徑長度

6.9.2霍夫曼樹

6.9.3霍夫曼編碼

習題

第7章 集合與搜索

7.1集合及其表示

7.1.1集合基本概念

7.1.2以集合為基礎的抽象數據類型

7.1.3用位向量實現集合抽象數據類型

7.1.4 用有序鏈表實現集合的抽象數據類型

7.2 等價類和並查集

7.2.1等價關係與等價類

7.2.2確定等價類的鏈表方法

7.2.3並查集

7.3靜態搜索結構

7.3.1搜索的概念

7.3.2靜態搜索結構 ^[1] 

7.3.3順序搜索

7.3.4 基於有序順序表的折半搜索

7.3.5基於有序順序表的斐波那契搜索和插值搜索

7.4 二叉搜索樹

7.4.1定義

7.4.2二叉搜索樹上的搜索

7.4.3二叉搜索樹的插入

7.4.4 二叉搜索樹的刪除

7.4.5與二叉搜索樹相關的中序遊標類

7.5最優二叉搜索樹

7.5.1擴充二叉搜索樹

7.5.2最優二叉搜索樹

7.6AVL樹

7.6.1AVL樹的定義

7.6.2平衡化旋轉

7.6.3AVL樹的插入和刪除

7.6.4AVL樹的高度

習題

第8章 圖

8.1圖的基本概念

8.1.1圖的基本概念

8.1.2圖的抽象數據類型

8.2圖的存儲表示

8.2.1鄰接矩陣

8.2.2 鄰接表

8.2.3鄰接多重表

8.3圖的遍歷與連通性

8.3.1深度優先搜索

8.3.2廣度優先搜索

8.3.3連通分量

8.3.4 重連通分量

8.4 最小生成樹

8.4.1克魯斯卡爾（Kruskal）算法

8.4.2普里姆（Prim）算法

8.5最短路徑

8.5.1邊上權值非負情形的單源最短路徑問題

8.5.2邊上權值為任意值的單源最短路徑問題

8.5.3所有頂點之間的最短路徑

8.6 活動網絡

8.6.1用頂點表示活動的網絡

8.6.2用邊表示活動的網絡

習題

第9章 排序

9.1概述

9.2插入排序

9.2.1直接插入排序

9.2.2折半插入排序

9.2.3鏈表插入排序

9.2.4 希爾排序

9.3交換排序

9.3.1起泡排序

9.3.2快速排序

9.4 選擇排序

9.4.1直接選擇排序

9.4.2錦標賽排序

9.4.3堆排序

9.5歸併排序

9.5.1歸併

9.5.2迭代的歸併排序算法

9.5.3遞歸的表歸併排序

9.6基數排序

9.6.1多關鍵碼排序

9.6.2鏈式基數排序

9.7外排序

9.7.1外排序的基本過程

9.7.2k路平衡歸併

9.7.3初始歸併段的生成

9.7.4 並行操作的緩衝區處理

9.7.5最佳歸併樹

習題

第10章 索引結構與散列

10.1靜態索引結構

10.1.1線性索引

10.1.2倒排表

10.1.3m路靜態搜索樹

10.2動態索引結構

10.2.1動態的m路搜索樹

10.2.2B_樹

10.2.3B_樹的插入

10.2.4 B_樹的刪除

10.2.5B＋樹

10.3Trie 樹

10.3.1Trie樹的定義

10.3.2Trie樹的搜索

10.3.3在Trie樹上的插入和刪除

10.4散列

10.4.1詞典（Dictionary）的抽象數據類型

10.4.2散列表與散列方法

10.4.3散列函數

10.4.4 處理溢出的閉散列方法

10.4.5處理溢出的開散列方法——鏈地址法

10.4.6散列表分析

10.5可擴充散列

10.5.1二叉Trie 樹

10.5.2將二叉Trie樹轉換為目錄

10.5.3插入與目錄擴充

10.5.4 刪除與目錄收縮

10.5.5性能分析

習題

附錄 實習要求與實習報告

實習1棧和隊列

實習2串（內容：全屏幕文本編輯器）

實習3樹（內容：作業調度）

實習4圖（內容：某公園導遊圖）

實習5查找、排序（內容：簡單的職工管理系統）

參考文獻 ^[1]