ch5数组和广义表

《ch5数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组和广义表数组的类型定义和表示方法特殊矩阵稀疏矩阵存储方法及运算的实现广义表的结构特点5.1二维数组的定义定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()数组是一组有固定（一旦定义了数组的维数和每一维的上下限个数）的元素的集合。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：数组可以看成是一种特殊的线性表，即线性表中数据元素本身

2、也是一个线性表可以将二维数组A看成是由m个行向量[X0，X1，…，Xm-1]组成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以将二维数组A看成是由n个列向量[y0,y1,……,yn-1]组成，其中yi=(a0i,a1i,…..,am-1i)，0≤i≤n-1。5.1.2数组的顺序存储结构例：设数组的基址为LOC(a00)，每个数组元素占据Ｓ个地址单元行优先顺序LOC(aij)=LOC(a00)+（i×n+j）×S列优先顺序LOC(aij)=LOC(a00)+(j×m+i)×S5.2

3、特殊矩阵及其存储若一个n阶方阵A中元素满足下列条件：aij=aji其中0≤i,j≤n-1，则称A为对称矩阵。1．对称矩阵对称阵的下三角矩阵对称阵的上三角矩阵按行存放于一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有：n+(n-1)++1=n*(n+1)/2个元素。2．三角矩阵（1）上三角矩阵：矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0。（2）下三角矩阵：矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0。111110111000....

4、.................----nnnnaaacaacca111111100100..................----nnnnacccaacaaa3．对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa三对角矩阵的压缩存储Ba

5、00a01a10a11a12a21a22a23…an-1n-2an-1n-1012345678910对角阵的下标从0起存放对角阵元素的一维数组的下标从0起应用实例设矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。算法：voidsaddle(intA[][],intm,in

6、tn)/*m,n是矩阵A的行和列*/{inti,j,k,min;for(i=0;imin)Break;if(j>=m)printf(＂%d,%d,%d＂,i,k,min);}/*endfori*/}算法的时间性能为O(m*

7、n))5.3稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7,8）唯一确定例如：稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode/*三元组表中元素类型*/{inti,j;/*非零元所在行号和列号*/intv;/*非零元素值*/}SP

8、Node;SPNodema[M];maijv012345678maijv012345678678011202920-3251432244118501553-7求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col