数据结构与程序设计方案.pdf

数据结构与程序设计方案.pdf 本资源是一个详细的数据结构与程序设计方案，涵盖了数据结构和算法、程序设计的基本概念和实现方法。该方案的目的是为了帮助学生和开发者更好地理解和应用数据结构和算法，提高编程能力和解决实际问题的能力。 一、数据结构概论 * 算法的基本概念、表达算法的抽象机制、算法的计算复杂性概念和分析方法 * 数据类型、数据结构和抽象数据类型的基本概念，及其区别和内在联系 *采用 C/C++ 与自然语言相结合的方式描述算法的方法 二、线性表 * 抽象数据类型表的基本概念及其逻辑特征 * 实现抽象数据类型的一般步骤 * 按照抽象数据类型设计和实现的一般性原则，常用的实现表的方法，如用数组实现表、用指针实现表、用间接寻址技术实现表、用游标实现表、单循环链表和双链表以及表的搜索游标的实现方法和步骤 三、栈 * 抽象数据类型栈的基本概念及其逻辑特征 * 按照抽象数据类型设计和实现的一般性原则，常用的用数组实现栈的方法和用指针实现栈的方法 * 用栈的应用方法，如集合的等价类划分等问题 四、队列 * 抽象数据类型队列的基本概念及其逻辑特征 * 按照抽象数据类型设计和实现的一般性原则，常用的用指针实现队列的方法和用循环数组实现队列的方法 * 用队列的应用方法，如电路布线等问题 五、集合 * 集合和以集合为基础的抽象数据类型的基本概念及其逻辑特征 * 如何用位向量和链表两种方式实现集合 六、排序与选择 * 排序问题的提法及其实质 * 常用的简单排序算法，如冒泡排序算法、插入排序算法和选择排序算法的设计思想与分析方法 * 快速排序算法的基本设计思想及其多方面的改进 * 合并排序算法的基本设计思想与分析方法 * 计数排序算法和桶排序算法等典型的线性时间排序算法的设计思想与分析方法 * 线性时间排序算法与基于比较的排序算法的主要差别和适用范围 * 与排序问题类似的选择问题及相应的算法 七、树 * 常用的非线性层次结构树以及作为抽象数据类型的树的一般操作和一些常用的表示树的数据结构 * 树的定义，树的前序遍历、中序遍历和后序遍历方法 * 常用的树的父结点数组表示法、树的儿子链表表示法和树的左儿子右兄弟表示法 * 二叉树和 ADT二叉树的概念 * 二叉树的顺序存储结构、二叉树的结点度表示法和用指针实现二叉树的方法 * 线索二叉树结构 * 树结构在实际问题中的应用方法，如信号传输网络中最优信号增强装置布局等问题 八、二叉搜索树 * 字典的概念，用数组和二叉搜索树实现字典的方法 * AVL 树的概念及相关运算 九、堆与优先队列 * 以集合为基础的抽象数据类型优先队列，以及优先级树、堆、左偏树和可并优先队列等概念 * 堆排序算法 十、散列 * 符号表的概念以及用数组、开散列、闭散列三种实现符号表的方法 * 常用的散列函数构造方法，如：除余法、数乘法、平方取中法等 * 主要的几种解决冲突的方法，如：线性探测法、二次探测法等 十一、并查集 * 以不相交的集合为基础的抽象数据类型并查集概念 * 并查集的实现方法及其合并策略 * 路径压缩技术及其实现方法 十二、图 * 常用的表示复杂非线性关系的数据结构图，以及作为抽象数据类型的图的一般操作和表示图的数据结构 * 图的邻接矩阵表示及其实现方法、图的邻接表表示及其实现方法以及图的紧缩邻接表表示方法 * 遍历一个图的 2 个重要方法，即图的深度优先搜索和广度优先搜索算法 * 单源最短路径问题的 Dijkstra 算法和 Bellman-Ford 算法，以及所有顶点对之间最短路径问题的 Floyd 算法 * 构造最小支撑树的 Prim 算法和 Kruskal 算法 * 无圈有向图 DAG 的拓扑排序及其最短路径和最长路径的求法 * 二分图的概念及其相关的图匹配问题，最大匹配问题的增广路径算法 十三、用 C++ 语言实现算法与数据结构 * C++ 语言基本成分、数据描述与基本操作 * C++ 语言流程设计和模块化设计 * 算法的基本控制结构（顺序、选择、循环结构设计） * 函数的定义与使用 * 数组、指针与字符串的综合使用 * 结构体的定义和使用 * 面向对象程序设计中的类与对象、继承与派生、多态性等基本概念和基本方法 * 熟练掌握面向对象程序设计方法，利用线性表、栈、队列、集合、排序算法、树及二叉树、二叉搜索树、优先队列、散列、并查集、图解决实际问题。