數據結構(Java版)（簡體書）

《普通高等教育“十二五”規劃教材：數據結構（Java版）》是鉗對數據結構初學者編寫的基礎教程，書中不僅講解了數據結構常用的基本理論知識，而且提供了大量應用實例，以幫助初學者對知識的理解。全書共分8章：緒論、線性表、棧和隊列、串和數組、樹和二叉樹、圖、查找、排序等。
《普通高等教育“十二五”規劃教材：數據結構（Java版）》內容實用，結構清晰，實例豐富，可操作性強，可作為高等學校數據結構的教材，也可作為計算機相關專業的培訓和自學教材。

《普通高等教育"十二五"規劃教材:數據結構(Java版)》內容實用，結構清晰，實例豐富，可操作性強，可作為高等學校數據結構的教材，也可作為計算機相關專業的培訓和自學教材。

前言
第1章 緒論
1.1 基本概念
1.1.1 數據和數據結構
1.1.2 數據類型
1.1.3 抽象數據類型
1.1.4 數據結構的符號描述舉例
1.2 算法和算法描述
1.2.1 概念和特性
1.2.2 算法設計要求
1.2.3 算法描述
1.3 算法的性能分析
1.3.1 時間複雜度
1.3.2 空間複雜度
1.3.3 分析算法時間複雜度舉例
1.4 習題

第2章 線性表
2.1 線性表的含義及ADT描述
2.2 順序存儲結構
2.2.1 順序表的存儲表示
2.2.2 順序表的基本操作的實現
2.2.3 順序表的基本操作的時間
複雜度分析
2.2.4 順序表的優缺點
2.2.5 順序存儲結構的應用
2.3 鏈式存儲結構
2.3.1 單鏈表的存儲表示
2.3.2 單鏈表基本操作的實現
2.3.3 循環鏈表的表示和基本操作的實現
2.3.4 雙向鏈表的表示和基本操作的實現
2.3.5 鏈式存儲結構的應用
2.4 習題

第3章 棧和隊列
3.1 棧
3.1.1 棧的定義及ADT描述
3.1.2 棧的順序存儲結構
3.1.3 棧的鏈式存儲結構
3.1.4 棧的應用
3.2 隊列
3.2.1 隊列的定義及ADT描述
3.2.2 隊列的順序存儲結構
3.2.3 隊列的鏈式存儲結構
3.2.4 隊列的應用
3.3 習題

第4章 串和數組
4.1 串
4.1.1 串的定義及ADT描述
4.1.2 串的順序存儲結構
4.1.3 串的鏈式存儲結構
4.1.4 串的應用舉例
4.2 數組
4.2.1 數組的定義及.ADT描述
4.2.2 數組的存儲結構
4.2.3 矩陣的壓縮存儲
4.2.4 矩陣轉置
4.2.5 數組的應用舉例
4.3 習題

第5章 樹和二叉樹
5.1 樹
5.1.1 樹的概念及ADT描述
5.1.2 樹的存儲結構
5.1.3 綜合應用舉例
5.2 二叉樹
5.2.1 二叉樹的概念及ADT描述
5.2.2 二叉樹的性質
5.2.3 二叉樹的存儲結構
5.2.4 遍歷二叉樹
5.2.5 遍歷算法的應用
5.2.6 樹、森林與二叉樹的轉換
5.2.7 一叉樹的綜合應用
5.3 樹和森林的遍歷
5.3.1 樹的遍歷
5.3.2 森林的遍歷
5.3.3 樹和森林的遍歷應用
5.4 哈夫曼樹及應用
5.4.1 哈夫曼樹
5.4.2 判定樹
5.4.3 前綴編碼
5.5 習題

第6章 圖
6.1 圖的概述
6.1.1 圖的概念
6.1.2 圖的ADT描述
6.2 圖的存儲結構
6.2.1 鄰接矩陣
6.2.2 鄰接表
6.2.3 應用舉例
6.3 圖的遍歷
6.3.1 深度優先遍歷
6.3.2 廣度優先遍歷
6.3.3 應用舉例
6.4 最小生成樹問題
6.4.1 圖的生成樹和最小生成樹
6.4.2 構造最小生成樹
6.4.3 應用舉例
6.5 有向無環圖及應用
6.5.1 基本定義
6.5.2 拓撲排序
6.5.3 關鍵路徑
6.6 習題

第7章 查找
7.1 基本概念
7.2 靜態查找
7.2.1 順序查找
7.2.2 折半查找
7.2.3 折半查找應用舉例
7.3 動態查找
7.3.1 二叉排序樹
7.3.2 二叉排序樹的查找
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 習題

第8章 排序
8.1 基本概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 希爾排序
8.2.3 應用舉例
8.3 交換排序
8.3.1 冒泡排序
8.3 2快速排序
8.3.3 應用舉例
8.4 選擇排序
8.4.1 簡單選擇排序
8.4.2 堆排序
8.4.3 應用舉例
8.5 歸併排序
8.5.1 歸併排序的基本思想
8.5.2 路歸併排序算法
8.5.3 應用舉例
8.6 基數排序
8.6.1 基數排序的基本思想
8.6.2 鏈式基數捧序算法
8.6.3 應用舉例
8.6.4 排序方法簡單比較
8.7 習題
參考文獻

第7章 查找
7.1 基本概念
查找，也稱為檢索，是數據處理中常用的一種操作。例如，從電話簿中查找某人的電話，從學生信息表中查找外籍學生信息等。計算機查找可以大大提高工作效率。
在計算機應用中，查找是指在數據元素集合中查找滿足某種條件的數據元素的過程。這里常將用于查找的數據元素集合稱為查找表。查找表由同一類型的數據元素（或記錄）構成的集合（文件或表）。查找條件可能多種多樣，但最常用的查找條件是“關鍵字值等于某個給定值”，即在查找表中檢索關鍵字等于給定值的數據元素（或記錄）。除非特別說明，本書約定的查找條件都屬于此種類型。
對查找表的操作可以分為四類：
（1）在查找表中查看某個特定的數據元素是否在查找表中。
（2）檢索某個特定元素的各種屬性。
（3）在查找表中插入一個數據元素。
（4）從查找表中刪除某個數據元素。
基于操作類型，可以將查找分為靜態查找和動態查找，相應地將查找表分為靜態查找表和動態查找表。
若只對查找表進行第（1）或（2）操作，則稱這類查找表為靜態查找表。靜態查找表在查找過程中查找表本身不發生變化。對靜態查找表進行的查找操作稱為靜態查找。
若在查找過程中可以將查找表中不存在的數據元素插入，或者從查找表中刪除某個數據元素，即允許對查找表進行第（3）或（4）操作，則稱這類查找表為動態查找表。動態查找表在查找過程中查找表可能會發生變化。對動態查找表進行的查找操作稱為動態查找。
查找的結果有成功、不成功兩種可能。若表中存在關鍵字等于給定值的記錄，則稱查找成功，此時的查找結果應給出找到記錄的全部信息或指示找到記錄的存儲位置；若表中不存在關鍵字等于給定值的記錄，則稱查找不成功，此時查找的結果可以給出一個空記錄或空指針。
一般在查找表中，每個數據元素或記錄由若干個數據項組成，其中用作查找條件的數據項稱為關鍵字。因此，關鍵字是數據元素（或記錄）中某個數據項的值，用它可以標識一個數據元素（或記錄）。若此關鍵字可以唯一地標識一個記錄，則稱此關鍵字為主關鍵字。反之，則稱此關鍵字為次關鍵字。例如，銀行賬戶中的賬號是主關鍵字，而姓名是次關鍵字。若按主關鍵字查找，查找結果是唯一的；若按次關鍵字查找，結果可能是多個記錄，即結果可能不唯一。
查找表是一種非常靈活的數據結構，對于不同的存儲結構，其查找方法不同。為了提高查找速度，有時會采用一些特殊的存儲結構。本章將介紹以線性結構、樹形結構及哈希表結構為存儲結構的各種查找算法。
用于查找的算法有很多，由于在查找過程的主要操作是關鍵字的比較，因此通常以“平均比較次數”來衡量查找算法的時間效率。
7.2 靜態查找
靜態查找是指在靜態查找表上進行的查找操作，在查找表中查找滿足條件的數據元素的存儲位置或各種屬性。本節將討論以線性結構表示的靜態查找表及相應的查找算法。
7.2.1一順序查找
1.順序查找的基本思想
順序查找是一種最簡單的查找方法。其基本思想是將查找表作為一個線性表（順序表或鏈表），從第一個數據元素（或記錄）開始，將給定值與表中元素逐一進行比較，若某個元素的關鍵字值與給定值相等，則查找成功，返回該元素的存儲位置，反之，若直到最后一個元素，其關鍵字值與給定值均不相等，則查找失敗，返回查找失敗標志。對于元素的關鍵字是無序的表來說，只能采用這種方法。
2.順序查找示例
順序表中數據元素的關鍵字序列為（38，75，19，57，100，48，50，7，62，11），則查找關鍵字K=48需要6次比較，查找成功；而查找關鍵字K=53需要11次比較，查找不成功。