高級數(shù)據(jù)結構

內容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    高級數(shù)據(jù)結構 PDF格式下載

---