数据结构(c语言版)课件(西安交大)第五章

《数据结构(c语言版)课件(西安交大)第五章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组的定义及其基本操作数组的存储结构特殊矩阵的压缩存储稀疏矩阵的压缩存储广义链表第五章数组数组的定义数组是n(n>=)个相同数据类型数据元素构成的有限序列。一个一维数组，一旦第一个元素ai的存储地址Loc(ai)确定，而每个元素所占用的存储空间大小k为则第i个元素的地址可以由以下公式计算：一、数组的定义及其基本操作一维数组的示例一维数组的数组元素可以是基本数据类型，可以是复杂数据类型。当基本类型也是数组时，一维数组扩充为二维数组(矩阵)。二维数组同样满足数组的定义。一个二维数组可以被看成是特殊的一维数组，其中，每个元素又是一个一维数组。多维数组可以按同样的方法类推。数组具有如下性质：数

2、组中的数据元素数目固定；数组中的数据元素具有相同的数据类型；数组中的每个数据元素都与一组唯一的下标值相对应；数组是一种随机存储结构。二维数组(矩阵)三维数组(书)行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k一维数组LOC(i)=LOC(i-1)+l=α+i*l二、数组的存储结构二维数组行优先LOC(j,k)==a+(j*m+k)*ln维数组将其中的每一个元素映射到一维数组的某一个位置，各维元素个数为m1,m2,m3,…,mn，下标为i1,i2,i3,…,in的数组元素的存储地址：三、特殊矩阵的压缩存储1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：则称A为对称矩阵。

3、对称矩阵中的元素关于主对角线对称，故只需要存储矩阵的上三角或下三角矩阵，这样可以节约大约一半的空间。在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：a00a10a11a20a21a22.......an-1,0........an-1,n-1因此，我们可以将这些元素存放在一个向量sa[n(n+1)/2]中。为了便于访问方阵A中的元素，必须在aij和sa[k]之间建立一个对应关系。若aij在上三角矩阵中，则有：若aij在下三角矩阵中，则有：令I=max(i,j)，J=min(i,j)，则k和i、j的对应关系可统一为：2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种：在多数

4、情况下，三角矩阵的常数c为0。三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[n(n+1)/2+1]中，其中c存放到向量的最后一个分量上。上三角矩阵中，aij和sa[k]之间的对应关系为：下三角矩阵中，aij和sa[k]之间的对应关系为：3、对角矩阵对角矩阵中，所有非0元素都集中在以主对角线为中心的带状区域中。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非0元素和向量下标的对应关系。四、稀疏矩阵的压缩存储如果一个矩阵的非0元素个数远远小于矩阵元素的总数，则称这个矩阵为稀疏矩阵。一般来说

5、，稀疏矩阵非0元素的分布是无规律的。因此，在存储非0元素的同时，还要存储适当的辅助信息，才能迅速确定某一指定非0元素的位置。稀疏矩阵常用的压缩存储方式：三元组表十字链表1、三元组表若将表示稀疏矩阵的非0元素的三元组按行优先顺序排列，则可得到一个其结点均是三元组的线性表，这个顺序存储结构就称为三元组表。显然，要唯一确定一个稀疏矩阵，还必须存储该矩阵的行数和列数，它们与非0元素本身一起构成三元表。#definesmax16typedefintdatatypetyprdefstruct{inti,j;datatypev;}node;typedefstruct{intm,n,t;/*行、列、非

6、零元素个数*/nodedata[smax];}spmatrix;以矩阵的转置为例说明这种压缩存储结构是如何实现矩阵运算的。一个m×n矩阵A，它的转置矩阵是一个n×m矩阵B，且A[i][j]=B[j][i]。矩阵的转置不能仅交换矩阵元素下标的次序，还要重新安排矩阵元素的位置。spmatrix*TRANSMAT(spmatrix*a){intano,bno,col;spmatrix*b;b=malloc(sizeof(spmatrix));b->m=a->n;b->n=a->m;b->t=a->t;if(b->t>0){bno=0;for(col=0;coln;col++)for(

7、ano=0;anot;ano++)if(a->data[ano].j==col){b->data[bno].i=a->data[ano].j;b->data[bno].j=a->data[ano].i;b->data[bno].v=a->data[ano].v;}}returnb;}2、十字链表当非0元素的位置和个数经常发生变化时，三元组表就不适合做稀疏矩阵的存储结构。因此，采用链接形式的存储结构更为恰当。十字链表是稀疏矩阵链接形式存储