數據結構教程

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

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

數據結構是計算機學科的必修課程，涵蓋了計算機學科的演演算法設計、數值分析、操作系統和編譯原理等課程所涉及的大部分相關演演算法的實現。學好該課程，不僅對這些後續課程的學習有很大幫助，而且能在實際中發揮其廣泛的用途。

計算機是進行數據處理的工具，而數據結構主要研究數據的各種組織形式以及建立在這些組織形式之上的各種運算演演算法的實現，它不僅為用計算機語言進行程序設計提供了方法性的理論指導，還在一個更高的層次上總結了程序設計的常用方法和常用技巧。

本教程是作者針對數據結構課程概念多、演演算法靈活和抽象性強等特點，在總結長期教學經驗的基礎上編寫的。全書分為13章和6個附錄，第1章為緒論，介紹數據結構的基本概念，特彆強調演演算法分析的方法；第2章為線性表，介紹線性表的兩種存儲結構——順序表和鏈表與其基本運算演演算法的實現；第3章為棧和隊列，介紹這兩種特殊的線性結構的概念與應用；第4章為串，介紹串的概念與模式匹配演演算法；第5章為遞歸，較深入地討論計算機學科中遞歸演演算法的設計方法；第6章為數組和廣義表，介紹數組、稀疏矩陣和廣義表的概念與相關運算演演算法的實現；第7章為樹和二叉樹，介紹樹和二叉樹的概念與各種運算演演算法的實現，其中特別突出二叉樹的各種遞歸演演算法；第8章為圖，介紹圖的概念和圖的各種運算演演算法的實現；第9章為查找，介紹各種查找演演算法的實現；第10章為內排序，介紹各種內排序演演算法的實現；第11章為外排序，介紹各種外排序演演算法的實現；第12章為文件，介紹各類文件的組織結構；第13章為採用面向對象的方法描述演演算法，介紹了面向對象的概念和採用C++語言描述數據結構演演算法的方法；附錄A給出6個綜合實驗題；附錄B給出實驗報告格式；附錄C是引用型參數的說明；附錄D是順序表、順序棧和順序隊列使用指針引用型參數的說明；附錄E給出書中部分演演算法清單；附錄F為教育部頒發的全國計算機專業數據結構2012年聯考大綱。

數據結構是一門應用性非常強的課程，學生在掌握各種數據結構特別是存儲結構的基礎上，一定要儘可能多地上機練習，通過實驗把難以理解的抽象概念轉化為實實在在的計算機能夠正確運行的程序，這樣才能將所學知識和實際應用結合起來，吸取演演算法的設計思想的精髓，提高運用這些知識解決實際問題的能力。因此，本教程突出上機練習內容，除最後一章外其餘各章都給出了大量的上機實驗題（屬驗證設計型實驗），供教師和學生選用，附錄A還給出6個綜合性較強的實驗題（屬綜合設計型實驗），目的是全面考查學生綜合運用數據結構知識的能力，教師一般可以在本課程學習末期或者在專門的數據結構集中實習課（通常為36課時）中向學生布置。

為了便於學習和上機實驗，我們還編寫了與本教程配套的《數據結構教程學習指導》和《數據結構教程上機實驗指導》兩本書，與本教程構成一個完整的教學系列。本系列中所有程序均在Visual C++6.0環境下調試通過。

本教程和配套的上機實驗指導、學習指導的編寫得到武漢大學教務部“數據結構綜合教學改革”教學項目的支持，是本群組許多教師多年來在數據結構課程教學研究和教學改革中的經驗與成果的結晶。本教程在編寫過程中得到王麗娜、黃傳河和黃竟偉等多位教授、博導的大力支持，也得到很多使用本書的老師和同學的熱心幫助，作者在此表示衷心感謝。

本書在前3版的基礎上，根據教育部新的考研大綱和大量讀者來信提出的要求進行了修訂，例如，廣義表在新考綱中沒有出現，所以將其合併到數組部分，同時對全書中多個演演算法進行了優化。另外，編者在VC++6.0環境中實現了書中各數據結構的基本運算演演算法和演演算法設計例題，這些源程序和本書的課件可以從網站免費下載。

由於水平所限，儘管編者不遺餘力，仍可能存在錯誤和不足之處，敬請讀者批評指正，特別希望使用本書的教師與作者探討，共同提高我國計算機專業數據結構課程的教學水平。

第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.4.1程序和數據結構

1.4.2演演算法和程序

1.4.3演演算法和數據結構

1.4.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.5.1有序表的抽象數據類型描述

2.5.2有序表的存儲結構及其基本運算演演算法

2.5.3有序表的歸併演演算法

2.5.4有序表的應用

本章小結

練習題2

上機實驗題2

第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.2.5雙端隊列

本章小結

練習題3

上機實驗題3

第4章串

4.1串的基本概念

4.2串的存儲結構

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

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

4.3串的模式匹配

4.3.1Brute?Force演演算法

4.3.2KMP演演算法

本章小結

練習題4

上機實驗題4

第5章遞歸

5.1什麼是遞歸

5.1.1遞歸的定義

5.1.2何時使用遞歸

5.1.3遞歸模型

5.1.4遞歸與數學歸納法

5.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.2稀疏矩陣

6.2.1稀疏矩陣的三元組表示

6.2.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.7AOE網與關鍵路徑

本章小結

練習題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.3B-樹

9.3.4B+樹

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.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.1ISAM文件

12.3.2VSAM文件

12.4哈希文件

12.5多關鍵字文件

12.5.1多重表文件

12.5.2倒排文件

本章小結

練習題12

上機實驗題12

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

13.1面向對象的概念

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綜合實驗題

綜合實驗題1鏈表綜合演演算法設計

綜合實驗題2求複雜表達式的值

綜合實驗題3用二叉樹實現家譜的相關運算

綜合實驗題4求無向圖中滿足約束條件的路徑

綜合實驗題5分析二分查找成功時的平均查找長度

綜合實驗題6求各種排序演演算法的執行時間

附錄B實驗報告格式

附錄C引用型參數的說明

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

附錄E書中部分演演算法清單

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

參考文獻