首页计算机计算机基础数据结构 09 数据结构复习.pptx

09 数据结构复习.pptx

页数:15页文件大小:102.0 KB来源: 数据结构ppt课件

本课件为数据结构课程总复习,按线性表、栈与队列、数组与广义表、树与二叉树、图、查找、排序等模块梳理知识体系,归纳各类结构的逻辑特性、存储方式与典型算法,并提示常见考点与解题思路,便于考前集中回顾。

数据结构总复习封面,标示本复习课件的主题与全课程整体回顾定位
绪言复习页,梳理数据结构基本概念、逻辑与存储结构及算法分析要点
线性表复习页,梳理逻辑结构、顺序与链式存储及插入删除查找基本操作
查看本课件的文字版(共 15 页,供检索与复制)

第1页:数据结构总复习封面

数据结构总复习

第2页:第一章绪言复习

第一章绪言 基本概念和术语 数据结构,数据,数据元素,数据项 逻辑结构与存储结构 算法分析 算法定义 算法特性:有穷性,确定性,可行性,输入,输出 算法评价:正确性、可读性、鲁棒性、时间复杂度与空间复杂度

第3页:第二章线性表复习

第二章线性表 逻辑结构有限、序列、同构 存储结构 顺序存储结构 链式存储结构–单链表–双向链表–循环链表–双向循环链表 基本操作 插入 删除 查找. 应用------一元多项式相加xSbaP

第4页:第三章栈复习

第三章栈和队列---操作受限的线性表 栈 特点:FILO(LIFO) 存储结构:顺序栈与链栈 基本操作:入栈与出栈 应用:–递归调用(Tower of Hanoi)–回文游戏–多进制输出–表达式求值–地图四染色–已知入栈顺序,判断可能得出栈序列

第5页:队列复习

队列 特点:FIFO(LILO) 存储结构:–

顺序
链式 循环队列.
入队
出队解决方案:少用一个元素空间: 队空:Q.front==Q.rear 队满:(Q.rear+1)%MAXQSIZE==Q.frontQ.frontJ4J5J6450123Q.rear队满J8J7

第6页:第四章数组复习

第四章数组 线性结构 存储结构 顺序存储结构:次序约定 压缩存储:压缩存储后元素下标计算–对称矩阵–对角矩阵–三角矩阵–稀疏矩阵. 算法:求转置矩阵.三元组顺序表、伪地址表示法带行指针向量的单链表十字链表按M列序转置快速转置

第7页:第五章树复习一

第五章树 逻辑结构:按分支关系定义的层次结构 定义: 深度、度、叶子等 满二叉树、完全二叉树 二叉树性质: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

第8页:第五章树复习二

二叉链表.
三叉链表 树、森林与二叉树转换.
遍历
按层次、先序、中序、
后序
遍历算法应用»由先序序列建立二叉链表»统计叶子结点»
求二叉树深度
已知先序和中序序列,构造二叉树在n个结点的二叉链表中,有n+1个空指针域树转换成的二叉树其右子树一定为空

第9页:哈夫曼树应用复习

应用 Huffman树–定义–构造方法–有n个叶子结点的Huffman树共有2n-1个结点–应用»Huffman编码»最佳判定树

第10页:第六章图复习

第六章图 定义:图、有向图、度、连通、完备图等 存储结构 邻接矩阵 邻接表与逆邻接表 遍历:深度优先与广度优先(在邻接表基础上)构成特点(与顶点度关系) 应用 生成树(Prim算法和Kruskal算法) 拓扑排序 最小生成树(Dijkstra算法)

第11页:第七章查找复习一

第七章查找 静态查找表 顺序查找 折半查找 分块查找存储结构、表顺序ASL查找某元素的比较次数

第12页:第七章查找复习二

第七章查找 哈希表 定义、哈希查找基本思想 Hash函数构造方法. 处理冲突方法. 哈希查找过程与ASL直接定址法数字分析法平方取中法折叠法除留余数法线性探测再散列二次探测再散列伪随机探测再散列开放定址法链地址法再哈希法

第13页:第八章排序复习

第八章排序 插入排序 直接插入排序 折半插入排序 交换排序 冒泡排序 选择排序 简单选择排序 堆排序 归并排序 2-路归并排序

第14页:排序复习要求

掌握: 排序方法思想 每趟排序结果 排序方法稳定性 排序方法评价

第15页:结束语

祝大家都取得好成绩!

顶部目录