內(nèi) 容 簡 介
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程。本書所有算法都采用C語言描述，書中不僅講解了數(shù)據(jù)結(jié)構(gòu)的基本理論知識(shí)，還提供了大量典型的應(yīng)用實(shí)例，所有實(shí)例均能直接運(yùn)行，以幫助讀者充分理解和掌握知識(shí)點(diǎn)。全書共分9章，內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)概述、線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等。
本書內(nèi)容實(shí)用，結(jié)構(gòu)清晰，實(shí)例豐富，可操作性強(qiáng)，可作為本、專科院校的計(jì)算機(jī)及相關(guān)專業(yè)的數(shù)據(jù)結(jié)構(gòu)教材，也可作為進(jìn)行計(jì)算機(jī)軟件開發(fā)、考研和軟件資格(水平)考試人員的參考書。
前 言
在多年來的教學(xué)與研究過程中，作者讀過不少關(guān)于數(shù)據(jù)結(jié)構(gòu)方面的教材，發(fā)現(xiàn)好多教材不是內(nèi)容不夠全面，就是語言表述方面偏于晦澀，看書時(shí)間久了就會(huì)比較辛苦。有鑒于此，作者采用通俗活潑的語言風(fēng)格編著了本書，把這些年來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的一些心得分享給大家，希望能對大家的學(xué)習(xí)有所幫助。
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來解決實(shí)際問題時(shí)，就要涉及數(shù)據(jù)與數(shù)據(jù)之間關(guān)系的表示與處理，而這正是數(shù)據(jù)結(jié)構(gòu)研究的對象。通過對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，可為后續(xù)課程，特別是軟件方面的課程打下堅(jiān)實(shí)的知識(shí)基礎(chǔ)。因此，數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)相關(guān)專業(yè)中起著舉足輕重的作用。
目前，數(shù)據(jù)結(jié)構(gòu)不僅是計(jì)算機(jī)專業(yè)的必修課程，而且大多數(shù)高等院校的非計(jì)算機(jī)專業(yè)也將數(shù)據(jù)結(jié)構(gòu)作為主干課程。數(shù)據(jù)結(jié)構(gòu)不僅是計(jì)算機(jī)專業(yè)考研的必考科目之一，還是全國計(jì)算機(jī)等級(jí)考試、軟件資格(水平)考試的主要考試內(nèi)容。
本書全面介紹數(shù)據(jù)結(jié)構(gòu)中的線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)及查找、排序技術(shù)，通過圖和實(shí)例的形式分析了算法思想，以便讀者理解和掌握。相信學(xué)完本書之后，讀者將具備一定的抽象思維的能力和算法設(shè)計(jì)的能力。
本書的特點(diǎn)
1．內(nèi)容全面，講解詳細(xì)
本書涵蓋了數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)的所有知識(shí)點(diǎn)，對于每一種數(shù)據(jù)結(jié)構(gòu)，都使用了所有可能的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)進(jìn)行描述，并對算法的實(shí)現(xiàn)盡量多地采用多種實(shí)現(xiàn)方式，如遞歸和非遞歸、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，從而使讀者對算法的理解更加深刻。
2．層次清晰，結(jié)構(gòu)合理
本書將數(shù)據(jù)結(jié)構(gòu)按章、節(jié)劃分知識(shí)點(diǎn)，將知識(shí)點(diǎn)細(xì)化，易于讀者理解。在知識(shí)點(diǎn)的講解過程中，循序漸進(jìn)，由淺入深，先引出概念，然后用例子說明，最后是算法描述與程序?qū)崿F(xiàn)。這樣的層次十分易于讀者的理解和消化。
3．結(jié)合圖表，敘述簡單
在每個(gè)概念提出后，都結(jié)合圖表和例子加以說明以方便讀者理解。在內(nèi)容的描述上，普遍采用短句子、易于理解的語言，而避免使用復(fù)雜句子和晦澀難懂的語言。通過以上方式的描述，讀者可以更加容易和輕松地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。
4．例子典型，深入剖析
在例子的選取上，都是一些最為常見且涵蓋知識(shí)點(diǎn)豐富的典型算法。在每章的最后，都會(huì)給出一個(gè)完整的程序，對算法進(jìn)行剖析，并給出程序運(yùn)行結(jié)果，以幫助讀者分析、理解算法。
5．配有習(xí)題，鞏固知識(shí)
在每章的最后，都有一個(gè)小結(jié)，對本章的知識(shí)點(diǎn)進(jìn)行總結(jié)。為了讓讀者熟練編寫算法，本書在每章的最后都會(huì)配有一定數(shù)量的實(shí)踐題目，在學(xué)習(xí)每章的內(nèi)容之后，可以通過這些習(xí)題試著編寫算法，以鞏固本章的學(xué)習(xí)內(nèi)容。
本書的內(nèi)容
第1章：如果讀者剛接觸數(shù)據(jù)結(jié)構(gòu)，這一章將告訴您數(shù)據(jù)結(jié)構(gòu)是什么，以及本書的學(xué)習(xí)目標(biāo)、學(xué)習(xí)方法和學(xué)習(xí)內(nèi)容；另外，還介紹了本書對算法的描述方法。
第2章：主要介紹了線性表。首先講解線性表的邏輯結(jié)構(gòu)，然后介紹線性表的各種常用存儲(chǔ)結(jié)構(gòu)，在每一節(jié)均給出了算法的具體應(yīng)用。通過學(xué)習(xí)這一章，讀者可以掌握順序表、動(dòng)態(tài)鏈表和靜態(tài)鏈表的操作。
第3章：主要介紹操作受限的線性表——棧和隊(duì)列，內(nèi)容包括棧的定義，棧的基本操作及棧與遞歸的轉(zhuǎn)化，隊(duì)列的概念，順序隊(duì)列和鏈?zhǔn)疥?duì)列的運(yùn)算。
第4章：主要介紹一種特殊的線性表——串。首先介紹串的概念，然后介紹串的各種存儲(chǔ)表示，以及串的模式匹配算法。
第5章：主要介紹數(shù)組與廣義表。首先介紹數(shù)組的概念，數(shù)組(矩陣)的存儲(chǔ)結(jié)構(gòu)及運(yùn)算，幾種特殊矩陣；然后介紹廣義表的概念，廣義表的兩種存儲(chǔ)方式，廣義表的操作實(shí)現(xiàn)。
第6章：主要介紹非線性數(shù)據(jù)結(jié)構(gòu)——樹和二叉樹。首先介紹樹和二叉樹的概念，然后介紹樹和二叉樹的存儲(chǔ)表示、二叉樹的性質(zhì)、二叉樹的遍歷和線索化、樹、森林與二叉樹的轉(zhuǎn)換及哈夫曼樹。
第7章：主要介紹非線性數(shù)據(jù)結(jié)構(gòu)——圖。首先介紹圖的概念和存儲(chǔ)結(jié)構(gòu)，然后介紹圖的遍歷、最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑及最短路徑。
第8章：主要介紹數(shù)據(jù)結(jié)構(gòu)的常用技術(shù)——查找。首先介紹查找的概念，然后結(jié)合具體實(shí)例介紹各種查找算法，并給出了完整程序。
第9章：主要介紹數(shù)據(jù)結(jié)構(gòu)的常用技術(shù)——排序。首先介紹排序的相關(guān)概念，然后介紹各種排序技術(shù)，并給出了具體實(shí)現(xiàn)算法。
本書由陳銳(高級(jí)程序員)擔(dān)任主編，空軍航空大學(xué)的扶曉、北京聯(lián)合大學(xué)的劉琨、鄭春霞擔(dān)任副主編，大連外國語學(xué)院的李紹華、河南工業(yè)大學(xué)的沈獻(xiàn)念、鄭州科技學(xué)院的汪東芳和張思卿、重慶科創(chuàng)職業(yè)學(xué)院的李學(xué)國、西安文理學(xué)院的王悅、長安大學(xué)的黃美玲參編。全書由陳銳統(tǒng)稿、定稿。
在本書的出版過程中，得到了來自中原工學(xué)院的夏敏捷、山東師范大學(xué)的李忠、華中師范大學(xué)漢口分校的劉河、北京信息職業(yè)技術(shù)學(xué)院的李紅、渤海船舶職業(yè)學(xué)院的邢容、湖南婁底職業(yè)學(xué)院的劉益洪、華北水利水電學(xué)院的徐艷杰等老師的支持，在此表示衷心感謝。
由于作者水平有限，書中難免存在一些不足之處，懇請讀者批評指正。郵件地址：nwuchenrui@126.com。
編 者
第1章 數(shù)據(jù)結(jié)構(gòu)概述
1.1 數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況
1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念
1.3 算法的描述與算法的分析
1.3.1 算法的定義與特性
1.3.2 算法設(shè)計(jì)的要求
1.3.3 算法的描述
1.3.4 算法分析
1.4 關(guān)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)
習(xí)題
第2章 線性表
2.1 線性表的概念及抽象數(shù)據(jù)類型
2.1.1 線性表的定義
2.1.2 線性表的抽象數(shù)據(jù)類型
2.2 線性表的順序存儲(chǔ)及實(shí)現(xiàn)
2.2.1 順序表
2.2.2 順序表的基本運(yùn)算
2.2.3 順序表應(yīng)用舉例
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)
2.3.1 單鏈表
2.3.2 單鏈表的基本運(yùn)算
2.3.3 循環(huán)鏈表
2.3.4 雙向鏈表
2.3.5 靜態(tài)鏈表
2.4 綜合案例──一元多項(xiàng)式的相加
2.4.1 一元多項(xiàng)式的表示與存儲(chǔ)
2.4.2 一元多項(xiàng)式的相加
2.5 順序表和鏈表的比較
2.6 小結(jié)
習(xí)題
第3章 棧和隊(duì)列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的抽象數(shù)據(jù)類型
3.1.3 棧的順序表示與實(shí)現(xiàn)
3.1.4 順序棧的基本運(yùn)算
3.1.5 共享?xiàng)５膯栴}
3.1.6 棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn)
3.1.7 棧的應(yīng)用舉例
3.1.8 棧與遞歸
3.2 隊(duì)列
3.2.1 隊(duì)列的定義
3.2.2 隊(duì)列的抽象數(shù)據(jù)類型
3.2.3 隊(duì)列的表示與實(shí)現(xiàn)
3.2.4 隊(duì)列的應(yīng)用舉例
3.3 小結(jié)
習(xí)題
第4章 串
4.1 串的基本概念
4.1.1 串的基本概念
4.1.2 串的抽象數(shù)據(jù)類型
4.2 串的存儲(chǔ)實(shí)現(xiàn)
4.2.1 定長順序串
4.2.2 串的模式匹配
4.3 堆串與塊鏈串
4.3.1 堆串的存儲(chǔ)結(jié)構(gòu)
4.3.2 堆串的基本運(yùn)算
4.3.3 塊鏈串
4.4 小結(jié)
習(xí)題
第5章 數(shù)組和廣義表
5.1 數(shù)組的定義及基本操作
5.1.1 數(shù)組的定義
5.1.2 數(shù)組的抽象數(shù)據(jù)類型
5.1.3 數(shù)組的存儲(chǔ)表示
5.2 特殊矩陣的壓縮存儲(chǔ)
5.2.1 對稱矩陣
5.2.2 三角矩陣
5.2.3 帶狀矩陣
5.3 稀疏矩陣
5.3.1 稀疏矩陣的三元組表存儲(chǔ)
5.3.2 稀疏矩陣的十字鏈表存儲(chǔ)
5.4 廣義表
5.4.1 廣義表的定義
5.4.2 廣義表的存儲(chǔ)結(jié)構(gòu)
5.4.3 廣義表基本操作的實(shí)現(xiàn)
5.5 小結(jié)
習(xí)題
第6章 樹和二叉樹
6.1 樹
6.1.1 樹的定義
6.1.2 樹的基本術(shù)語
6.1.3 樹的表示形式
6.1.4 樹的抽象數(shù)據(jù)類型
6.2 二叉樹
6.2.1 二叉樹的定義與性質(zhì)
6.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)
6.2.3 二叉樹的基本操作
6.3 二叉樹的遍歷
6.3.1 二叉樹的遞歸遍歷
6.3.2 二叉樹的遍歷算法的應(yīng)用
6.3.3 二叉樹非遞歸遍歷
6.4 二叉樹的線索化
6.4.1 二叉樹的線索化定義
6.4.2 二叉樹的線索化
6.4.3 線索二叉樹的遍歷
6.5 樹和森林
6.5.1 樹的存儲(chǔ)結(jié)構(gòu)
6.5.2 樹、森林與二叉樹的轉(zhuǎn)換
6.5.3 樹的遍歷
6.5.4 森林的遍歷
6.6 哈夫曼樹及其應(yīng)用
6.6.1 哈夫曼樹
6.6.2 哈夫曼編碼
6.6.3 哈夫曼編碼算法的實(shí)現(xiàn)
6.7 小結(jié)
習(xí)題
第7章 圖
7.1 圖的基本概念
7.1.1 圖的定義
7.1.2 圖的相關(guān)概念
7.1.3 圖的抽象數(shù)據(jù)類型
7.2 圖的存儲(chǔ)結(jié)構(gòu)
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.3.3 圖的遍歷應(yīng)用舉例
7.4 圖的應(yīng)用
7.4.1 圖的連通性問題
7.4.2 有向無環(huán)圖
7.4.3 最短路徑
7.5 小結(jié)
習(xí)題
第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.4 哈希表的查找
8.4.1 哈希函數(shù)的構(gòu)造方法
8.4.2 處理沖突的方法
8.4.3 哈希表的查找與分析
8.4.4 哈希表的應(yīng)用舉例
8.5 小結(jié)
習(xí)題
第9章 排序
9.1 排序的基本概念
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 希爾排序
9.3 交換排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 選擇排序
9.4.1 簡單選擇排序
9.4.2 堆排序
9.5 歸并排序
9.6 基數(shù)排序
9.6.1 基數(shù)排序的算法思想
9.6.2 基數(shù)排序的算法實(shí)現(xiàn)
9.7 各種排序的性能比較
9.8 小結(jié)
習(xí)題
參考文獻(xiàn)
