內(nèi) 容 簡 介
本書是高職高專精品課程規(guī)劃教材，可供計算機類相關(guān)專業(yè)的教學使用。
本書內(nèi)容共分9章，系統(tǒng)地介紹了各種類型的數(shù)據(jù)結(jié)構(gòu)，主要從算法的角度詳細介紹了不同結(jié)構(gòu)上算法的實現(xiàn)和排序及查找技術(shù)，并針對線性表、棧、隊列、串、數(shù)組、二叉樹、樹、圖等從物理角度講解了每種邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)，以及相應(yīng)操作的實現(xiàn)，還對結(jié)構(gòu)特點進行了分析。
本書理論與實際結(jié)合，配有相關(guān)的例題、習題、實驗，使抽象的內(nèi)容更易理解。
書中各章的實驗均有實現(xiàn)代碼，且已調(diào)試通過。每章都有類型練習題，各習題都有電子答案。
前 言
數(shù)據(jù)結(jié)構(gòu)是一門研究如何存儲和組織數(shù)據(jù)以及如何操作數(shù)據(jù)的科學。在許多程序設(shè)計領(lǐng)域中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)課程作為高校計算機及相關(guān)專業(yè)的核心基礎(chǔ)課程，研究的對象是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的各種運算。
從邏輯角度看，基本的數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為集合、線性表、樹和圖4種；從計算機中存儲的角度看，數(shù)據(jù)可分為順序結(jié)構(gòu)和非順序結(jié)構(gòu)(或稱鏈式結(jié)構(gòu))。對每一種邏輯結(jié)構(gòu)，可以根據(jù)實際需要采用順序或鏈式存儲結(jié)構(gòu)存放到存儲單元中，當然也可以采用兩種不同存儲結(jié)構(gòu)相結(jié)合的方式。當數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)確定后，就可以根據(jù)數(shù)據(jù)的某些操作要求去編寫算法并寫出程序，從而實現(xiàn)對數(shù)據(jù)的操作。
本書使用類C語言作為算法描述語言，包括線性表、棧、隊列、串、數(shù)組、樹與二叉樹、圖、查找、排序共9章內(nèi)容，對數(shù)據(jù)結(jié)構(gòu)的講解從邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)到在不同存儲結(jié)構(gòu)上算法的實現(xiàn)應(yīng)有盡有。對算法的講解力求從數(shù)據(jù)結(jié)構(gòu)到算法再到程序的思路表現(xiàn)出來，使學習者能深入理解并學會應(yīng)用。
對數(shù)據(jù)結(jié)構(gòu)的學習，能夠使我們以問題求解方法、程序設(shè)計方法及一些典型的數(shù)據(jù)結(jié)構(gòu)算法為研究對象，學會分析數(shù)據(jù)對象的特征，掌握數(shù)據(jù)組織的方法和在計算機中的表示方法，為數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)以及相應(yīng)的處理算法，初步掌握算法的時間、空間復(fù)雜度的分析技巧，培養(yǎng)良好的程序設(shè)計風格以及獲得進行復(fù)雜程序設(shè)計的技能。本書列舉了一些示例進行算法分析，將抽象的內(nèi)容清晰地展現(xiàn)出來。
再版后，本書目錄結(jié)構(gòu)保持不變，糾正了原書中的一些問題，并補充了一些新的算法。書中增加了典型例題，尤其增加了例題的分析過程，通過不同存儲結(jié)構(gòu)上同一問題的不同實現(xiàn)，使讀者能夠在解決實際問題時正確選擇存儲結(jié)構(gòu)。例題的實現(xiàn)過程附上了C語言的實現(xiàn)代碼。再版書的實驗環(huán)節(jié)在原有基礎(chǔ)上增加了實驗內(nèi)容，補充了原有實驗結(jié)構(gòu)上的不足，每個實驗附加了調(diào)試過的代碼。此外習題部分也做了少量的修改，各章習題均有電子版答案(習題答案可以與出版社或作者聯(lián)系)，這些都會給學習者提供很大的方便。
本書作為高職高專的教材，參考學時為60學時，其中含48學時的理論課，12學時的實驗課。
本書作者多年從事計算機程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)以及計算機軟件課程教學工作和計算機軟件開發(fā)工作，有豐富的實踐和教學經(jīng)驗。主編是沈陽理工大學李筠、姜學軍，副主編是孫承福、虞闖，參編的還有王艷梅、張大偉、蔣強、苑擎飏、袁鳳蓮、李瑩、王紀、馬永軒、許亮、李芳、譚小波、徐志勇、付立冬、姚旭東、王海濤等。
由于作者水平有限，書中難免存在錯誤之處，歡迎讀者提出寶貴意見。
第1章 緒論
1.1 數(shù)據(jù)結(jié)構(gòu)簡介
1.2 基本術(shù)語
1.3 數(shù)據(jù)的存儲結(jié)構(gòu)
1.3.1 順序存儲結(jié)構(gòu)
1.3.2 鏈式存儲結(jié)構(gòu)
1.4 算法及算法分析
1.4.1 算法
1.4.2 算法分析
1.5 數(shù)據(jù)結(jié)構(gòu)課程的地位
1.5.1 數(shù)據(jù)結(jié)構(gòu)與其他課程的關(guān)系
1.5.2 數(shù)據(jù)結(jié)構(gòu)課程學習的特點
習題
第2章 線性表
2.1 線性表的邏輯結(jié)構(gòu)
2.2 線性表的順序存儲結(jié)構(gòu)
2.3 線性表的鏈式存儲結(jié)構(gòu)
2.3.1 線性單鏈表
2.3.2 靜態(tài)單鏈表
2.3.3 循環(huán)鏈表
2.3.4 雙向鏈表
2.4 線性表的應(yīng)用
習題
實驗
第3章 棧和隊列
3.1 棧
3.1.1 棧的意義及抽象數(shù)據(jù)類型
3.1.2 棧操作的實現(xiàn)
3.2 隊列
3.2.1 隊列及其抽象數(shù)據(jù)類型
3.2.2 隊列的鏈式存儲結(jié)構(gòu)
3.2.3 隊列的順序存儲結(jié)構(gòu)——
循環(huán)隊列
3.3 棧和隊列的應(yīng)用
習題
實驗
第4章 串
4.1 串的基本概念和存儲結(jié)構(gòu)
4.1.1 串的基本概念
4.1.2 串的存儲結(jié)構(gòu)
4.2 串基本操作的實現(xiàn)
4.3 模式匹配
4.3.1 子串定位函數(shù)
4.3.2 模式匹配的一種改進算法
4.4 串操作應(yīng)用
習題
實驗
第5章 數(shù)組
5.1 數(shù)組的定義和運算
5.2 數(shù)組的順序存儲結(jié)構(gòu)
5.3 矩陣的壓縮存儲
5.3.1 特殊矩陣
5.3.2 稀疏矩陣
5.3.3 稀疏矩陣操作實例
習題
實驗
第6章 樹與二叉樹
6.1 樹的邏輯結(jié)構(gòu)和基本操作
6.2 二叉樹
6.2.1 二叉樹的定義及邏輯結(jié)構(gòu)
6.2.2 二叉樹的性質(zhì)
6.2.3 二叉樹的存儲結(jié)構(gòu)
6.3 遍歷二叉樹和線索二叉樹
6.3.1 遍歷二叉樹
6.3.2 線索二叉樹
6.4 樹和森林
6.4.1 樹的存儲結(jié)構(gòu)
6.4.2 森林與二叉樹的轉(zhuǎn)換
6.4.3 樹的遍歷
6.5 哈夫曼樹及其應(yīng)用
6.5.1 最優(yōu)二叉樹(哈夫曼樹)
6.5.2 哈夫曼編碼
習題
實驗
第7章 圖
7.1 圖的定義與基本術(shù)語
7.1.1 圖的定義
7.1.2 圖的基本術(shù)語
7.2 圖的存儲
7.2.1 鄰接矩陣表示法
7.2.2 鄰接表表示法
7.2.3 十字鏈表
7.2.4 鄰接多重表
7.3 圖的遍歷
7.3.1 深度優(yōu)先搜索
7.3.2 廣度優(yōu)先搜索
7.4 圖的連通性
7.4.1 無向圖的連通分量
與生成樹
7.4.2 最小生成樹
7.5 有向無環(huán)圖及應(yīng)用
7.5.1 拓撲排序(Topological Sort)
7.5.2 關(guān)鍵路徑
7.6 最短路徑
習題
實驗
第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 B樹
8.3.4 靜態(tài)樹表的查找
8.4 哈希表
8.4.1 哈希表的概念
8.4.2 哈希函數(shù)的構(gòu)造方法
8.4.3 處理沖突的方法
8.4.4 哈希表的實現(xiàn)
8.4.5 哈希表的查找分析
習題
實驗
第9章 排序
9.1 概述
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 二路插入排序
9.2.4 表插入排序
9.2.5 希爾排序
9.3 交換排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 選擇排序
9.4.1 簡單選擇排序
9.4.2 堆排序
9.5 歸并排序
9.6 基數(shù)排序
9.6.1 多關(guān)鍵字排序
9.6.2 基數(shù)排序
9.7 外部排序
9.7.1 二路歸并排序
9.7.2 多路歸并排序
9.7.3 初始順串的生成
習題
實驗
參考文獻
