- 1、本文档共149页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
国家级精品课程—《数据结构与算法》;主要内容;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,
您可能关注的文档
- 《数控加工工艺与编程》(教学资源) 第4章 数控电火花加工工艺与编程.ppt
- 《无机化学》第3版 宋天佑 15 氮族元素.ppt
- 《物联网控制技术》 物联网控制技术-第5章计算机控制算法.ppt
- 《税费计算与申报》(第四版)教学课件 教学课件:情境2-2 增值税纳税申报.ppt
- 《体育服务营销》课件 序言.ppt
- 《数学建模方法及其应用》电子课件 第7章 概率统计方法3.ppt
- 《市场营销(居长志)(第五版)(居长志) 项目八(4):促销策略.ppt
- 《土木工程材料》课件 第7章墙体材料.ppt
- 《税费计算与申报》(第三版)教学课件:情境4-2关税的缴纳.ppt
- 《税费计算与申报》(第四版)教学课件 教学课件:情境4-2关税的缴纳.ppt
最近下载
- ZJ70-4500D20石油钻机使用说(2022年-2023年)明书.docx VIP
- 2023-2024学年人教版高中信息技术必修一第二章第一节《解决问题的一般过程和用计算机解决问题》教案.docx VIP
- GB7258—2022机动车运行安全技术条件修订内容解读29.pdf
- 医学装备使用安全培训.pptx
- Unit6单元整体设计人教版九年级英语全册.pdf
- 中考数学轨迹问题集锦69739.doc VIP
- 2024年河北省继续医学教育公共必修课参考答案.pdf VIP
- 驾校学员心理调节精编.ppt
- 自考06269工程应用英语(13-19)真题试卷.doc VIP
- 智能农业传感器监测和优化农作物生长环境.pptx
文档评论(0)