數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)(附光盤(pán))
定 價(jià):45 元
叢書(shū)名:高等院校信息管理與信息系統(tǒng)專(zhuān)業(yè)系列教材
- 作者:嚴(yán)蔚敏 ,陳文博 著
- 出版時(shí)間:2011/5/1
- ISBN:9787302243908
- 出 版 社:清華大學(xué)出版社
- 中圖法分類(lèi):TP311.12
- 頁(yè)碼:391
- 紙張:膠版紙
- 版次:1
- 開(kāi)本:16開(kāi)
《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)》從數(shù)據(jù)類(lèi)型的角度,分別討論了四大類(lèi)型的數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲(chǔ)表示及其應(yīng)用。此外,還專(zhuān)辟一章,以若干實(shí)例闡述以抽象數(shù)據(jù)類(lèi)型為中心的程序設(shè)計(jì)方法。書(shū)中每一章后都配有適量的習(xí)題,以供讀者復(fù)習(xí)提高之用。第1~9章還專(zhuān)門(mén)設(shè)有“解題指導(dǎo)與示例”一節(jié)內(nèi)容,不僅給出答案,對(duì)大部分題目提供了詳盡的解答注釋?zhuān)黄渲械囊恍┧惴}還給出了多種解法。書(shū)中主要算法和最后一章的實(shí)例中的全部程序代碼均收錄在與《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)》配套的光盤(pán)之中。
《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)》內(nèi)容豐富,概念闡述細(xì)致清楚,可作為高等院校計(jì)算機(jī)類(lèi)專(zhuān)業(yè)和信息類(lèi)相關(guān)專(zhuān)業(yè)“數(shù)據(jù)結(jié)構(gòu)”或“軟件基礎(chǔ)”課程的本科教材。另外,對(duì)于準(zhǔn)備參加計(jì)算機(jī)類(lèi)研究生專(zhuān)業(yè)課統(tǒng)考的考生,《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)》也可作為應(yīng)試的解題指導(dǎo)。
“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論基礎(chǔ),它所討論的知識(shí)內(nèi)容和提倡的技術(shù)方法,無(wú)論對(duì)進(jìn)一步學(xué)習(xí)計(jì)算機(jī)領(lǐng)域的其他課程,還是對(duì)從事軟件工程的開(kāi)發(fā),都有著不可替代的作用。“數(shù)據(jù)結(jié)構(gòu)”是公認(rèn)的計(jì)算機(jī)學(xué)科本科和大專(zhuān)的核心課程,也是計(jì)算機(jī)類(lèi)專(zhuān)業(yè)“考研”和等級(jí)水平考試的必考科目,而且正逐漸發(fā)展成為眾多理工專(zhuān)業(yè)的熱門(mén)選修課。本書(shū)正是針對(duì)這一背景和社會(huì)需求編寫(xiě)的教材性讀物,在內(nèi)容選材方面,更多地考慮了普通高等院校計(jì)算機(jī)專(zhuān)業(yè)和信息類(lèi)相關(guān)專(zhuān)業(yè)的讀者的實(shí)際需要。
為了便于讀者理解,書(shū)中對(duì)數(shù)據(jù)結(jié)構(gòu)眾多知識(shí)點(diǎn)的來(lái)龍去脈都做了詳細(xì)的解釋和說(shuō)明,并配有大量的算法實(shí)例穿插其間。書(shū)的最后還專(zhuān)門(mén)辟出一章,用來(lái)講解數(shù)據(jù)結(jié)構(gòu)在解決實(shí)際問(wèn)題中的應(yīng)用示例,便于讀者舉一反三?紤]到計(jì)算機(jī)技術(shù)的發(fā)展和進(jìn)步,在內(nèi)容的編排方面盡量做到推陳出新,實(shí)例也力求新穎,以適應(yīng)技術(shù)發(fā)展的潮流。
本書(shū)的第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型等基本概念和算法;第2章、第4章至第7章從數(shù)據(jù)類(lèi)型的角度,分別討論線性表、棧和隊(duì)列、串和數(shù)組、二叉樹(shù)和樹(shù)以及圖和廣義表等數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲(chǔ)表示及其應(yīng)用;第3章和第8章分別討論排序和查找表的各種實(shí)現(xiàn)方法,其中除介紹各種實(shí)現(xiàn)方法外,并著重對(duì)算法的時(shí)間效率做了定性的分析,對(duì)算法的應(yīng)用場(chǎng)合及適用范圍進(jìn)行了比較和介紹;第9章討論常用的文件結(jié)構(gòu);第10章則以8個(gè)數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用為例,闡述以抽象數(shù)據(jù)類(lèi)型為中心的程序設(shè)計(jì)方法。書(shū)的每一章都配有適量的習(xí)題,供讀者復(fù)習(xí)提高之用。
本書(shū)在編排方面注意了數(shù)據(jù)結(jié)構(gòu)本身的內(nèi)在聯(lián)系和從易到難的學(xué)習(xí)規(guī)律。例如,將排序安排在第3章,因?yàn)閷?duì)讀者來(lái)說(shuō),排序的內(nèi)容比較容易理解,而且所涉及的數(shù)據(jù)結(jié)構(gòu)主要是線性結(jié)構(gòu);又如對(duì)棧和隊(duì)列的學(xué)習(xí)重點(diǎn)是它們的應(yīng)用,因此在第4章里更多地列舉了棧和隊(duì)列的應(yīng)用例子;在第5章中,結(jié)合C語(yǔ)言的串類(lèi)型講解串結(jié)構(gòu)的知識(shí)內(nèi)容,以使實(shí)際和理論在應(yīng)用中和諧統(tǒng)一起來(lái),等等。雖然廣義表屬線性結(jié)構(gòu),但由于它的“遞歸”特性,使得涉及廣義表操作的算法和樹(shù)更相似,因此將它放在圖之后進(jìn)行討論,以降低理解難度。第10章的內(nèi)容相當(dāng)于“數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)指導(dǎo)”,本意是為學(xué)生提供一個(gè)“綜合利用數(shù)據(jù)結(jié)構(gòu)知識(shí)編制小型軟件”的規(guī)范示例。
全書(shū)采用了類(lèi)C語(yǔ)言作為數(shù)據(jù)結(jié)構(gòu)和操作算法的描述工具,它是C語(yǔ)言的一個(gè)精選子集,同時(shí)又采用了C++對(duì)C的非面向?qū)ο蟮脑鰪?qiáng)功能。例如,動(dòng)態(tài)分配和釋放順序存儲(chǔ)結(jié)構(gòu)的空間;利用引用參數(shù)傳遞函數(shù)運(yùn)算的結(jié)果;使用默認(rèn)參數(shù)以簡(jiǎn)化函數(shù)參數(shù)表的描述等。這些措施使數(shù)據(jù)類(lèi)型的定義和數(shù)據(jù)結(jié)構(gòu)相關(guān)操作算法的描述更加簡(jiǎn)明清晰,可讀性更好,轉(zhuǎn)變成C程序也極為方便。另一方面又埋下了伏筆,把類(lèi)型定義和操作算法稍加技術(shù)處理,就很容易將其封裝成類(lèi),并進(jìn)一步轉(zhuǎn)化成面向?qū)ο蟮某绦蚰P汀?br /> 從課程性質(zhì)上講,“數(shù)據(jù)結(jié)構(gòu)”是一門(mén)專(zhuān)業(yè)技術(shù)基礎(chǔ)課。它的教學(xué)要求應(yīng)當(dāng)是:學(xué)會(huì)從問(wèn)題入手,分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性,以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的操作算法,并初步掌握時(shí)間和空間分析技術(shù)。另一方面,本課程的學(xué)習(xí)過(guò)程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程,要求學(xué)生會(huì)書(shū)寫(xiě)符合軟件工程規(guī)范的文件,編寫(xiě)的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀,能上機(jī)調(diào)試并排除錯(cuò)誤。數(shù)據(jù)結(jié)構(gòu)比高級(jí)程序設(shè)計(jì)語(yǔ)言課有著更高的要求,它重在培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。事實(shí)一再證明,任何具有創(chuàng)新成分的軟件成果都離不開(kāi)數(shù)據(jù)的抽象和在數(shù)據(jù)抽象基礎(chǔ)上的算法描述。數(shù)據(jù)抽象能力是一種創(chuàng)造性的思維活動(dòng),是任何軟件開(kāi)發(fā)工具也無(wú)法取代的。本書(shū)將通過(guò)不同層次的應(yīng)用示例培養(yǎng)學(xué)生逐步掌握數(shù)據(jù)抽象的能力,學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型的使用方法,為今后的學(xué)習(xí)和提高編程水平打下扎實(shí)的基礎(chǔ)。
本書(shū)可作為計(jì)算機(jī)類(lèi)專(zhuān)業(yè)的本科教材,也可以作為電子信息類(lèi)相關(guān)專(zhuān)業(yè)的選修教材,教授可為40至60學(xué)時(shí),另外應(yīng)留有一定的時(shí)間供學(xué)生完成適量的上機(jī)作業(yè)。本書(shū)在編寫(xiě)方面以通俗易懂為其宗旨,特別注意了技術(shù)細(xì)節(jié)的交代,以便于自學(xué),故也可作為從事計(jì)算機(jī)應(yīng)用等工作的科技人員參考和查閱用書(shū)。在學(xué)習(xí)本書(shū)時(shí)應(yīng)至少掌握一門(mén)高級(jí)程序設(shè)計(jì)的知識(shí),如掌握的是C語(yǔ)言則最為理想;若能具有初步的離散數(shù)學(xué)和概率論的知識(shí),對(duì)書(shū)中某些內(nèi)容的理解會(huì)更容易。學(xué)習(xí)本書(shū)的同時(shí)還可把《數(shù)據(jù)結(jié)構(gòu)》 (C語(yǔ)言版)作為配套參考用書(shū)。
與本書(shū)配套的光盤(pán)中含有書(shū)中所有算法和最后一章應(yīng)用示例的全部源程序,可在Visual C++ 5.0或6.0的環(huán)境下編譯執(zhí)行,讀者還可改變其中的輸入數(shù)據(jù),以觀察程序?qū)Σ煌斎氲膱?zhí)行結(jié)果。為了便于讀者理解算法,在光盤(pán)中還為部分算法配有執(zhí)行過(guò)程的示例演示。
應(yīng)當(dāng)感謝因特網(wǎng),在本書(shū)的寫(xiě)作過(guò)程中,通過(guò)E-mail傳送書(shū)稿使不在同一地方工作的兩位作者可以做到隨時(shí)交換意見(jiàn)并頻繁修改書(shū)稿,以便使本書(shū)內(nèi)容盡可能地做到令讀者滿(mǎn)意。但因時(shí)間倉(cāng)促,仍有不盡如人意之處,請(qǐng)讀者和同行賜教。
在寫(xiě)作本書(shū)的過(guò)程中,劉巍、錢(qián)大智、李莉、樓健、徐佳、金穎、林京秀、王福建等同學(xué)參加了第10章有關(guān)程序的調(diào)試工作,在此表示感謝。
嚴(yán)蔚敏 清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系
陳文博 北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院
2000年7月
第1章 緒論
1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇
1.2 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念
1.2.1 基本概念和術(shù)語(yǔ)
1.2.2 數(shù)據(jù)結(jié)構(gòu)(data structures)
1.2.3 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型
1.3 算法及其描述和分析
1.3.1 算法
1.3.2 算法的描述
1.3.3 算法效率的衡量方法和準(zhǔn)則
1.3.4 算法的存儲(chǔ)空間需求
解題指導(dǎo)與示例
習(xí)題
第2章 線性表
2.1 線性表的類(lèi)型定義
2.1.1 線性表的定義
2.1.2 線性表的基本操作
2.2 線性表的順序表示和實(shí)現(xiàn)
2.2.1 順序表--線性表的順序存儲(chǔ)表示
2.2.2 順序表中基本操作的實(shí)現(xiàn)
2.2.3 順序表其他算法舉例
2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
2.3.1 單鏈表和指針
2.3.2 單鏈表的基本操作
2.3.3 單鏈表的其他操作舉例
2.3.4 循環(huán)鏈表
2.3.5 雙向鏈表
2.4 有序表
2.5 順序表和鏈表的綜合比較
解題指導(dǎo)與示例
習(xí)題
第3章 排序
3.1 排序的基本概念
3.2 簡(jiǎn)單排序方法
3.2.1 插入排序
3.2.2 起泡排序
3.3 先進(jìn)排序方法
3.3.1 快速排序
3.3.2 歸并排序
3.3.3 堆排序
3.4 基數(shù)排序
3.5 各種排序方法的綜合比較
解題指導(dǎo)與示例
習(xí)題
第4章 棧和隊(duì)列
4.1 棧
4.1.1 棧的結(jié)構(gòu)特點(diǎn)和操作
4.1.2 棧的表示和操作的實(shí)現(xiàn)
4.2 棧的應(yīng)用舉例
4.3 隊(duì)列
4.3.1 隊(duì)列的結(jié)構(gòu)特點(diǎn)和操作
4.3.2 隊(duì)列的表示和操作的實(shí)現(xiàn)
4.4 隊(duì)列應(yīng)用舉例
解題指導(dǎo)與示例
習(xí)題
第5章 串和數(shù)組
5.1 串的定義和操作
5.2 串的表示和實(shí)現(xiàn)
5.2.1 定長(zhǎng)順序存儲(chǔ)表示
5.2.2 堆分配存儲(chǔ)表示
5.2.3 塊鏈存儲(chǔ)表示
5.3 正文模式匹配
5.4 正文編輯--串操作應(yīng)用舉例
5.5 數(shù)組
5.5.1 數(shù)組的定義和操作
5.5.2 數(shù)組的順序表示和實(shí)現(xiàn)
5.5.3 數(shù)組的應(yīng)用
5.6 矩陣的壓縮存儲(chǔ)
5.6.1 特殊形狀矩陣的存儲(chǔ)表示
5.6.2 隨機(jī)稀疏矩陣的存儲(chǔ)壓縮
解題指導(dǎo)與示例
習(xí)題
第6章 二叉樹(shù)和樹(shù)
6.1 二叉樹(shù)
6.1.1 二叉樹(shù)的定義和基本術(shù)語(yǔ)
6.1.2 二叉樹(shù)的幾個(gè)基本性質(zhì)
6.1.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
6.2 二叉樹(shù)遍歷
6.2.1 問(wèn)題的提出
6.2.2 遍歷算法描述
6.2.3 二叉樹(shù)遍歷應(yīng)用舉例
6.2.4 線索二叉樹(shù)
6.3 樹(shù)和森林
6.3.1 樹(shù)和森林的定義
6.3.2 樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)
6.3.3 樹(shù)和森林的遍歷
6.4 樹(shù)的應(yīng)用
6.4.1 堆排序的實(shí)現(xiàn)
6.4.2 二叉排序樹(shù)
6.4.3 赫夫曼樹(shù)及其應(yīng)用
解題指導(dǎo)與示例
習(xí)題
第7章 圖和廣義表
7.1 圖的定義和術(shù)語(yǔ)
7.2 圖的存儲(chǔ)結(jié)構(gòu)
7.2.1 圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示
7.2.2 圖的鄰接表存儲(chǔ)表示
7.3 圖的遍歷
7.3.1 深度優(yōu)先搜索遍歷圖
7.3.2 廣度優(yōu)先搜索遍歷圖
7.4 連通網(wǎng)的最小生成樹(shù)
7.5 單源最短路徑
7.6 拓?fù)渑判?br />7.7 關(guān)鍵路徑
7.8 廣義表
7.8.1 廣義表的定義
7.8.2 廣義表的存儲(chǔ)結(jié)構(gòu)
7.8.3 廣義表的遍歷
解題指導(dǎo)與示例
習(xí)題
第8章 查找表
8.1 靜態(tài)查找表
8.1.1 順序查找
8.1.2 折半查找
8.1.3 分塊查找
8.2 動(dòng)態(tài)查找表
8.2.1 二叉查找樹(shù)
8.2.2 鍵樹(shù)
8.3 哈希表及其查找
8.3.1 什么是哈希表
8.3.2 構(gòu)造哈希函數(shù)的幾種方法
8.3.3 處理沖突的方法和建表示例
8.3.4 哈希表的查找及其性能分析
8.3.5 哈希表的應(yīng)用舉例
解題指導(dǎo)與示例
習(xí)題
第9章 文件
9.1 基本概念
9.1.1 外存儲(chǔ)器簡(jiǎn)介
9.1.2 有關(guān)文件的基本概念
9.2 順序文件
9.2.1 存儲(chǔ)在順序存儲(chǔ)器上的文件
9.2.2 存儲(chǔ)在直接存儲(chǔ)器上的文件
9.3 索引文件
9.3.1 B樹(shù)
9.3.2 B?+ 樹(shù)和索引順序文件
9.4 哈希文件
9.4.1 文件組織方式
9.4.2 文件的操作
9.5 多關(guān)鍵碼文件
9.5.1 倒排文件
9.5.2 索引鏈接文件
解題指導(dǎo)與示例
習(xí)題
第10章 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)示例
10.1 抽象數(shù)據(jù)類(lèi)型
10.2 從問(wèn)題到程序的求解過(guò)程
10.2.1 建立數(shù)據(jù)結(jié)構(gòu)模型設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型
10.2.2 算法設(shè)計(jì)
10.2.3 實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型
10.2.4 編制程序代碼并進(jìn)行靜態(tài)測(cè)試和動(dòng)態(tài)調(diào)試
10.3 程序的規(guī)范說(shuō)明
10.4 應(yīng)用示例分析
10.4.1 含并、交和差運(yùn)算的集合類(lèi)型
10.4.2 最佳任務(wù)分配方案求解
10.4.3 排隊(duì)問(wèn)題的系統(tǒng)仿真
10.4.4 十進(jìn)制四則運(yùn)算計(jì)算器
10.4.5 自行車(chē)零部件庫(kù)的庫(kù)存模型
10.4.6 教務(wù)課程計(jì)劃的輔助制定
10.4.7 一個(gè)小型全文檢索模型
10.4.8 汽車(chē)牌照的快速查找
實(shí)習(xí)題
實(shí)習(xí)一 鏈表的維護(hù)與文件形式的保存
實(shí)習(xí)二 用回溯法求解“穩(wěn)定婚配”問(wèn)題
實(shí)習(xí)三 以隊(duì)列實(shí)現(xiàn)的仿真技術(shù)預(yù)測(cè)理發(fā)館的經(jīng)營(yíng)狀況
實(shí)習(xí)四 利用樹(shù)形結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢(xún)
實(shí)習(xí)五 管道鋪設(shè)施工的最佳方案選擇
實(shí)習(xí)六 使用哈希表技術(shù)判別兩個(gè)源程序的相似性
附錄 算法一覽表
參考文獻(xiàn)