数据结构与数据库》复习.ppt

数据结构数据结构复习复习 （仅供复习参考，考试范围不受此课件的限制（仅供复习参考，考试范围不受此课件的限制 ） 数据结构数据结构 7070分分 参考题型：参考题型： n n 填空填空, ,选择选择, ,判断：判断： n n 解答题：解答题： n n 算法题：算法题： 对算法的要求：对算法的要求：根据教学知识点的难易和根据教学知识点的难易和 重要性，将相关的算法理解和应用分三个重要性，将相关的算法理解和应用分三个 层次进行要求：层次进行要求： 层次层次1)1) 能阅读和理解算法，能结合具体能阅读和理解算法，能结合具体 数据给出算法执行结果；数据给出算法执行结果； 层次层次2)2) 能写出算法的伪代码；能写出算法的伪代码； 层次层次3)3) 能灵活运用算法，对实际问题进能灵活运用算法，对实际问题进 行算法设计。行算法设计。 第一章第一章 序论序论 数据结构的知识点：数据结构的知识点： 1.1.数据的逻辑结构数据的逻辑结构 2.2.数据的存储结构数据的存储结构 3.3.对数据的运算（运算的定义和运算的实现）对数据的运算（运算的定义和运算的实现） 4.4.抽象数据类型的概念和表示方法抽象数据类型的概念和表示方法 第一章第一章 序论序论 算法的知识点：算法的知识点： n n 算法的定义算法的定义 n n 算法的特性算法的特性 n n 算法的时间分析和空间分析方法算法的时间分析和空间分析方法 第二章第二章 线性表线性表 5 5个主要知识点：个主要知识点： 1.1.线性表的定义线性表的定义 2.2.线性表的存储表示线性表的存储表示-顺序表，链表顺序表，链表 3.3.线性表的运算在不同存储结构上的实现线性表的运算在不同存储结构上的实现 4.4.有序表的操作有序表的操作 5.5.线性表的应用线性表的应用 第二章第二章 线性表线性表 线性表顺序存储结构的特点：线性表顺序存储结构的特点： 1.1.逻辑上相邻的元素在物理上也相邻；逻辑上相邻的元素在物理上也相邻； 2.2.不需要为表示元素之间的逻辑相邻关系开辟附不需要为表示元素之间的逻辑相邻关系开辟附 加空间；加空间； 3.3.可以随机访问数据元素；可以随机访问数据元素； 4.4.插入和删除元素时需要大量移动元素。插入和删除元素时需要大量移动元素。 第二章第二章 线性表线性表 线性表链式存储结构的特点：线性表链式存储结构的特点： 1.1.逻辑上相邻的元素在物理上不一定相邻；逻辑上相邻的元素在物理上不一定相邻； 2.2.需要为表示元素之间的逻辑相邻关系开辟附需要为表示元素之间的逻辑相邻关系开辟附 加空间：指针域；加空间：指针域； 3.3.无法随机访问数据元素；无法随机访问数据元素； 4.4.插入和删除元素时不需要大量移动元素，插入和删除元素时不需要大量移动元素， 只要修改相关结点的指针值即可。只要修改相关结点的指针值即可。 第二章第二章 线性表线性表 几种常用的线性链表几种常用的线性链表: : 1.1.单链表单链表 2.2.循环单链表循环单链表( (既可以用头指针引导既可以用头指针引导, ,又可以用又可以用 尾指针引导尾指针引导) ) 3.3.双向链表双向链表 4.4.双向循环链表双向循环链表 第二章第二章 线性表线性表 带头结点的链表和不带头结点的链表带头结点的链表和不带头结点的链表 在操作上有差别在操作上有差别. . 判表空条件判表空条件: : 带头结点时带头结点时不带头结点时不带头结点时 单链表单链表 head-next=NULLhead-next=NULLhead=NULLhead=NULL 循环单链表循环单链表 head=head-nexthead=head-nexthead=NULLhead=NULL 第三章第三章 栈和队列栈和队列 n n 栈和队列都是插入和删除操作受到限制的栈和队列都是插入和删除操作受到限制的 特殊线性表；特殊线性表； n n 栈的特点：栈的特点：后进先出（后进先出（LIFOLIFO） n n 队列的特点：先进先出（队列的特点：先进先出（FIFOFIFO） 第三章第三章 栈和队列栈和队列 栈的操作：栈的操作： n n 顺序栈：顺序表操作的特例顺序栈：顺序表操作的特例 n n 链栈：单链表操作的特例链栈：单链表操作的特例 第三章第三章 栈和队列栈和队列 队列的操作：队列的操作： n n 链队列：带头结点、头指针和尾指针的单链队列：带头结点、头指针和尾指针的单 链表，入队端在表尾，出队端在表头。链表，入队端在表尾，出队端在表头。 n n 循环链队列：可以只用一个尾指针循环链队列：可以只用一个尾指针 n n 用定长数组作为队列的存储结构时，一般用定长数组作为队列的存储结构时，一般 采用循环队列的形式采用循环队列的形式-循环队列循环队列。 第三章第三章 栈和队列栈和队列 队列的操作：队列的操作： n n 链队列：带头结点、头指针和尾指针的单链队列：带头结点、头指针和尾指针的单 链表，入队端在表尾，出队端在表头。链表，入队端在表尾，出队端在表头。 n n 循环链队列：可以只用一个尾指针循环链队列：可以只用一个尾指针 n n 用定长数组作为队列的存储结构时，一般用定长数组作为队列的存储结构时，一般 采用采用循环队列循环队列的形式的形式 第三章第三章 栈和队列栈和队列 循环队列：循环队列： 数组：数组：Q1maxsize-1Q1maxsize-1 frontfront指向对头元素指向对头元素 rearrear指向队尾元素的下一个指向队尾元素的下一个 队列的最大容量：队列的最大容量：maxsize-1maxsize-1 0 6 5 4 3 21 7 front rear a5 a1a2 a3 a4 第三章第三章 栈和队列栈和队列 循环队列的计算公式循环队列的计算公式Q0maxsize-1Q0maxsize-1： 入队：入队： rear = ( rear+1 ) mod maxsizerear = ( rear+1 ) mod maxsize 出队：出队： front = ( front +1 ) mod maxsizefront = ( front +1 ) mod maxsize 队空条件：队空条件： front = rearfront = rear 队满条件：队满条件： front = (rear+1) mod maxsizefront = (rear+1) mod maxsize 队列长度：队列长度： (rear (rear front + maxsize) mod maxsize front + maxsize) mod maxsize 第三章第三章 栈和队列栈和队列 循环队列的计算公式循环队列的计算公式Q1maxsizeQ1maxsize： 入队：入队： rear = rear mod maxsize+1rear = rear mod maxsize+1 出队：出队： front = front mod maxsize +1front = front mod maxsize +1 队空条件：队空条件： front = rearfront = rear 队满条件：队满条件： front = rear mod maxsize+1front = rear mod maxsize+1 队列长度：队列长度： (rear (rear front + maxsize) mod maxsize front + maxsize) mod maxsize 第第4 4章章 数组数组 数组知识点：数组知识点： n n 多维数组多维数组行优先行优先和和列优先列优先的存储方式；的存储方式； n n 数组元素地址的计算方法；数组元素地址的计算方法； n n 特殊矩阵的压缩存储方法以及下标变换算特殊矩阵的压缩存储方法以及下标变换算 公式的推导；公式的推导； n n 稀疏矩阵的压缩存储技术稀疏矩阵的压缩存储技术-三元组表、十三元组表、十 字链表。字链表。 第第6 6章章 树和二叉树树和二叉树 知识点知识点(1)(1)： n n 树和二叉树的定义树和二叉树的定义 n n 二叉树的（二叉树的（5 5个）性质个）性质 n n 完全二叉树的特点完全二叉树的特点 n n 二叉树的存储结构，主要掌握二叉链表二叉树的存储结构，主要掌握二叉链表 n n 二叉树的遍历算法以及二叉树常用运算二叉树的遍历算法以及二叉树常用运算 第第6 6章章 树和二叉树树和二叉树 知识点（知识点（2 2）：）： n n 表达式的二叉树表示表达式的二叉树表示 n n 树的存储结构树的存储结构 n n 树、森林与二叉树的相互转换树、森林与二叉树的相互转换 n n 树和森林的遍历树和森林的遍历 n n 哈夫曼树的定义和构造，哈夫曼编码方法哈夫曼树的定义和构造，哈夫曼编码方法 第第7 7章章 图图 知识点知识点(1)(1)： 图的概念：图的概念： n n 有向图，无向图有向图，无向图 n n 路径，回路（环），简单路径，简单环路径，回路（环），简单路径，简单环 n n 无向连通图、连通分量无向连通图、连通分量 n n 有向强连通图、强连通分量有向强连通图、强连通分量 n n 完全图完全图 第第7 7章章 图图 知识点（知识点（2 2）：）： n n 生成树、生成森林生成树、生成森林 n n 熟练掌握图的存储结构邻接矩阵和邻接熟练掌握图的存储结构邻接矩阵和邻接 表，他们的特点和操作表，他们的特点和操作 n n 熟练掌握图的熟练掌握图的DFSDFS遍历和遍历和BFSBFS遍历的概念和遍历的概念和 实现算法实现算法 第第7 7章章 图图 知识点（知识点（3 3）：）： n n 最小生成树的概念和最小生成树的概念和primprim、KlusclaKluscla算法思想算法思想 n n 拓扑序列的概念和拓扑排序算法拓扑序列的概念和拓扑排序算法 n n 最短路径的概念和最短路径的概念和DijkstraDijkstra算法算法 n n 关键路径的概念和关键路径的算法思想关键路径的概念和关键路径的算法思想 第第8 8章章 查找查找 知识点知识点(1)(1)： n n 平均查找长度平均查找长度ASLASL的定义和计算方法的定义和计算方法 n n 顺序查找的特点、算法和顺序查找的特点、算法和ASLASL（等概情况下（等概情况下 查找成功的查找成功的ASLASL（n+1)/2n+1)/2） n n 折半查找的特点、算法和折半查找的特点、算法和ASLASL（折半查找判（折半查找判 定树的定义和使用）定树的定义和使用） 第第8 8章章 查找查找 知识点知识点(2)(2)： n n 索引顺序查找的特点、查找方法和索引顺序查找的特点、查找方法和ASLASL n n 二叉排序树的定义、查找、插入、删除二叉排序树的定义、查找、插入、删除 n n 哈希表的概念、哈希函数的构造、装填因子哈希表的概念、哈希函数的构造、装填因子 对查找效率的影响、解决冲突的方法（线性对查找效率的影响、解决冲突的方法（线性 探测、二次探测和拉链法）、冲突和堆积的探测、二次探测和拉链法）、冲突和堆积的 不同、哈希表的构造和不同、哈希表的构造和ASLASL计算计算 第第9 9章章 排序排序 知识点：知识点： n n 直接插入排序直接插入排序 n n 希尔排序希尔排序 n n 冒泡排序冒泡排序 n n 快速排序快速排序 n n 简单选择排序简单选择排序 n n 堆排序堆排序 n n 归并排序归并排序 排序算法思想排序算法思想（会写过程）（会写过程） 稳定性稳定性 时间复杂度时间复杂度 特点特点 最好、最坏情况分析最好、最坏情况分析 数据库系统数据库系统 n n 基本概念：基本概念：DBDB，DBSDBS，DBMSDBMS，概念模型，数，概念模型，数 据模型，实体，联系（据模型，实体，联系（1:11:1，1:n1:n，n:m)n:m)，数据，数据 独立性，独立性，ERER图，数据模型的三要素图，数据模型的三要素 n n 关键字：候选码，主码，外部码，主属性关键字：候选码，主码，外部码，主属性 n n 数据库系统模式结构（三级模式，两级映射）数据库系统模式结构（三级模式，两级映射） n n 用数据库系统来管理数据的特点用数据库系统来管理数据的特点 数据库系统数据库系统 n n 关系模型的数据结构关系模型的数据结构 n n 关系的定义、关系的性质关系的定义、关系的性质 n n 关系的完整性规则关系的完整性规则 n n 关系模式的概念关系模式的概念 n n 关系代数运算（关系代数运算（9 9种，其中原子运算有种，其中原子运算有5 5种）种） n n 灵活运用关系代数运算实现复杂的查询灵活运用关系代数运算实现复杂的查询 数据库系统数据库系统 n n 函数依赖的概念函数依赖的概念 n n 完全函数依赖、部分函数依赖、传递函数依赖完全函数依赖、部分函数依赖、传递函数依赖 n n 1NF1NF、2NF2NF、3N