读者对象:本书既便于教师课堂讲授, 又便于自学者阅读,可作为高等院校计算机相关专业本科生、专科生的教材, 也可供广大从事计算机应用的科技人员参考
《高等学校数据结构课程系列教材:数据结构教程(C#语言描述)》系统地介绍了常用的数据结构以及排序、查找的各种算法,阐述了各种数据结构的逻辑关系、存储表示及运算操作,并采用C#语言描述数据组织和算法实现。
《高等学校数据结构课程系列教材:数据结构教程(C#语言描述)》既注重原理,又注重实践,配有大量图表、实践教学项目和习题,内容丰富,概念讲解清楚,表达严谨,逻辑性强,语言精练,可读性好。
《高等学校数据结构课程系列教材:数据结构教程(C#语言描述)》既便于教师课堂讲授,又便于自学者阅读,可作为高等院校计算机相关专业本科生、专科生的教材,也可供广大从事计算机应用的科技人员参考。
计算机是数据处理的工具。数据结构课程作为计算机科学与技术专业的核心课程,主要讲授数据的各种组织方式以及建立在这些结构之上的各种运算算法的实现,它不仅为计算机语言程序设计提供了方法性的指导,还在一个更高的层次上总结了程序设计的常用方法和常用技巧。
要学好数据结构课程,首先要从宏观上理解本课程的目的和地位。该课程是在学完某种程序设计语言后开设的。仅掌握一门程序设计语言,不一定能编写出“好程序”,数据结构课程就是为写好程序服务的。程序是用于数据计算的,在编写程序之前要理解数据的结构,这里是指数据的逻辑结构。从数据元素之间的相邻关系归纳起来,数据的逻辑结构主要有线性结构、树形结构和图形结构。仅弄清数据逻辑结构是不够的,还要将这些数据存放到计算机内,这称为数据的存储结构。一种数据逻辑结构可能由多种存储结构实现。当设计好数据存储结构后,就可以对其进行操作了,这种操作的指令序列称为算法。不同的功能对应不同的算法,同一功能也可以有多种算法,从算法的时间和空间来分析,可以得到最佳算法。数据结构课程总结和归纳了在软件开发中常用的数据结构,从数据逻辑结构、存储结构和基本运算算法设计3个层面来讨论,可以提高学生基本的数据组织和处理能力,为后续课程,如操作系统、数据库原理和编译原理等的学习打下基础。
本书是作者根据近20年的教学经验,参考近年国内外出版的多种数据结构以及C#面向对象程序设计教材,考虑教与学的特点,合理地进行内容的取舍,精心组织编写而成的。目前,国内外数据结构教材大多数采用C/C++语言描述算法,考虑到C#语言与C/C++的一致性和良好的Windows界面设计优点,本书采用C#语言面向对象方法描述算法和实验程序设计。
全书由10章构成,各章内容如下:
第1章绪论,介绍数据结构的基本概念、采用C#语言描述算法的特点、算法分析方法和如何设计好算法等。
第2章线性表,介绍线性表的定义、线性表的两种主要的存储结构和各种基本运算算法设计,最后通过示例讨论线性表的应用。
第3章栈和队列,介绍栈的定义、栈的存储结构、栈的各种基本运算算法设计和栈的应用; 队列的定义、队列的存储结构和队列的各种基本运算算法设计和队列的应用。
第4章串,介绍串的定义、串的存储结构、串的各种基本运算算法设计和串的模式匹配算法。
第5章数组和广义表,介绍数组的定义、几种特殊矩阵的压缩存储方式、稀疏矩阵的压缩存储及相关算法设计; 递归的定义和递归算法设计方法; 广义表的定义、广义表的存储结构及相关算法设计方法。
第6章树和二叉树,介绍树的定义、树的逻辑表示方法、树的性质、树的遍历和树的存储结构二叉树; 介绍二叉树的定义、二叉树的性质、树/森林和二叉树的转换与还原、二叉树存储结构、二叉树基本运算算法设计、二叉树的递归和非递归遍历算法、二叉树的构造、线索二叉树和哈夫曼树等。
第7章图,介绍图的定义、图的存储结构、图的基本运算算法设计、图的两种遍历算法以及图的应用(包括图的最小生成树、最短路径、拓扑排序和关键路径等)。
第8章查找,介绍查找的定义、线性表上的各种查找方法、树表上的各种查找方法以及哈希表查找方法等。
第9章内排序,介绍排序的定义、插入排序方法、交换排序方法、选择排序方法、归并排序方法和基数排序方法,并对各种排序方法进行了比较。
第10章外排序,介绍外排序的定义、外排序的基本步骤,重点讨论了磁盘排序中的各种算法。
另外,附录A中给出各章练习题单项选择题部分的答案。
本书主要特点如下:
(1) 结构清晰,内容丰富,文字叙述简洁明了,可读性强。
(2) 图文并茂,全书用300多幅图来表述和讲解数据的组织结构和算法设计思想。
(3) 力求归纳各类算法设计的规律,如单链表算法中很多是基于建表算法的,二叉树算法中很多是基于遍历算法的,图算法中很多是基于深度优先遍历的。如果读者掌握了建表算法、二叉树的遍历算法和图遍历算法,那么设计相关算法就会驾轻就熟了。
(4) 深入讨论递归算法设计的方法。递归算法设计是数据结构课程中的难点之一。作者从递归模型入手,介绍了从求解问题中提取递归模型的通用方法,讲解了从递归模型到递归算法设计的基本规律。
(5) 书中含有大量的实践项目,全面覆盖并超越了教育部制定的《高等学校计算机科学与技术专业实践教学体系与规范》中数据结构课程的实践教学要求。作者已在Visual Studio.NET 2005/2008开发环境中全部调试并通过这些实践项目。
本书的编写工作得到湖北省教育厅和武汉大学教学研究项目《计算机科学与技术专业课程体系改革》的大力支持,特别是国家级名师何炎祥教授和主管教学工作的王丽娜副院长对本书的编写给予了建设性的指导,国家珠峰计划——武汉大学计算机弘毅班的两届学生和众多编者授课的本科生提出了许多富有启发的建议,清华大学出版社魏江江主任全力支持本书的编写工作,作者在此一并表示衷心感谢!
本书是课程组全体教师多年教学经验的总结和体现,尽管作者不遗余力,但由于水平所限,仍难免有错误和不足之处,敬请广大教师和同学们批评指正。欢迎读者通过邮箱跟作者联系,在此表示万分感谢!
编者2012年10月
李春葆,武汉大学计算机学院教授,主要研究方向为数据挖掘和算法设计,先后主持和参加多个大型研究项目。主要为本科生讲授数据结构(15年以上)和软件工程等课程,为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程,并出版十多部精品著作。
第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.3 算法分析
1.3.1 算法的特性和算法设计的目标
1.3.2 算法时间效率分析
1.3.3 算法存储空间分析
1.4 数据结构的目标
本章小结
练习题1
第2章 线性表
2.1 线性表的定义
2.1.1 什么是线性表
2.1.2 线性表的抽象数据类型描述
2.2 线性表的顺序存储结构
2.2.1 线性表的顺序存储结构顺序表
2.2.2 顺序表基本运算的实现
2.3 线性表的链式存储结构
2.3.1 线性表的链式存储结构链表
2.3.2 单链表
2.3.3 双链表
2.3.4 循环链表
2.4 线性表的应用
本章小结
练习题2
第3章 栈和队列
3.1 栈
3.1.1 栈的定义
3.1.2 栈的顺序存储结构及其基本运算的实现
3.1.3 栈的链式存储结构及其基本运算的实现
3.1.4 栈的应用
3.2 队列
3.2.1 队列的定义
3.2.2 队列的顺序存储结构及其基本运算的实现
3.2.3 队列的链式存储结构及其基本运算的实现
3.2.4 队列的应用
本章小结
练习题3
第4章 串
4.1 串的基本概念
4.1.1 什么是串
4.1.2 串的抽象数据类型
4.2 串的存储结构
4.2.1 串的顺序存储结构顺序串
4.2.2 串的链式存储结构链串
4.3 串的模式匹配
4.3.1 Brute-Force算法
4.3.2 KMP算法
本章小结
练习题4
第5章 数组和广义表
5.1 数组
5.1.1 数组的定义
5.1.2 数组的存储结构
5.1.3 特殊矩阵的压缩存储
……
第6章 树和二叉树
第7章 图
第8章 查找
第9章 内排序
第10章 外排序
附录A 部分练习题参考答案
参考文献