数组可以看成是一种特殊的线性表.ppt

第四章 数组 数组可以看成是一种特殊的线性表，即线性表中数 据元素本身也是一个线性表 v4.1 数组的定义和特点 定义 数组特点 v数组结构固定 v数据元素同构 数组运算 v给定一组下标，存取相应的数据元素 v给定一组下标，修改数据元素的值 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) v4.2 数组的顺序存储结构 次序约定 v以行序为主序 v以列序为主序 a11 a12 a1n a21 a22 a2n am1 am2 amn . Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放 amn am2 am1 . a2n a22 a21 a1n . a12 a11 0 1 n-1 m*n-1 n 按列序为主序存放 0 1 m-1 m*n-1 m amn a2n a1n . am2 a22 a12 am1 . a21 a11 a11 a12 a1n a21 a22 a2n am1 am2 amn . Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l v4.3 矩阵的压缩存储 对称矩阵 a11 a12 . a1n a21 a22 . a2n an1 an2 ann . a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序： 三角矩阵 a11 0 0 0 a21 a22 0 0 an1 an2 an3 ann . 0 Loc(aij)=Loc(a11)+( +(j-1)*l i(i-1) 2 a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序： 对角矩阵 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序： 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）唯一确定 稀疏矩阵 v定义：非零元较零元少，且分布没有一定规律的矩阵 v压缩存储原则：只存矩阵的行列维数和每个非零元的 行列下标及其值 v稀疏矩阵的压缩存储方法 顺序存储结构 v三元组表 #define M 20 typedef struct node int i,j; int v; JD; JD maM; 三元组表所需存储单元个数为3(t+1) 其中t为非零元个数 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 ma i j v 0 1 2 3 4 5 6 7 8 ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数 行列下标 非零元值 v带辅助行向量的二元组表 增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有： NRA1=1 NRAi=NRAi-1+第i-1行非零元个数(i2) 0 1 2 3 4 5 6 NRA 1 3 3 5 6 7 6 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 ma j v 0 1 2 3 4 5 6 7 8 矩阵列数和 非零元个数 列下标和 非零元值 NRA0不用或 存矩阵行数 二元组表需存储单元 个数为2(t+1)+m+1 v伪地址表示法 伪地址：本元素在矩阵中（包括零元素再内） 按行优先顺序的相对位置 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 ma addr v 伪地址 非零元值 矩阵行列维数 0 1 2 3 4 5 6 7 8 伪地址表示法需存储单元个数 为2(t+1) v求转置矩阵 Y问题描述：已知一个稀疏矩阵的三元组表，求该矩 阵转置矩阵的三元组表 Y问题分析 一般矩阵转置算法： for(col=0;colp-col时，p和q右移 （2）插入： a、若p=NULL且q=NULL，即本行空，则rhr-1=s; b、若p=NULL,q!=NULL，即走到行末，则q-right=s c、若c=p-col，则修改p-val d、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s; s-right=p; e、若ccol且q!