数据结构（C语言描述）

中国水利水电出版社

【作者】马秋菊主编

【I S B N 】978-7-5084-3839-6

【责任编辑】张玉玲

【适用读者群】高职高专

【出版时间】2006-09-01

【开本】16开本

【装帧信息】平装（光膜）

【版次】第1版

【页数】204

【千字数】

【印张】

【定价】￥20

【丛书】21世纪高职高专新概念教材

【备注信息】

图书详情

简介

本书特色

前言

章节列表

精彩阅读

下载资源

相关图书

本书所选内容都是高职高专计算机及相关专业必须掌握的知识点，全书共9章，主要内容包括：线性表、栈和队列、数组、特殊矩阵和广义表、串、树、图、查找和排序等。各章中对所涉及的数据结构与算法均给出了通俗的解释和类C语言描述，其中的重点内容是以C语言函数或过程形式给出的，同时在每章后面的上机实习中给出了具体应用调用（已经运行通过），其目的是使读者能够将学到的知识落实到应用中。

本书内容精炼、叙述通俗、示例说服力强、便于讲解和学习、突出实用性和应用性。

本书可作为高等职业学校、高等专科学校、成人高等学校及本科院校举办的二级职业技术学院计算机及相关专业数据结构的教材，也适合计算机软件开发的科技人员自学参考。

“数据结构”是计算机程序设计的重要理论技术基础，是计算机专业的核心课程。在目前大力发展职业技术应用教育的新形势下，急需概念通俗易懂，知识针对性强，实验、实习及工程训练等内容齐全的教科书，本书正是针对这种目的编写的。本书系统地介绍了各种数据结构的概念、存储结构和有关算法，并采用了当前通用的C语言描述算法。主要内容包括绪论、线性表、栈和队列、数组、串、树、图、查找和排序等。

参加本书编写的作者全部是有本课程教学实践和课程建设经验的教师，在多年的教学和课程建设的实践中，我们体会到，学生在学习中普遍存在的突出问题是：入门难、算法抽象难理解、算法与实现和应用存在一定距离、应用针对性差等，制约着学习效果。针对实际情况，我们进行了充分的讨论，在本课程建设的基础上，制定了本书的编写原则：重视基础，循序渐进，内容精炼，叙述通俗，重点突出，示例说服力强，便于讲解和学习，强调理论与实践相结合，突出实践和应用能力的培养。

本书的主要特点如下：

（1）教学内容的深度与广度合适、定位准确，具有鲜明的高职高专特色。

所选择的教学内容既体现了应用型人才教育对基础理论知识较扎实的要求即够用，又兼顾了知识的系统性与完整性、应用性和工程实践性。

（2）融入先进教学理念，概念通俗易懂、知识针对性强，符合应用型人才认知规律。

体现“以学生为主体”的现代教学理念，选择了具有启发性、思考性和鼓励自主学习的教学内容，设计了引发学生学习与探究兴趣的“驱动问题”，面向教学方法和过程，语言通俗，降低难度，针对性强，重点突出。

（3）算法描述清晰，有利于教师讲解。

在算法思想和算法描述中，尽量避免教学过程中的混淆，如“关键字”使用key标识符，则在同一问题中就不再选择key作为其他变量，使教学、理解更简单。

（4）强调理论与实践相结合，突出实践和应用能力的培养。

在重点知识突出的基础上，强调算法的具体实现：以C语言函数或过程形式给出内容，同时在每章后面的上机实习中给出了具体应用调用（已经运行通过），达到学以致用的目的，培养学生具有完整应用程序的开发理念，对应用系统开发有一个明晰的概念。

（5）本书配备了电子教案等相关教学资源。

电子教案中的实例是在PowerPoint环境下嵌入VBA技术来实现算法与数据处理的，使教学更形象、更容易理解，另外还可提供源代码、同步训练题等资料。

本书可作为职业技术应用型计算机专业教材，建议讲授学时为60～70学时。

本书由马秋菊主编，王学军、刘延岭任副主编。本书主要编写人员分工如下：第1～5章由马秋菊编写，第6章由殷华英编写，第7～9章由王学军编写；上机实习内容的第2、4～7章由刘延岭编写，第8、9章由张清涛编写，第3章由刘延岭与张清涛共同编写，全书由马秋菊和刘延岭统稿。另外参加大纲讨论、提供实用信息的人员还有：孔小利、宋汉珍、李海明、郝春雷、董国增、谢懿、张占昭、李小芳、薛茹等老师。在编写过程中，得到了主审马晓晨副教授和相关专家的指导，在此一并表示衷心的感谢。

由于编者水平有限，书中难免有一些不足之处，恳请广大读者批评指正。

序
前言
第1章数据结构概述 1
本章学习目标 1
1.1 为什么要学习数据结构 1
1.2 数据结构的有关概念和术语 3
1.2.1 基本概念和术语 3
1.2.2 数据结构定义 4
1.3 算法和算法描述 5
1.3.1 算法与算法特性 5
1.3.2 算法描述 6
1.4 算法时空效率分析方法 7
习题 9
第2章线性表 12
本章学习目标 12
2.1 线性表的逻辑结构 12
2.1.1 线性表的定义 12
2.1.2 线性表的基本操作 13
2.2 线性表的顺序存储结构及运算实现 13
2.2.1 顺序表 13
2.2.2 顺序表上基本运算的实现 14
2.3 线性表的链式存储和运算实现 18
2.3.1 单链表 18
2.3.2 单链表基本运算的实现 20
2.3.3 循环链表 24
2.3.4 双向链表 25
2.3.5 静态链表 28
2.3.6 顺序表和链表的比较 29
2.4 线性表的典型应用 29
习题 32
上机实习 33
第3章栈和队列 39
3.1 栈 39
3.1.1 栈的定义及基本运算 39
3.1.2 栈的顺序存储结构及运算实现 40
3.1.3 栈的链式存储结构及运算实现 42
3.2 队列 43
3.2.1 队列的定义及基本运算 43
3.2.2 队列的顺序存储结构及运算实现 44
3.2.3 队列的链式存储结构及运算实现 46
3.3 栈和队列的典型应用 48
习题 56
上机实习 57
第4章数组、特殊矩阵和广义表 64
本章学习目标 64
4.1 数组 64
4.1.1 数组的基本概念 64
4.1.2 数组的存储结构 65
4.2 特殊矩阵的压缩存储 66
4.2.1 对称矩阵 66
4.2.2 三角矩阵 67
4.2.3 对角矩阵 68
4.2.4 稀疏矩阵 69
4.3 广义表 75
4.3.1 广义表的定义和性质 75
4.3.2 广义表的基本运算 76
习题 76
上机实习 77
第5章串 80
本章学习目标 80
5.1 串的定义及其基本运算 80
5.1.1 串的基本概念 80
5.1.2 串的基本运算 80
5.2 串的存储结构 81
5.2.1 串的顺序存储 81
5.2.2 串的链式存储 82
5.3 串运算的应用 83
习题 85
上机实习 86
第6章树 89
本章学习目标 89
6.1 树的概念与表示 89
6.1.1 树的定义 89
6.1.2 树的相关术语 90
6.1.3 树的表示 91
6.2 二叉树的概念与性质 91
6.2.1 二叉树的基本概念 91
6.2.2 二叉树的重要性质 92
6.3 二叉树的存储结构 93
6.3.1 顺序存储结构 93
6.3.2 链式存储结构 94
6.3.3 建立二叉树的二叉链表 95
6.4 二叉树的遍历 96
6.5 线索二叉树 100
6.5.1 线索二叉树的定义及结构 100
6.5.2 中序线索二叉树操作 102
6.6 树的存储结构 104
6.7 树、森林与二叉树的转换 105
6.7.1 树和森林转换为二叉树 105
6.7.2 二叉树还原为树和森林 107
6.8 哈夫曼树及其应用 107
习题 113
上机实习 114
第7章图 118
本章学习目标 118
7.1 图的基本概念 118
7.2 图的存储表示 120
7.2.1 邻接矩阵 120
7.2.2 邻接表 121
7.3 图的遍历 123
7.3.1 深度优先遍历（DFS） 123
7.3.2 广度优先遍历（BFS） 124
7.4 图的生成树 125
7.4.1 生成树 125
7.4.2 最小生成树的基本概念 126
7.4.3 构造最小生成树的Prim算法 126
7.4.4 构造最小生成树的Kruskal算法 128
7.5 最短路径 128
7.6 拓扑排序 131
7.6.1 有向无环图的概念 131
7.6.2 AOV网与拓扑排序 131
7.7 关键路径 134
7.7.1 AOE网 134
7.7.2 关键路径 135
7.7.3 关键路径的确定 135
7.8 工程应用实例 136
习题 138
上机实习 140
第8章查找 145
本章学习目标 145
8.1 基本概念与术语 145
8.2 静态查找表 145
8.2.1 静态查找表结构 145
8.2.2 顺序查找 146
8.2.3 二分查找 147
8.2.4 分块查找 149
8.3 动态查找表 150
8.3.1 二叉排序树 150
8.3.2 二叉排序树的建立 150
8.3.3 平衡二叉树 154
8.3.4 B树 156
8.4 哈希表查找 157
8.4.1 哈希表与哈希方法 157
8.4.2 常用的哈希函数 158
8.4.3 处理冲突的方法 160
8.4.4 哈希表的查找分析 161
习题 161
上机实习 162
第9章排序 166
本章学习目标 166
9.1 基本概念 166
9.2 插入排序 167
9.2.1 直接插入排序 167
9.2.2 希尔排序 168
9.3 交换排序 169
9.3.1 冒泡排序 169
9.3.2 快速排序 170
9.4 选择排序 172
9.4.1 直接选择排序 172
9.4.2 堆排序（Heap Sort） 174
9.5 归并排序 176
9.6 基数排序 178
9.7 内部排序的比较 180
9.8 外部排序 180
9.8.1 外部排序 180
9.8.2 多路平衡归并的实现 182
习题 182
上机实习 183
参考文献 187

电子教案
源代码和习题参考答案

关闭

打印