数据结构与算法设计
2012-7
机械工业出版社
王晓东
242
《数据结构与算法设计》以基本数据结构为知识单元，系统地介绍数据结构知识与应用、计算机算法的设计与分析方法。全书共分13章，第1章介绍数据结构、抽象数据类型和算法的基本概念；第2～4章以抽象数据类型为主线索，围绕常用的基本数据结构，分别介绍基于序列的常用数据结构表、栈、队列；第5章介绍递归以及递归在数据结构和算法设计中的应用；第6章介绍实际应用中常用的排序与选择算法；第7～12章讨论反映层次关系的数据结构树、表示集合的抽象数据类型、符号表以及散列表等实践中常用实现符号表的方法、字典及其实现方法、优先队列及其实现方法、并查集及其实现方法；第13章介绍非线性结构图及图的算法。
《数据结构与算法设计》内容丰富，观点新颖，理论联系实际，不仅可用做高等院校计算机科学与工程专业学生学习数据结构与算法的教材，而且也适合广大工程技术人员参考。本书由王晓东著。
出版者的话
前言
教学方案设计
第1章 引论
1.1 算法及其复杂性的概念
1.1.1 算法与程序
1.1.2 算法复杂性的概念
1.1.3 算法复杂性的渐近性态
1.2 算法的表达与数据表示
1.2.1 问题求解
1.2.2 表达算法的抽象机制
1.3 抽象数据类型
1.3.1 抽象数据类型的基本概念
1.3.2 使用抽象数据类型的好处
1.4 数据结构和抽象数据类型
1.5 用C语言描述数据结构与算法
1.5.1 变量和指针
1.5.2 函数与参数传递
1.5.3 结构
1.5.4 动态存储分配
本章小结
习题
算法实验
算法实验题1.1 哥德巴赫猜想问题
算法实验题1.2 连续整数和问题
第2章 表
2.1 表的基本概念
2.2 用数组实现表
2.3 用指针实现表
2.4 用间接寻址方法实现表
2.5 用游标实现表
2.6 循环链表
2.7 双链表
2.8 表的搜索游标
2.8.1 用数组实现表的搜索游标
2.8.2 单循环链表的搜索游标
2.9 应用
本章小结
习题
算法实验
算法实验题2.1 向量分类问题
算法实验题2.2 条形图轮廓问题
第3章 栈
3.1 栈的基本概念
3.2 用数组实现栈
3.3 用指针实现栈
3.4 应用
本章小结
习题
算法实验
算法实验题3.1 车皮编序问题
算法实验题3.2 单柱Hanoi塔问题
算法实验题3.3 多栈模拟问题
算法实验题3.4 亲兄弟问题
第4章 队列
4.1 队列的基本概念
4.2 用指针实现队列
4.3 用循环数组实现队列
4.4 应用
本章小结
习题
算法实验
算法实验题4.1 组队列问题
算法实验题4.2 双栈队列问题
算法实验题4.3 猴子分桃问题
算法实验题4.4 逆序表问题
……
第5章 递归
第6章 排序与选择
第7章 树
第8章 集合
第9章 符号表
第10章 字典
第11章 优先队列
第12章 并查集
第13章 图
参考文献
版权页： 插图： 用指针实现上述扩充后的抽象数据类型队列。 4.2扩充抽象数据类型队列的定义，增加如下队列运算： （1）QueueSplit（S1，S2）：将队列S1分为大小相同的2个队列S1和S2。队列S2中含原队列S1中第1，3，5，…个元素，其余元素留在队列S1中。 （2）QueueCombine（S1，s2）：将队列S2中元素交错地合并于队列S1中，且保持原队列中元素的相对次序。S2成为空队列。 用指针实现上述扩充后的抽象数据类型队列。 4.3扩充抽象数据类型队列的定义，增加如下队列运算： OnQueue（x，Q）：若x是队列中的一个元素，则函数返回1，否则返回0。 用指针实现上述扩充后的抽象数据类型队列。 4.4如何实现以任意长的字符串为元素的队列？将一个字符串人队的运算耗时如何？ 4.5 实现队列的另一种链表结构使用一个指向队首结点的哨兵结点来简化出队运算。试用这种表示法实现队列的各种基本运算，并分析这种表示法的优缺点。 4.6写出用循环数组表示的队列长度的计算公式。 4.7用循环数组实现的队列重做习题4.1。 4.8用循环数组实现的队列重做习题4.2。 4.9用循环数组实现的队列重做习题4.3。 4.10如果用一个布尔量来表示循环数组中的队列是否为空队列，那么应当如何定义这种队列结构的类型?在这种表示法下实现队列的基本运算。 4.11 用循环数组表示队列的另一种方法是用一个游标指示队首元素所在的单元，并用一个整数表示队列长度。 （1）如果用这种方法来实现队列，是否有必要限制队列的长度? （2）在这种表示法下，实现队列的6个基本运算。 （3）与本章介绍的用循环数组表示的队列进行比较。 4.12 区分用循环数组实现的满队列和空队列的一个方法是在Queue结构中增加一个变量LastOp来记录最近一次执行的队列运算。如果LastOp记录的最近一次执行的队列运算是EnterQueue，则可断定当前队列一定非空；如果LastOp记录的最近一次执行的队列运算是DeleteQueue，则可断定当前队列一定不满。因此，当front=rear时，可借助LastOp来区分满队列和空队列。 试用上述思想修改用循环数组实现的队列。 4.13 双向队列是一种特殊的表，对这种表进行插人或删除操作都只能在表的任意一端进行。试用数组、指针和游标这3种不同结构实现双向队列。
《华章教育•高等院校精品课程系列教材•国家级:数据结构与算法设计》内容丰富，观点新颖，理论联系实际，不仅可用做高等院校计算机科学与工程专业学生学习数据结构与算法的教材，而且也适合广大工程技术人员参考。
