本书通过具体的编程实例,详细介绍了数据结构及其算法。全书共分11章,内容包括数据结构和算法的简介,解决线性表、堆栈、队列、串、数组、二叉树及树、图的编程,执行排序和查找算法。全书采用C#语言作为算法描述语言。
本书内容丰富,层次清晰,讲解深入浅出,可作为计算机及相关专业本、专科数据结构课程的教材,也适合各类成人教育相关课程使用,还可以供从事计算机软件开发和应用的工程技术人员阅读、参考。
数据结构知识是计算机科学教育的一个基本组成部分,其他许多计算机科学领域都构建在这个基础之上。对于想从事实际的软件设计、实现、测试和维护工作的读者而言,掌握基本数据结构的知识是非常必要的。该领域的知识将对一个人的编程能力有着极深的影响,它告诉您如何在软件开发过程中建立一个合理高效的程序。然而由于数据结构是一门实践性较强而理论知识较为抽象的课程,目前很多学生在学完了这门课后,还是不知道如何运用所学的知识解决实际的问题,针对这种情况本书进行了精心的设计。本书主要特点如下:
(1) 基于典型任务
本书的每一章都通过典型任务引出问题,通过典型任务创设学习情境。所有典型任务都是经过精心筛选和设计的与生活紧密相连的、生动直观的、难易适中的实际问题,可以让学生先思考如何利用以往所学的知识去解决该问题,然后再由教师分析教材上如何运用数据结构的理论来解决同一问题,让学生深刻体会到所学数据结构在程序中的作用和使用方法,从而真正体会到“程序=数据结构+算法”的真正含义。
(2) 基于问题求解过程
本书除第1章外,所有其他章节都是按照问题提出→分析逻辑结构→分析存储结构→分析基于存储结构的算法→用C#实现数据结构和算法这样一个完整问题求解过程来组织内容的。也就是说对于每一个实际的问题,首先明确数据元素及数据元素之间的逻辑关系,即逻辑结构; 其次要理解这些数据元素在计算机中的存储结构以及基于这种存储结构的对数据元素的基本操作(即算法),最后用C#语言将数据结构和算法转换为能够直接运行的程序代码。
(3) C#语言描述
目前,C#语言是微软公司在新一代开发平台.NET上推出的完全面向对象的语言,凭着其简洁、高效、模板、标准化的特性,使得C#语言像程序设计语言中的一件艺术品,吸引着越来越多的开发人员。相比于很多数据结构的教材用C语言描述,本教材的算法将采用最新语言C#进行编写,将更有助于学生熟悉如何用面向对象的语言来描述数据结构的算法,从而和实际的开发工作能更加紧密地联系起来。
本书以雷军环为主编写,对全书的教学内容和学习情境进行了精心的设计。刘震、邓文达、谢英辉、谢海波、唐一韬、马佩勋、贺宗梅、吴名星分别对第1、2、3、4、5、6、7、8章内容进行了编写,第9、10、11章由雷军环编写。
本教材的编写得益于著名职业教育学家姜大源教授的开发基于工作过程系统化课程方法的启示,并有幸得到姜大源教授的指导,在此向他表示衷心的感谢。出版社的编辑为本书的修订和出版做了大量的工作,与他们的合作非常愉快。还有我的学生陈军和张自葵参与了本书的校稿和调试代码工作,在此一并表示感谢。
尽管编者在写作过程中非常认真和努力,但由于编者水平有限,书中难免存在错误和不足之处,恳请广大读者批评指正。
编者2008年12月
第1章数据结构和算法简介
1.1问题引入
1.1.1查找电话号码问题
1.1.2问题求解基本步骤
1.2认识数据结构
1.2.1数据的概念
1.2.2数据元素和数据项
1.2.3数据结构的概念
1.2.4数据结构的存储
1.3认识算法
1.3.1算法的定义及特征
1.3.2算法性能分析与度量
1.4寻求问题求解的实现方法
本章小结
综合练习
第2章解决线性表的编程问题
学习情境: 用线性表解决学生成绩表的编程
2.1认识线性表
2.1.1分析线性表的逻辑结构
2.1.2识别线性表的基本操作
2.2用顺序表解决线性表的编程问题
2.2.1用顺序表表示线性表
2.2.2对顺序表进行操作
2.2.3顺序表在学生成绩表中的应用
独立实践
2.3用单链表解决线性表的编程问题
2.3.1用单链表表示线性表
2.3.2对单链表进行操作
2.3.3单链表在学生成绩表中的应用
独立实践
2.4用双向链表解决线性表的编程问题
2.4.1用双向链表表示线性表
2.4.2对双向链表进行操作
2.4.3双向链表在学生成绩表中的应用
独立实践
2.5用循环链表解决线性表的编程问题
2.5.1用循环链表表示线性表
2.5.2对循环链表进行操作
2.5.3循环链表在学生成绩表中的应用
独立实践
2.6度量不同存储结构的算法效率
2.6.1分析顺序表的算法效率
2.6.2分析单链表的算法效率
本章小结
综合练习
第3章解决堆栈的编程问题
学习情境: 用堆栈解决火车车厢重排问题的编程
3.1认识堆栈
3.1.1分析堆栈的逻辑结构
3.1.2识别堆栈的基本操作
3.2用顺序栈解决堆栈的编程问题
3.2.1用顺序栈表示堆栈
3.2.2对顺序栈进行操作
3.2.3用顺序栈解决火车车厢重排问题的编程
3.3用链栈解决堆栈的编程问题
3.3.1用链栈表示堆栈
3.3.2对链栈进行操作
3.3.3用链栈解决火车车厢重排问题的编程
独立实践
本章小结
综合练习
第4章解决队列的编程问题
学习情境: 用队列解决银行排队叫号软件的编程
4.1认识队列
4.1.1分析队列的逻辑结构
4.1.2识别队列的基本操作
4.2用顺序队列解决队列的编程问题
4.2.1用顺序存储结构表示队列
4.2.2对顺序队列进行操作
4.2.3用循环顺序队列解决银行排队叫号软件的编程
4.3用链队列解决队列的编程问题
4.3.1用链队列表示队列
4.3.2对链队列进行操作
4.3.3用链队列解决银行排队叫号软件的编程
独立实践
本章小结
综合练习
第5章解决串的编程问题
学习情境: 用串解决“以一敌百”游戏的编程
5.1认识串
5.1.1分析串的逻辑结构
5.1.2识别串的基本操作
5.2用顺序存储解决串的编程问题
5.2.1用顺序存储结构表示串
5.2.2对顺序串进行操作
5.2.3用顺序串解决“以一敌百”游戏的编程
独立实践
本章小结
综合练习
第6章解决数组的编程问题
学习情境: 用数组解决数学魔术游戏编程
6.1认识数组
6.1.1描述数组的逻辑结构
6.1.2识别数组的基本操作
6.1.3用顺序存储结构存储数组
6.1.4编程实现数组的基本操作
6.1.5用数组解决数学魔术游戏的编程
独立实践
学习情境: 用特殊矩阵解决查询城市间的距离的编程
6.2认识特殊矩阵
6.2.1分析特殊矩阵的逻辑结构
6.2.2特殊矩阵的压缩存储
6.2.3用特殊矩阵解决查询城市间距离的编程
独立实践
学习情境: 用稀疏矩阵解决超市物品购买数据的编程
6.3认识稀疏矩阵
6.3.1描述稀疏矩阵的逻辑结构
6.3.2稀疏矩阵的压缩存储
6.3.3编程实现稀疏矩阵的基本运算
6.3.4用稀疏矩阵实现超市物品购买数据的编程
独立实践
本章小结
综合练习
第7章解决二叉树的编程问题
学习情境: 解决快速搜索磁盘文件中记录的问题
7.1认识二叉树
7.1.1分析二叉树的逻辑结构
7.1.2识别二叉树的基本操作
7.1.3识别二叉树的主要性质
7.2二叉树的存储实现
7.2.1用顺序存储结构表示二叉树
7.2.2用链式存储结构表示二叉树
7.3二叉树的遍历方法及递归实现
7.4用二叉搜索树解决快速搜索磁盘文件中记录的问题
独立实践
7.5最优二叉树——哈夫曼树
7.5.1哈夫曼树的基本概念
7.5.2哈夫曼树的构造算法
本章小结
综合练习
第8章解决树和森林的编程问题
学习情境: 用树来解决学院组织结构的编程问题
8.1认识树
8.1.1分析树的逻辑结构
8.1.2树的逻辑表示
8.1.3识别树的基本操作
8.2实现树的存储
8.2.1用多重链表表示法存储树
8.2.2用双亲表示法存储树
8.2.3用孩子链表表示法存储树
8.2.4用双亲孩子表示法存储树
8.2.5用孩子兄弟表示法存储树
8.2.6用多重链表表示法解决学院组织结构的编程
8.3树、森林与二叉树的转换
8.3.1树转换为二叉树
8.3.2森林转换为二叉树
8.3.3二叉树转换为树和森林
8.4解决树和森林的遍历问题
8.4.1树的遍历
8.4.2森林的遍历
8.5树的应用
8.5.1集合的表示
独立实践
本章小结
综合练习
第9章解决图的编程问题
学习情境: 用图解决高速公路交通网的编程
9.1认识图
9.1.1图的定义和术语
9.1.2识别图的基本操作
9.2用邻接矩阵解决图的编程问题
9.2.1用邻接矩阵表示图
9.2.2对邻接矩阵进行操作
9.2.3使用邻接矩阵解决高速公路交通网的存储问题
9.3用邻接表解决图的编程问题
9.3.1用邻接表表示图
9.3.2对邻接表进行操作
9.3.3使用邻接表解决高速公路交通网的存储问题
独立实践
9.4解决图的遍历问题
9.4.1深度优先搜索
9.4.2广度优先搜索
9.4.3使用图的遍历解决高速公路交通网城市的遍历
独立实践
9.5图的最短路径问题
9.5.1Dijkstra算法的引入
9.5.2分析高速公路交通网的最短路径
9.5.3编码实现Dijkstra算法
9.5.4用Dijkstra算法解决高速公路交通网中最短路径的编程
独立实践
本章小结
综合练习
第10章实现排序算法
学习情境: 实现第29届奥运会奥运奖牌的排名
10.1认识排序
10.1.1排序的概念
10.1.2排序的分类
10.2插入排序
10.2.1直接插入排序
10.2.2希尔排序
10.3选择排序
10.3.1直接选择排序
10.3.2堆排序
10.4交换排序
10.4.1冒泡排序
10.4.2快速排序
10.5归并排序
10.5.1归并排序
10.6分配排序
10.6.1基数排序
10.7编程实现第29届奥运会奥运奖牌的排名
独立实践
本章小结
综合练习
第11章执行查询算法
学习情境: 根据指定的条件查询第29届奥运会获奖情况
11.1熟悉查找的基本概念
11.2线性表查找技术
11.2.1顺序查找
11.2.2二分查找
11.2.3分块查找
11.3哈希表查询技术
11.3.1认识哈希表
11.3.2构造哈希函数
11.3.3解决哈希冲突
11.3.4实现哈希表的查找算法
11.3.5分析哈希表的性能
11.4编程实现第29届奥运会排行榜的查询功能
独立实践
本章小结
综合练习
参考文献