高級(jí)數(shù)據(jù)結(jié)構(gòu)

內(nèi)容概要

　　《高級(jí)數(shù)據(jù)結(jié)構(gòu)》在基本數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，圍繞一些常用的高級(jí)數(shù)據(jù)結(jié)構(gòu)，結(jié)合大量實(shí)戰(zhàn)例題，深入分析“數(shù)據(jù)結(jié)構(gòu)是如何服務(wù)于算法的”。本書主要內(nèi)容包括：哈希表、樹與二叉樹、優(yōu)先隊(duì)列與堆、并查集、線段樹、樹狀數(shù)組、伸展樹、Treap、AVL樹、紅—黑樹、SBT、塊狀鏈表與塊狀樹、后綴樹與后綴數(shù)組、樹鏈剖分與動(dòng)態(tài)樹等。　　《高級(jí)數(shù)據(jù)結(jié)構(gòu)》的適用對(duì)象包括：中學(xué)信息學(xué)競(jìng)賽選手及輔導(dǎo)老師、大學(xué)ACM比賽選手及教練、高等院校計(jì)算機(jī)專業(yè)的師生、程序設(shè)計(jì)愛好者等。

書籍目錄

第1章 哈希表 1.1哈希表的基本原理 1.2哈希表的基本概念 1.3哈希函數(shù)的構(gòu)造 1.4哈希表的基本操作 1.5沖突的處理 1.6哈希表的性能分析 1.7哈希表的應(yīng)用舉例 1.8本章習(xí)題 第2章 樹與二叉樹 2.1樹 2.1.1樹的存儲(chǔ)結(jié)構(gòu) 2.1.2樹的遍歷 2.2二叉樹 2.2.1普通樹轉(zhuǎn)換成二叉樹 2.2.2二叉樹的遍歷 2.2.3二叉樹的其他操作 2.2.4二叉樹的形態(tài) 2.3二叉排序樹 2.4哈夫曼二叉樹 2.5字典樹 2.6本章習(xí)題 第3章 優(yōu)先隊(duì)列與二叉堆 3.1優(yōu)先隊(duì)列 3.2二叉堆 3.2.1Put操作 3.2.2Get操作 3.3可并堆 3.3.1左偏樹的定義 3.3.2左偏樹的基本操作 3.4本章習(xí)題 第4章 并查集 4.1并查集的主要操作 4.2并查集的實(shí)現(xiàn) 4.2.1并查集的數(shù)組實(shí)現(xiàn) 4.2.2并查集的鏈表實(shí)現(xiàn) 4.2.3并查集的樹實(shí)現(xiàn) 4.3并查集的應(yīng)用舉例 4.4本章習(xí)題 第5章 線段樹 5.1線段樹的應(yīng)用背景 5.2線段樹的初步實(shí)現(xiàn) 5.2.1線段樹的結(jié)構(gòu) 5.2.2線段樹的性質(zhì) 5.2.3線段樹的存儲(chǔ) 5.2.4線段樹的常用操作 5.2.4.1線段樹的構(gòu)造 5.2.4.2線段樹的查詢 5.2.4.3線段樹的修改 5.2.4.4線段樹的延遲修改 5.3線段樹在一些經(jīng)典問題中的應(yīng)用 5.3.1逆序?qū)栴} 5.3.2矩形覆蓋問題 5.4線段樹的擴(kuò)展 5.4.1用線段樹優(yōu)化動(dòng)態(tài)規(guī)劃 5.4.2將線段樹擴(kuò)展到高維 5.4.3線段樹與平衡樹的結(jié)合 5.5線段樹與其他數(shù)據(jù)結(jié)構(gòu)的比較 5.6線段樹的應(yīng)用舉例 5.7本章習(xí)題 第6章 樹狀數(shù)組 6.1樹狀數(shù)組的問題模型 6.2樹狀數(shù)組的基本思想 6.3樹狀數(shù)組的實(shí)現(xiàn) 6.3.1子集的劃分方法 6.3.2查詢前綴和 6.3.3修改子集和 6.4樹狀數(shù)組的常用技巧 6.4.1查詢?nèi)我鈪^(qū)間和 6.4.2利用SHill數(shù)組求出原數(shù)組a的某個(gè)元素值 6.4.3找到某個(gè)前綴和對(duì)應(yīng)的前綴下標(biāo)index 6.4.4成倍擴(kuò)張/縮減 6.4.5初始化樹狀數(shù)組 6.5樹狀數(shù)組與線段樹的比較 6.6樹狀數(shù)組擴(kuò)展到高維的情形 6.7樹狀數(shù)組的應(yīng)用舉例 6.8本章習(xí)題 第7章 伸展樹 7.1伸展樹的主要操作 7.1.1伸展操作 7.1.2伸展樹的基本操作 7.2伸展樹的算法實(shí)現(xiàn) 7.3伸展樹的效率分析 7.4伸展樹的應(yīng)用舉例 7.5本章習(xí)題 第8章 Treap 8.1Treap的基本操作 8.2Treap的算法實(shí)現(xiàn) 8.3Treap的應(yīng)用舉例 8.4本章習(xí)題 第9章 平衡樹 9.1AVL樹 9.2紅—黑樹 9.3SBT 9.3.1SBT的基本操作 9.3.2SBT的效率分析 9.3.3SBT的算法實(shí)現(xiàn) 9.4本章習(xí)題 第10章 塊狀鏈表與塊狀樹 10.1塊狀鏈表的基本思想 10.2塊狀鏈表的基本操作 10.3塊狀鏈表的擴(kuò)張 10.3.1維護(hù)區(qū)間和以及區(qū)間最值 10.3.2維護(hù)局部數(shù)據(jù)有序化 10.3.3維護(hù)區(qū)間翻轉(zhuǎn) 10.4塊狀鏈表與其他數(shù)據(jù)結(jié)構(gòu)的比較 10.5分塊思想在樹上的應(yīng)用——塊狀樹 10.6塊狀鏈表的應(yīng)用舉例 10.7本章習(xí)題 第11章 后綴樹與后綴數(shù)組 11.1后綴樹的簡(jiǎn)介 11.2后綴樹的定義 11.3后綴樹的構(gòu)建 11.3.1后綴樹的樸素構(gòu)建算法 11.3.2后綴樹的線性時(shí)間構(gòu)建算法 11.3.2.1隱式樹的樸素構(gòu)建 11.3.2.2擴(kuò)展規(guī)則約定 11.3.2.3后綴鏈加速 11.3.2.4進(jìn)一步加速 11.3.2.5后綴樹拓展到多串的形式 11.3.2.6代碼實(shí)現(xiàn) 11.3.2.7相關(guān)證明 11.4后綴樹的應(yīng)用 11.4.1字符串（集合）的精確匹配 11.4.1.1情形一 11.4.1.2情形二 11.4.1.3情形三 11.4.1.4情形四 11.4.2公共子串問題 11.4.2.1情形五 11.4.2.2情形六 11.4.2.3情形七 11.4.2.4情形八 11.4.2.5情形九 11.4.3重復(fù)子串問題 11.4.3.1情形十 11.4.3.2情形十一 11.4.3.3情形十二 11.5后綴數(shù)組的簡(jiǎn)介 11.6后綴數(shù)組的定義 11.7后綴數(shù)組的構(gòu)建 11.7.1一種直接的構(gòu)建算法 11.7.2倍增算法 11.7.2.1倍增算法描述 11.7.2.2倍增算法代碼 11.7.3由后綴樹得到后綴數(shù)組 11.7.4DC3算法和DC算法 11.7.4.1DC3算法 11.7.4.2DC算法 11.8LCP的引入 11.9后綴數(shù)組的應(yīng)用 11.9.1后綴排序的直接應(yīng)用 11.9.1.1Burrows—Wheeler變換 11.9.1.2多模式串的匹配 11.9.2通過引入LCP優(yōu)化 11.9.2.1多模式串的匹配 11.9.2.2重復(fù)子串問題 11.9.2.3最長(zhǎng)回文子串 11.9.2.4最長(zhǎng)公共子串 11.9.3后綴數(shù)組的應(yīng)用舉例 11.10本章習(xí)題 第12章 樹鏈剖分與動(dòng)態(tài)樹 12.1樹鏈剖分的思想和性質(zhì) 12.2樹鏈剖分的實(shí)現(xiàn)及應(yīng)用 12.3動(dòng)態(tài)樹的初探 12.3.1動(dòng)態(tài)樹的常用功能 12.3.2動(dòng)態(tài)樹的簡(jiǎn)單情形 12.4動(dòng)態(tài)樹的實(shí)現(xiàn) 12.4.1動(dòng)態(tài)樹的基本操作及其實(shí)現(xiàn) 12.4.1.1動(dòng)態(tài)樹的問題模型 12.4.1.2用Splay維護(hù)實(shí)路徑 12.4.2動(dòng)態(tài)樹操作的時(shí)間復(fù)雜度分析 12.4.2.1動(dòng)態(tài)樹操作的次數(shù) 12.4.2.2Splay操作的平攤時(shí)間 12.5動(dòng)態(tài)樹的經(jīng)典應(yīng)用 12.5.1求最近公共祖先 12.5.2并查集操作 12.5.3求最大流 12.5.4求生成樹 12.6動(dòng)態(tài)樹的應(yīng)用舉例 12.7本章習(xí)題 致謝

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   并查集（Union Find Set）是一種用于處理分離集合的抽象數(shù)據(jù)類型。當(dāng)給出兩個(gè)元素的一個(gè)無序?qū)Γ╝，b）時(shí)，需要快速合并a和b分別所在的集合，這期間需要反復(fù)查找某元素所在的集合，“并”、“查”和“集”三字由此而來。也就是說，并查集的作用是動(dòng)態(tài)地維護(hù)和處理集合元素之間的復(fù)雜關(guān)系。 在并查集中，n個(gè)不同的元素被分為若干組，每組是一個(gè)集合，這種集合就叫做“分離集合（Disjoint Set）”。并查集支持查找一個(gè)元素所屬的集合以及兩個(gè)元素各自所屬集合的合并操作。例如，有這樣一個(gè)問題：一個(gè)城鎮(zhèn)里居住著n個(gè)市民，已知一些人互為朋友，而且朋友的朋友也是朋友，也就是說，如果A和B是朋友，C和B是朋友，則A和C也是朋友，請(qǐng)你根據(jù)給出的若干組朋友關(guān)系，求出最大的一個(gè)朋友圈的人數(shù)。這就有了并查集的用武之地了；一開始我們把所有人都各自放在一個(gè)集合中，然后根據(jù)依次給出的朋友關(guān)系，查找判斷兩個(gè)人是否屬于同一個(gè)集合（是否已經(jīng)是朋友），如果不在同一個(gè)集合，則將這兩個(gè)集合合并成一個(gè)集合（形成一個(gè)朋友圈），最后看哪個(gè)集合的元素最多并輸出個(gè)數(shù)即可。 4.1并查集的主要操作 使用并查集首先要記錄一組分離的動(dòng)態(tài)集合S={S1，S2，…，Sk}，每個(gè)集合還要設(shè)置一個(gè)代表來識(shí)別，代表只要選擇該集合中的某個(gè)元素（成員）即可，哪一個(gè)元素被選作代表是無所謂的，重要的是，如果請(qǐng)求某一動(dòng)態(tài)集合的代表兩次，且在兩次請(qǐng)求間不修改集合，則兩次得到的答案應(yīng)該是相同的。并查集主要有三種操作：初始化、查找與合并。 （1）初始化：MAKE—SET（x） 建立一個(gè)新的集合，其僅有的成員是x（同時(shí)就是代表）。由于各集合是分離的，所以要求x沒有在其他集合中出現(xiàn)過。使用并查集前都需要執(zhí)行一次初始化操作，無論采用何種實(shí)現(xiàn)方式，其時(shí)間復(fù)雜度都是O（n）。 （2）查找：FIND—SET（x） 查找一個(gè)元素所在的集合，本操作返回一個(gè)包含x的集合的代表。查找是并查集的核心操作，也是優(yōu)化并查集效率的重點(diǎn)。 （3）合并：UNION（x，y） 將包含x和y的動(dòng)態(tài)集合（假設(shè)為Sx和Sy）合并成一個(gè)新的集合S，本操作返回集合SxUSy的代表。一般來說，在不同的實(shí)現(xiàn)中通常都以Sx或者Sy的代表作為薪集合的代表。合并之前一般要先判斷兩個(gè)元素是否屬于同一集合，這可以通過查找操作來實(shí)現(xiàn)。

編輯推薦

《青少年信息學(xué)奧林匹克競(jìng)賽實(shí)戰(zhàn)輔導(dǎo)叢書:高級(jí)數(shù)據(jù)結(jié)構(gòu)》的適用對(duì)象包括：中學(xué)信息學(xué)競(jìng)賽選手及輔導(dǎo)老師、大學(xué)ACM比賽選手及教練、高等院校計(jì)算機(jī)專業(yè)的師生、程序設(shè)計(jì)愛好者等。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    高級(jí)數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---