數據結構

數據結構

作 者：呂青；張華；劉旭春；楊葉平；袁勁松；秦科；姜鵬

責任編輯：姜鵬

出版社：航空工業出版社

出版日期：2010年06月

本書以項目方式全面系統地介紹了各種類型的數據結構，並從邏輯結構、存儲結構和基本操作幾個方面進行了詳細地闡述。全書共八個項目，分別介紹了線性表、棧、隊列、串、數組、樹、圖等基本類型的數據結構，以及查找、排序技術。

本書可作為高職高專計算機、信息技術類專業的專業課教材，也可作為從事軟體設計和開發的相關工程技術人員的參考書。

目錄

項目一 數據結構導論

任務一 數據結構入門

一、基本術語

二、數據的邏輯結構

三、數據的存儲結構

四、數據類型

任務二 演演算法與演演算法分析

一、演演算法的概念

二、演演算法的特性

三、演演算法的描述方法

四、演演算法設計的要求

五、演演算法性能分析

六、類C語言簡介

項目小結

習題與上機操作

項目二 線性表

任務一 線性表的定義和基本操作

一、線性表的定義

二、線性表的基本操作

任務二 線性表的順序存儲結構

一、順序表的結構特點

二、順序表的基本操作

任務三 線性表的鏈式存儲結構

一、單鏈表的結構特點

二、單鏈表的基本操作

三、靜態鏈表及其基本操作

四、循環鏈表及其基本操作

五、雙向鏈表及其基本操作

項目小結

習題與上機操作

項目三 棧和隊列

任務一 棧的定義、存儲結構和基本操作

一、棧的定義及其基本操作

二、棧的順序存儲結構

三、棧的鏈式存儲結構

四、棧在遞歸中的應用

任務二 隊列的定義、存儲結構和基本操作

一、隊列的定義及其基本操作

二、隊列的順序存儲結構

三、隊列的鏈式存儲結構

項目小結

習題與上機操作

項目四 串和數組

任務一 串的定義、存儲結構和基本操作

一、串的定義及其基本操作

二、定長順序存儲結構

三、堆存儲結構

四、塊鏈存儲結構

任務二 數組的定義和存儲結構

一、數組的定義及其基本操作

二、數組的順序存儲結構

任務三 矩陣的壓縮存儲

一、特殊矩陣的壓縮存儲

二、稀疏矩陣的壓縮存儲

任務四 廣義表的定義和存儲結構

一、廣義表的定義

二、廣義表的存儲結構

項目小結

習題與上機操作

項目五 樹與二叉樹

任務一 樹的定義和基本操作

一、樹的定義和表示方法

二、樹的基本術語

三、樹的基本操作

任務二 二叉樹

一、二叉樹的定義及其基本操作

二、二叉樹的性質

三、二叉樹的存儲結構

四、遍歷二叉樹

五、線索二叉樹

任務三 樹和森林

一、樹的存儲結構

二、樹、森林和二叉樹的轉換

三、樹和森林的遍歷

任務四 哈夫曼樹及其應用

一、哈夫曼樹的定義

二、哈夫曼樹的構造

三、哈夫曼樹編碼

項目小結

習題與上機操作

項目六 圖

任務一 圖的定義和基本操作

一、圖的定義

二、圖的基本術語

三、圖的基本操作

任務二 圖的存儲結構

一、鄰接矩陣表示法

二、鄰接表表示法

三、十字鏈表表示法

四、鄰接多重表表示法

任務三 圖的遍歷

一、深度優先遍歷

二、廣度優先遍歷

任務四 圖的應用

一、生成樹和最小生成樹

二、最短路徑

三、拓撲排序

四、關鍵路徑

項目小結

習題與上機操作

項目七 查找

任務一 查找的相關術語

任務二 靜態查找表

一、順序查找

二、折半查找

三、索引順序查找

任務三 動態查找表

一、二叉排序樹

二、平衡二叉樹

任務四 哈希查找

一、哈希表的基本概念

二、構造哈希函數的方法

三、處理衝突的方法

四、哈希表的查找及分析

項目小結

習題與上機操作

項目八 排序

任務一 排序的相關概念

任務二 插入排序

一、直接插入排序

二、折半插入排序

三、希爾排序

任務三 交換排序

一、冒泡排序

二、快速排序

任務四 選擇排序

一、直接選擇排序

二、樹形選擇排序

三、堆排序

任務五 歸併排序和基數排序

一、歸併排序

二、基數排序

項目小結

習題與上機操作