程序設(shè)計(jì)中實(shí)用的數(shù)據(jù)結(jié)構(gòu)

內(nèi)容概要

　　本書對(duì)近年來程序設(shè)計(jì)教育和競(jìng)賽培訓(xùn)活動(dòng)中涌現(xiàn)的許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法進(jìn)行了全面總結(jié)，通過深入的分析和生動(dòng)的實(shí)例引導(dǎo)讀者尋找問題中各對(duì)象之間的關(guān)系，確定數(shù)學(xué)模型所使用的邏輯結(jié)構(gòu)；實(shí)現(xiàn)對(duì)各個(gè)對(duì)象的操作，即確定數(shù)據(jù)所采用的存儲(chǔ)結(jié)構(gòu)；將數(shù)據(jù)類型與定義在該類型上的運(yùn)算融于一體，為面向?qū)ο蟮某绦蛟O(shè)計(jì)方法奠定基礎(chǔ)。
　　 本書既是大學(xué)計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程和算法設(shè)計(jì)課程的優(yōu)秀參考書，也是大中學(xué)生程序設(shè)計(jì)競(jìng)賽不可多得的培訓(xùn)教材。
本書特色
　　按照數(shù)據(jù)結(jié)構(gòu)的知識(shí)體系，全書分為“線性表”、“樹型問題”和“圖型問題”三篇，介紹了幾十種存儲(chǔ)方式和相應(yīng)的算法。
介紹了許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法，同時(shí)引導(dǎo)讀者盡可能采用“揚(yáng)長避短”的選擇原則和“取長補(bǔ)短”的結(jié)合方法，選擇有利于提升算法效率的數(shù)據(jù)結(jié)構(gòu)。
對(duì)每個(gè)比較難懂的概念都舉實(shí)例加以說明，對(duì)每個(gè)比較抽象的定理都有具體的應(yīng)用例證幫助理解，對(duì)每個(gè)經(jīng)典算法都有清晰的程序流程給予示范。此外，還大量運(yùn)用圖表，使得概念、定理和算法的由來變得具體、形象和直觀。
書中采用了一種結(jié)構(gòu)清晰、移植性強(qiáng)且貼近自然語言表述的類程序設(shè)計(jì)語言。只要讀者具備Pascal和C等任一種語言的基礎(chǔ)，就可以比較輕松地讀懂其語義。

作者簡(jiǎn)介

　　王建德
國務(wù)院特殊津貼專家、上海師范大學(xué)特聘教授、控江中學(xué)特級(jí)教師。他輔導(dǎo)學(xué)生在國際奧林匹克信息學(xué)競(jìng)賽（IOI）中獲8金、4銀、2銅，先后出版了《新編實(shí)用算法分析與程序設(shè)計(jì)》和《程序設(shè)計(jì)中常用的計(jì)算思維方式》等多本廣受好評(píng)的圖書，這些圖書長期以來是國內(nèi)各類程序設(shè)計(jì)競(jìng)賽的必備教程。
　　吳永輝
博士，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系副教授，ACM-ICPC中國賽區(qū)指導(dǎo)委員會(huì)成員，復(fù)旦大學(xué)ACM程序設(shè)計(jì)競(jìng)賽隊(duì)教練。自2001年起連續(xù)帶隊(duì)進(jìn)入
ACM-ICPC世界總決賽，并取得過世界第六名的佳績。主要研究方向?yàn)閿?shù)據(jù)庫，在《計(jì)算機(jī)研究與發(fā)展》、《軟件學(xué)報(bào)》以及重大學(xué)術(shù)會(huì)議上發(fā)表過多篇論文，參與翻譯的著作有《數(shù)據(jù)通信與網(wǎng)絡(luò)》和《數(shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)與開放系統(tǒng)》。

書籍目錄

上篇 討論線性表
　第1章 數(shù)組
　　1.1 數(shù)組的基本概念
　　1.1.1 數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)
　　1.1.2 數(shù)組是程序設(shè)計(jì)中使用頻率最高的數(shù)據(jù)類型
　　1.2 優(yōu)化數(shù)組的存儲(chǔ)方式
　　1.2.1 規(guī)則矩陣的壓縮存儲(chǔ)
　　1.2.2 稀疏矩陣的壓縮存儲(chǔ)
　　1.2.3 矩陣的壓縮存儲(chǔ)
　　1.3 排序與順序統(tǒng)計(jì)
　　1.3.1 排序的基本概念
　　1.3.2 計(jì)數(shù)排序與貪心策略
　　1.3.3 采用“二分”策略的排序方法
　　1.3.4 順序統(tǒng)計(jì)的基本方法
　第2章 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
　　2.1 鏈表的基本概念
　　2.1.1 單鏈表
　　2.1.2 循環(huán)鏈表
　　2.1.3 雙向鏈表
　　2.2 鏈表的基本運(yùn)算
　　2.2.1 構(gòu)建單鏈表
　　2.2.2 插入操作
　　2.2.3 刪除操作
　　2.2.4 讀取操作
　　2.3 鏈表的應(yīng)用
　第3章 兩種存取方式特殊的線性表
　　3.1 “后進(jìn)先出”的棧
　　3.1.1 棧的基本運(yùn)算
　　3.1.2 棧的應(yīng)用
　　3.2 “先進(jìn)先出”的隊(duì)列
　　3.2.1 隊(duì)列的基本運(yùn)算
　　3.2.2 隊(duì)列的應(yīng)用
　第4章 散列技術(shù)
　　4.1 散列表
　　4.2 散列函數(shù)的設(shè)計(jì)
　　4.3 消除沖突的基本方法
　　4.3.1 使用開放尋址法消除沖突
　　4.3.2 使用分離鏈接法消除沖突
　第5章 后綴數(shù)組
　　5.1 后綴數(shù)組的基本概念
　　5.2 采用倍增算法求解rank數(shù)組
　　5.3 利用rank數(shù)組計(jì)算最長公共前綴
　　5.3.1 計(jì)算最長公共前綴是一個(gè)典型的RMQ問題
　　5.3.2 計(jì)算最長公共前綴的基本方法
　　5.4 后綴數(shù)組的應(yīng)用
　　5.4.1 利用后綴數(shù)組處理單個(gè)字符串
　　5.4.2 兩個(gè)字符串的公共子串問題
　　5.4.3 多個(gè)字符串共享子串的問題
　　上篇小結(jié)
中篇 討論樹型問題
　第6章 樹的基本概念和遍歷規(guī)則
　　6.1 樹的遞歸定義
　　6.2 節(jié)點(diǎn)的分類
　　6.3 有關(guān)度的定義
　　6.4 樹的深度(高度)
　　6.5 森林
　　6.6 有序樹和無序樹
　　6.7 樹的表示方法
　　6.8 樹的遍歷規(guī)則
　　6.8.1 先根次序遍歷樹
　　6.8.2 后根次序遍歷樹
　第7章 樹的存儲(chǔ)結(jié)構(gòu)
　　7.1 采用數(shù)組存儲(chǔ)入邊信息
　　7.1.1 存儲(chǔ)無權(quán)樹的入邊信息
　　7.1.2 存儲(chǔ)加權(quán)樹的入邊信息
　　7.2 采用數(shù)組存儲(chǔ)所有兒子的地址信息
　　7.2.1 采用整數(shù)存儲(chǔ)兒子的數(shù)組下標(biāo)
　　7.2.2 采用指針存儲(chǔ)兒子的地址
　　7.3 采用鄰接表存儲(chǔ)出邊信息
　　7.3.1 采用數(shù)組存儲(chǔ)方式的鄰接表
　　7.3.2 采用單鏈表存儲(chǔ)方式的鄰接表
　　7.4 無根樹的一般存儲(chǔ)方式
　第8章 二叉樹
　　8.1 二叉樹的基本概念和存儲(chǔ)結(jié)構(gòu)
　　8.1.1 二叉樹的基本概念
　　8.1.2 二叉樹的存儲(chǔ)結(jié)構(gòu)
　　8.2 將普通有序樹和森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹
　　8.2.1 將普通有序樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹
　　8.2.2 將普通有序樹組成的森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹
　　8.3 二叉樹的遍歷
　　8.3.1 前序遍歷
　　8.3.2 中序遍歷
　　8.3.3 后序遍歷
　　8.3.4 由兩種遍歷確定二叉樹結(jié)構(gòu)
　第9章 并查集
　　9.1 并查集的基本概念
　　9.2 查找元素所在樹的根節(jié)點(diǎn)并進(jìn)行路徑壓縮
　　9.3 合并兩個(gè)元素所在的集合
　第10章 堆
　　10.1 二叉堆的概念
　　10.2 在插入或刪除節(jié)點(diǎn)時(shí)維護(hù)堆性質(zhì)
　　10.2.1 插入節(jié)點(diǎn)
　　10.2.2 刪除最小值元素
　　10.3 建堆
　　10.4 堆排序
　第11章 最優(yōu)二叉樹
　　11.1 最優(yōu)二叉樹的基本概念
　　11.2 構(gòu)造最優(yōu)二叉樹
　第12章 線段樹
　　12.1 線段樹的基本概念
　　12.1.1 用于區(qū)間運(yùn)算的線段樹
　　12.1.2 用于數(shù)據(jù)統(tǒng)計(jì)的線段樹
　　12.1.3 線段樹的數(shù)據(jù)結(jié)構(gòu)
　　12.2 線段樹的基本操作
　　12.2.1 建立線段樹
　　12.2.2 在區(qū)間內(nèi)插入線段或數(shù)據(jù)
　　12.2.3 刪除區(qū)間內(nèi)的線段或數(shù)據(jù)
　　12.2.4 計(jì)算區(qū)間內(nèi)的線段或數(shù)據(jù)狀態(tài)
　　12.3 線段樹在靜態(tài)統(tǒng)計(jì)問題上的應(yīng)用
　　12.4 線段樹在動(dòng)態(tài)統(tǒng)計(jì)問題上的應(yīng)用
　第13章 二叉查找樹
　　13.1 二叉排序樹
　　13.1.1 二叉排序樹的基本概念
　　13.1.2 二叉排序樹的基本操作
　　13.2 靜態(tài)二叉排序樹
　　13.2.1 靜態(tài)二叉排序樹的特征
　　13.2.2 靜態(tài)二叉排序樹的構(gòu)造方法
　　13.2.3 在靜態(tài)二叉排序樹上進(jìn)行數(shù)據(jù)統(tǒng)計(jì)
　　13.3 子樹大小平衡樹(SBT)
　　13.3.1 SBT的性質(zhì)
　　13.3.2 旋轉(zhuǎn)
　　13.3.3 動(dòng)態(tài)維護(hù)SBT的平衡特性
　　13.3.4 SBT的基本操作
　　中篇小結(jié)
下篇 討論圖型問題
　第14章 圖的基本概念及其存儲(chǔ)結(jié)構(gòu)
　　14.1 圖的基本概念
　　14.2 圖的簡(jiǎn)單分類
　　14.2.1 無向圖和有向圖
　　14.2.2 無權(quán)圖和加權(quán)圖
　　14.2.3 稀疏圖和稠密圖
　　14.2.4 完全圖和補(bǔ)圖
　　14.2.5 樹和森林
　　14.2.6 圖的生成樹和生成森林
　　14.2.7 平面圖
　　14.2.8 二分圖
　　14.2.9 相交圖和區(qū)間圖
　　14.3 圖的存儲(chǔ)結(jié)構(gòu)
　　14.3.1 存儲(chǔ)節(jié)點(diǎn)間相鄰關(guān)系的相鄰矩陣
　　14.3.2 存儲(chǔ)邊信息的3種數(shù)據(jù)結(jié)構(gòu)
　第15章 圖的遍歷及其應(yīng)用
　　15.1 廣度優(yōu)先遍歷(BFS算法)
　　15.1.1 BFS算法的基本概念
　　15.1.2 BFS算法的應(yīng)用
　　15.2 深度優(yōu)先遍歷(DFS算法)
　　15.2.1 DFS的基本概念
　　15.2.2 在DFS遍歷過程中記錄節(jié)點(diǎn)顏色變化的時(shí)間
　　15.2.3 根據(jù)節(jié)點(diǎn)顏色對(duì)邊進(jìn)行分類
　　15.2.4 分析DFS森林的結(jié)構(gòu)
　　15.2.5 使用DFS算法進(jìn)行拓?fù)渑判?br />　　15.2.6 使用DFS算法計(jì)算歐拉回路
　第16章 有向圖的強(qiáng)連通分量和傳遞閉包
　　16.1 判定仙人掌圖
　　16.2 計(jì)算強(qiáng)連通分量
　　16.3 傳遞閉包的應(yīng)用
　第17章 無向圖的連通性分析
　　17.1 計(jì)算節(jié)點(diǎn)的low函數(shù)
　　17.2 計(jì)算連通圖的割點(diǎn)和橋
　　17.2.1 計(jì)算連通圖的割點(diǎn)
　　17.2.2 計(jì)算連通圖的橋
　　17.3 計(jì)算雙連通子圖
　　17.4 分析連通圖的連通程度
　　17.4.1 連通圖的頂連通度
　　17.4.2 連通圖的邊連通度
　第18章 最小生成樹
　　18.1 基本概念
　　18.2 最小生成樹的應(yīng)用價(jià)值
　　18.3 最小生成樹的計(jì)算策略
　　18.4 計(jì)算最小生成樹的兩種算法
　　18.4.1 Kruskal算法
　　18.4.2 Prim算法
　　18.5 最小生成樹算法的應(yīng)用實(shí)例
　第19章 加權(quán)圖的單源最短路徑問題
　　19.1 基本概念
　　19.1.1 單源算法是高效解決所有最短路徑問題的基礎(chǔ)
　　19.1.2 負(fù)權(quán)回路影響單源最短路徑的計(jì)算
　　19.1.3 松弛技術(shù)是單源算法的核心
　　19.2 求解單源最短路徑問題的3 種算法
　　19.2.1 Dijkstra算法
　　19.2.2 Bellman-Ford算法
　　19.2.3 SPFA算法
　　19.3 單源最短路徑算法的應(yīng)用實(shí)例
　第20章 二分圖的匹配問題
　　20.1 基本概念
　　20.1.1 圖的匹配概念
　　20.1.2 二分圖的概念和判定方法
　　20.2 計(jì)算無權(quán)二分圖的最大匹配
　　20.2.1 匈牙利算法的基本思路
　　20.2.2 匈牙利算法的基本流程
　　20.2.3 匈牙利算法的應(yīng)用實(shí)例
　　20.3 計(jì)算帶權(quán)二分圖的最佳匹配
　　20.3.1 最佳匹配的概念
　　20.3.2 KM算法的基本思路
　　20.3.3 KM算法的基本流程和應(yīng)用實(shí)例
　第21章 最大流問題
　　21.1 基本概念
　　21.2 在可增廣路徑的基礎(chǔ)上計(jì)算最大流
　　21.2.1 可增廣路徑的基本概念
　　21.2.2 基于最大流定理上的最大流算法
　　21.3 按層次計(jì)算最大流的Dinic算法
　　21.3.1 Dinic算法的基本思路
　　21.3.2 Dinic算法的基本流程
　　21.4 利用最大流最小割定理解題
　　21.4.1 割的概念
　　21.4.2 最小割的計(jì)算方法和應(yīng)用實(shí)例
　　21.5 計(jì)算多源多匯網(wǎng)絡(luò)的可行流
　　21.6 網(wǎng)絡(luò)增加容量下界因素后的流量計(jì)算問題
　　21.6.1 求容量有上下界的網(wǎng)絡(luò)的最大流
　　21.6.2 求容量有上下界的網(wǎng)絡(luò)的最小流
　　21.7 網(wǎng)絡(luò)增加費(fèi)用因素后的流量計(jì)算問題
　　21.7.1 計(jì)算最小費(fèi)用最大流
　　21.7.2 計(jì)算容量有上下界的網(wǎng)絡(luò)的最小費(fèi)用最小流
　　下篇小結(jié)
　　　　

編輯推薦

　  ACM競(jìng)賽的培訓(xùn)資料， 程序設(shè)計(jì)競(jìng)賽的經(jīng)典試題。 

圖書封面

圖書標(biāo)簽Tags

無

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

---

    程序設(shè)計(jì)中實(shí)用的數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---