第五章,数组和广义表.ppt
《第五章,数组和广义表.ppt》由会员分享,可在线阅读,更多相关《第五章,数组和广义表.ppt(19页珍藏版)》请在三一文库上搜索。
1、第五章,数组和广义表,第一节 数组的定义,数组的概念 数组是由一组个数固定,类型相同的数据元素组成的阵列。 以二维数组为例:二维数组中的每个元素都受两个线性关系的约束即行关系和列关系,在每个关系中,每个元素aij都有且仅有一个直接前趋,都有且仅有一个直接后继。 二维数组也可看作这样的线性表,其每一个数据元素也是一个线性表。,Amn=,Amn=(a00, a01 a0,n-1),(a10, a11 a1,n-1),(am-1,0, am-1,1 am-1,n-1),基本操作 InitArray(&A,n,bound1,boundn)构造一个n维数组 DestroyArray(&A)销毁数组A V
2、alue(A,&e,index1,indexn)取元素值到e Assign(&A,e,index1,indexn)存e的值到数组A,第二节 数组的顺序表示和实现,由于存储单元是一维结构,而数组是个多维的结构,则用一组连续存储单元存放数组的数据元素就有个次序约定即行列存储。,第1行,第2行,第m行,Loc(a00),Loc(a10),Loc(am-1,0),以行为主序,第1列,第2列,第n列,Loc(a00),Loc(a01),Loc(a0,n-1),以列为主序,数组元素存储地址的计算 假设二维数组Amn每个元素占用L 个存储单元, Loc(aij)为元素aij 的存储地址,Loc(a00 )
3、是a00存储位置, 也是二维数组A的基址。 若以行序为主序的方式存储二维数组,则元素aij 的存储位置可由下式确定: Loc(aij ) = Loc(a00 ) +(n i+j ) L 若以列序为主序的方式存储二维数组,则元素aij 的存储位置可由下式确定: Loc(aij ) = Loc(a00) +(m j+i ) L,第三节 矩阵的压缩存储,矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。 一个m行n列的矩阵是一平面阵列,有mn个元素。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素,因而能较为容易地实现矩阵的各种运算。 应用中常遇到一些阶数很高的矩阵
4、,矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。因此,需要使用高效的存储方法,减少数据的存储量,即对原矩阵,根据数据分布特征进行压缩存储。,一、特殊矩阵 值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例如对称矩阵、上(下)三角矩阵都是特殊矩阵。 特殊矩阵压缩存储 (以对称矩阵为例) 对称矩阵是满足下面条件的n 阶矩阵: aij= aji 0 i,j n-1,对称矩阵元素可以只存储下三角部分,共需 n(n+1)/2 个单元的空间( 三角矩阵的存储方式类似),K= 0 1 2 n(n+1)/2-1,以一维数组sa 作为n 阶对称矩阵A的存储结构,A中任意一元素 a
5、ij与它的存储位置 sak 之间存在着如下对应关系:,k =,i(i-1)/2 +j -1 当 i j j(j-1)/2 +i -1 当 i j,例如, a32 在 sa 中的存储位置是:k=3*(3-1)/2+2-1=4 则sa4= a32,K= 0 1 2 3 4 n(n+1)/2-1,压缩存储的对称矩阵的取值算法 int get_M(int i, int j) if(i=j) return(sai*(i+1)/2+j); else return(saj*(j+1)/2+i); ,压缩存储的对称矩阵的 赋值算法 void assign_M(int i, int j, int value)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 数组 广义
链接地址:https://www.31doc.com/p-2583116.html