程式设计中实用的数据结构 _生活百科

文章插图
程式设计中实用的数据结构《程式设计中实用的数据结构》是人民邮电出版社2014年出版的一部书。
【程式设计中实用的数据结构】该书按照数据结构知识的分类，以线性表、树型问题和图型问题为基本构件，介绍了几十种存储方式和相应算法，同时深入浅出地分析和证明了每一种存储方式和算法的套用场合和效率，引导读者儘可能选择有利于提升算法效率的数据结构。
基本介绍书名：程式设计中实用的数据结构
作者：王建德吴永辉
ISBN：9787115268655
页数：369
定价：59.00元
出版社：人民邮电出版社
出版时间：2012 年1月
装帧：平装
开本：16开
内容简介《程式设计中实用的数据结构》既可以作为大专院校计算机专业数据结构或算法类课程的教材，亦可以作为大学生和中学生程式设计竞赛活动的培训教程，还可以作为计算机软体研发的参考资料。作者简介王建德国务院特殊津贴专家、上海师範大学特聘教授、控江中学特级教师。他辅导学生在国际奥林匹克信息学竞赛（IOI）中获8金、4银、2铜，先后出版了《新编实用算法分析与程式设计》和《程式设计中常用的计算思维方式》等多本广受好评的图书，这些图书长期以来是国内各类程式设计竞赛的必备教程。吴永辉博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会成员，复旦大学ACM程式设计竞赛队教练。自2001年起连续带队进入 ACM-ICPC世界总决赛，并取得过世界第六名的佳绩。主要研究方向为资料库，在《计算机研究与发展》、《软体学报》以及重大学术会议上发表过多篇论文，参与翻译的着作有《数据通信与网路》和《数据通信、计算机网路与开放系统》。图书目录《程式设计中实用的数据结构》上篇讨论线性表第1 章数组31.1 数组的基本概念31.1.1 数组是一种顺序存储结构31.1.2 数组是程式设计中使用频率最高的数据类型41.2 最佳化数组的存储方式61.2.1 规则矩阵的压缩存储61.2.2 稀疏矩阵的压缩存储71.2.3 01 矩阵的压缩存储　111.3 排序与顺序统计141.3.1 排序的基本概念141.3.2 计数排序与贪心策略151.3.3 採用“二分”策略的排序方法211.3.4 顺序统计的基本方法28第2 章链式存储结构342.1 鍊表的基本概念342.1.1 单鍊表342.1.2 循环鍊表352.1.3 双向鍊表35.2.2 鍊表的基本运算352.2.1 构建单鍊表362.2.2 插入操作362.2.3 删除操作362.2.4 读取操作362.3 鍊表的套用37第3 章两种存取方式特殊的线性表433.1 “后进先出”的栈433.1.1 栈的基本运算　433.1.2 栈的套用　443.2 “先进先出”的伫列　523.2.1 伫列的基本运算　523.2.2 伫列的套用　54第4 章散列技术　594.1 散列表　594.2 散列函式的设计　594.3 消除冲突的基本方法　614.3.1 使用开放定址法消除冲突　614.3.2 使用分离连结法消除冲突　67第5 章后缀数组　715.1 后缀数组的基本概念　715.2 採用倍增算法求解rank 数组　735.3 利用rank 数组计算最长公共前缀　745.3.1 计算最长公共前缀是一个典型的rmq 问题　755.3.2 计算最长公共前缀的基本方法　755.4 后缀数组的套用　785.4.1 利用后缀数组处理单个字元串　785.4.2 两个字元串的公共子串问题　875.4.3 多个字元串共享子串的问题　90上篇小结　97中篇讨论树型问题第6 章树的基本概念和遍历规则　1016.1 树的递归定义　1016.2 节点的分类　1016.3 有关度的定义1016.4 树的深度（高度）1026.5 森林1026.6 有序树和无序树1026.7 树的表示方法1036.8 树的遍历规则1036.8.1 先根次序遍历树1036.8.2 后根次序遍历树104第7 章树的存储结构　1057.1 採用数组存储入边信息1057.1.1 存储无权树的入边信息1057.1.2 存储加权树的入边信息1067.2 採用数组存储所有儿子的地址信息1087.2.1 採用整数存储儿子的数组下标1087.2.2 採用指针存储儿子的地址1097.3 採用邻接表存储出边信息1107.3.1 採用数组存储方式的邻接表1107.3.2 採用单鍊表存储方式的邻接表1147.4 无根树的一般存储方式116第8 章二叉树　1238.1 二叉树的基本概念和存储结构1238.1.1 二叉树的基本概念1238.1.2 二叉树的存储结构1258.2 将普通有序树和森林转换成对应的二叉树　1288.2.1 将普通有序树转换成对应的二叉树1288.2.2 将普通有序树组成的森林转换成对应的二叉树1298.3 二叉树的遍历1308.3.1 前序遍历1308.3.2 中序遍历1308.3.3 后序遍历1318.3.4 由两种遍历确定二叉树结构133第9 章并查集　1359.1 并查集的基本概念1359.2 查找元素所在树的根节点并进行路径压缩1379.3 合併两个元素所在的集合　138第10 章堆　143 10.1 二叉堆的概念14310.2 在插入或删除节点时维护堆性质14410.2.1 插入节点14410.2.2 删除最小值元素14410.3 建堆14510.4 堆排序146第11 章最优二叉树15411.1 最优二叉树的基本概念15411.2 构造最优二叉树155第12 章线段树　16012.1 线段树的基本概念16012.1.1 用于区间运算的线段树16012.1.2 用于数据统计的线段树16112.1.3 线段树的数据结构16212.2 线段树的基本操作16212.2.1 建立线段树16212.2.2 在区间内插入线段或数据16312.2.3 删除区间内的线段或数据16412.2.4 计算区间内的线段或数据状态16512.3 线段树在静态统计问题上的套用16512.4 线段树在动态统计问题上的套用168第13 章二叉查找树17613.1 二叉排序树17613.1.1 二叉排序树的基本概念17613.1.2 二叉排序树的基本操作17713.2 静态二叉排序树18013.2.1 静态二叉排序树的特徵18013.2.2 静态二叉排序树的构造方法18013.2.3 在静态二叉排序树上进行数据统计18113.3 子树大小平衡树（sbt）18613.3.1 sbt 的性质18613.3.2 旋转18613.3.3 动态维护sbt 的平衡特性19113.3.4 sbt 的基本操作196中篇小结205下篇讨论图型问题第14 章图的基本概念及其存储结构20914.1 图的基本概念20914.2 图的简单分类21114.2.1 无向图和有向图21214.2.2 无权图和加权图21214.2.3 稀疏图和稠密图21214.2.4 完全图和补图21214.2.5 树和森林21314.2.6 图的生成树和生成森林21314.2.7 平面图21414.2.8 二分图21414.2.9 相交图和区间图21414.3 图的存储结构21514.3.1 存储节点间相邻关係的相邻矩阵21514.3.2 存储边信息的3 种数据结构217第15 章图的遍历及其套用220 15.1 广度优先遍历（bfs 算法）22015.1.1 bfs 算法的基本概念22015.1.2 bfs 算法的套用22215.2 深度优先遍历（dfs 算法）23315.2.1 dfs 的基本概念23315.2.2 在dfs 遍历过程中记录节点颜色变化的时间23915.2.3 根据节点颜色对边进行分类24015.2.4 分析dfs 森林的结构24215.2.5 使用dfs 算法进行拓扑排序24415.2.6 使用dfs 算法计算欧拉迴路248第16 章有向图的强连通分量和传递闭包　25516.1 判定仙人掌图　25516.2 计算强连通分量　25916.3 传递闭包的套用　266第17 章无向图的连通性分析　27117.1 计算节点的low 函式　27117.2 计算连通图的割点和桥　27217.2.1 计算连通图的割点　27217.2.2 计算连通图的桥　27317.3 计算双连通子图　27517.4 分析连通图的连通程度　27617.4.1 连通图的顶连通度　27717.4.2 连通图的边连通度　278第18 章最小生成树　27918.1 基本概念　27918.2 最小生成树的套用价值　27918.3 最小生成树的计算策略　28118.4 计算最小生成树的两种算法　28118.4.1 kruskal 算法　28218.4.2 prim 算法　28318.5 最小生成树算法的套用实例　285第19 章加权图的单源最短路径问题　29319.1 基本概念　29319.1.1 单源算法是高效解决所有最短路径问题的基础　29319.1.2 负权迴路影响单源最短路径的计算　29419.1.3 鬆弛技术是单源算法的核心　29519.2 求解单源最短路径问题的3 种算法　29619.2.1 dijkstra 算法　29619.2.2 bellman-ford 算法　29819.2.3 spfa 算法　29919.3 单源最短路径算法的套用实例　301第20 章二分图的匹配问题　31020.1 基本概念　31020.1.1 图的匹配概念31020.1.2 二分图的概念和判定方法31120.2 计算无权二分图的最大匹配31520.2.1 匈牙利算法的基本思路　316 20.2.2 匈牙利算法的基本流程　31620.2.3 匈牙利算法的套用实例　31720.3 计算带权二分图的最佳匹配32020.3.1 最佳匹配的概念32020.3.2 km算法的基本思路32120.3.3 km算法的基本流程和套用实例323第21 章最大流问题　32721.1 基本概念32721.2 在可增广路径的基础上计算最大流32921.2.1 可增广路径的基本概念32921.2.2 基于最大流定理上的最大流算法33421.3 按层次计算最大流的dinic 算法33421.3.1 dinic 算法的基本思路33421.3.2 dinic 算法的基本流程33521.4 利用最大流最小割定理解题33921.4.1 割的概念33921.4.2 最小割的计算方法和套用实例34021.5 计算多源多汇网路的可行流34621.6 网路增加容量下界因素后的流量计算问题34821.6.1 求容量有上下界的网路的最大流34821.6.2 求容量有上下界的网路的最小流35321.7 网路增加费用因素后的流量计算问题35821.7.1 计算最小费用最大流35921.7.2 计算容量有上下界的网路的最小费用最小流364下篇小结370