A数据结构-总结

数据结构与算法基础 课程回顾与总结 第一章绪论 A数据结构研究对象信息数据数据元素数据项数据结构数据对象数据类型 B数据结构逻辑结构存储结构 物理结构 数据结构分类 C数据结构发展概况 D抽象数据型 ADT 数据型 数据结构与抽象数据型抽象数据型的规格描述 语法 语义 抽象数据型的实现抽象数据型的优点多层次抽象技术 E算法什么叫算法 算法的特征 好 的算法的评价标准对算法的正确性的要求算法的描述类语言F算法分析算法的时间特性时间复杂度T n 空间复杂度S n Insert x p L Locate x L Retrieve p L Delete p L Previous p L Next p L MakeNull L First L MakeNull S Top S Pop S Push x S Empty S MakeNull Q Front Q EnQueue x Q DeQueue Q Empty Q Empty BT IsEmpty BT CeeateBT V LT RT Lchild BT Rchild BT Data BT NodeNewNode G v VoidDelNode G v VoidSetSucc G v1 v2 VoidDelSucc G v1 v2 ListofnodeSucc G v LisyofnodePred G v IntIsEdge G v1 v2 NodeFirstAdjVex G v NodeNextAdjVex G v w stringNULL booleanIsNull S VoidIn S a intLen S VoidConcat S1 S2 stringSubstr S m n booleanIndex S S1 Create 建立一个空数组 Retrieve array index 返回第index个元素 Store array index value 在数组array中 为第index个元素赋值value 第二章线性表 A线性表的概念什么叫线性表抽象数据型线性表 B线性表的实现静态数据结构动态数据结构顺序存储 数组实现 链式存储 指针 游标 静态链表 C线性链表表头结点单向链表双向链表单向循环量表双向循环链表 D限定性数据结构 栈 队列 E栈栈的概念ADT栈栈的存储结构栈的应用 栈与递归迷宫求解表达式转换与求值 F队列队列的概念ADT队列队列的存储结构循环队列 G线性表的应用 多项式的表示多项式相加运算 H串串的基本概念ADT串串的存储结构存储密度 I数组数组的概念ADT数组数组的存储结构数组的压缩存储 特殊矩阵 对角或带状矩阵 稀疏矩阵 J广义表基本概念广义表的存储结构 第三章树与二叉树 A树的基本术语树子树结点分支度路叶子非终结 端 结点终结 端 结点儿子父亲兄弟堂兄弟祖先子孙结点 层高度 深度 结点的顺序层序有序树无序树森林 B二叉树二叉树的定义 ADT二叉树 满二叉树 完全二叉树二叉树的遍历 先序遍历 中序遍历和后序遍历 层序遍历二叉树遍历的非递归算法 先序 中序和后序 二叉树的性质 1 5 二叉树的存储结构 顺序存储 链式存储 二叉链表 线索二叉树 基本概念 先序 中序与后序线索求线索二叉树的 先序 中序 后序 前驱与后继结点线索二叉树的遍历线索二叉树中插入 删除结点的讨论 D树ADT树树的存储结构 双亲表示法 孩子表示法 邻接表 树的左右链表示树与二叉树的转换 森林与二叉树的转换树的遍历 先序 中序和后序遍历树 E树的应用用树表示集合 判定树 哈夫曼树及其应用 最优编码 C二叉树的相似与等价 二叉树的复制算法 第四章图以及与图有关的算法 A图的基本概念图的定义ADT图有向图无向图弧边顶点邻接点相邻依附环路权子图带标号的图 网 路径简单路径连通图强连通图连通分量强连通分量完全图稀疏图稠密图度入度出度生成树 B图的表示 存储结构 邻接矩阵邻接表 C图的遍历 搜索 算法 先深搜索 DFS 先广搜索 BFS D图与树的关系生成树先深生成森林先广生成森林树边与回退边开放树最小生成树及其算法 MST性质 Prim Kruskal算法 E无向图的双连通性关结点双连通图双连通分量 F有向图的搜索生成树生成森林如何区别树边 向前边 回退边和横边 G强连通性 强连通分量 归约图 图的中心点的概念及求解方法 H拓扑分类有向无环图及其应用拓扑分类拓扑分类算法 I关键路径AOE网AOV网事件活动路径长度关键活动关键路径AOE网问题 1 完成整个工程至少需要多少时间 2 哪些活动是影响工程进度的关键活动 关键路径算法中的关键变量 事件Vj的最早可能发生时间VE j 活动ai的最早可能开始时间E k 事件Vk的最迟发生时间VL k 活动ai的最迟允许开始时间L i 时间余量L i E i J最短路径问题单源最短路径 Dijkstra算法任意顶点间的最短路径 Floyd算法 Warshall算法 B线性查找C折半查找 条件D分快查找EAVL树FB 树B 树G二叉查找树 什么叫二叉查找树 插入结点 删除结点 查找结点H散列法 哈稀函数冲突哈希表的长度哈希函数 直接定址法质数除余法平方取中法折叠法数字分析法随机法处理冲突 开放定址法 线性探测 二次探测 再散列法链地址法建立公共溢出区 第五章查找 A基本概念查找 检索 查找表关键字静态查找动态查找平均查找长度 装填因子 标志着哈希表的装满程度 越小 发生冲突的可能性越小 反之 发生冲突的可能性越大 J成功查找平均查找长度 ASLs查找到散列表中已存在结点的平均比较次数 K失败查找平均查找长度 ASLu查找失败 但找到插入位置的平均比较次数 理解概念掌握结构阅读算法 C简单的分类算法 气泡排序插入排序冒泡 选择 排序 O n2 DShell分类 缩小增量法E快速分类 快速分类的递归算法与非递归算法F归并分类G堆分类 堆的概念整理堆的算法H基数分类 多关键字 第六章内部排序 分类 A排序 分类 排序内部排序外部排序稳定与不稳定的排序方法 B影响分类性能的因素 比较关键字的次数 当关键字是字符串时 是主要因素 交换记录位置和移动记录的次数 当记录很大时 是主要因素 各种排序的比较 分析 1 平均时间性能 2 当序列 基本有序 时 简单排序中的插入排序最佳 3 基数排序适用于n值很大而关键字较小的序列 4 稳定性以基数排序为最佳 算法简单性比较 从算法简单性看 一类是简单算法 包括直接插入排序 直接选择排序和起泡排序 另一类是改进后的算法 包括希尔排序 堆排序 快速排序和归并排序 这些算法都很复杂 待排序的记录个数比较 从待排序的记录个数n的大小看n越小 采用简单排序方法越合适 n越大 采用改进的排序方法越合适 因为n越小 O n2 同O nlog2n 的差距越小 并且输入和调试简单算法比输入和调试改进算法要少用许多时间 关键字值的分布情况比较当待排序记录按关键的值有序时 插入排序和起泡排序能达到O n 的时间复杂度 对于快速排序而言 这是最坏的情况 此时的时间性能蜕化为O n2 选择排序 堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变 不同条件下 排序方法的选择 1 若n较小 如n 50 可采用直接插入或直接选择排序 当记录规模较小时 直接插入排序较好 否则因为直接选择移动的记录数少于直接插人 应选直接选择排序为宜 2 若文件初始状态基本有序 指正序 则应选用直接插人 冒泡或随机的快速排序为宜 且以直接插入排序最佳 3 若n较大 则应采用时间复杂度为O nlgn 的排序方法 快速排序 堆排序或归并排序 快速排序是目前基于比较的内部排序中被认为是最好的方法 当待排序的关键字是随机分布时 快速排序的平均时间最短 堆排序所需的辅助空间少于快速排序 并且不会出现快速排序可能出现的最坏况 这两种排序都是不稳定的 基数排序适用于n值很大而关键字较小的序列 若要求排序稳定 则可选用归并排序 基数排序稳定性最佳 第七章外部排序 分类 B磁盘文件的归并分类 1 多路归并 减少归并遍数 2 并行操作的缓冲区处理 使输入 输出和CPU处理尽可能重叠 3 初始归并段的生成 m个初始段进行2路归并 需要log2m遍归并 一般地 m个初始段 采用k路归并 需要logkm遍归并 显然 k越大 归并遍数越少 可提高归并的效率 在k路归并时 从k个关键字中选择最小记录时 要比较K 1次 若记录总数为n 每遍要比较的次数为 n k 1 log2m log2k 选择树或败者树 k路归并时间O n log2m 与k无关 A归并方法 首先将文件中的数据输入到内存 采用内部分类方法进行分类 归并段 然后将有序段写回外存 对多归并段 已有序 进行多遍合并 归并 最后形成一个有序序列 C磁带文件的归并分类 k路平衡归并分类 第八章文件 A文件及文件操作文件的概念关键字主关键字次关键字文件的逻辑结构和物理结构文件的操作 InsertDeleteModifyRetrieve检索方式 实时or成批更新方式 实时or成批查询方式 Q1 简单查询 Q2 范围查询 Q3 函数查询 Q4 布尔查询 B文件的组织顺序方式 索引方式 散列方式 链接方式 倒排方式 复习时注意几个问题 知识的连贯性 认真读书 尊重教材 要注意参考其它教材 注意基本概念 名词的理解 问题的研究对象 算法 1 遍历算法 线性表 树与二叉树 图 2 结点插入与删除算法 线性表 线索二叉树 二叉排序树 3 注意图中解决同一个问题的不同算法之间的区别 4 递归算法与非递归算法 5 查找与分类算法的性能比较 6 算法的分析 时间复杂度 空间复杂度 平均查找长度ASL 存储结构 线性表 树与二叉树 图 包括文件的组织方式注意顺序结构与链式结构的比较 你应该掌握的算法 结点的插入和删除链表建立 正序 反序 有序线性表 数组 链表 逆序重排 数组 链表 线性链表 求倒数第K个数线性链表 求中位数数组按照升序排列 给定一个数M 求数组中的两个元素 其合等于M 线性表 树及二叉树 二叉树的建立二叉树遍历 先序 中序 后序 层序 递归和非递归 各类结点数量统计 度为0 1 2 结点总数 判断满二叉树 完全二叉树二叉树左右孩子交换 二叉树镜像二叉树的深度 宽度二叉树最大 最短路径任意两个结点的最近公共祖先任意两个结点的路径结点层号 祖先根结点到叶子结点的所有路径 图 图的遍历算法 DFS BFS 最小生成