數據結構教程（第3版）

《數據結構教程（第3版）》是2009年由清華大學出版社出版的額一部圖書。

基本介紹

• 書名：數據結構教程（第3版）
• 作者：李春葆
• ISBN：9787302193791
• 頁數：355
• 定價：36.00元
• 出版社：清華大學出版社
• 出版時間：2009-3-1
• 裝幀：平裝

內容簡介

本書在前兩版的基礎上，針對教育部新的考研大綱和大量讀者來信提出的要求進行了修訂。本書內容包括緒論、線性表、棧和佇列、串、數組和廣義表、遞歸、樹形結構、圖、查找、內排序、外排序和檔案，還給出了3個綜合實驗題、實驗報告格式、引用型參數的說明、順序表和順序棧以及順序佇列使用指針引用型參數的說明、書中部分算法清單、2009年全國計算機專業數據結構考研大綱。

本書適合高等院校計算機及相關專業本科生及研究生使用。

目錄

第1章 緒論

1.1 什麼是數據結構

1.1.1 數據結構的定義

1.1.2 邏輯結構類型

1.1.3 存儲結構類型

1.1.4 數據結構和數據類型

1.2 算法及其描述

1.2.1 什麼是算法

1.2.2 算法描述

1.3 算法分析

1.3.1 算法設計的目標

1.3.2 算法效率分析

1.3.3 算法存儲空間分析

1.4 數據結構+算法=程式

本章 小結

練習題1

上機實驗題1

第2章 線性表

2.1 線性表及其邏輯結構

2.1.1 線性表的定義

2.1.2 線性表的抽象數據類型描述

2.2 線性表的順序存儲結構

2.2.1 線性表的順序存儲結構——順序表

2.2.2 順序表基本運算的實現

2.3 線性表的鏈式存儲結構

2.3.1 線性表的鏈式存儲結構——鍊表

2.3.2 單鍊表基本運算的實現

2.3.3 雙鍊表

2.3.4 循環鍊表

2.4 線性表的套用

2.5 有序表

本章 小結

練習題2

上機實驗題2

目錄

數

據結構教程（第3版）

第3章 棧和佇列

3.1 棧

3.1.1 棧的定義

3.1.2 棧的順序存儲結構及其基本運算實現

3.1.3 棧的鏈式存儲結構及其基本運算的實現

3.1.4 棧的套用舉例

3.2 佇列

3.2.1 佇列的定義

3.2.2 佇列的順序存儲結構及其基本運算的實現

3.2.3 佇列的鏈式存儲結構及其基本運算的實現

3.2.4 佇列的套用舉例

本章 小結

練習題3

上機實驗題3

第4章 串

4.1 串的基本概念

4.2 串的存儲結構

4.2.1 串的順序存儲結構——順序串

4.2.2 串的鏈式存儲結構——鏈串

4.3 串的模式匹配

4.3.1 BruteForce算法

4.3.2 KMP算法

本章 小結

練習題4

上機實驗題4

第5章 數組和廣義表

5.1 數組

5.1.1 數組的基本概念

5.1.2 數組的存儲結構

5.1.3 特殊矩陣的壓縮存儲

5.2 稀疏矩陣

5.2.1 稀疏矩陣的三元組表示

5.2.2 稀疏矩陣的十字鍊表表示

5.3 廣義表

5.3.1 廣義表的定義

5.3.2 廣義表的存儲結構

5.3.3 廣義表的運算

本章 小結

練習題5

上機實驗題5

第6章 遞歸

6.1 什麼是遞歸

6.1.1 遞歸的定義

6.1.2 何時使用遞歸

6.1.3 遞歸模型

6.1.4 遞歸與數學歸納法

6.2 遞歸調用的實現原理

6.3 遞歸算法的設計

6.3.1 遞歸算法設計的步驟

6.3.2 遞歸數據結構的遞歸算法設計

6.3.3 遞歸求解方法的遞歸算法設計

本章 小結

練習題6

上機實驗題6

第7章 樹和二叉樹

7.1 樹的基本概念

7.1.1 樹的定義

7.1.2 樹的邏輯表示方法

7.1.3 樹的基本術語

7.1.4 樹的性質

7.1.5 樹的基本運算

7.1.6 樹的存儲結構

7.2 二叉樹的概念和性質

7.2.1 二叉樹的概念

7.2.2 二叉樹的性質

7.2.3 二叉樹與樹、森林之間的轉換

7.3 二叉樹存儲結構

7.3.1 二叉樹的順序存儲結構

7.3.2 二叉樹的鏈式存儲結構

7.4 二叉樹的基本運算及其實現

7.4.1 二叉樹的基本運算概述

7.4.2 二叉樹的基本運算算法實現

7.5 二叉樹的遍歷

7.5.1 二叉樹遍歷的概念

7.5.2 二叉樹遍歷遞歸算法

7.5.3 二叉樹遍歷非遞歸算法

7.5.4 層次遍歷算法

7.6 二叉樹的構造

7.7 線索二叉樹

7.7.1 線索二叉樹的概念

7.7.2 線索化二叉樹

7.7.3 遍歷線索化二叉樹

7.8 哈夫曼樹

7.8.1 哈夫曼樹概述

7.8.2 哈夫曼樹的構造算法

7.8.3 哈夫曼編碼

7.9 用並查集求解等價問題

7.9.1 什麼叫並查集

7.9.2 並查集的算法實現

本章 小結

練習題7

上機實驗題7

第8章 圖

8.1 圖的基本概念

8.1.1 圖的定義

8.1.2 圖的基本術語

8.2 圖的存儲結構

8.2.1 鄰接矩陣存儲方法

8.2.2 鄰接表存儲方法

8.3 圖的遍歷

8.3.1 圖的遍歷的概念

8.3.2 深度優先搜尋遍歷

8.3.3 廣度優先搜尋遍歷

8.3.4 非連通圖的遍歷

8.3.5 圖遍歷算法的套用

8.4 生成樹和最小生成樹

8.4.1 生成樹的概念

8.4.2 無向圖的連通分量和生成樹

8.4.3 普里姆算法

8.4.4 克魯斯卡爾算法

8.5 最短路徑

8.5.1 路徑的概念

8.5.2 從一個頂點到其餘各頂點的最短路徑

8.5.3 每對頂點之間的最短路徑

8.6 拓撲排序

8.7 AOE網與關鍵路徑

本章 小結

練習題8

上機實驗題8

第9章 查找

9.1 查找的基本概念

9.2 線性表的查找

9.2.1 順序查找

9.2.2 二分查找

9.2.3 索引存儲結構和分塊查找

9.3 樹表的查找

9.3.1 二叉排序樹

9.3.2 平衡二叉樹

9.3.3 B-樹

9.3.4 B+樹

9.4 哈希表查找

9.4.1 哈希表的基本概念

9.4.2 哈希函式構造方法

9.4.3 哈希衝突解決方法

9.4.4 哈希表上的運算

本章 小結

練習題9

上機實驗題9

第10章 內排序

10.1 排序的基本概念

10.2 插入排序

10.2.1 直接插入排序

10.2.2 二分插入排序

10.2.3 希爾排序

10.3 交換排序

10.3.1 冒泡排序

10.3.2 快速排序

10.4 選擇排序

10.4.1 直接選擇排序

10.4.2 堆排序

10.5 歸併排序

10.6 基數排序

10.7 各種內排序方法的比較和選擇

本章 小結

練習題10

上機實驗題10

第11章 外排序

11.1 外排序概述

11.2 磁碟排序

11.2.1 磁碟排序過程

11.2.2 多路平衡歸併

11.2.3 初始歸併段的生成

11.2.4 最佳歸併樹

11.3 磁帶排序

11.3.1 多路平衡歸併排序

11.3.2 多階段歸併排序

本章 小結

練習題11

上機實驗題11

第12章 檔案

12.1 檔案的基本概念

12.1.1 什麼是檔案

12.1.2 檔案的邏輯結構及操作

12.1.3 檔案的存儲結構

12.2 順序檔案

12.3 索引檔案

12.3.1 ISAM檔案

12.3.2 VSAM檔案

12.4 哈希檔案

12.5 多關鍵字檔案

12.5.1 多重表檔案

12.5.2 倒排檔案

本章 小結

練習題12

上機實驗題12

第13章 採用面向對象的方法描述算法

13.1 面向對象的概念

13.1.1 重要概念

13.1.2 主要優點

13.2 用C++描述面向對象的程式

13.2.1 類

13.2.2 類對象

13.2.3 構造函式和析構函式

13.2.4 派生類

13.3 用C++描述數據結構算法

13.3.1 順序表類

13.3.2 鏈棧類

13.3.3 二叉樹類

附錄A 綜合實驗題

附錄B 實驗報告格式

附錄C 引用型參數的說明

附錄D 順序表、順序棧和順序佇列使用指針引用型參數的說明

附錄E 書中部分算法清單

附錄F 全國計算機專業數據結構考研大綱

參考文獻