Open ssfc opened 6 years ago
16.ep 11: 串的堆分配存储表示; malloc, free; 串的块链存储表示, 每个结点放一个串; 串的模式匹配; 简单算法index; 首尾匹配算法; KMP算法, 时间复杂度O(m+n), 因为解决了指针回溯问题; 把串比较转化成自比较; 模式串的next函数; (2018-4-11) 17.Ep 12: 寻找模式串; review; (2018-4-14) 18.Ep 13: 数组和广义表; 数组的类型定义; InitArray, DestroyArray, Value, Assign; 数组的顺序表示和实现; 行序为主序; n维数组的映像函数; 稀疏矩阵的压缩存储; 稀疏因子; 特殊矩阵的压缩存储(三角矩阵, 对角矩阵); 三元组顺序表, 类似于多项式; 求转置矩阵, 需要移动元素; (2018-4-14) 19.Ep 14: FastTransposeMatrix; 统计每一列非零元; 行逻辑连接的顺序表; 矩阵乘法的经典算法; 三元顺序表的矩阵相乘, 时间复杂度大大降低; (2018-4-18) 20.ep 15: 十字链表; review, (1) 了解数组的两种存储表示方法, 并掌握以行为主的地址计算; (2)掌握特殊矩阵压缩表示的坐标变换; (3)了解稀疏矩阵的两种压缩存储方法, 领会三元组进行矩阵运算; 树; 空树; 子树; 有向树; Node; 结点的度; 叶子结点; 分支结点; 孩子父亲兄弟祖先子孙; 结点的层次; 树的深度; 树的查找; 树的插入; 树的删除; 有向树; 有序树, 子树间存在次序关系; 线性结构和树结构的比较; 二叉树; 二叉树的5种基本形态; (2018-4-18) 21.ep 16: 习题课; example 2.4, 比较两个顺序表大小(类似于字符串比较); 删除有序表中区间(a, b)元素; example 2.8, ABC都是有序表, 从A链表中删除B表和C表共有的数据元素, 谁小谁后移; example 2.9, 双向循环链表, 增加访问频度; (2018-4-18) 22.Ep 17: example 3.2, 给出证明栈操作是否合法的准则; 第一个子列s>=x, 整个序列s=x; example 3.6, 用while和stack代替递归; 识别一个读入的反对称序列, 用stack; example 3.15, 判断是否回文, 比较栈顶和队头; example 4.7, 从串S中删除所有和串T相同的子串; example 4.11, 求最长重复子串; (2018-4-20) 23.Ep 18: 又讲了一遍KMP算法的next; 时间复杂度O(m+n); 性质1, 二叉树第i层最多有2^(i-1)结点; 性质2, 深度为k的二叉树上至多有2^k-1个结点; 性质3, n0 = n2 + 1; 性质4, 具有n个结点的二叉树深度为log2n+1; (2018-4-20) 24.ep 19: 满二叉树; 完全二叉树; (1) i/2是i的parent; (2) 若2i>n, 则i无左孩, 若2i=n, 则2i为i左孩; (3)若2i+1>n, 则i无右孩, 若2i+1=n, 则2i+1为i右孩; 二叉树的顺序存储表示; 用完全二叉树规模的数组存储普通二叉树; 二叉树的链式存储; 二叉链表; 三叉链表; 二叉树的遍历; 每个结点经过3次; 先序遍历, 第1次访问时送报; 中序遍历, 第2次访问时送报; 后序遍历, 第3次访问时送报; Preorder递归; 用栈来实现遍历回退; 中序遍历的非递归实现; (2018-4-20) 25.Ep 20: 统计二叉树中叶子结点的个数(先序遍历); 求二叉树的深度(后序遍历); 复制二叉树(后序遍历); 建立二叉树的存储结构; 按给定的先序序列建立二叉链表; 按给定的表达式建相应二叉树, 由先缀表达式建树; (2018-4-27)
16.ep 11: 串的堆分配存储表示; malloc, free; 串的块链存储表示, 每个结点放一个串; 串的模式匹配; 简单算法index; 首尾匹配算法; KMP算法, 时间复杂度O(m+n), 因为解决了指针回溯问题; 把串比较转化成自比较; 模式串的next函数; (2018-4-11) 17.Ep 12: 寻找模式串; review; (2018-4-14) 18.Ep 13: 数组和广义表; 数组的类型定义; InitArray, DestroyArray, Value, Assign; 数组的顺序表示和实现; 行序为主序; n维数组的映像函数; 稀疏矩阵的压缩存储; 稀疏因子; 特殊矩阵的压缩存储(三角矩阵, 对角矩阵); 三元组顺序表, 类似于多项式; 求转置矩阵, 需要移动元素; (2018-4-14) 19.Ep 14: FastTransposeMatrix; 统计每一列非零元; 行逻辑连接的顺序表; 矩阵乘法的经典算法; 三元顺序表的矩阵相乘, 时间复杂度大大降低; (2018-4-18) 20.ep 15: 十字链表; review, (1) 了解数组的两种存储表示方法, 并掌握以行为主的地址计算; (2)掌握特殊矩阵压缩表示的坐标变换; (3)了解稀疏矩阵的两种压缩存储方法, 领会三元组进行矩阵运算; 树; 空树; 子树; 有向树; Node; 结点的度; 叶子结点; 分支结点; 孩子父亲兄弟祖先子孙; 结点的层次; 树的深度; 树的查找; 树的插入; 树的删除; 有向树; 有序树, 子树间存在次序关系; 线性结构和树结构的比较; 二叉树; 二叉树的5种基本形态; (2018-4-18) 21.ep 16: 习题课; example 2.4, 比较两个顺序表大小(类似于字符串比较); 删除有序表中区间(a, b)元素; example 2.8, ABC都是有序表, 从A链表中删除B表和C表共有的数据元素, 谁小谁后移; example 2.9, 双向循环链表, 增加访问频度; (2018-4-18) 22.Ep 17: example 3.2, 给出证明栈操作是否合法的准则; 第一个子列s>=x, 整个序列s=x; example 3.6, 用while和stack代替递归; 识别一个读入的反对称序列, 用stack; example 3.15, 判断是否回文, 比较栈顶和队头; example 4.7, 从串S中删除所有和串T相同的子串; example 4.11, 求最长重复子串; (2018-4-20) 23.Ep 18: 又讲了一遍KMP算法的next; 时间复杂度O(m+n); 性质1, 二叉树第i层最多有2^(i-1)结点; 性质2, 深度为k的二叉树上至多有2^k-1个结点; 性质3, n0 = n2 + 1; 性质4, 具有n个结点的二叉树深度为log2n+1; (2018-4-20) 24.ep 19: 满二叉树; 完全二叉树; (1) i/2是i的parent; (2) 若2i>n, 则i无左孩, 若2i=n, 则2i为i左孩; (3)若2i+1>n, 则i无右孩, 若2i+1=n, 则2i+1为i右孩; 二叉树的顺序存储表示; 用完全二叉树规模的数组存储普通二叉树; 二叉树的链式存储; 二叉链表; 三叉链表; 二叉树的遍历; 每个结点经过3次; 先序遍历, 第1次访问时送报; 中序遍历, 第2次访问时送报; 后序遍历, 第3次访问时送报; Preorder递归; 用栈来实现遍历回退; 中序遍历的非递归实现; (2018-4-20) 25.Ep 20: 统计二叉树中叶子结点的个数(先序遍历); 求二叉树的深度(后序遍历); 复制二叉树(后序遍历); 建立二叉树的存储结构; 按给定的先序序列建立二叉链表; 按给定的表达式建相应二叉树, 由先缀表达式建树; (2018-4-27)