算法和数据结构 相辅相成、缺一不可的两个方面。 数据结构是算法处理的对象、是设计算法的基础。 个具体问题的数据,有多种数据结构表示 个计算过程的实现,有多种可用的算法。 重点掌握基本知识,理解它们在问题求解中的作用 概念:数据的逻辑结构、存储结构和操作, 空间代价和时间代价等
相辅相成、缺一不可的两个方面。 数据结构是算法处理的对象、是设计算法的基础。 一个具体问题的数据，有多种数据结构表示 一个计算过程的实现，有多种可用的算法。 重点掌握基本知识，理解它们在问题求解中的作用； 概念：数据的逻辑结构、存储结构和操作， 空间代价和时间代价等。 算法和数据结构
数据结构的主要内容 问题 数学模型 实现 机外表示建模逻辑结构求精存储结构 处理要求 基本运算 实现 不同结构的比较及算法分析
数据结构的主要内容 问题 机外表示 处理要求 逻辑结构 基本运算 数学模型 存储结构 实现 建模 求精 不同结构的比较及算法分析 实现
基本算法 1.枚举法 2.迭代法 3.递归法 4递推法 5分治法 6回溯法
基本算法 ◼ 1.枚举法 ◼ 2.迭代法 ◼ 3.递归法 ◼ 4.递推法 ◼ 5.分治法 ◼ 6.回溯法
线性表 A.线性结构栈 数据的逻辑结构 数组 数据结构的三个方面 B.非线性结约/树形结构 图形结构 2、数据的存储结构A顺序存储 (亦称物理结构)(B链式存储 3、数据的运算:检索、排序、插入、删除、修改等
1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数 据 结 构 的 三 个 方 面 (亦称物理结构) 数组
线性表 线性表:它是n个数据元素的有限序列 存储方式:顺序存储和链式存储
线性表：它是n个数据元素的有限序列。 存储方式：顺序存储和链式存储。 线性表
栈和队列 操作受限的线性表:栈和队列。 栈:插入和删除都是在表的同一端进行的 顺序存储结构,注意栈满、栈空的条件 链式存储结构,注意链的方向。 应用:递归问题、回溯算法、程序调用、表达式计算 队列:插入删除运算在表的不同端进行 顺序存储结构,用环形队列,可解决假溢岀问题,注意队 列满和队列空的条件及描述。 应用:排队、缓冲区
操作受限的线性表：栈和队列。 栈：插入和删除都是在表的同一端进行的 顺序存储结构，注意栈满、栈空的条件 链式存储结构，注意链的方向。 应用：递归问题、回溯算法、程序调用、表达式计算 队列：插入删除运算在表的不同端进行 顺序存储结构，用环形队列，可解决假溢出问题，注意队 列满和队列空的条件及描述。 应用：排队、缓冲区 栈和队列
树、二叉树 ■树、树林、二叉树的基本概念 和转换; 二叉树性质 ■二叉链表存储结构 二叉树的遍历 ■哈夫曼树的构造方法及应用
树、二叉树 ◼ 树、树林、二叉树的基本概念 和转换； ◼ 二叉树性质 ◼ 二叉链表存储结构 ◼ 二叉树的遍历 ◼ 哈夫曼树的构造方法及应用
图的基本概念 图的存储结构:关联矩阵、求值矩阵和邻接表 图的遍历 应用:最小生成树、最短路径、拓扑排序、关键路 径等问题 重点掌握图的存储表示、遍历和各种应用算法的基 本思想
图 图的基本概念 图的存储结构：关联矩阵、求值矩阵和邻接表 图的遍历 应用：最小生成树、最短路径、拓扑排序、关键路 径等问题 重点掌握图的存储表示、遍历和各种应用算法的基 本思想
查找 本查找(查挑方法) A.顺序检索: 简单,常用于未排序元素的检索,效率不高;o(n) B.对分法检索: 仅用于排序元素,检索效率较高当插入、删除运算时 会引起大量数据的移动。O(og2n) (2)哈希表技术(构造、查找方法 检索操作达到近乎随机存取的速度。但散列表示经常 出现碰撞与堆积现象,增加了检索长度。 (平均检索长度与n无关,与装填因子有关) (3)二叉排序树(构造、查找方法) 元素插入次序不同,会构成不同的二叉排序树。最佳 二叉排序树的平均检索长度为oog2n)
（1）基本查找（查找方法） A. 顺序检索： 简单，常用于未排序元素的检索，效率不高； O(n) B. 对分法检索： 仅用于排序元素，检索效率较高当插入、删除运算时 会引起大量数据的移动。 O(log2n) （2）哈希表技术（构造、查找方法） 检索操作达到近乎随机存取的速度。但散列表示经常 出现碰撞与堆积现象，增加了检索长度。 （平均检索长度与n无关，与装填因子有关） （3）二叉排序树（构造、查找方法） 元素插入次序不同，会构成不同的二叉排序树。最佳 二叉排序树的平均检索长度为O(log2 n) 。 查找
排序 辉排序的定义和各种排序方法的特点。 了解各方法的排序过程及其依据的原则。 基本排序方法的选择 各种排序方法各有优缺点,故在不同情况下可作不同 的选择。通常需考虑的因素有:待排序的记录个数 记录本身的大小;记录的键值分布情况等 若待排序的记录 n较小时,可采用简单排序方法。 n较大时,采用快速排序或堆排序。 记录已基本有序,可采用起泡排序、希尔排序
排序 理解排序的定义和各种排序方法的特点。 了解各方法的排序过程及其依据的原则。 基本排序方法的选择 各种排序方法各有优缺点，故在不同情况下可作不同 的选择。通常需考虑的因素有：待排序的记录个数； 记录本身的大小；记录的键值分布情况等。 若待排序的记录: n较小时，可采用简单排序方法。 n 较大时，采用快速排序或堆排序。 记录已基本有序，可采用起泡排序、希尔排序
