本书是作者针对数据结构课程概念多、算法灵活和抽象性强的特点,在总结长期教学经验的基础上编写而成的。
本书共10章,内容涵盖数据结构的基本概念,定义了线性表、栈、队列、串、数组、广义表、树和二叉树、图、查找、排序等各种结构的抽象数据类型,并给出了相应操作的实现算法。采用C语言描述算法,并给出了各种算法的效率分析,以及这些结构在计算机科学及其他领域的应用。每章后均配有典型算法设计、上机实验题和练习题。所有算法都在VC++环境下调试通过。
数据结构与算法
C语言版
徐凤生 主编
数据结构课程的特点是概念多、算法灵活和抽象性强。针对这种情况,作者在参考各种数据结构教材的基础上,结合多年的教学经验,编写了这本适用于普通高等院校计算机及相关专业本科生数据结构课程的教材。本书的编写突出了课程学科能力的培养,体现了兼顾“理论和应用”的教学改革理念。
本书特点:
语言通俗易懂,阐述简洁明了。
重点突出算法设计思路,注重培养学生的编程思想和解决实际问题的能力。
为激发学生学习该课程的兴趣,增强学生的创新意识,书中融入了一些利用所学知识解决实际问题的例子,如真值表的求解算法、出栈序列的求解算法等。
算法丰富,讲解透彻,便于学生自学。
通过典型算法设计的分析,使学生对所学知识的掌握更加系统化和条理化,更易于对所学知识融会贯通和举一反三。
本书为教师提供教学课件、习题答案以及所有算法的调试程序,有需要者可登录华章网站(www.hzbook.com)下载。
“数据结构”是计算机程序设计的重要理论技术基础,是计算机学科的核心课程,也是计算机专业考研的必考课程,而且已成为其他理工科专业的热门课程。学好该课程,不仅对其后续算法设计、数值分析、操作系统、编译原理等课程的学习有很大帮助,而且在实际中有广泛的用途。
数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算的实现。它不仅为计算机语言进行程序设计提供了方法性的理论指导,还在一个更高的层次上总结了程序设计的常用方法和常用技巧。
“数据结构”课程的特点是概念多、算法灵活和抽象性强。针对这种情况,我们在参考各种数据结构教材的基础上,结合作者多年的教学经验,编写了这本适用于普通高等院校计算机及相关专业本科生的数据结构教材。该教材的编写突出了课程学科能力的培养,体现了兼顾“理论和应用”的教学改革理念。
本书分为10章,第1章绪论,介绍数据、数据结构、抽象数据类型等基本概念,特别是算法分析的方法;第2章线性表,介绍线性表的两种存储结构(顺序表和链表)的逻辑结构与基本运算的实现过程;第3章栈与队列,介绍两种特殊的线性结构的概念与应用;第4章串,介绍串的概念与模式匹配算法;第5章数组与广义表,介绍数组和稀疏矩阵的概念及相关运算的实现,以及广义表的存储结构及相关运算的实现;第6章树与二叉树,介绍树与二叉树的概念和各种运算的实现过程,其中特别突出二叉树的各种递归和非递归算法;第7章图,介绍图的基本概念和各种运算的实现过程;第8章查找,介绍各种常用查找算法的实现过程;第9章排序,介绍各种常用排序算法的实现过程;第10章文件,介绍常用的文件结构。
数据结构是一门应用性非常强的课程,必须在掌握了各种数据结构的基础上,尽可能多地上机练习。为此,本书每章后面都配有相应的上机实验题。
全书采用C语言作为数据结构和算法的描述语言,所有算法均在VC++环境下调试通过。
本书由徐凤生教授任主编。其中,第1章至第4章和第6章至第9章由徐凤生编写,第5章由戎丽霞编写,第10章由李天志编写。最后,全书由徐凤生统稿并定稿。
本书具有以下特色:
1)语言通俗易懂,阐述简洁明了。
2)重点突出算法设计思路,注重培养学生的编程思想和解决实际问题的能力。
3)为激发学生学习该课程的兴趣,增强学生的创新意识,书中融入了一些利用所学知识解决实际问题的例子,如真值表的求解算法、出栈序列的求解算法等。
4)算法丰富,讲解透彻,便于学生自学。
5)通过典型算法设计的分析,使学生所学知识更加系统化和条理化,更易于对所学知识融会贯通和举一反三。
6)为方便教师教学,本书配有电子教案和习题答案,可登录华章网站(www.hzbook.com)下载或发送邮件至xfs@dzu.edu.cn与作者联系。
在编写中我们参阅了许多数据结构教材和相关资料,在此向其作者一并表示感谢。本教材的出版得到了德州学院教材出版基金的资助。最后,还要特别感谢机械工业出版社华章分社的大力支持,使得本书得以顺利出版。
限于作者水平,书中不当和疏漏之处在所难免,敬请读者不吝指正。
编者
计算机\数据结构
数据结构课程的特点是概念多、算法灵活和抽象性强。针对这种情况,我们在参考各种数据结构教材的基础上,结合作者多年的教学经验,编写了这本适用于普通高等院校计算机及相关专业本科生数据结构课程的教材。本书的编写突出了课程学科能力的培养,体现了兼顾“理论和应用”的教学改革理念。
本书具有以下特色:
语言通俗易懂,阐述简洁明了。
重点突出算法设计思路,注重培养学生的编程思想和解决实际问题的能力。
为激发学生学习该课程的兴趣,增强学生的创新意识,书中融入了一些利用所学知识解决实际问题的例子,如真值表的求解算法、出栈序列的求解算法等。
算法丰富,讲解透彻,便于学生自学。
通过典型算法设计的分析,使学生对所学知识的掌握更加系统化和条理化,更易于对所学知识的融会贯通和举一反三。
本书为教师提供教学课件、习题答案以及所有算法的调试程序,有需要者可登录华章网站(www.hzbook.com)下载。
前言
教学建议
第1章绪论1
11数据结构的研究对象1
12数据结构的发展概况4
13基本概念与术语4
14数据类型与抽象数据类型6
141数据类型6
142抽象数据类型6
143抽象数据类型的表示与实现7
15算法与算法分析9
151算法9
152算法设计的原则10
153算法效率的衡量方法和准则10
154算法的存储空间需求12
16典型例题12
17上机实验13
习题13
第2章线性表16
21线性表的定义16
211线性表的概念16
212线性表的抽象数据类型定义16
22线性表的顺序表示与实现17
221线性表的顺序表示17
222线性表的顺序实现18
223顺序表的应用举例21
23线性表的链式表示与实现22
231单链表22
232双向链表26
233循环链表29
234静态链表31
235链表的应用举例33
24典型例题35
25上机实验37
习题39
第3章栈与队列41
31栈41
311栈的抽象数据类型定义41
312栈的表示与实现42
32栈的应用举例44
321数制转换44
322括号匹配的检验45
323表达式求值46
324求命题公式的真值50
33栈与递归实现53
331递归的定义53
332递归与栈的关系53
333递归的实现54
334用递归求所有出栈序列56
335递归的消除57
34队列59
341队列的抽象数据类型定义59
342队列的链式表示与实现60
343队列的顺序表示与实现——循环队列61
344队列的应用举例63
35典型例题64
36上机实验66
习题68
第4章串70
41串的定义70
42串的表示与实现72
421串的顺序存储表示72
422串的链式存储表示75
43串的模式匹配75
431简单匹配算法75
432首尾匹配算法77
433KMP算法78
44典型例题80
45上机实验82
习题83
第5章数组与广义表85
51数组的定义85
52数组的顺序存储86
53矩阵的压缩存储88
531特殊矩阵89
532稀疏矩阵90
54广义表94
541广义表的定义94
542广义表的存储结构96
55典型例题98
56上机实验99
习题100
第6章树与二叉树101
61树的定义101
611树的概念与术语101
612树的逻辑表示方法102
613树的抽象数据类型定义102
62二叉树的定义103
621二叉树的概念103
622二叉树的重要性质105
63二叉树的存储结构106
631二叉树的顺序存储表示106
632二叉树的链式存储表示106
64二叉树的遍历108
641二叉树遍历的概念108
642二叉树遍历的递归算法108
643二叉树遍历的非递归算法109
644层次遍历算法111
645遍历算法的应用举例112
65二叉树的构造115
66线索二叉树116
661线索二叉树的定义116
662线索链表的建立117
663线索链表的遍历算法118
67树和森林的表示方法119
671双亲表示法119
672孩子链表表示法120
673孩子-兄弟链表表示法121
674树、森林和二叉树的对应关系121
68树和森林的遍历122
681树的遍历122
682森林的遍历123
683树遍历算法的应用124
69赫夫曼树与赫夫曼编码124
691赫夫曼树的定义125
692赫夫曼树的构造125
693赫夫曼编码127
610典型例题128
611上机实验130
习题130
第7章图133
71图的定义与术语133
711图的相关术语133
712图的抽象数据类型定义135
72图的存储表示136
721图的邻接矩阵存储表示136
722图的邻接表存储表示137
723有向图的十字链表存储表示138
724无向图的邻接多重表存储表示140
73图的遍历141
731深度优先搜索遍历图141
732广度优先搜索遍历图142
733图遍历的应用举例143
74最小生成树145
741普里姆算法145
742克鲁斯卡尔算法147
75两点之间的最短路径问题148
751从某个源点到其余各点的最短路径148
752每一对顶点之间的最短路径150
76拓扑排序151
77关键路径153
78典型例题156
79上机实验158
习题160
第8章查找162
81基本概念162
82静态查找表163
821顺序查找163
822有序表查找164
823索引查找167
83动态查找树表168
831二叉排序树169
832平衡二叉树173
833B-树179
834B+树183
835键树184
84哈希表185
841哈希表的概念185
842哈希函数的构造方法185
843处理冲突的方法187
844哈希表的查找189
845哈希表的插入操作190
846哈希表的删除操作191
85典型例题191
86上机实验193
习题194
第9章排序196
91概述196
911什么是排序196
912内部排序和外部排序196
913内部排序的方法197
92插入排序198
921直接插入排序198
922折半插入排序199
923二路插入排序200
924表插入排序202
925希尔排序204
93交换排序205
931起泡排序205
932快速排序206
94选择排序209
941简单选择排序209
942堆排序209
95归并排序212
96基数排序213
961多关键字排序213
962链式基数排序214
97各种排序方法的综合比较216
98外排序简介217
981外存信息的存取218
982外排序的基本方法218
99典型例题219
910上机实验221
习题222
第10章文件224
101文件的基本概念224
1011什么是文件224
1012文件的逻辑结构及操作224
1013文件的存储结构225
102顺序文件225
103索引文件226
1031ISAM文件227
1032VSAM文件229
104哈希文件231
105多关键字文件232
1051多重表文件232
1052倒排文件232
1053倒排文件的应用234
106典型例题235
107上机实验237
习题237
参考文献239