数据结构 课件 第5章 数组和广义表 .pptx
第5章数组和广义表;5.2矩阵的压缩存储;5.1.1数组的基本概念;一个m行n列的二维数组A可以看作每个数据元素为线性表的线性表。;5.1.2数组的存储结构;一旦a1的存储地址LOC(a1)确定，并假设每个数据元素占用k个存储单元，则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：;m行n列的二维数组Am×n，存储方式：;;a1,1，a1,2，…，a1,n，…，ai,1，ai,2，…，ai,j-1，ai,j，…，ai,n，…;同理可推出在以列序为主序的计算机系统中有：;压缩存储的矩阵的主要有：
（1）特殊矩阵的存储
（2）稀疏矩阵的存储
;特殊矩阵的主要形式有：
（1）对称矩阵
（2）上三角矩阵／下三角矩阵
（3）对角矩阵
它们都是方阵，即行数和列数相同(m=n)。;对称矩阵的压缩存储;;k=;n2个元素n(n+1)/2个元素
A[0..n-1,..n2-1]B[0..n(n+1)/2-1]
a[i][j]b[k];a1,1;a1,1;B=（a1,1，a2,1，a2,2，?，an,1，an,2，?，an,n）;若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（i≤j）的下标i、j与k的对应关系是（）。;半带宽为b的对角矩阵;AB
a[i][j]b[k];一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即st时，称该矩阵为稀疏矩阵。
例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。;特殊矩阵的特殊元素（值相同元素、常量元素）分布有规律。
稀疏矩阵的特殊元素（非0元素）分布没有规律。;稀疏矩阵的压缩存储方法是只存储非零元素。
稀疏矩阵中的每一个非零元素需由一个三元组：
(i，j，ai,j)
唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表。;一个6×7阶稀疏矩阵A的三元组线性表表示;把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。;稀疏矩阵的压缩存储方法是只存储非零元素。;i;voidCreatMat(TSMatrixt,ElemTypeA[M][N])
{inti,j;t.rows=M;t.cols=N;t.nums=0;
for(i=0;iM;i++)
{for(j=0;jN;j++)
if(A[i][j]!=0)
{t.data[t.nums].r=i;
t.data[t.nums].c=j;
t.data[t.nums].d=A[i][j];
t.nums++;
}
}
};（2）三元组元素赋值：A[i][j]=x
分为两种情况：①将一个非0元素修改为另一个非0值，如A[5][6]=8。;i;boolValue(TSMatrixt,ElemTypex,inti,intj)
{intk=0,k1;
if(i=t.rows||j=t.cols)
returnfalse; //失败时返回false
while(kt.numsit.data[k].r)k++; //查找行
while(kt.numsi==t.data[k].r
jt.data[k].c)k++; //查找列
;
if(t.data[k].r==it.data[k].c==j)//存在这样的元素
t.data[k].d=x;
else //不存在这样的元素时插入一个元素
{for(k1=t.nums-1;k1=k;k1--)
{t.data[k1+1].r=t.data[k1].r;
t.data[k1+1].c=t.data[k1].c;
t.data[k1+1].d=t.data[k1].d;
}
t.data[k].r=i;t.data[k].c=j;t.data[k].d=x;
t.nums++;
}
returntrue; //成功时返回true
};boolAssign(TSMatrixt,Ele