数据结构总结.ppt

数据结构与算法基础 数据结构与算法总结 * 《数据结构与算法基础》 课程回顾与总结 第一章 绪论 A数据结构研究对象 信息 数据 数据元素 数据项 数据结构 数据对象 数据类型 B数据结构 逻辑结构 存储结构（物理结构） 数据结构分类 C数据结构发展概况 D抽象数据型(ADT) 数据型、数据结构与抽象数据型 抽象数据型的规格描述（语法、语义） 抽象数据型的实现 抽象数据型的优点 多层次抽象技术 E算法 什么叫算法？ 算法的特征 “好”的算法的评价标准 对算法的正确性的要求 算法的描述 类语言 F算法分析 算法的时间特性 时间复杂度T(n) 空间复杂度S(n) 第三章 线性表 A线性表的概念 什么叫线性表 抽象数据型线性表 B线性表的实现 静态数据结构 动态数据结构 顺序存储（数组实现） 链式存储（指针） 游标（静态链表） C线性链表 表头结点 单向链表 双向链表 单向循环量表 双向循环链表 D限定性数据结构： 栈 队列 E栈 栈的概念 ADT栈 栈的存储结构 栈的应用: 栈与递归 迷宫求解 表达式转换与求值 F队列 队列的概念 ADT队列 队列的存储结构 循环队列 G线性表的应用： 多项式的表示 多项式相加运算 H串 串的基本概念 ADT串 串的存储结构 存储密度 I 数组 数组的概念 ADT数组 数组的存储结构 数组的压缩存储：特殊矩阵、对角或带状矩阵、稀疏矩阵 J广义表 基本概念 广义表的存储结构 第四章 树与二元树 A树的基本术语 树 子树 结点 分支 度 路 叶子 非终结（端）结点 终结（端）结点 儿子 父亲 兄弟 堂兄弟 祖先 子孙结点； 层 高度（深度） 结点的顺序 层序 有序树 无序树 森林 B二元树 二元树的定义，ADT二元树，满二元树，完全二元树 二元树的遍历：先序遍历、中序遍历和后序遍历，层序遍历 二元树遍历的非递归算法（先序、中序和后序） 二元树的性质：（1～5） 二元树的存储结构：顺序存储、链式存储（二叉链表） 线索二元树：基本概念，先序、中序与后序线索 求线索二元树的（先序、中序、后序）前驱与后继结点 线索二元树的遍历 线索二元树中插入、删除结点的讨论 性质1：在二元树中的第 i 层的结点数最多为：2i-1 。 性质2：高度为k的二元树其结点总数最多为2k－1 (k ≥ 1) 。 性质3：对任意的非空二元树 T ，如果叶结点的个数为 n0，而 其度为 2 的结点数为 n2，则：n0 = n2 + 1 。 性质4：具有 n 个结点的完全二元树的深度为 log2n + 1。 性质5：如果对一棵有n个结点的二元树的结点按层序编号，则对任一结点i有： ⑴ 如果 i=1，则结点i是二元树的根，无双亲； 如果 i＞1，则其双亲结点是i/2； ⑵ 如果 2i＞n，则结点i无左孩子结点，否则其左孩子结点是 2i； ⑶ 如果 2i+1＞n，则结点i无右孩子结点，否则其右孩子结点是