《数据结构清华版》4-串和数组.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 数组,数组能够看成是一个特殊线性表，即线性表中数据元素本身也是一个线性表,4.1 数组定义和特点,定义,数组特点,数组结构固定,数据元素同构,数组运算,给定一组下标，存取对应数据元素,给定一组下标，修改数据元素值,(),(),(),(),(),(),(),(),(),1/20,4.2 数组次序存放结构,次序约定,以行序为主序,以列序为主序,a,11,a,12,.a,1n,a,21,a,22,.a,2n,a,m1,a,m2,.a,mn,.,Loc(,a,ij,)=Loc(,a,11,)+,(i-1)n+(j-1),*l,按行序为主序存放,a,mn,.,a,m2,a,m1,.,a,2n,.,a,22,a,21,a,1n,.,a,12,a,11,0,1,n-1,m*n-1,n,按列序为主序存放,0,1,m-1,m*n-1,m,a,mn,.,a,2n,a,1n,.,a,m2,.,a,22,a,12,a,m1,.,a,21,a,11,a,11,a,12,.,a,1n,a,21,a,22,.,a,2n,a,m1,a,m2,.,a,mn,.,Loc(aij)=Loc(,a,11,)+(j-1)m+(i-1)*l,2/20,4.3 矩阵压缩存放,对称矩阵,a,11,a,12,.,.,a,1n,a,21,a,22,.,a,2n,a,n1,a,n2,.,a,nn,.,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,3/20,三角矩阵,a,11,0 0,.,0,a,21,a,22,0,.,0,a,n1,a,n2,a,n3,.,a,nn,.,0,Loc(aij)=Loc(,a,11,)+(+(j-1)*l,i(i-1),2,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,4/20,对角矩阵,a,11,a,12,0,.,0,a,21,a,22,a,23,0,0,0,0,a,n-1,n-2,a,n-1,n-1,a,n-1,n,0,0,a,n,n-1,a,nn.,0,a,32,a,33,a,34,0,0,Loc(aij)=Loc(,a,11,)+2(i-1)+(j-1),a,11,a,12,a,21,a,22,a,23,a,nn-1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,5/20,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）唯一确定,稀疏矩阵,定义：非零元较零元少，且分布没有一定规律矩阵,压缩存放标准：只存矩阵行列维数和每个非零元行列下标及其值,6/20,稀疏矩阵压缩存放方法,次序存放结构,三元组表,#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,分别存放,矩阵行列维数和非零元个数,行列下标,非零元值,7/20,带辅助行向量二元组表,增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元,在二元组表中起始地址（m为行数）,显然有：,NRA1=1,NRAi=NRAi-1+第i-1,行非零元个数(i,2),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,8/20,伪地址表示法,伪地址：本元素在矩阵中（包含零元素再内）,按行优先次序相对位置,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),9/20,求转置矩阵,问题描述：已知一个稀疏矩阵三元组表，求该矩阵转置矩阵三元组表,问题分析,普通矩阵转置算法：,for(col=0;coln;col+),for(row=0;rowp-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!=NULL，则在p之前插入s，,即 s-right=p;q-right=s;,19/20,4,1,8,2,3,4,m=4,n=3,1,1,3,2,2,5,2,3,4,4,1,8,2,1,7,Ch4_3.c,1,1,3,2,1,7,2,2,5,20/20,