出版時(shí)間:2007年 出版社:人民郵電出版社 作者:[美]Mark Allen Weiss 頁(yè)數(shù):435 字?jǐn)?shù):787000 譯者:張懷勇
Tag標(biāo)簽:無(wú)
內(nèi)容概要
本書是數(shù)據(jù)結(jié)構(gòu)和算法分析的經(jīng)典教材,書中使用主流的程序設(shè)計(jì)語(yǔ)言C++作為具體的實(shí)現(xiàn)語(yǔ)言。書的內(nèi)容包括表、棧、隊(duì)列、樹、散列表、優(yōu)先隊(duì)列、排序、不相交集算法、圖論算法、算法分析、算法設(shè)計(jì)、攤還分析、查找樹算法、k-d樹和配對(duì)堆等。本書適合作為計(jì)算機(jī)相關(guān)專業(yè)本科生的數(shù)據(jù)結(jié)構(gòu)課程和研究生算法分析課程的教材。本科生的數(shù)據(jù)結(jié)構(gòu)課程可以使用本書第1章~第9章,多學(xué)時(shí)課程還可以講解第10章;研究生算法分析課程可以使用第6章~第12章。
作者簡(jiǎn)介
Mark Allen Weiss,1987年在普林斯頓大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位,師從著名算法大師Robert Sedgewick,現(xiàn)任美國(guó)佛羅里達(dá)國(guó)際大學(xué)計(jì)算與信息科學(xué)學(xué)院教授。他曾經(jīng)擔(dān)任全美AP(Advanced Placement)考試計(jì)算機(jī)學(xué)科委員會(huì)的主席(2000-2004)。他的主要研究方向是數(shù)據(jù)結(jié)構(gòu),算法
書籍目錄
第1章 引論 1.1 本書討論的內(nèi)容 1.2 數(shù)學(xué)知識(shí)復(fù)習(xí) 1.2.1 指數(shù) 1.2.2 對(duì)數(shù) 1.2.3 級(jí)數(shù) 1.2.4 模運(yùn)算 1.2.5 證明方法 1.3 遞歸的簡(jiǎn)單介紹 1.4 C++類 1.4.1 基本class語(yǔ)法 1.4.2 特別的構(gòu)造函數(shù)語(yǔ)法與訪問(wèn)函數(shù) 1.4.3 接口與實(shí)現(xiàn)的分離 1.4.4 vector和string 1.5 C++細(xì)節(jié) 1.5.1 指針 1.5.2 參數(shù)傳遞 1.5.3 返回值傳遞 1.5.4 引用變量 1.5.5 三大函數(shù):析構(gòu)函數(shù)、復(fù)制構(gòu)造函數(shù)和operator= 1.5.6 C風(fēng)格的數(shù)組和字符串 1.6 模板 1.6.1 函數(shù)模板 1.6.2 類模板 1.6.3 Object、Comparable和例子 1.6.4 函數(shù)對(duì)象 1.6.5 類模板的分離編譯 1.7 使用矩陣 1.7.1 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本訪問(wèn)函數(shù) 1.7.2 operator[] 1.7.3 析構(gòu)函數(shù)、復(fù)制賦值和復(fù)制構(gòu)造函數(shù) 小結(jié) 練習(xí) 參考文獻(xiàn) 第2章 算法分析 2.1 數(shù)學(xué)基礎(chǔ) 2.2 模型 2.3 要分析的問(wèn)題 2.4 運(yùn)行時(shí)間計(jì)算 2.4.1 一個(gè)簡(jiǎn)單的例子 2.4.2 一般法則 2.4.3 最大子序列和問(wèn)題的解 2.4.4 運(yùn)行時(shí)間中的對(duì)數(shù) 2.4.5 檢驗(yàn)?zāi)愕姆治觥 ?.4.6 分析結(jié)果的準(zhǔn)確性 小結(jié) 練習(xí) 參考文獻(xiàn) 第3章 表、棧和隊(duì)列 3.1 抽象數(shù)據(jù)類型(ADT) 3.2 表ADT 3.2.1 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn) 3.2.2 簡(jiǎn)單鏈表 3.3 STL中的向量和表 3.3.1 迭代器 3.3.2 示例:對(duì)表使用erase 3.3.3 const_iterator 3.4 向量的實(shí)現(xiàn) 3.5 表的實(shí)現(xiàn) 3.6 棧ADT 3.6.1 棧模型 3.6.2 棧的實(shí)現(xiàn) 3.6.3 應(yīng)用 3.7 隊(duì)列ADT 3.7.1 隊(duì)列模型 3.7.2 隊(duì)列的數(shù)組實(shí)現(xiàn) 3.7.3 隊(duì)列的應(yīng)用 小結(jié) 練習(xí) 第4章 樹 4.1 預(yù)備知識(shí) 4.1.1 樹的實(shí)現(xiàn) 4.1.2 樹的遍歷及應(yīng)用 4.2 二叉樹 4.2.1 實(shí)現(xiàn) 4.2.2 一個(gè)例子——表達(dá)式樹 4.3 查找樹ADT——二叉查找樹 4.3.1 contains 4.3.2 findMin和findMax 4.3.3 insert 4.3.4 remove 4.3.5 析構(gòu)函數(shù)和復(fù)制賦值操作符 4.3.6 平均情況分析 4.4 AVL樹 4.4.1 單旋轉(zhuǎn) 4.4.2 雙旋轉(zhuǎn) 4.5 伸展樹 4.5.1 一個(gè)簡(jiǎn)單的想法(不能直接使用) 4.5.2 伸展 4.6 樹的遍歷 4.7 B樹 4.8 標(biāo)準(zhǔn)庫(kù)中的set和map 4.8.1 set 4.8.2 map 4.8.3 set和map的實(shí)現(xiàn) 4.8.4 使用幾個(gè)map的例子 小結(jié) 練習(xí) 參考文獻(xiàn) 第5章 散列 5.1 基本思想 5.2 散列函數(shù) 5.3 分離鏈接法 5.4 不使用鏈表的散列表 5.4.1 線性探測(cè) 5.4.2 平方探測(cè) 5.4.3 雙散列 5.5 再散列 5.6 標(biāo)準(zhǔn)庫(kù)中的散列表 5.7 可擴(kuò)散列 小結(jié) 練習(xí) 參考文獻(xiàn) 第6章 優(yōu)先隊(duì)列(堆) 6.1 模型 6.2 一些簡(jiǎn)單的實(shí)現(xiàn) 6.3 二叉堆 6.3.1 結(jié)構(gòu)性質(zhì) 6.3.2 堆序性質(zhì) 6.3.3 基本的堆操作 6.3.4 堆的其他操作 6.4 優(yōu)先隊(duì)列的應(yīng)用 6.4.1 選擇問(wèn)題 6.4.2 事件模擬 6.5 d堆 6.6 左式堆 6.6.1 左式堆性質(zhì) 6.6.2 左式堆操作 6.7 斜堆 6.8 二項(xiàng)隊(duì)列 6.8.1 二項(xiàng)隊(duì)列結(jié)構(gòu) 6.8.2 二項(xiàng)隊(duì)列操作 6.8.3 二項(xiàng)隊(duì)列的實(shí)現(xiàn) 6.9 標(biāo)準(zhǔn)庫(kù)中的優(yōu)先隊(duì)列 小結(jié) 練習(xí) 參考文獻(xiàn) 第7章 排序 7.1 預(yù)備知識(shí) 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的STL實(shí)現(xiàn) 7.2.3 插入排序的分析 7.3 一些簡(jiǎn)單排序算法的下界 7.4 謝爾排序 7.5 堆排序 7.6 歸并排序 7.7 快速排序 7.7.1 選取樞紐元 7.7.2 分割策略 7.7.3 小數(shù)組 7.7.4 實(shí)際的快速排序例程 7.7.5 快速排序的分析 7.7.6 選擇問(wèn)題的線性期望時(shí)間算法 7.8 間接排序 7.8.1 vector<Comparable*>不運(yùn)行 7.8.2 智能指針類 7.8.3 重載operator< 7.8.4 使用“*”解引用指針 7.8.5 重載類型轉(zhuǎn)換操作符 7.8.6 隨處可見的隱式類型轉(zhuǎn)換 7.8.7 雙向隱式類型轉(zhuǎn)換會(huì)導(dǎo)致歧義 7.8.8 指針減法是合法的 7.9 排序算法的一般下界 7.10 桶排序 7.11 外部排序 7.11.1 為什么需要新算法 7.11.2 外部排序模型 7.11.3 簡(jiǎn)單算法 7.11.4 多路合并 7.11.5 多相合并 7.11.6 替換選擇 小結(jié) 練習(xí) 參考文獻(xiàn) 第8章 不相交集類 8.1 等價(jià)關(guān)系 8.2 動(dòng)態(tài)等價(jià)性問(wèn)題 8.3 基本數(shù)據(jù)結(jié)構(gòu) 8.4 靈巧求并算法 8.5 路徑壓縮 8.6 按秩求并和路徑壓縮的最壞情形 8.7 一個(gè)應(yīng)用 小結(jié) 練習(xí) 參考文獻(xiàn) 第9章 圖論算法 9.1 若干定義 9.2 拓?fù)渑判颉 ?.3 最短路徑算法 9.3.1 無(wú)權(quán)最短路徑 9.3.2 Dijkstra算法 9.3.3 具有負(fù)邊值的圖 9.3.4 無(wú)環(huán)圖 9.3.5 所有頂點(diǎn)對(duì)的最短路徑 9.3.6 最短路徑舉例 9.4 網(wǎng)絡(luò)流問(wèn)題 9.5 最小生成樹 9.5.1 Prim算法 9.5.2 Kruskal算法 9.6 深度優(yōu)先搜索的應(yīng)用 9.6.1 無(wú)向圖 9.6.2 雙連通性 9.6.3 歐拉回路 9.6.4 有向圖 9.6.5 查找強(qiáng)分支 9.7 NP完全性介紹 9.7.1 難與易 9.7.2 NP類 9.7.3 NP完全問(wèn)題 小結(jié) 練習(xí) 參考文獻(xiàn) 第10章 算法設(shè)計(jì)技巧 10.1 貪心算法 10.1.1 一個(gè)簡(jiǎn)單的調(diào)度問(wèn)題 10.1.2 赫夫曼編碼 10.1.3 近似裝箱問(wèn)題 10.2 分治算法 10.2.1 分治算法的運(yùn)行時(shí)間 10.2.2 最近點(diǎn)問(wèn)題 10.2.3 選擇問(wèn)題 10.2.4 一些算術(shù)問(wèn)題的理論改進(jìn) 10.3 動(dòng)態(tài)規(guī)劃 10.3.1 用表代替遞歸 10.3.2 矩陣乘法的順序安排 10.3.3 最優(yōu)二叉查找樹 10.3.4 所有點(diǎn)對(duì)最短路徑 10.4 隨機(jī)化算法 10.4.1 隨機(jī)數(shù)生成器 10.4.2 跳躍表 10.4.3 素性測(cè)試 10.5 回溯算法 10.5.1 公路收費(fèi)點(diǎn)重建問(wèn)題 10.5.2 博弈 小結(jié) 練習(xí) 參考文獻(xiàn) 第11章 攤還分析 11.1 一個(gè)無(wú)關(guān)的智力問(wèn)題 11.2 二項(xiàng)隊(duì)列 11.3 斜堆 11.4 斐波那契堆 11.4.1 切除左式堆中的結(jié)點(diǎn) 11.4.2 二項(xiàng)隊(duì)列的懶惰合并 11.4.3 斐波那契堆操作 11.4.4 時(shí)間界的證明 11.5 伸展樹 小結(jié) 練習(xí) 參考文獻(xiàn) 第12章 高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn) 12.1 自頂向下伸展樹 12.2 紅黑樹 12.2.1 自底向上插入 12.2.2 自頂向下紅黑樹 12.2.3 自頂向下刪除 12.3 確定性跳躍表 12.4 AA樹 12.5 treap樹 12.6 k-d樹 12.7 配對(duì)堆 小結(jié) 練習(xí) 參考文獻(xiàn) 附錄 類模板的分離編譯 索引
編輯推薦
《數(shù)據(jù)結(jié)構(gòu)與算法分析:C++描述(第3版)》秉承Weiss著作一貫的嚴(yán)謹(jǐn)風(fēng)格,同時(shí)又突出了實(shí)踐。書中充分應(yīng)用了現(xiàn)代C++語(yǔ)言特性,透徹地講述了數(shù)據(jù)結(jié)構(gòu)的原理和應(yīng)用,不僅使學(xué)生具備算法分析能力,能夠開發(fā)高效的程序,而且讓學(xué)生掌握良好的程序設(shè)計(jì)技巧。Mark Allerl Weiss教授撰寫的數(shù)據(jù)結(jié)構(gòu)與算法分析方面的著作曾被評(píng)為20世紀(jì)最佳的30部計(jì)算機(jī)著作之一,已經(jīng)成為公認(rèn)的經(jīng)典之作,被全球數(shù)百所大學(xué)采用為教材,廣受好評(píng)。
圖書封面
圖書標(biāo)簽Tags
無(wú)
評(píng)論、評(píng)分、閱讀與下載
數(shù)據(jù)結(jié)構(gòu)與算法分析 PDF格式下載