数据结构与算法

出版社:陈明 中国铁道出版社 (2012-01出版)
出版日期:2012-1
ISBN:9787113136659
作者:陈明
页数:268页

章节摘录

版权页:   插图:   算法中用到了对队列操作的几个函数,可参看队列一章中的相关内容。遍历函数BFS()与深度优先搜索中给出的相同,这里不再给出。 分析算法的实质,每个顶点至多只能有一次机会进入队列。遍历图的过程实际上就是以边或弧为线索,寻找邻接点的过程。图的广度优先遍历算法的时间复杂度和深度优先搜索相同,采用邻接矩阵存储结构时,其时间复杂度为O(n2),而采用邻接表存储结构时,其时间复杂度为O(n+e),e为图中边的个数。 值得注意的一点是,无论采用深度优先搜索法,还是广度优先搜索法进行图的遍历,如果选定的出发点不同或者是所建立的存储结构不一致,则可能得到不同的遍历结果。只有当选取的出发点、采用的存储结构以及遍历图的方式都是确定的,遍历的结果才是唯一的。 7.4 图的应用 本节从生成树、最短路径、拓扑排序和关键路径方面介绍图的应用。 7.4.1 生成树 7.1节中介绍了生成树的概念。设G(V,E)是一个连通的无向图,从图中任意一个顶点出发,可以访问到全部顶点。在遍历的过程中,所经过的边集设为T(G),没有经过的边集设为B(G)。显然,T∪B=E,且T∩B=。考虑一个新图G’=(V,T),由于V(G’)=V(G),E(G’)E(G),则G’是G的连通子图,且G’中含有G的全部顶点。把图中的顶点加上遍历时经过的所有边所构成的子图称为生成树。如G’是G的生成树。显然,n个顶点的连通图至少有n-1条边。由于生成树有n-1条边,所以生成树是连通图的极小连通子图。对于一个非连通图和不是强连通的有向图,从任意一点出发,不能访问到图中所有顶点,只能得到连通分量的生成树,所有连通分量的生成树组成生成森林。 一个连通图的生成树并不是唯一的,这是因为遍历图时选择的起始点不同,遍历的策略不同,因此遍历所经过的边也就不同,故而产生不同的生成树。如图7-20所示就是几种不同的生成树。 因为网的边带权,而生成树不唯一,于是就产生了这样一个问题:如何找到一个各边的权数总和最小的生成树,这对于实际生活有很大的意义。例如,如果想在几个城市之间进行通信联络,首先需要建设一个基础通信网络,如果城市数量是n个,要想实现各个城市间的通信则至少需要n-1条线路。当选择具体的通信线路时,首先应该考虑通信经费问题。任意两个城市之间的通信线路都相应地存在通信代价权值。n个城市,如果任意两个城市之间均有线路,则最多可设置n(n-1)/2条线路,如何在这n(n-1)/2条线路中选择行-1条,使得总的耗费最低,这是一个需考虑的问题。 对于n个城市之问的基础通信网络可以用连通网来表示,其中网的顶点表示城市,边表示两城市之间的线路,边的权值表示相应线路上的通信代价。依据这个连通网可以建立多棵生成树,每一棵生成树都可以形成一个通信网方案。生成树的代价是各个边的代价之和,如果选择生成树的目标是使总体的通信费用最小,这个问题就是构造连通网的最小代价生成树,简称为最小生成树的问题。

书籍目录

第1章数据结构概论 1.1 问题的提出 1.2基本概念与术语 1.3数据结构的概念 1.4数据的逻辑结构、存储结构及运算 1.4.1数据的逻辑结构 1.4.2数据的存储结构 1.4.3数据的运算 1.4.4逻辑结构、存储结构及运算的关系 1.5算法与算法特性 1.5.1算法及其特性 1.5.2算法的描述方法 1.5.3算法与程序及数据结构 1.6算法性能分析及算法度量 1.6.1 算法性能分析 1.6.2算法度量 小结 习题 拓展实验:电话号码的查询 第2章线•陛表 2.1线性表的定义与运算 2.1.1线性表的定义 2.1.2线性表的抽象数据类型 2.2线性表的顺序存储 2.2.1顺序存储 2.2.2顺序表的运算 2.3线性表的链式存储 2.3.1线性链表及运算 2.3.2静态链表及运算 2.3.3 循环链表及运算 2.3.4双向链表及运算 2.4线性表的应用 2.4.1 约瑟夫问题 2.4.2一元多项式求和问题 2.4.3 集合应用问题 小结 习题 拓展实验:线性表的合并 第3章栈与队列 3.1 栈 3.1.1 栈的定义 3.1.2栈的顺序存储结构 3.1.3栈的链式存储结构 3.2栈的应用 3.2.1 子程序的调用和返回问题 3.2.2数制转换问题 3.3 队列 3.3.1 队列的定义 3.3.2 队列的顺序存储结构 3.3.3 队列的链式存储结构 3.4队列的应用 3.4.1 设备速度不匹配问题 3.4.2舞伴问题 小结 习题 拓展实验:算术表达式求值 第4章 串 4.1 串的基本概念 4.2串的存储结构 4.2.1 串的静态存储结构 4.2.2 串的动态存储结构 4.3 串的基本运算 4.3.1 串的抽象数据类型定义 4.3.2 串的基本运算实现 4.4模式匹配 4.4.1 BF算法 4.4.2 KMP算法 4.5 串的应用 小结 习题 拓展实验:设计简单的文本编辑器 第5章数组 5.1 数组及其基本操作 5.1.1数组的概念 5.1.2抽象数据类型数组的定义 5.2数组的存储结构 5.3 数组在矩阵运算中的应用 5.3.1 特殊矩阵的压缩存储 5.3.2稀疏矩阵的压缩存储 小结 习题 拓展实验:一元多项式的值计算 第6章树 6.1树的概念 6.1.1树的定义 6.1.2树的表示方法 6.1.3树的基本术语 6.1.4树的ADT定义 6.2 二叉树 6.2.1 二叉树的定义及基本结构 6.2.2二叉树的存储结构 6.2.3二叉树的遍历 6.3线索二叉树 6.3.1二叉树的线索化 6.3.2利用线索遍历 6.4树、森林、二叉树之间的关系 6.4.1树的存储结构 6.4.2森林与二叉树的转换 6.4.3树和森林的遍历 6.5 哈夫曼算法及其应用 6.5.1 哈夫曼树的定义 6.5.2哈夫曼二叉树的构造 6.5.3 哈夫曼树在编码问题中的应用 小结 习题 拓展实验:创建二叉树 第7章 图 7.1 图的概念与ADT定义 7.1.1 图的概念 7.1.2 图的抽象数据类型定义 7.2 图的存储结构 7.2.1 邻接矩阵 7.2.2邻接表 7.2.3十字链表 7.2.4邻接多重表 7.3图的遍历 7.3.1深度优先搜索 7.3.2广度优先搜索 7.4图的应用 7.4.1 生成树 7.4.2最短路径 7.4.3 拓扑排序 7.4.4关键路径 小结 习题 拓展实验:图的深度优先搜索 第8章 查找 8.1 查找的基本概念 8.2静态查找问题 8.2.1顺序查找 8.2.2二分查找 8.3线性表的查找方法 8.3.1线性查找 8.3.2折半查找 8.3.3 分块查找 8.4树表的查找方法 8.4.1 二叉查找树 8.4.2平衡二叉树 8.4.3 B-树 8.5 哈希表的查找方法 8.5.1 哈希表 8.5.2 构造哈希表的基本方法 8.5.3解决冲突的方法 8.5.4 哈希表的查找方法 8.6各种查找方法的比较 小结 习题 拓展实验:折半查找 第9章 排序 9.1排序的基本概念 9.2内部排序 9.2.1 插入排序 9.2.2 冒泡排序 9.2.3快速排序 9.2.4选择排序 9.2.5 归并排序 9.2.6 基数排序 9.3 内部排序方法比较 9.4 内部排序方法的选择 9.5外部排序简介 小结 习题 拓展实验:希尔排序 第10章递归 10.1 递归的定义与类型 10.1.1递归的定义 10.1.2递归的类型 10.2递归应用举例 10.2.1汉诺塔问题 10.2.2八皇后问题 10.3递归的实现 10.4递归到非递归的转换过程 10.5 递归的时间和空问复杂度 小结 习题 拓展实验:汉诺塔问题研究 第11章 文件 11.1外存储器简介 11.2有关文件的概念 11.2.1 文件及其类别 11.2.2文件的操作 11.3 文件的组织 11.3.1 顺序文件 11.3.2索引文件 11.3.3散列文件 11.3.4多关键字文件 小结 习题 拓展实验:索引文件 参考文献

编辑推荐

《高等学校计算机科学与技术专业核心课程系列规划教材:数据结构与算法(C语言版)》语言与选材精练、概念清晰、注重实用、逻辑性强,对于各章节中所涉及的数据结构与算法都给出了C语言描述,并都附有大量的习题,便于学生理解与掌握。《高等学校计算机科学与技术专业核心课程系列规划教材:数据结构与算法(C语言版)》适合作为高等院校计算机及相关专业的教材,也可作为计算机应用技术人员的参考书。

作者简介

《高等学校计算机科学与技术专业核心课程系列规划教材:数据结构与算法(C语言版)》为高等院校计算机及相关专业“数据结构”课程的教学用书,系统地介绍了各种典型的数据结构,内容包括:数据结构概论、线性表、栈与队列、串、数组、树、图、查找、排序、递归、文件等:为了加强对算法的理解,还介绍了算法分析方面的内容。


 数据结构与算法下载



发布书评

 
 


 

外国儿童文学,篆刻,百科,生物科学,科普,初中通用,育儿亲子,美容护肤PDF图书下载,。 零度图书网 

零度图书网 @ 2024