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

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---