数据结构课件—总复习.ppt

* 第一章 绪言 基本概念和术语 数据结构，数据，数据元素，数据项 逻辑结构与存储结构 算法分析 算法定义 算法特性：有穷性，确定性，可行性，输入，输出 算法评价：正确性、可读性、鲁棒性、 时间复杂度与空间复杂度 第二章 线性表 逻辑结构 有限、序列、同构 存储结构 顺序存储结构 链式存储结构 单链表 双向链表 循环链表 双向循环链表 基本操作 插入 删除 查找. 应用------一元多项式相加 x S b a P 第三章 栈和队列---操作受限的线性表 栈 特点：FILO(LIFO) 存储结构：顺序栈与链栈 基本操作：入栈与出栈 应用： 递归调用（Tower of Hanoi) 回文游戏 多进制输出 表达式求值 地图四染色 已知入栈顺序，判断可能得出栈序列 队列 特点：FIFO（LILO） 存储结构： 顺序 链式 循环队列. 基本操作 入队 出队 解决方案： 少用一个元素空间： 队空：Q.front==Q.rear 队满：(Q.rear+1)%MAXQSIZE==Q.front Q.front J4 J5 J6 4 5 0 1 2 3 Q.rear 队满 J8 J7 第四章 数组 线性结构 存储结构 顺序存储结构：次序约定 压缩存储： 压缩存储后元素下标计算 对称矩阵 对角矩阵 三角矩阵 稀疏矩阵. 算法：求转置矩阵. 三元组顺序表、伪地址表示法 带行指针向量的单链表 十字链表 按M列序转置 快速转置 第五章 树 逻辑结构：按分支关系定义的层次结构 定义： 深度、度、叶子等 满二叉树、完全二叉树 二叉树性质：5个. 存储结构 树 双亲表示法 孩子表示法 孩子兄弟表示法 性质1： 性质2：深度为k的二叉树至多有 个结点(k?1) 性质3：对任何一棵二叉树T，如果其终端结点 数为n0，度为2的结点数为n2，则n0=n2+1 性质4： 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1?i?n)，有： (1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是?i/2? (2)如果2i>n，则结点i无左孩子；如果2i?n，则其左孩子是2i (3如果2i+1>n，则结点i无右孩子；如果2i+1?n，则其右孩子是2i+1 二叉树 顺序存储结构 二叉链表. 三叉链表 树、森林与二叉树转换. 遍历 按层次、先序、中序、后序 遍历算法应用 由先序序列建立二叉链表 统计叶子结点 求二叉树深度 已知先序和中序序列，构造二叉树 在n个结点的二叉链表中，有n+1个空指针域 树转换成的二叉树其右子树一定为空 应用 Huffman树 定义 构造方法 有n个叶子结点的Huffman树共有2n-1个结点 应用 Huffman编码 最佳判定树 第六章 图 定义：图、有向图、度、连通、完备图等 存储结构 邻接矩阵 邻接表与逆邻接表 遍历：深度优先与广度优先(在邻接表基础上) 构成 特点（与顶点度关系） 应用 生成树(Prim算法和Kruskal算法) 拓扑排序 最小生成树(Dijkstra算法) 第七章 查找 静态查找表 顺序查找 折半查找 分块查找 存储结构、 表顺序 ASL 查找某元素的比较次数 第七章 查找 哈希表 定义、哈希查找基本思想 Hash函数构造方法. 处理冲突方法. 哈希查找过程与ASL 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 线性探测再散列 二次探测再散列 伪随机探测再散列 开放定址法 链地址法 再哈希法 *