本书是以高等工科院校本科计算机类专业、信息技术类专业和相关专业“应用型”人才培养为目标编写的一本实用性教材。以学习软件设计开发中涉及到的各种数据结构及常用算法和解决基本应用问题的实际应用需求为基本点,深入介绍了各种数据结构的定义(逻辑结构、存储结构和基本算法)和基本应用等方面的知识。本书以“数据结构”的逻辑结构作为引线,突出以实例和应用为特色,把数据结构与算法问题同应用问题结合起来,通过介绍大量的应用问题,缩短了理论知识与应用问题之间的距离。算法学习由基本算法和应用问题算法两部分组成,这里注重介绍算法的设计过程和算法分析。为便于教学,每章都有教学目标和教学提示,每章*后都配备有满足教学要求的各类习题。本书所有算法均在Microsoft Visual c++6.0��境中通过测试,并在附录A中给出了源程序以供读者选用。
本书可作为理工科高等院校计算机工程类、软件工程类和信息技术类等相关专业的教材,也可供从事相关工作的科技工作者参考。

第1章 数据结构和算法
教学目标:本书主要学习如何组织数据和设计算法,学习软件开发中所涉及到的各种常 用数据结构。作为全书导引,本章要求掌握数据、数据类型、数据结构、算法及算法分析等 基本概念和基础知识。另外,本章还结合课程学习要求,复习和掌握算法描述工具—C语言
中的指针类型与指针变量、结构类型与结构变量、函数与参数、递归定义和递归函数、动态 存储分配、文件操作、程序测试与测试集、测试数据的设计和程序调试等问题。
教学提示:如何合理地组织数据、**率地处理数据是扩大计算机应用领域、提高 软件效率的关键。因此,必须完整地讲解和理解数据结构(逻辑结构、存储结构和相关 算法)的定义及其实现的方法,算法数据类型的定义本质上是存储结构的实现。算法的时间性能分析是难点,算法的空间性能分析不可忽视。程序调试问题将影响算法的实现,在实践中要注意。
1.1 数据和数据类型
通常,我们将计算机的处理对象称为“数据”。数据的类型可分为数值型和非数值型两大类。本节介绍数据、数据元素、数据项、关键项、关键字、数据类型和抽象数据类型等有关知识。
1.1.1 数据和数据元素
1.数据
定义1.1在计算机科学中,数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称。
在计算机系统的表示层次,数据以各种数据类型来表示,在计算机系统的物理层次,数据都是以二进制形式表示的。
【例1.1】在计算机系统中,除数值型数据之外,字符、声音、图像、图形等信息是数据吗?
在计算机**语言程序设计课程中,我们描述的客观事物通常以数值数据来表示。
例如,从客观事物抽象而来的数值,通常用整型、实型、布尔型等基本数据类型数值来表示。
……

第1章 数据结构和算法
1.1 数据和数据类型
1.1.1 数据和数据元素
1.1.2 数据类型
1.1.3 抽象数据类型
1.1.4 抽象数据类型程序应用实例
1.1.5 数据对象
1.2 数据结构
1.2.1 数据的逻辑结构
1.2.2 数据元素的存储结构
1.2.3 常用的数据运算
1.3 算法描述工具——C语言
1.3.1 指针类型与指针变量
1.3.2 结构类型与结构变量
1.3.3 函数与参数
1.3.4 递归定义和递归函数
1.3.5 动态存储分配
1.3.6 文件操作
1.3.7 程序测试与测试集
1.3.8 测试数据的设计
1.3.9 程序调试问题
1.4 算法和算法评价
1.4.1 算法的概念
1.4.2 算法的性质
1.4.3 算法的评价标准
1.5 算法性能分析
1.5.1 算法的时间性能分析
1.5.2 算法的空间性能分析
小结
习题
第2章 顺序表及其应用
2.1 顺序表的基本概念
2.1.1 顺序表的定义
2.1.2 顺序表的数据结构分析
2.1.3 顺序表的数据类型描述
2.2 顺序表基本算法
2.3 顺序表基本算法性能分析
2.3.1 时间性能分析
2.3.2 空间性能分析
2.4 顺序表的应用l——查找问题
2.4.1 查找的概念
2.4.2 简单顺序查找算法
2.4.3 有序表的二分查找算法
2.4.4 分块查找算法
2.4.5 3种查找算法的性能比较
2.5 顺序表的应用2——排序问题
2.5.1 排序的概念
2.5.2 顺序表的数据类型
2.5.3 插入排序——直接插入排序算法
2.5.4 插入排序——希尔排序算法
2.5.5 交换排序——冒泡排序算法
2.5.6 交换排序——快速排序算法
2.5.7 选择排序——直接选择排序算法
2.5.8 归并排序算法
2.5.9 排序算法的性能分析与比较
2.6 顺序表的应用3——字符处理问题
2.6.1 串和顺序串的定义及相关概念
2.6.2 顺序串的数据结构分析
2.6.3 顺序串的基本运算
2.6.4 顺序串的数据类型定义
2.6.5 顺序串的基本运算算法
2.6.6 串的模式匹配算法
小结
习题
第3章 链表及其应用
3.1 链表的基本概念
3.1.1 链表的定义
3.1.2 链表的逻辑结构
3.1.3 链表的存储结构
3.1.4 静态链表和动态链表
3.1.5 链表基本运算
3.2 单链表的数据结构
……
第4章 堆栈及其应用
第5章 队列及其应用
第6章 特殊矩阵、广义表及其应用
第7章 二叉树及其应用
第8章 树和森林及其应用
第9章 散列结构及其应用
第10章 图及其应用
第11章 算法性能分析和算法设计方法简介
附录A 本书算法原程序
参考文献