《数组和广义表》由会员分享，可在线阅读，更多相关《数组和广义表（45页珍藏版）》请在金锄头文库上搜索。
1、第五章 多维数组和广义表,5.1 多 维 数 组,一、多维数组的概念,对多维数组的看法： 观点一：多维数组是向量的推广。 观点二：多维数组是线性表的推广。,观点一和观点二是统一的！,多维数组:所有的数据元素均具有统一的数据类型，每个数据元素的下标具有固定的上、下界且每个数据元素都受到n个关系的约束（n个关系确定一个数据元素）。,1.二维数组,5.1 多 维 数 组,从两个方向看,m个行向量组成的一维向量,n个列向量组成的一维向量,这样，任一元素aij均属于两个向量：,第i 行的行向量,第 j列的列向量,1.二维数组,逻辑特征: 除边界外，每个元素aij恰好有两个直接前趋和两个直接后继。,5.1
2、 多 维 数 组,特殊的 a11:无前趋，有行列两个后继 amn:无后继，有行列两个前趋 a1n:只有一个列后继和一个行前趋 am1:只有一个列前趋和一个行后继 a1j ai1:有两个直接后继，但只有一个直接前趋 amj ain :有两个直接前趋，但只有一个直接后继,2.三维及多维数组,三维数组Amnp: 可看成有p个二维数组(m*n)所组成的向量，每个元素aijk同属于三个向量，每个元素最多有3个直接前趋和3个直接后继。,推广：多维数组An1n2nm可看成nm个（m-1）维数组所构成的向量, 任一元素ai1i2im都属于m个向量，最多有m个直接前趋和m个直接后继。,对于多维数组，通常只有两种
3、操作： 取值：给定一组下标，存取相应的数据元素； 修改：给定一组下标，修改相应数据元素中的某一个或几个数据项的值。,二、多维数组的运算,重要结论： 对于多维数组，通常只进行读、写操作，不进行元素的插入和删除操作； 计算机的内存结构是一维的，一般采用顺序存储结构表示数组。,(1) 行优先顺序(row major order) (c,pascal语言采用）特点：将数组元素按行向量排列。 (以二维数组为例）,(2) 列优先顺序(column major order) (fortran语言采用） 特点：将数组元素按行向量排列。 (以二维数组为例）,三、顺序存储方法,随机存取结构,顺序存储的数组是一个随
4、机存取结构，即只要知道开始元素的存储起址，维数和每一维的上、下界及单个元素所占单数，便可将数组元素的存储地址表示为其下标的线性函数。,(以二维数组Amn为例,且数组采用行优先顺序） LOC(aij)=LOC(a11)+(i-1)*n+j-1*d,d为单个元素 所占单元数,开始元素的 存储起址,n为列数,c语言中因数组下标从0开始，因此上面的式子应改为：LOC(aij)=LOC(a00)+(i*n+j)*d,5.2 矩阵的压缩存储,矩阵通常采用二维数组来存储,随机访问元素,运算简单,存储密度为1。,问题:,1.矩阵中非零元素呈某种规律分布 2.矩阵中有大量零元素，非零元素个数远远小于零元素个数,
5、5.2 矩阵的压缩存储,压缩存储: 定义：多个值相同的非零元素只分配一个存储空 间，值为零的元素不分配存储空间。 前提：非零元素呈某种规律分布或矩阵中有大量 零元素。,采用压缩存储的矩阵分为两类：特殊矩阵 和 稀疏矩阵。,a00 a10 a11 a20 a21 a n-1,0 a n-1,1 an-1,2 a n-1,n-1,5.2.1 特 殊 矩 阵,特殊矩阵：指的是非零元素或零元素的分布有一定规律的矩阵。对特殊矩阵常采用一维数组存储。,需解决的问题：如何将二维数组元素下标转换成一维数组元素下标。,1.对称矩阵1）定义: 已知n阶方阵A，若其元 素满足如下性质：,aij=aji 0=i,j=
6、j 则 k=i*(i+1)/2+j b: 若 i1 时，元素aij=0。,2）存储方法：按行优先顺序将其压缩，以一维数组存储，并根据aij与sk的相应关系对压缩矩阵进行访问。,a00 a01a10 a11 a12a21 a22 a23. . an-2 n-3 an-2 n-2 an-2 n-1an-1 n-2 an-1 n-1,三对角矩阵,5.2.1 特 殊 矩 阵,除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。,在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素。,a00 a01a10 a11 a12a21 a22
7、a23. . an-2 n-3 an-2 n-2 an-2 n-1an-1 n-2 an-1 n-1,5.2.1 特 殊 矩 阵,总结:特殊矩阵的非零元素的分布都具有规律,可以压缩存储到一个向量中,并且可找到矩阵元素和向量的对应关系. 通过这种关系仍能对矩阵的元素进行随机存取。,k= 3*i-1+(j-i+1)=2i+j,5.2.2 稀 疏 矩 阵,1、基本概念,稀疏矩阵：非零元素的个数远远少于矩阵元素的总数 （sm=3; a-n=5; a-t=4; a-data16,0 1 21 3 12 0 -32 3 2,i j v,A的三元组表,传统转置方法介绍,基本思想：由于A的列是B的行，因此按a
8、-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先顺序存放的。为了找到A的每一列中的所有非零元素，每次需要对三元组表a-data从第一个元素起扫描一遍，由于a-data是按A的行优先顺序存放的，因此得到的恰是b-data应有的顺序。,时间复杂度：O(n*t)O(m*n),spmatrix *TRANSMAT(spmatrix *a) int ano,bno,col; spmatrix *b;b=malloc(sizeof(spmatrix); b-m=a-n; b-n=a-m; b-t=a-t; /* b初始化*/ if(b-t0) /* 有非零元素*/ bno=0;
9、for(col=0; coln; col+) /*按*a列序转置*/ for(ano=0; anot; ano+) /*扫描整个三元组表*/ if(a-dataano.j=col) /*列号为col则进行交换*/ b-databno.i=a-dataano.j; b-databno.j=a-dataano.i; b-databno.v=a-dataano.v; bno+; /*b-data结点下标加1*/ return b; ,3、十字链表,1) 十字链表中结点的结构：,存储行号,存储列号,存储元素值或指 向下一个表头结点,列指针域，指向 本列下一个非零元素,行指针域，指向 本行下一个非零元素,
