页数:15页文件大小:102.0 KB来源: 数据结构ppt课件
本课件为数据结构课程总复习,按线性表、栈与队列、数组与广义表、树与二叉树、图、查找、排序等模块梳理知识体系,归纳各类结构的逻辑特性、存储方式与典型算法,并提示常见考点与解题思路,便于考前集中回顾。
数据结构总复习
第一章绪言 基本概念和术语 数据结构,数据,数据元素,数据项 逻辑结构与存储结构 算法分析 算法定义 算法特性:有穷性,确定性,可行性,输入,输出 算法评价:正确性、可读性、鲁棒性、时间复杂度与空间复杂度
第二章线性表 逻辑结构有限、序列、同构 存储结构 顺序存储结构 链式存储结构–单链表–双向链表–循环链表–双向循环链表 基本操作 插入 删除 查找. 应用------一元多项式相加xSbaP
第三章栈和队列---操作受限的线性表 栈 特点:FILO(LIFO) 存储结构:顺序栈与链栈 基本操作:入栈与出栈 应用:–递归调用(Tower of Hanoi)–回文游戏–多进制输出–表达式求值–地图四染色–已知入栈顺序,判断可能得出栈序列
队列 特点:FIFO(LILO) 存储结构:–
第四章数组 线性结构 存储结构 顺序存储结构:次序约定 压缩存储:压缩存储后元素下标计算–对称矩阵–对角矩阵–三角矩阵–稀疏矩阵. 算法:求转置矩阵.三元组顺序表、伪地址表示法带行指针向量的单链表十字链表按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
应用 Huffman树–定义–构造方法–有n个叶子结点的Huffman树共有2n-1个结点–应用»Huffman编码»最佳判定树
第六章图 定义:图、有向图、度、连通、完备图等 存储结构 邻接矩阵 邻接表与逆邻接表 遍历:深度优先与广度优先(在邻接表基础上)构成特点(与顶点度关系) 应用 生成树(Prim算法和Kruskal算法) 拓扑排序 最小生成树(Dijkstra算法)
第七章查找 静态查找表 顺序查找 折半查找 分块查找存储结构、表顺序ASL查找某元素的比较次数
第七章查找 哈希表 定义、哈希查找基本思想 Hash函数构造方法. 处理冲突方法. 哈希查找过程与ASL直接定址法数字分析法平方取中法折叠法除留余数法线性探测再散列二次探测再散列伪随机探测再散列开放定址法链地址法再哈希法
第八章排序 插入排序 直接插入排序 折半插入排序 交换排序 冒泡排序 选择排序 简单选择排序 堆排序 归并排序 2-路归并排序
掌握: 排序方法思想 每趟排序结果 排序方法稳定性 排序方法评价
祝大家都取得好成绩!
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}