《数据结构与数据库》复习.pptVIP

* 《数据结构》复习 （仅供复习参考，考试范围不受此课件的限制） · 数据结构 70分 参考题型： 填空,选择,判断： 解答题： 算法题： · 对算法的要求：根据教学知识点的难易和重要性，将相关的算法理解和应用分三个层次进行要求： 层次1) 能阅读和理解算法，能结合具体数据给出算法执行结果； 层次2) 能写出算法的伪代码； 层次3) 能灵活运用算法，对实际问题进行算法设计。 第一章 序论 数据结构的知识点： 数据的逻辑结构 数据的存储结构 对数据的运算（运算的定义和运算的实现） 抽象数据类型的概念和表示方法 第一章 序论 算法的知识点： 算法的定义 算法的特性 算法的时间分析和空间分析方法 第二章 线性表 5个主要知识点： 线性表的定义 线性表的存储表示----顺序表，链表 线性表的运算在不同存储结构上的实现 有序表的操作 线性表的应用 第二章 线性表 线性表顺序存储结构的特点： 逻辑上相邻的元素在物理上也相邻； 不需要为表示元素之间的逻辑相邻关系开辟附加空间； 可以随机访问数据元素； 插入和删除元素时需要大量移动元素。 第二章 线性表 线性表链式存储结构的特点： 逻辑上相邻的元素在物理上不一定相邻； 需要为表示元素之间的逻辑相邻关系开辟附加空间：指针域； 无法随机访问数据元素； 插入和删除元素时不需要大量移动元素，只要修改相关结点的指针值即可。 第二章 线性表 几种常用的线性链表: 单链表 循环单链表(既可以用头指针引导,又可以用尾指针引导) 双向链表 双向循环链表 第二章 线性表 带头结点的链表和不带头结点的链表在操作上有差别. 判表空条件: 带头结点时 不带头结点时 单链表 head-next==NULL head==NULL 循环单链表 head==head-next head==NULL 第三章 栈和队列 栈和队列都是插入和删除操作受到限制的特殊线性表； 栈的特点： 后进先出（LIFO） 队列的特点：先进先出（FIFO） 第三章 栈和队列 栈的操作： 顺序栈：顺序表操作的特例 链栈：单链表操作的特例 第三章 栈和队列 队列的操作： 链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。 循环链队列：可以只用一个尾指针 用定长数组作为队列的存储结构时，一般采用循环队列的形式----循环队列。 第三章 栈和队列 队列的操作： 链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。 循环链队列：可以只用一个尾指针 用定长数组作为队列的存储结构时，一般采用循环队列的形式 第三章 栈和队列 循环队列： 数组：Q[1..maxsize-1] front指向对头元素 rear指向队尾元素的下一个 队列的最大容量：maxsize-1 0 6 5 4 3 2 1 7 front rear a5 a1 a2 a3 a4 第三章 栈和队列 循环队列的计算公式Q[0..maxsize-1]： 入队： rear = ( rear+1 ) mod maxsize 出队： front = ( front +1 ) mod maxsize 队空条件： front == rear 队满条件： front == (rear+1) mod maxsize 队列长度： (rear – front + maxsize) mod maxsize 第三章 栈和队列 循环队列的计算公式Q[1..maxsize]： 入队： rear = rear mod maxsize+1 出队： front = front mod maxsize +1 队空条件： front == rear 队满条件： front == rear mod maxsize+1 队列长度： (rear – front + maxsize) mod maxsize 第4章 数组 数组知识点： 多维数组行优先和列优先的存储方式； 数组元素地址的计算方法； 特殊矩阵的压缩存储方法以及下标变换算公式的推导； 稀疏矩阵的压缩存储技术----三元组表、十字链表。 第6章 树和二叉树 知识点(1)： 树和二叉树的定义 二叉树的（5个）性质 完全二叉树的特点 二叉树的存储结构，主要掌握二叉链表 二叉树的遍历算法以及二叉树常用运算 第6章 树和二叉树 知识点（2）： 表达式的二叉树表示 树的存储结构 树、森林与二叉树的相互转换 树和森林的遍历 哈夫曼树的定义和构造，哈夫曼编码方法 第7章 图 知识点(1)： 图的概念： 有向图，无向图 路径，回路（环），简单路径，简单环 无向连通图、连通分量 有向强连通图、强连通分量 完全图 第7章 图 知识点（2）： 生成