《数据结构与算法》-教学课件 DS12_AdvDS.pptVIP

国家级精品课程—《数据结构与算法》;主要内容;12.1 多维数组;基本概念;基本概念（续）;数组的空间结构;数组的存储;Pascal的行优先存储;FORTRAN的列优先存储;C/C++、 Pascal行优先 先排最右的下标 从右向左 最后最左的下标 例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：;;FORTRAN列优先 先排最左的下标 从左向右 最后最右的下标 例如对于三维数组a[1..k, 1..m, 1..n]的元素axyz可以如下排列：;; ;用数组表示特殊矩阵;下三角矩阵图例;对称矩阵;对角矩阵;稀疏矩阵;稀疏矩阵;稀疏因子 在m ×n的矩阵中，有t个非零元素，则稀疏因子为: 当这个值小于时，可以认为是稀疏矩阵 三元组(i, j, aij )：输入/输出常用 i是该元素的行号 j是该元素的列号 aij是该元素的值 ;稀疏矩阵的十字链表;经典矩阵乘法;p=d1-c1+1，m=d3-c3+1，n=d2-c2+1； A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵 经典矩阵乘法所需要的时间代价为O(p×m×n);稀疏矩阵乘法;稀疏矩阵乘法时间代价;稀疏矩阵的应用;12.2 广义表和存储管理;12.2.1 广义表;基本概念 ;L＝（x0，x1，…，xi，…，xn-1） L是广义表的名称 n为长度 每个xi（0≤i≤n-1）是L的成员 可以是单个元素，即原子（atom ) 也可以是一个广义表，即子表（sublist） 广义表的深度：表中元素都化解为原子后的括号层数;L＝（x0，x1，…，xi，…，xn-1） 表头head = x0 表尾tail =（x1，…，xn-1） 规模更小的表 有利于存储和实现 ; 广义表的各种类型;广义表的各种类型（续）;广义表的各种类型（续）;;图?再入表?纯表(树)?线性表 广义表是线性与树形结构的推广 递归表是有回路的再入表 广义表应用 函数的调用关系 内存空间的引用关系 LISP语言 ;广义表存储ADT（续）;增加头指针，简化删除、插入操作 重入表，尤其是循环表 mark标志位——图的因素;带表头结点的循环广义表;;;12.2.2 存储管理技术;动态内存分配 new和delete 内存管理技术 链表、广义表;分配与回收 ;虚拟存储：内存溢出的管理 ;可利用空间表 ;;可利用空间表的函数重载 ;//重载new运算符实现 template class Elem void * LinkNodeElem::operator new(size_t){ if(avail == NULL) //可利用空间表为空 return ::new LinkNode; //利用系统的new分配空间 LinkNodeElem * temp = avail;//从可利用空间表中分配 avail = avail-next; return temp; };//重载delete运算符实现 template class Elem void LinkNodeElem::operator delete(void * p){ ((LinkNodeElem *) p)-next = avail; avail = (LinkNodeElem *)p; };可利用空间表：单链表栈 new即栈的删除操作 delete即栈的插入操作 直接引用系统的new和delete操作符，需要强制用“::new p”和“::delete p” 例如，程序运行完毕时，把avail所占用的空间都交还给系统（真正释放空间）;;存储的动态分配和回收 ;空闲块的数据结构;碎片问题;顺序适配(sequential fit) ;顺序适配;顺序适配;顺序适配;回收：考虑合并相邻块;适配策略选择;伙伴系统 ;;失败处理策略和无用单元回收 ;存储压缩( compact );无用单元收集;; Trie结构和Patricia树;Trie结构 ;二叉Trie结构;英文字符树——26叉Trie ;不等长的字符树，加“*”标记;压缩靠近叶结点的单路径;Trie字符树的特点;PATRICIA 结构;PATRICIA 结构图;压缩PATRICIA 结构;PATRICIA的特点;12.4 改进的二叉搜索树; ;最佳二叉搜索树的动态规划;包含关键码keyi+1，keyi+2，…，keyj为内部结点(0≤i≤j≤n) 结点的权为(qi，pi+1， qi+1，…，pj，qj)， 根为r(i，j) 开销为C(i，j)，即 权的总和为W(i，j) = pi+1+…+pj+qi+qi+1+…+qj;以keyk为根 左子树包含keyi+1，…，keyk-1 C(i， k-1) 右子树包含keyk+l，keyk+2，…，keyj C(k，