書????名 | 算法設(shè)計與數(shù)據(jù)結(jié)構(gòu) | 作????者 | Kleinberg |
---|---|---|---|
出版社 | Kleinberg | 出版時間 | 2005年 |
ISBN | 978-0-321-29535-4 [1]? |
本書是近年來關(guān)于算法設(shè)計和分析的不可多得的優(yōu)秀教材。本書圍繞算法設(shè)計技術(shù)組織素材,對每種算法技術(shù)選擇了多個典型范例進(jìn)行分析。本書將直觀性與嚴(yán)謹(jǐn)性完美地結(jié)合起來。每章從實際問題出發(fā),經(jīng)過具體、深入、細(xì)致的分析,自然且富有啟發(fā)性地引出相應(yīng)的算法設(shè)計思想,并對算法的正確性、復(fù)雜性進(jìn)行恰當(dāng)?shù)姆治觥⒄J(rèn)證。本書覆蓋的面較寬,凡屬串行算法的經(jīng)典論題都有涉及,并且論述深入有新意。全書共200多道豐富而精彩的習(xí)題是本書的重要組成部分,也是本書的突出特色之一。
本書特點:
本教材內(nèi)容非常豐富,不但深入系統(tǒng)地闡述了算法設(shè)計與分析的理論,而且給出了大量的典型范例和參考文獻(xiàn)。
本教材以算法為主線來處理算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。這種安排突出了算法設(shè)計的中心思想,避免了與數(shù)據(jù)結(jié)構(gòu)課程在內(nèi)容上的重復(fù),更加適合于國內(nèi)的教學(xué)計劃。
本教材的敘述和選材非常適合教學(xué)。內(nèi)容由淺入深,由具體到抽象,從算法設(shè)計技術(shù)與分析方法自然過渡到計算復(fù)雜性理論,選配了大量難度適當(dāng)?shù)木毩?xí),并給出求解范例。
about the authors
preface.
1 introduction: some representative problems
1.1 a first problem: stable matching
1.2 five representative problems
solved exercises
excercises
notes and further reading
2 basics of algorithms analysis
2.1 computational tractability
2.2 asymptotic order of growth notation
2.3 implementing the stable matching algorithm using lists and arrays
2.4 a survey of common running times
2.5 a more complex data structure: priority queues
solved exercises
exercises
notes and further reading
3 graphs
3.1 basic definitions and applications
3.2 graph connectivity and graph traversal
等 2100433B
中文名: 算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)
原名: Algorithm Design
圖書分類: 軟件
資源格式: PDF
版本: 英文掃描版
地區(qū): 美國
語言: 英文
數(shù)據(jù)結(jié)構(gòu)中的是樹形的結(jié)構(gòu)有哪些,算法叫什么名字?
基礎(chǔ)類:二叉搜索(排序)樹,線索二叉樹,哈夫曼樹(最優(yōu)二叉樹),二叉堆平衡樹類:AVL,紅黑樹,2-3樹,2-3-4樹,B樹,B+樹,B-樹,treap,SBT。優(yōu)先隊列類:左高樹(左偏樹,可并堆,斜...
怎樣將數(shù)據(jù)結(jié)構(gòu)中的算法代碼轉(zhuǎn)換成純C語言程序
1、如果算法描述已經(jīng)很徹底了,只要補(bǔ)充變量定義,等語言細(xì)節(jié)就可以,把算法描述轉(zhuǎn)化為各種編程語言了。如果只是泛泛而論,自己去把算法轉(zhuǎn)換成偽代碼描述,或者流程圖之類的,然后再用C語言實現(xiàn)。2、算法只是一種...
何謂數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成,即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成,以什么方式構(gòu)成,呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的...
格式:pdf
大?。?span id="uj24ypg" class="single-tag-height">19KB
頁數(shù): 2頁
評分: 4.5
本文從教師隊伍建設(shè)、教學(xué)內(nèi)容、教學(xué)方法、教材建設(shè)以及教學(xué)管理等方面總結(jié)了北京市精品課程\"數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計\"的建設(shè)與實踐過程。教學(xué)實踐證明,該課程符合信息技術(shù)發(fā)展的需要,為學(xué)生繼續(xù)學(xué)習(xí)和可持續(xù)發(fā)展奠定了良好的基礎(chǔ)。
格式:pdf
大?。?span id="zxk1ni9" class="single-tag-height">19KB
頁數(shù): 未知
評分: 4.6
《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》是理工科學(xué)生必修的一門計算機(jī)基礎(chǔ)核心課程。根據(jù)《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》課程的具體特點,從教學(xué)課程和實驗兩個大方面入手,提出了包括教學(xué)內(nèi)容、教學(xué)方法及實驗方法的改革研究方案。通過對課程內(nèi)容的設(shè)計以及實驗方法的創(chuàng)新,能夠提高學(xué)生的學(xué)習(xí)積極性和興趣,增加學(xué)生的綜合能力,達(dá)到該課程最終教學(xué)的目的。
前言
第1章 緒論
1.1 數(shù)據(jù)結(jié)構(gòu)的實踐意義
1.2 數(shù)據(jù)結(jié)構(gòu)的理論意義
1.3 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容和關(guān)鍵問題
習(xí)題
第2章 線性表
2.1 線性表的概念及抽象數(shù)據(jù)類型定義
2.2 線性表的順序存儲
2.3 線性表的鏈?zhǔn)酱鎯?/p>
2.4 線性表的應(yīng)用--一元多項式的表示及相加
2.5 順序表與鏈表的綜合比較
習(xí)題
第3章 棧和隊列
3.1 棧
3.2 隊列
習(xí)題
第4章 串
4.1 串的定義與操作
4.2 串的存儲結(jié)構(gòu)及操作
4.3 串操作應(yīng)用舉例
習(xí)題
第5章 數(shù)組和廣義表
5.1 數(shù)組的定義
5.2 數(shù)組的順序表示和實現(xiàn)
5.3 矩陣的壓縮存儲
5.4 廣義表
習(xí)題
第6章 樹
6.1 樹的定義、操作及基本術(shù)語
6.2 二叉樹
6.3 遍歷二叉樹和線索二叉樹
6.4 樹和森林
6.5 哈夫曼樹及其應(yīng)用
習(xí)題
第7章 圖
7.1 圖定義和術(shù)語
7.2 圖的存儲結(jié)構(gòu)
7.3 圖的遍歷
7.4 圖的連通性
7.5 有向無環(huán)圖及其應(yīng)用
7.6 最短路徑
習(xí)題
第8章 查找
8.1 查找的基本概念
8.2 靜態(tài)查找表
8.3 動態(tài)查找表
8.4 哈希表
習(xí)題
第9章 排序
9.1 概述
9.2 插入排序
9.3 交換排序
9.4 選擇排序
9.5 歸并排序
9.6 外部排序簡介
習(xí)題
第10章 文件
10.1 基本概念
10.2 順序文件
10.3 索引文件
10.4 ISAM文件和VSAM文件
10.5 直接存取文件(散列文件)
習(xí)題
第11章 算法設(shè)計策略
11.1 分而治之(DivideandConqureAlgorithm)
11.2 貪心算法(GreedyAlgorithm)
11.3 動態(tài)規(guī)劃算法(DynamicProgramming)
11.4 狀態(tài)搜索策略(StateSearch)
11.5 回溯算法(BacktrakingAlgorithm)
11.6 隨機(jī)算法(RandomAlgorithm)
11.7 算法設(shè)計中關(guān)鍵與技巧
習(xí)題
參考文獻(xiàn)
……
第1章 緒論 1
1.1 預(yù)備知識 1
1.1.1 集合的笛卡兒積 1
1.1.2 二元關(guān)系 2
1.1.3 二元關(guān)系的基本性質(zhì)和幾種重要關(guān)系 3
1.2 什么是數(shù)據(jù)結(jié)構(gòu) 4
1.2.1 從實際問題理解數(shù)據(jù)結(jié)構(gòu) 4
1.2.2 數(shù)據(jù)結(jié)構(gòu)所討論的內(nèi)容 6
1.2.3 如何表示數(shù)據(jù)結(jié)構(gòu) 9
1.3 抽象數(shù)據(jù)類型 10
1.3.1 什么是抽象數(shù)據(jù)類型 10
1.3.2 抽象數(shù)據(jù)類型的定義與實現(xiàn) 12
1.4 算法與算法分析 13
1.4.1 什么是算法 13
1.4.2 算法描述 15
1.4.3 常用的算法設(shè)計方法 16
1.4.4 算法分析 21
習(xí)題 24
上機(jī)練習(xí)題 26
第2章 線性表的順序存儲及其運算 27
2.1 線性表的概念 27
2.1.1 什么是線性表 27
2.1.2 線性表的抽象數(shù)據(jù)類型 29
2.2 順序表及其運算實現(xiàn) 30
2.2.1 線性表的順序存儲--順序表 30
2.2.2 順序表的基本運算 31
2.2.3 順序表應(yīng)用例--求子集 36
2.3 棧 36
2.3.1 什么是棧 37
2.3.2 棧的抽象數(shù)據(jù)類型 39
2.3.3 順序棧及其運算 39
2.4 棧應(yīng)用 42
2.4.1 棧在優(yōu)先級處理中的應(yīng)用 42
2.4.2 棧與分治法 48
2.4.3 棧與回溯法 50
2.4.4 棧與遞歸 55
2.5 隊列 63
2.5.1 隊列及其抽象數(shù)據(jù)類型 63
2.5.2 順序隊列及其運算 64
2.5.3 隊列應(yīng)用例 68
* 2.5.4 優(yōu)先隊列 72
2.6 數(shù)組與特殊矩陣的表示 74
2.6.1 數(shù)組的順序存儲 74
2.6.2 規(guī)則矩陣的壓縮存儲 76
* 2.6.3 稀疏矩陣的三列二維數(shù)組表示--三元組順序表 78
習(xí)題 81
上機(jī)練習(xí)題 82
第3章 鏈表 83
3.1 線性表的鏈?zhǔn)酱鎯?-線性鏈表 83
3.1.1 線性鏈表的結(jié)構(gòu)特點 83
3.1.2 線性鏈表的運算 84
3.2 鏈?zhǔn)綏Ec鏈?zhǔn)疥犃?91
3.2.1 棧的鏈?zhǔn)酱鎯?-鏈?zhǔn)綏?91
3.2.2 隊列的鏈?zhǔn)酱鎯?-鏈?zhǔn)疥犃?95
3.3 循環(huán)鏈表 98
3.3.1 循環(huán)鏈表的結(jié)構(gòu)特點 98
3.3.2 循環(huán)鏈表的基本運算 99
3.3.3 鏈表應(yīng)用例 103
*3.4 多重鏈表 109
3.4.1 多重鏈表結(jié)構(gòu) 109
3.4.2 雙向鏈表 110
*3.5 廣義表 112
3.5.1 什么是廣義表 113
3.5.2 廣義表的存儲表示 114
3.5.3 廣義表的基本運算 116
習(xí)題 120
上機(jī)練習(xí)題 121
第4章 樹與二叉樹 122
4.1 樹的基本概念 122
4.1.1 什么是樹 122
4.1.2 樹的性質(zhì) 127
4.2 二叉樹 128
4.2.1 什么是二叉樹 128
4.2.2 二叉樹的基本性質(zhì) 128
4.2.3 二叉樹的抽象數(shù)據(jù)類型 131
4.2.4 二叉樹的存儲結(jié)構(gòu) 131
4.2.5 二叉樹的遍歷及其他運算 133
* 4.2.6 線索二叉樹 138
4.3 二叉樹應(yīng)用 141
4.3.1 表達(dá)式線性化 141
4.3.2 最優(yōu)二叉樹 143
4.3.3 二叉搜索樹 148
4.3.4 堆 154
* 4.3.5 二叉樹與減治法 160
4.4 樹的運算 163
4.4.1 樹的抽象數(shù)據(jù)類型 163
4.4.2 樹的存儲結(jié)構(gòu) 164
4.4.3 樹的遍歷 165
* 4.4.4 樹的其他運算 167
* 4.5 樹與回溯法 170
4.5.1 問題解的描述--解空間樹 171
4.5.2 回溯法的求解過程分析--遍歷解空間樹 172
4.5.3 回溯法求解問題的形式化描述 174
* 4.6 森林的遍歷 176
4.6.1 森林與二叉樹的轉(zhuǎn)換 176
4.6.2 森林的遍歷 177
習(xí)題 178
上機(jī)練習(xí)題 179
第5章 圖 180
5.1 圖的基本概念 180
5.1.1 圖的定義和概念 180
5.1.2 圖的抽象數(shù)據(jù)類型 184
*5.1.3 歐拉路徑 185
5.2 圖的存儲結(jié)構(gòu) 186
5.2.1 圖的鄰接矩陣表示 186
5.2.2 圖的鄰接表表示 189
*5.2.3 圖的其他表示方法 192
5.3 圖的遍歷 195
5.3.1 圖的深度優(yōu)先遍歷 195
5.3.2 圖的廣度優(yōu)先遍歷 197
5.3.3 圖遍歷的應(yīng)用 198
*5.3.4 圖的連通性 200
*5.4 有向圖與有向無環(huán)圖 201
5.4.1 有向圖的連通性和傳遞閉包 202
*5.4.2 有向無環(huán)圖和拓?fù)渑判?204
*5.4.3 關(guān)鍵路徑 207
5.5 最小生成樹 208
5.5.1 圖的生成樹與最小生成樹 209
5.5.2 普里姆(Prim)算法 210
5.5.3 克魯斯卡爾(Kruskal)算法 213
5.5.4 貪心算法 215
5.6 最短路徑問題 218
5.6.1 單源最短路徑 218
5.6.2 全源最短路徑 220
5.6.3 動態(tài)規(guī)劃算法 223
5.7 圖應(yīng)用例--城市間公路交通網(wǎng)問題 227
5.7.1 問題描述 227
5.7.2 問題求解思路 228
習(xí)題 228
上機(jī)練習(xí)題 230
第6章 查找 231
6.1 線性查找表 231
6.1.1 順序查找 232
6.1.2 折半查找 232
*6.1.3 斐波那契查找 234
6.1.4 線性查找表的性能比較 234
6.2 二叉搜索樹查找性能 235
6.3 AVL樹 236
6.3.1 BST的旋轉(zhuǎn)操作 237
6.3.2 AVL樹的插入和平衡化旋轉(zhuǎn) 238
*6.3.3 AVL樹的刪除 240
*6.3.4 AVL樹的性能 241
6.4 B-樹 242
6.4.1 多路動態(tài)搜索樹 242
6.4.2 B-樹的查找 243
6.4.3 B-樹的插入 244
*6.4.4 B-樹的刪除 245
6.5 散列方法 246
6.5.1 散列技術(shù) 246
6.5.2 散列函數(shù) 247
6.5.3 沖突處理 250
6.5.4 散列的刪除 252
6.5.5 散列的性能 252
6.6 靜態(tài)索引結(jié)構(gòu) 253
6.6.1 索引查找 253
6.6.2 索引存儲方式 254
*6.6.3 索引文件結(jié)構(gòu) 255
6.7 模式匹配 258
6.7.1 字符串及其ADT 258
6.7.2 字符串的存儲表示 259
6.7.3 字符串的模式匹配及簡單匹配算法 259
6.7.4 字符串匹配的KMP算法 260
習(xí)題 263
上機(jī)練習(xí)題 264
第7章 排序 265
7.1 排序的概念及算法性能分析 265
7.2 基本排序方法 266
7.2.1 冒泡排序 267
7.2.2 插入排序 268
7.2.3 直接選擇排序 272
7.2.4 基本排序方法的比較 273
7.3 快速排序 274
7.3.1 快速排序的過程 274
7.3.2 快速排序的性能分析 275
7.4 歸并排序 276
7.4.1 二路歸并 276
7.4.2 自底向上的歸并排序 276
7.4.3 自頂向下的歸并排序 278
*7.5 錦標(biāo)賽排序 279
7.6 堆排序 280
7.6.1 堆排序的思想 280
7.6.2 堆排序的實現(xiàn) 282
7.7 內(nèi)排序方法分析 283
*7.7.1 排序方法的下界 283
7.7.2 內(nèi)排序方法的比較 284
7.8 線性時間復(fù)雜度的排序算法 285
*7.8.1 計數(shù)排序 285
7.8.2 基數(shù)排序 287
7.9 外部排序 290
7.9.1 外部排序方法 290
*7.9.2 基于敗者樹的k路歸并方法 291
*7.9.3 排序--歸并的改進(jìn) 292
習(xí)題 296
上機(jī)練習(xí)題 297
實驗指導(dǎo) 298
實驗一 順序表及其應(yīng)用 299
實驗二 求解迷宮問題 301
實驗三 簡單算術(shù)表達(dá)式的處理 302
實驗四 求解簡單背包問題 303
實驗五 鏈表及其應(yīng)用 304
實驗六 實驗室機(jī)時機(jī)位的管理 305
實驗七 實現(xiàn)Huffman編碼 307
實驗八 文件管理的模擬 309
實驗九 求網(wǎng)絡(luò)站點間的最短連接 312
實驗十 查找最高分與次高分 314
實驗十一 比賽日程安排與成績統(tǒng)計 316
本書可以作為大專院校數(shù)據(jù)結(jié)構(gòu)課程的教材,也可以作為從事計算機(jī)應(yīng)用開發(fā)的科技人員的參考書。本書以清華大學(xué)電子系數(shù)據(jù)結(jié)構(gòu)講義為藍(lán)本,主要針對高等院校非計算機(jī)專業(yè)開設(shè)"數(shù)據(jù)結(jié)構(gòu)"課程的需要而編寫的。全書從應(yīng)用的角度,重點介紹數(shù)據(jù)處理中常用的數(shù)據(jù)結(jié)構(gòu)--線性表、樹與二叉樹、圖,以及基本的數(shù)據(jù)處理技術(shù)--查找和排序方法,同時通過實例把回溯法、分治法、貪心法、動態(tài)規(guī)劃法等常用的算法設(shè)計思想的應(yīng)用融入其中,把數(shù)據(jù)結(jié)構(gòu)的介紹和常用算法設(shè)計的討論緊密結(jié)合,并且輔之以充足的練習(xí)題,從而使讀者更具體、更深刻地理解各種常用的數(shù)據(jù)結(jié)構(gòu),及它們與算法之間的關(guān)系,以達(dá)到學(xué)以致用的目的。