本书介绍了数据结构的基本概念和基本算法。全书共11章,主要内容包括:绪论、线性表、栈和队列、串、数组和广义表、树、图、查找、内排、文件和上机实验等。全书内容深入浅出,条理清晰,概念清楚,逻辑推理严谨,内容翔实,既注重数据结构和算法原理,又十分强调程序设计训练。书中算法都配有完整的C程序,程序结构清晰,构思精巧,所有程序都已在Win-TC2.0下编译通过并能正确运行,它们既是学习数据结构和算法的很好示例,也是很好的程序设计示例。本书配有大量的实例和图示,并有丰富的习题,适于自学。
本书是供普通高等院校计算机科学与技术专业本、专科学生使用的教材,也可供从事计算机工作者和其他希望学习数据结构的人员参考。

第1章 绪论
“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。在这之前,它的某些内容曾在其他课程,如表处理语言中有所阐述。1968年在美国一些大学的计算机系的教学计划中,虽然把数据结构规定为一门课程,但对课程的范围仍没有作明确规定。当时,数据结构几乎和图论,特别是和表、树的理论为同义语。随后,数据结构这个概念扩充到包括网络、集合代数论、格、关系等方面,从而变成了现在称之为“离散结构”的内容。然而,由于数据必须在计算机中进行处理,因此,不仅考虑数据本身的数学性质,还必须考虑数据的存储结构,这就进一步扩大了数据结构的内容。近年来,随着数据库系统的不断发展,在“数据结构”课程中又增加了文件管理(特别是大型文件的组织等)的内容。
1968年美国唐.欧。克努特教授开创了数据结构的*初体系,他所著的《计算机程序设计》**卷《基本算法》是**本较系统地阐述数据的逻辑结构和存储结构及其操作的著作,从20世纪60年代末到70年代初,出现了大型程序,软件也相对独立,结构程序设计成为程序设计方法学的主要内容,人们就越来越重视数据结构,并认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。从20世纪60年代中期到80年代初,各种版本的数据结构著作相继出现。
目前,在我国数据结构已经不仅仅是计算机专业教学计划中的核心课程之一,也是其他非计算机专业的主要选修课程之一。
1.1 什么是数据结构
什么是数据结构?这是一个难以直接回答的问题。一般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法(algorithm),*后编出程序、进行测试、调整直至得到*终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。为了说明这个问题,首先举一个例子,然后再给出明确的含义。 假定有一个学生通讯录,记录了某校全体学生的姓名和相应住址,现在要写一个算法,要求当给定任何一个学生的姓名时,该算法能够查出该学生的住址。这样一个算法的设计将完全取决于��讯录中的学生姓名及相应的住址是如何组织的,以及计算机是怎样存储通讯录中的信息的。 如果通讯录中的学生姓名是随意排列的,其次序没有任何规律,那么当给定一个姓名时,则只能对通讯录从头开始逐个与给定的姓名比较,顺序查对,直至找到所给定的姓名为止。这种方法相当费时间,效率很低。然而,若我们对学生通讯录进行适当的组织,按学生所在班级来排列,并且再造一个索引表,这个表用来登记每个班级学生姓名在通讯录中的起始位置。这样一来,情况将大为改善。这时,当要查找某学生的住址时,则可先从索引表中查到该学生所在班级的学生姓名是从何处起始的,然后就从此起始处开始查找,而不必去查看其他部分的姓名。由于采用了新的结构,于是就可以写出一个完全不相同的算法。
……

第1章 绪论
1.1 什么是数据结构
1.2 基本概念和常用术语
1.3 数据抽象和抽象数据类型
1.3.1 数据抽象
1.3.2 抽象数据类型
1.3.3 抽象数据类型描述和实现
1.4 算法和算法分析
1.4.1 算法及其性能标准
1.4.2 算法时间复杂度和渐近时间复杂度
1.4.3 算法的空间复杂度
小结
习题
第2章 线性表
2.1 线性表概念
2.2 线性表的顺序表示和实现
2.2.1 线性表的顺序存储结构
2.2.2 线性表在顺序存储结构下的运算
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向循环链表
2.3.4 顺序表和链表的比较
2.4 一元多项式的表示及相加
小结
习题
第3章 栈和队列
3.1 栈
3.1.1 栈的定义及其运算
3.1.2 顺序栈
3.1.3 多栈共享邻接空间
3.1.4 链栈
3.1.5 栈的应用举例
3.1.6 栈与递归的实现
3.2 队列
3.2.1 队列的定义
3.2.2顺序队列
3.2.3 链队列
3.2.4 队列应用举例
小结
习题
第4章 串
4.1 串的类型定义
4.2 串的定长顺序存储
4.3 串的堆存储结构
4.3.1 串名存储映像
4.3.2 堆存储结构
4.3.3 基于堆结构的基本运算
4.4 串的块链存储结构
4.5 模式匹配
4.6 串的应用举例——正文编辑
小结
习题
第5章 数组和广义表
5.1 数组类型的定义
5.2 数组顺序存储和实现
5.3 矩阵压缩存储
5.3.1 对称矩阵
5.3.2 三角矩阵
5.3.3 带状矩阵
5.4 稀疏矩阵
5.4.1 稀疏矩阵三元组表存储
5.4.2 稀疏矩阵十字链表存储
5.5 广义表
5.5.1 广义表的定义和基本运算
5.5.2 广义表的存储
5.5.3 广义表基本操作的实现
小结
习题
第6章 树
6.1 树的基本概念
6.1.1 树的定义
6.1.2 树的逻辑表示方法
6.1.3 树的基本术语
……
第7章 图
第8章 查找
第9章 内排序
第10章 文件
第11章 上机实验题
参考文献

本书针对应用型本科和高职高专学生的特点,结合编者多年的教学和编程实践经验,力图用生动、通俗易懂的语言,并结合大量的算法实例来讲解各个知识点,便于读者理解和掌握。
本书通过各种实例具体讲解如何运用各种数据结构和算法设计方法,使学生不但可以印证许多基本概念,而且能加深理解,以激发学生的学习兴趣,书中所有实例程序都己在Win-T02.0下编译通过并能正确运行。
本书每章都配有小结和习题,便于读者掌握各章的**和难点,并进行必要的训练;为了方便学生上机实训练习,本书还专门设计了8套上机实验题,供学生在每章学习过后上机练习,巩固所学知识。