本書在緒論部分介紹數(shù)據(jù)結(jié)構(gòu)、算法的相關(guān)概念和算法分析方法等,其后各章分別討論棧、隊(duì)列、線性表、哈希表、二叉樹、樹、森林和圖等數(shù)據(jù)結(jié)構(gòu)的定義、表示和實(shí)現(xiàn)。將查找和排序融入相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的討論中,并在二叉樹前介紹遞歸內(nèi)容。在多數(shù)章節(jié)中加入應(yīng)用實(shí)例,介紹運(yùn)用數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行程序設(shè)計(jì)和解決實(shí)際問題的方法,以增強(qiáng)讀者對基本知識的理解與掌握,有利于分析問題能力和程序設(shè)計(jì)能力的提高。全書采用C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言。
“數(shù)據(jù)結(jié)構(gòu)”是一門研究用計(jì)算機(jī)進(jìn)行信息數(shù)據(jù)表示和處理的課程。一方面,信息的表示和組織直接關(guān)系到處理信息的程序的效率;另一方面,信息的處理方法往往是根據(jù)信息的組織關(guān)系來設(shè)計(jì)的。課程致力于訓(xùn)練計(jì)算機(jī)軟件開發(fā)人員運(yùn)用抽象思維表示和處理數(shù)據(jù),進(jìn)而以計(jì)算機(jī)程序的形式運(yùn)行并獲得結(jié)果。
基于多年的數(shù)據(jù)結(jié)構(gòu)教學(xué)經(jīng)驗(yàn),編者編寫了這部教材,其具有以下特色。
1.內(nèi)容體系重構(gòu)優(yōu)化
遵循循序漸進(jìn)和由易到難的教學(xué)原則,重構(gòu)、優(yōu)化了教材內(nèi)容體系。
對于線性數(shù)據(jù)結(jié)構(gòu),一改以往先介紹線性表再介紹棧和隊(duì)列的做法,先介紹接口簡單的棧和隊(duì)列,再拓展到更一般的線性表。
緊接線性結(jié)構(gòu)之后,設(shè)置“排序基礎(chǔ)”一章,介紹排序概念和基本算法,涉及遞歸的排序算法則分散于后續(xù)相關(guān)章節(jié)。類似地,對于查找結(jié)構(gòu)與算法,單獨(dú)設(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é)合。
將教學(xué)難點(diǎn)“遞歸”單獨(dú)設(shè)章,介紹遞歸函數(shù)的調(diào)用原理,通過折半查找、快速排序和歸并排序3個(gè)經(jīng)典算法的討論,學(xué)習(xí)遞歸與分治的算法設(shè)計(jì)思想。作力從線性結(jié)構(gòu)到非線性結(jié)構(gòu)的過渡,廣義表為后續(xù)二叉樹和樹的學(xué)習(xí)建立了遞歸數(shù)據(jù)結(jié)構(gòu)的基本概念。
2.接口定義精簡實(shí)用
現(xiàn)有教材大多對接口的定義往往是過分追求操作集的完備,而忽略了實(shí)用性,不夠合理;趯(shí)際應(yīng)用的分析和歸納,本書對各種數(shù)據(jù)結(jié)構(gòu)的接口定義進(jìn)行了全面的精簡與優(yōu)化,總體降低了教學(xué)難度,減少了學(xué)時(shí)。
比如,現(xiàn)有教材大多在順序表和單鏈表的接口中都含有插入和刪除第i個(gè)元素的操作,其中順序表需要移動大量數(shù)據(jù)元素,單鏈表需要找到第i-1個(gè)位置的元素。這些操作效率不高且實(shí)際應(yīng)用很少,本書已將其去掉。又如,一般二叉樹的接口操作都相當(dāng)多,本書將其縮減到僅7個(gè)。
3.算法代碼可上機(jī)運(yùn)行
本書采用擴(kuò)展了引用形參的C語言描述數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)和接口的實(shí)現(xiàn),所有代碼無須轉(zhuǎn)換就可以上機(jī)編譯、運(yùn)行和實(shí)際應(yīng)用。
吳偉民,國務(wù)院政府特殊津貼專家,廣東省計(jì)算機(jī)學(xué)會常務(wù)理事,廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院教授。與清華大學(xué)嚴(yán)蔚敏教授合著數(shù)據(jù)結(jié)構(gòu)系列教材,曾先后榮獲國家高校優(yōu)秀教材特等獎和國家科技進(jìn)步三等獎。主要研究領(lǐng)域:計(jì)算機(jī)系統(tǒng)軟件與系統(tǒng)結(jié)構(gòu),計(jì)算機(jī)系統(tǒng)逆向和介入工程技術(shù)及工具,數(shù)據(jù)結(jié)構(gòu)與算法,可視計(jì)算及程序可視化運(yùn)行、調(diào)試與測評,程序設(shè)計(jì)語言和編譯系統(tǒng),虛擬機(jī)和虛擬化技術(shù),智能系統(tǒng)與電器,嵌入式系統(tǒng)等。其他主要獲獎:電子工業(yè)部科技成果二等獎、霍英東青年教師三等獎、曾憲梓高師教師三等獎、廣東省教學(xué)成果二等獎、廣東省計(jì)算機(jī)學(xué)會特等獎等。
第1章 緒論
1.1 數(shù)據(jù)抽象與數(shù)據(jù)結(jié)構(gòu)
1.1.1 抽象與結(jié)構(gòu)
1.1.2 抽象與封裝
1.1.3 程序設(shè)計(jì)中的抽象
1.1.4 數(shù)據(jù)結(jié)構(gòu)
1.2 抽象數(shù)據(jù)類型與應(yīng)用程序接口
1.2.1 抽象數(shù)據(jù)類型
1.2.2 接口和實(shí)現(xiàn)
1.2.3 良好的接口設(shè)計(jì)規(guī)則
1.3 算法和算法分析
1.3.1 算法和算法描述
1.3.2 算法分析基礎(chǔ)
1.4 數(shù)據(jù)結(jié)構(gòu)與算法的描述與實(shí)現(xiàn)
1.4.1 一維數(shù)組
1.4.2 指針與結(jié)構(gòu)體
習(xí)題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 棧的順序表示和實(shí)現(xiàn)
2.2.2 應(yīng)用舉例
2.3 循環(huán)隊(duì)列
2.3.1 隊(duì)列的順序表示
2.3.2 一循環(huán)隊(duì)列的實(shí)現(xiàn)
2.3.3 應(yīng)用舉例
2.4 順序表
2.4.1 線性表的順序表示與實(shí)現(xiàn)
2.4.2 一元稀疏多項(xiàng)式
2.4.3 稀疏矩陣
2.5 鏈棧與鏈隊(duì)列
2.5.1 鏈棧
2.5.2 鏈隊(duì)列
2.6 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
2.6.1 單鏈表
2.6.2 雙向鏈表
2.6.3 循環(huán)鏈表
2.7 線性表兩種存儲結(jié)構(gòu)的比較
習(xí)題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ù)排序
習(xí)題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 哈希表的實(shí)現(xiàn)
4.4.1 鏈地址哈希表的實(shí)現(xiàn)
4.4.2 開放定址哈希表的實(shí)現(xiàn)
4.5 哈希表的查找性能
習(xí)題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 廣義表常用操作的實(shí)現(xiàn)
習(xí)題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 鏈?zhǔn)酱鎯Y(jié)構(gòu)
6.3 遍歷二叉樹
6.3.1 二叉樹的遞歸遍歷
6.3.2 二叉樹的非遞歸遍歷
6.3.3 遍歷的應(yīng)用
6.4 堆
6.4.1 堆的定義
6.4.2 基本操作的實(shí)現(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 平衡二叉樹的插入
習(xí)題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+樹
習(xí)題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 拓?fù)渑判?/span>
8.7 關(guān)鍵路徑
習(xí)題8
參考文獻(xiàn)