数据结构课件Ch5.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构课件Ch5.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 Ch5
- 资源描述:
-
1、1第五章第五章 数组和广义表数组和广义表23456789101112 2、数组的顺序存储 由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化。因此,采用顺序存储结构表示数组是顺理成章的事了。本章中,仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析。多维数组的顺序存储有两种形式。行优先顺序列优先顺序13行优先顺序行优先顺序 行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放第二行元素,第三行元素,依次类推 在BA
2、SIC语言、PASCAL语言、C/C+语言等高级语言程序设计中,都是按行优先顺序存放的。例如,对刚才的Amn二维数组,可用如下形式存放到内存:a00,a01,a0n-1,a10,a11,., a1 n-1,am-1 0 , am-1 1,am-1 n-1。即二维数组按行优先存放到内存后,变成了一个线性序列(线性表)。 因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。因此,在算法中,最左边下标可以看成是外循环,最右边下标可以看成是最内循环。14地址计算地址计算由于多维数组在内存中排列成一个线性序列,因此,若知
3、道第一个元素的内存地址,如何求得其他元素的内存地址?我们可以将它们的地址排列看成是一个等差数列,假设每个元素占l个字节,元素aij 的存储地址应为第一个元素的地址加上排在aij 前面的元素所占用的单元数,而aij 的前面有i行(0i-1)共in个元素,而本行前面又有j个元素,故aij的前面一共有in+j个元素,设a00的内存地址为LOC(a00),则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+(in+j)l。同理,三维数组Amnp按行存放的地址计算公式为:LOC(aijk)=LOC(a000)+(优先inp+jp+k)l。15列优先顺序列优先顺序 1存放规则存放规则 列
4、优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时,按列号从小到大的顺序,先将第一列中元素全部存放好,再存放第二列元素,第三列元素,依次类推 在FORTRAN语言程序设计中,数组是按列优先顺序存放的。例如,对前面提到的Amn二维数组,可以按如下的形式存放到内存:a00, a10, am-10, a01,a11, , am-1 1, a0 m-1,a1m-1,., am-1 n-1。 即二维数组按列优先存放到内存后,也变成了一个线性序列(线性表)。 因此,可以得出多维数组按列优先存放到内存的规律:最右边下标变化最慢,最左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次。因
5、此,在算法中,最右边下标可以看成是外循环,最左边下标可以看成是最内循环。16173、矩阵的压缩存储特殊矩阵稀疏矩阵18矩阵压缩存储矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对象。矩阵可以用行优先或列优先方法顺序存放到内存中,但是,当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储单元,即进行压缩存储。所谓压缩存储是指:为多个值相同的元素只分配一个存储空间,值为零的元素不分配空间。但是压缩存储时,节约了存储单元,但怎样在压缩后找到某元素呢?因此还必须给出压缩前的下标和压缩后下标之间变换公式,才能使压缩存储变
6、得有意义。19特殊矩阵1对称矩阵对称矩阵2三角矩阵三角矩阵201对称矩阵若一个n阶方阵A中元素满足下列条件:aij=aji 其中 0 i, jn-1 ,则称A为对称矩阵。例如,下图是一个3*3的对称矩阵。21上三角矩阵即矩阵上三角部分元素是随机的,而下三角部分元素全部相同(为某常数C)或全为0,具体形式见图)。22下三角矩阵即矩阵的下三角部分元素是随机的,而上三角部分元素全部相同(为某常数C)或全为0,具体形式见图。23对角矩阵对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为0,则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。图为77的三对角矩阵(
展开阅读全文