发表于2024-11-24
数据结构毫无疑问是计算机科学既经典又核心的课程之一,不管是从事计算机软件还是硬件的开发工作,如果没有系统地学习数据结构或者是没有专心自学过,很容易被人打上“非专业”的标签。对于任何在信息技术行业工作的专业人员或者想进入此行业的人来说,什么时候开始学数据结构都不会晚,更不会过时。
从“数据结构”的名字看,它不仅仅只是讲授数据的结构以及在计算机内如何存储和组织数据的方式,这些只是它的表面现象。数据结构背后真正蕴含的是与之息息相关的算法,精心选择的数据结构配合恰如其分的算法就意味着数据或者信息在计算机内被高效率地存储和高效率地处理。算法其实就是数据结构的灵魂,它既神秘又神奇“好玩”,当然对初学者也比较难,算法可以说是“聪明人在计算机上的游戏”。
本书是一本综合而且全面讲述数据结构及其算法分析的教科书,为了便于高校的教学或者读者自学,作者在描述数据结构原理和算法时文字清晰并且严谨,为每个算法及其数据结构提供了演算的详细图解。另外,为了适合在教学中让学生上机实践或者自学者上机“操练”,本书为每个经典的算法都提供了C语言编写的完整范例程序的源代码,每个范例程序都不需要经过修改,直接通过编译就可以运行,目的就是让本书的学习者以这些范例程序作为参照迅速掌握数据结构和算法的要点。
全书的所有范例程序都可以在标准的C语言编程环境中编译通过并且成功运行,我们在改编本书的过程中选用了免费的Dev C++ 5.11集成开发环境,对原书的所有范例程序进行编译、修改、调试和测试,并确保它们都可以准确无误地运行。附录A包含了“C/C++编译程序的介绍与安装”,其中重点就介绍了Dev C++。附录B则包含了“C语言快速入门”。
本书用轻松的图解方式来讲解数据结构,全书采用丰富的图例阐述数据结构的基本概念及应用,并将重要理论、演算方法做详细的诠释与举例,是一本兼具内容及专业的数据结构的教学用书。
由于作者长期从事信息教育及写作,在文字的表达上简洁明了、逻辑清晰,并安排了大量的习题,供读者检验学习成果。
胡昭民,现任荣钦科技股份有限公司董事长,美国Rochester Institute of Technology计算机科学研究所毕业,长期从事信息教育及计算机图书写作的工作,并监制过多套游戏及教学软件的研发。
第1章 数据结构导论 1
1-1 数据结构简介 2
1-1-1 数据与信息 2
1-1-2 算法 3
1-1-3 算法的条件 3
1-1-4 数据结构的应用 6
1-2 数据抽象化 7
1-2-1 基本数据类型 7
1-2-2 抽象数据类型 7
1-3 算法与程序设计 8
1-3-1 认识程序设计 8
1-3-2 程序开发流程 9
1-3-3 程序设计的风格 9
1-4 面向对象程序设计 11
1-4-1 封装(Encapsulation) 12
1-4-2 继承(Inheritance) 13
1-4-3 多态(Polymorphism) 13
1-5 模块化设计与C语言 13
1-5-1 函数的基本概念 13
1-5-2 参数类型的介绍 14
1-5-3 参数的传递方式 15
1-6 递归算法 15
1-6-1 递归的定义 15
1-6-2 斐波拉契数列 17
1-6-3 汉诺塔问题 18
1-7 程序效率的分析 23
1-7-1 Big-oh 25
1-7-2 Ω(omega) 26
1-7-3 θ(theta) 27
本章习题 27
第2章 线性表 32
2-1 线性表的定义 33
2-1-1 线性表的用途 33
2-2 数组 34
2-2-1 一维数组 34
2-2-2 二维数组 36
2-2-3 多维数组 40
2-2-4 结构数组 44
2-2-5 字符数组 46
2-2-6 字符串数组 48
2-2-7 指针数组 49
2-3 矩阵 50
2-3-1 矩阵的运算 51
2-3-2 稀疏矩阵 53
2-3-3 上三角形矩阵 55
2-3-4 下三角形矩阵 59
2-3-5 带状矩阵 64
本章习题 65
第3章 链表 69
3-1 动态分配内存 70
3-1-1 C的动态分配变量 70
3-1-2 C++的动态分配变量 72
3-2 单向链表 73
3-2-1 建立单向链表 74
3-2-2 遍历单向链表 75
3-2-3 释放单向链表节点的空间 76
3-2-4 单向链表插入新节点 77
3-2-5 单向链表删除节点 79
3-2-6 单向链表的反转 81
3-3 环形链表 83
3-3-1 环形链表的建立与遍历 83
3-3-2 环形链表中插入新节点 85
3-3-3 环形链表节点的删除 86
3-3-4 环形链表的连接功能 88
3-4 双向链表 89
3-4-1 双向链表的建立与遍历 90
3-4-2 双向链表中加入新节点 92
3-4-3 双向链表节点的删除 94
3-5 链表相关应用简介 96
3-5-1 多项式表式法 96
3-5-2 稀疏矩阵表示法 100
本章习题 102
第4章 堆栈与队列 109
4-1 堆栈简介 110
4-1-1 堆栈的基本操作 111
4-1-2 用数组实现堆栈 111
4-1-3 用链表实现堆栈 112
4-1-4 堆栈类样板的实现 114
4-1-5 老鼠走迷宫 116
4-1-6 八皇后问题 119
4-2 算术表达式的表示法 120
4-2-1 中序转为前序与后序 121
4-2-2 前序与后序转为中序 126
4-2-3 中序表示法求值 129
4-2-4 前序法的求值运算 130
4-2-5 后序法的求值运算 131
4-3 队列 132
4-3-1 队列的基本操作 133
4-3-2 用数组实现队列 133
4-3-3 环形队列 135
4-3-4 双向队列 139
4-3-5 双向队列 141
4-3-6 优先队列 143
本章习题 144
第5章 树状结构 156
5-1 树的基本概念 157
5-1-1 专有名词介绍 158
5-2 二叉树 159
5-2-1 二叉树的特性 159
5-2-2 特殊二叉树简介 160
5-3 二叉树的存储方式 161
5-3-1 一维数组表示法 161
5-3-2 链表表示法 164
5-4 二叉树的遍历 166
5-4-1 中序遍历 166
5-4-2 后序遍历 167
5-4-3 前序遍历 167
5-4-4 二叉树节点的插入与删除 170
5-4-5 二叉运算树 174
5-5 线索二叉树 176
5-5-1 二叉树转为线索二叉树 176
5-6 树的二叉树表示法 180
5-6-1 树转化为二叉树 180
5-6-2 二叉树转换成树 182
5-6-3 森林化为二叉树 183
5-6-4 二叉树转换成森林 184
5-6-5 树与森林的遍历 185
5-6-6 确定唯一二叉树 189
5-7 优化二叉查找树 191
5-7-1 扩充二叉树 191
5-7-2 霍夫曼树 192
5-8 平衡树 194
5-8-1 平衡树的定义 194
5-9 高级树状结构的研究 196
5-9-1 决策树 196
5-9-2 B树 198
5-9-3 二叉空间分割树 198
5-9-4 四叉树与八叉树 199
本章习题 200
第6章 图形结构 210
6-1 图形简介 211
6-1-1 图的定义 212
6-1-2 无向图 212
6-1-3 有向图 214
6-2 图的数据表示法 215
6-2-1 邻接矩阵法 215
6-2-2 邻接表法 218
6-2-3 邻接复合链表法 220
6-2-4 索引表格法 222
6-3 图的遍历 225
6-3-1 深度优先遍历法 225
6-3-2 广度优先遍历法 227
6-4 生成树 229
6-4-1 DFS生成树和BFS生成树 229
6-4-2 最小生成树 231
6-4-3 Kruskal算法 231
6-4-4 Prim算法 235
6-5 图的最短路径 236
6-5-1 单点对全部顶点 237
6-5-2 两两顶点间的最短路径 240
6-6 AOV网络与拓扑排序 244
6-6-1 拓扑排列简介 244
6-7 AOE网络 246
6-7-1 关键路径 246
本章习题 248
第7章 排序 257
7-1 排序简介 258
7-1-1 排序的分类 259
7-2 内部排序法 260
7-2-1 冒泡排序法 260
7-2-2 选择排序法 262
7-2-3 插入排序法 264
7-2-4 希尔排序法 266
7-2-5 合并排序法 268
7-2-6 快速排序法 269
7-2-7 堆积排序法 271
7-2-8 基数排序法 278
7-3 外部排序法 280
7-3-1 直接合并排序法 280
7-3-2 k路合并法 284
7-3-3 多相合并法 284
本章习题 285
第8章 查找 295
8-1 常见的查找方法 296
8-1-1 顺序查找法 296
8-1-2 二分查找法 297
8-1-3 插值查找法 299
8-1-4 斐波那契查找法 301
8-2 哈希查找法 305
8-2-1 哈希法简介 305
8-3 常见的哈希函数 306
8-3-1 除留余数法 306
8-3-2 平方取中法 307
8-3-3 折叠法 308
8-3-4 数字分析法 308
8-4 碰撞与溢出问题的处理 309
8-4-1 线性探测法 309
8-4-2 平方探测 310
8-4-3 再哈希 310
8-4-4 链表 311
本章习题 312
附录A C/C++编译程序的介绍与安装 318
A-1 C/C++编译程序简介 319
A-1-1 Visual C++ 2010 Express 319
A-1-2 C++ Builder 320
A-1-3 Visual C++ 320
A-1-4 Dev C++ 321
A-1-5 GCC 322
A-2 Dev C++的安装与介绍 322
A-2-1 下载Dev-C++ 323
A-2-2 安装Dev C++ 323
附录B C语言快速入门介绍与安装 329
B-1 轻松学C程序 330
B-1-1 编译与执行 331
B-1-2 编译程序 332
B-1-3 开始执行程序 333
B-2 C的基本数据处理 333
B-2-1 变量 333
B-2-2 常数 334
B-2-3 数据类型简介 334
B-3 C语言的输出与输入 335
B-3-1 printf()函数 336
B-3-2 scanf()函数 337
B-4 流程控制 338
B-4-1 顺序结构 338
B-4-2 选择结构 339
B-4-3 重复结构 343
B-5 数组简介 346
B-5-1 字符串简介 347
B-5-2 字符串数组 347
B-6 函数介绍 349
B-6-1 传递参数的方式 350
B-6-2 标准函数库 352
第8章 查找
在数据处理过程中,是否能在最短时间内查找到所需要的数据,是一个相当值得信息从业人员关心的问题。所谓查找(search,或搜索)指的是从数据文件中找出满足某些条件的记录。用以查找的条件称为“键值”(key),就如同排序所用的键值一样。
例如联系人中找某人的电话号码,那么这个人的姓名就成为在联系人中查找电话号码的键值。通常影响查找时间长短的主要因素包括算法的选择、数据存储的方式和结构。
8-1 常见的查找方法
如果根据数据量的大小,可将查找分为:
1. 内部查找:数据量较小的文件,可以一次性全部加载到内存中进行查找。
2. 外部查找:数据量大的文件,无法一次加载到内存中处理,而需使用辅助存储器来分次处理。
如果从另一个角度来看,查找的技巧又可分为“静态查找”和“动态查找”两种。定义如下所示。
1. 静态查找:指的是在查找过程中,查找的表格或文件的内容不会被改动。例如符号表的查找就是一种静态查找。
2. 动态查找:指的是在查找过程中,查找的表格或文件的内容可能会被改动,例如在树状结构中所谈的B-tree查找就属于一种动态查找。
至于查找技巧中比较常见的方法有顺序法、二分查找法、斐波那契法、插值法、哈希法、m路查找树、B-tree等。为了让大家能确实掌握各种查找的技巧和基本原理,以便应用于日后的各种领域,现将几个主要的查找方法分述于后。
8-1-1 顺序查找法
顺序查找通常用于未经组织化的文件,又称为线性查找。查找的过程从文件第一项数据开始,按序比较每个键值。由于顺序查找法是逐项对比,因此只要一找到数据就可以结束数据的查找。以n项数据为例,使用顺序查找法来查找数据时,有可能在第1项就找到了,在这种情形下仅需执行一次比较操作。如果数据在第2项、第3项…第n项,则其需要的比较次数分别为2、3、4、…、n次。因此,在平均情况下,顺序查找法,查找一项数据需要的平均比较次数为 (n+1)/2。
现在以一个例子来说明,假设已有数列74、53、61、28、99、46、88,若要查找28,则需要比较4次;要查找74仅需比较1次;要查找88则需查找7次,这表示当查找的数列长度n很大时,利用顺序查找是不太适合的,它是一种适用于小数据文件的查找方法。
另外,在最差的情况下,逐一对比后没有找到数据,则必须花费n次,其最坏情况下(Worst Case)的时间复杂度为O(n)。也就是说,除非可以预知要查找的数据大概位于文件的前端,否则当文件的数据项数过大时,顺序查找法在查找的效率上显然不如其他的查找法。
线性查找法的优点是文件或数据事前不需要经过任何的处理与排序,也由于它未考虑到数据的特征对于查找的影响,所以在应用上适合于各种情况,其缺点则是查找的速度较慢。
顺序查找法的C语言算法如下所示。
while (val!=-1)
{
find=0;
printf("请输入查找键值(1-150),输入-1离开:");
scanf("%d",&val;);
for (i=0;i<80;i++)
{
if(data[i]==val)
{
printf("在第 %3d个位置找到键值 [%3d] ",i+1,data[i]);
find++;
}
}
if(find==0 && val !=-1)
printf("######没有找到 [%3d]###### ",val);
}
8.1.1
请设计一个C程序,以随机数生成1~150之间的80个整数,然后实现顺序查找法的过程。
请参考程序CH08_01.c,本范例程序的运行结果如图8-1所示。
图8-1 实现顺序查找法的范例程序的运行结果
8-1-2 二分查找法
如果要查找的数据已经事先排好序了,则可使用二分查找法来进行查找。二分查找法是将数据平均分割成两份,再比较键值与中间值的大小,如果键值小于中间值,可确定要查找的数据在前半段,否则在后半部。如此分割数次直到找到或确定不存在为止。例如,以下已排序的数列 2、3、5、8、9、11、12、16、18 ,而所要查找值为11时:
首先跟第5个数值 9 比较,如图8-2所示。
图8-2 先和中值比较
因为11>9,所以和后半部的中间值 12 比较,如图8-3所示:
图8-3 再和后半部的中值比较
因为 11<12,所以和前半部的中间值 11比较,如图8-4所示:
图8-4 再和后半部的前半部中值比较
因为 11=11,表示查找到了即查找完成,如果不相等则表示没有找到。
二分查找法的C语言算法如下所示。
int bin_search(int data[50],int val)
{
int low,mid,high;
low=0;
high=49;
printf("查找过程中...... ");
while(low <= high && val !=-1)
{
mid=(low+high)/2 图解数据结构(第二版) 下载 mobi epub pdf txt 电子书 格式
图解数据结构(第二版) 下载 mobi pdf epub txt 电子书 格式 2024
图解数据结构(第二版) 下载 mobi epub pdf 电子书图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)
评分。
评分好书
评分不错
评分。
评分图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)图解数据结构(第二版)
评分一般吧,不适合初学者,内容不够详细。
评分不错
评分。
图解数据结构(第二版) mobi epub pdf txt 电子书 格式下载 2024