本書在緒論部分介紹數(shù)據(jù)結(jié)構(gòu)、算法的相關(guān)概念和算法分析方法等,其后各章分別討論棧、隊列、線性表、哈希表、二叉樹、樹、森林和圖等數(shù)據(jù)結(jié)構(gòu)的定義、表示和實現(xiàn)。將查找和排序融入相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的討論中,并在二叉樹前介紹遞歸內(nèi)容。在多數(shù)章節(jié)中加入應(yīng)用實例,介紹運用數(shù)據(jù)結(jié)構(gòu)和算法進行程序設(shè)計和解決實際問題的方法,以增強讀者對基本知識的理解與掌握,有利于分析問題能力和程序設(shè)計能力的提高。全書采用C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言。
“數(shù)據(jù)結(jié)構(gòu)”是一門研究用計算機進行信息數(shù)據(jù)表示和處理的課程。一方面,信息的表示和組織直接關(guān)系到處理信息的程序的效率;另一方面,信息的處理方法往往是根據(jù)信息的組織關(guān)系來設(shè)計的。課程致力于訓(xùn)練計算機軟件開發(fā)人員運用抽象思維表示和處理數(shù)據(jù),進而以計算機程序的形式運行并獲得結(jié)果。
基于多年的數(shù)據(jù)結(jié)構(gòu)教學經(jīng)驗,編者編寫了這部教材,其具有以下特色。
1.內(nèi)容體系重構(gòu)優(yōu)化
遵循循序漸進和由易到難的教學原則,重構(gòu)、優(yōu)化了教材內(nèi)容體系。
對于線性數(shù)據(jù)結(jié)構(gòu),一改以往先介紹線性表再介紹棧和隊列的做法,先介紹接口簡單的棧和隊列,再拓展到更一般的線性表。
緊接線性結(jié)構(gòu)之后,設(shè)置“排序基礎(chǔ)”一章,介紹排序概念和基本算法,涉及遞歸的排序算法則分散于后續(xù)相關(guān)章節(jié)。類似地,對于查找結(jié)構(gòu)與算法,單獨設(shè)置“哈希表”一章,二又排序樹和平衡二叉樹以及B樹則安排在二叉樹和樹的章節(jié)中。經(jīng)典的排序和查找算法都是與具體的數(shù)據(jù)結(jié)構(gòu)相結(jié)合的,本質(zhì)上是相應(yīng)數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用,如此編排體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)與算法的緊密結(jié)合。
將教學難點“遞歸”單獨設(shè)章,介紹遞歸函數(shù)的調(diào)用原理,通過折半查找、快速排序和歸并排序3個經(jīng)典算法的討論,學習遞歸與分治的算法設(shè)計思想。作力從線性結(jié)構(gòu)到非線性結(jié)構(gòu)的過渡,廣義表為后續(xù)二叉樹和樹的學習建立了遞歸數(shù)據(jù)結(jié)構(gòu)的基本概念。
2.接口定義精簡實用
現(xiàn)有教材大多對接口的定義往往是過分追求操作集的完備,而忽略了實用性,不夠合理。基于對實際應(yīng)用的分析和歸納,本書對各種數(shù)據(jù)結(jié)構(gòu)的接口定義進行了全面的精簡與優(yōu)化,總體降低了教學難度,減少了學時。
比如,現(xiàn)有教材大多在順序表和單鏈表的接口中都含有插入和刪除第i個元素的操作,其中順序表需要移動大量數(shù)據(jù)元素,單鏈表需要找到第i-1個位置的元素。這些操作效率不高且實際應(yīng)用很少,本書已將其去掉。又如,一般二叉樹的接口操作都相當多,本書將其縮減到僅7個。
3.算法代碼可上機運行
本書采用擴展了引用形參的C語言描述數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)和接口的實現(xiàn),所有代碼無須轉(zhuǎn)換就可以上機編譯、運行和實際應(yīng)用。
吳偉民,國務(wù)院政府特殊津貼專家,廣東省計算機學會常務(wù)理事,廣東工業(yè)大學計算機學院教授。與清華大學嚴蔚敏教授合著數(shù)據(jù)結(jié)構(gòu)系列教材,曾先后榮獲國家高校優(yōu)秀教材特等獎和國家科技進步三等獎。主要研究領(lǐng)域:計算機系統(tǒng)軟件與系統(tǒng)結(jié)構(gòu),計算機系統(tǒng)逆向和介入工程技術(shù)及工具,數(shù)據(jù)結(jié)構(gòu)與算法,可視計算及程序可視化運行、調(diào)試與測評,程序設(shè)計語言和編譯系統(tǒng),虛擬機和虛擬化技術(shù),智能系統(tǒng)與電器,嵌入式系統(tǒng)等。其他主要獲獎:電子工業(yè)部科技成果二等獎、霍英東青年教師三等獎、曾憲梓高師教師三等獎、廣東省教學成果二等獎、廣東省計算機學會特等獎等。
第1章 緒論
1.1 數(shù)據(jù)抽象與數(shù)據(jù)結(jié)構(gòu)
1.1.1 抽象與結(jié)構(gòu)
1.1.2 抽象與封裝
1.1.3 程序設(shè)計中的抽象
1.1.4 數(shù)據(jù)結(jié)構(gòu)
1.2 抽象數(shù)據(jù)類型與應(yīng)用程序接口
1.2.1 抽象數(shù)據(jù)類型
1.2.2 接口和實現(xiàn)
1.2.3 良好的接口設(shè)計規(guī)則
1.3 算法和算法分析
1.3.1 算法和算法描述
1.3.2 算法分析基礎(chǔ)
1.4 數(shù)據(jù)結(jié)構(gòu)與算法的描述與實現(xiàn)
1.4.1 一維數(shù)組
1.4.2 指針與結(jié)構(gòu)體
習題1
第2章 線性數(shù)據(jù)結(jié)構(gòu)
2.1 典型線性數(shù)據(jù)結(jié)構(gòu)
2.1.1 線性結(jié)構(gòu)的邏輯描述
2.1.2 線性結(jié)構(gòu)的存儲表示
2.2 順序棧
2.2.1 棧的順序表示和實現(xiàn)
2.2.2 應(yīng)用舉例
2.3 循環(huán)隊列
2.3.1 隊列的順序表示
2.3.2 一循環(huán)隊列的實現(xiàn)
2.3.3 應(yīng)用舉例
2.4 順序表
2.4.1 線性表的順序表示與實現(xiàn)
2.4.2 一元稀疏多項式
2.4.3 稀疏矩陣
2.5 鏈棧與鏈隊列
2.5.1 鏈棧
2.5.2 鏈隊列
2.6 線性表的鏈式表示和實現(xiàn)
2.6.1 單鏈表
2.6.2 雙向鏈表
2.6.3 循環(huán)鏈表
2.7 線性表兩種存儲結(jié)構(gòu)的比較
習題2
第3章 排序基礎(chǔ)
3.1 排序的概念與分類
3.1.1 排序的概念
3.1.2 排序的分類
3.2 直接插入排序
3.3 希爾排序
3.4 基數(shù)排序
3.4.1 多關(guān)鍵字排序
3.4.2 基數(shù)排序
習題3
第4章 晗希表
4.1 哈希表的概念
4.2 哈希函數(shù)的構(gòu)造方法
4.2.1 直接定址法
4.2.2 除留余數(shù)法
4.2.3 數(shù)字分析法
4.2.4 折疊法
4.2.5 平方取中法
4.3 處理沖突的方法
4.3.1 鏈地址法
4.3.2 開放定址法
4.4 哈希表的實現(xiàn)
4.4.1 鏈地址哈希表的實現(xiàn)
4.4.2 開放定址哈希表的實現(xiàn)
4.5 哈希表的查找性能
習題4
第5章 遞歸
5.1 遞歸基礎(chǔ)
5.1.1 漢諾塔問題
5.1.2 遞歸函數(shù)執(zhí)行過程
5.2 遞歸與分治
5.2.1 分治法
5.2.2 折半查找
5.2.3 歸并排序
5.2.4 快速排序
5.3 遞歸與迭代
5.3.1 迭代三要素
5.3.2 迭代與遞歸的聯(lián)系與區(qū)別
5.4 廣義表
5.4.1 廣義表的定義
5.4.2 廣義表的存儲結(jié)構(gòu)
5.4.3 廣義表常用操作的實現(xiàn)
習題5
第6章 二叉樹
6.1 二叉樹的概念和性質(zhì)
6.1.1 二叉樹的定義和術(shù)語
6.1.2 二叉樹的性質(zhì)
6.2 二叉樹的存儲結(jié)構(gòu)
6.2.1 順序存儲結(jié)構(gòu)
6.2.2 鏈式存儲結(jié)構(gòu)
6.3 遍歷二叉樹
6.3.1 二叉樹的遞歸遍歷
6.3.2 二叉樹的非遞歸遍歷
6.3.3 遍歷的應(yīng)用
6.4 堆
6.4.1 堆的定義
6.4.2 基本操作的實現(xiàn)
6.4.3 堆排序
6.5 二叉查找樹
6.5.1 二叉查找樹的定義
6.5.2 二叉查找樹的查找
6.5.3 二叉查找樹的插入
6.5.4 二叉查找樹的刪除
6.5.5 二叉查找樹的查找性能
6.6 平衡二叉樹
6.6.1 平衡二叉樹的定義
6.6.2 平衡二叉樹的失衡及調(diào)整
6.6.3 平衡二叉樹的插入
習題6
第7章 樹和森林
7.1 樹的定義
7.2 樹的存儲結(jié)構(gòu)
7.2.1 雙親表示法
7.2.2 雙親孩子表示法
7.2.3 孩子兄弟表示法
7.3 樹和森林的遍歷
7.4 并查集
7.5 B樹
7.5.1 B樹的定義
7.5.2 B樹的查找
7.5.3 B樹的插入
7.5.4 B樹的刪除
7.5.5 B+樹
習題7
第8章 圖
8.1 圖的基本概念
8.1.1 圖的定義
8.1.2 圖的術(shù)語
8.2 圖的存儲結(jié)構(gòu)
8.2.1 鄰接數(shù)組
8.2.2 鄰接表
8.3 圖的遍歷
8.3.1 深度優(yōu)先遍歷
8.3.2 廣度優(yōu)先遍歷
8.3.3 遍歷的應(yīng)用
8.4 最小生成樹
8.4.1 普里姆算法
8.4.2 克魯斯卡爾算法
8.5 最短路徑
8.6 拓撲排序
8.7 關(guān)鍵路徑
習題8
參考文獻