《数据结构(c语言版)课件(西安交大)第五章.ppt》由会员分享，可在线阅读，更多相关《数据结构(c语言版)课件(西安交大)第五章.ppt（34页珍藏版）》请在三一办公上搜索。
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)*l,n维数组,将其中的每一个元素映射到一维数组的某一个位置，各维元素个数为 m1,m2,m3,mn，下标为 i1,i2,i3,in 的数组元素的存储地址：,三、特殊矩阵的压缩存储,1、对称矩
3、阵 在一个n阶方阵A中，若元素满足下述性质：,则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只需要存储矩阵的上三角或下三角矩阵，这样可以节约大约一半的空间。,在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：,a00a10 a11a20 a21 a22.an-1,0.an-1,n-1,因此，我们可以将这些元素存放在一个向量san(n+1)/2中。为了便于访问方阵A中的元素，必须在aij和sak之间建立一个对应关系。若aij在上三角矩阵中，则有：,若aij在下三角矩阵中，则有：,令I=max(i,j)，J=min(i,j)，则k和i、j的对应关系可统一为：,2、三角矩阵,以主对角线
4、划分，三角矩阵有上三角和下三角两种：,在多数情况下，三角矩阵的常数c为0。,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量san(n+1)/2+1中，其中c存放到向量的最后一个分量上。上三角矩阵中，aij和sak之间的对应关系为：,下三角矩阵中，aij和sak之间的对应关系为：,3、对角矩阵,对角矩阵中，所有非0元素都集中在以主对角线为中心的带状区域中。,对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非0元素和向量下标的对应关系。,四、稀疏矩阵的压缩存储,如果一个矩阵的非0元素个数远远小于矩阵元 素
5、的总数，则称这个矩阵为稀疏矩阵。一般来说，稀疏矩阵非0元素的分布是无规律 的。因此，在存储非0元素的同时，还要存储 适当的辅助信息，才能迅速确定某一指定非0 元素的位置。稀疏矩阵常用的压缩存储方式：三元组表十字链表,1、三元组表,若将表示稀疏矩阵的非0元素的三元组按行优先顺序排列，则可得到一个其结点均是三元组的线性表，这个顺序存储结构就称为三元组表。显然，要唯一确定一个稀疏矩阵，还必须存储该矩阵的行数和列数，它们与非0元素本身一起构成三元表。,#define smax 16typedef int datatypetyprdef struct int i,j;datatype v;node;ty
6、pedef struct int m,n,t;/*行、列、非零元素个数*/node datasmax;spmatrix;,以矩阵的转置为例说明这种压缩存储结构是如何实现矩阵运算的。一个mn矩阵A，它的转置矩阵是一个nm矩阵B，且Aij=Bji。矩阵的转置不能仅交换矩阵元素下标的次序，还要重新安排矩阵元素的位置。,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;if(b-t0)bno=0;for(col=0;coln;col+)for
7、(ano=0;anot;ano+)if(a-dataano.j=col)b-databno.i=a-dataano.j;b-databno.j=a-dataano.i;b-databno.v=a-dataano.v;return b;,2、十字链表,当非0元素的位置和个数经常发生变化时，三元组表就不适合做稀疏矩阵的存储结构。因此，采用链接形式的存储结构更为恰当。十字链表是稀疏矩阵链接形式存储结构的一种（当然还有其它形式）。在该方法中每一个非0元素用一个结点表示，结点中除了表示非0元素的行、列和值的三元组外，还增加了两个链域：行指针域，用来指向本行中下一个非0元素；列指针域，用来指向本列中下一个
8、非0元素。,在每一个行链表和每一个列链表增加一个和表结点相同的表头结点，表头结点中的行、列域置为0，并且将所有的行、列链表和他们的头结点一起链成一个循环链表。,实际实现时，两组头结点可以合用，即第i行链表和第i列链表共享一个表头结点。因为表头结点中值域v无用，所以可以将它作为指针域，用来指向下一个表头结点的指针。,稀疏矩阵十字链表表示法的结点说明typedef struct lnode int i,j;struct lnode*cptr,rptr;union struct lnode*next;datatype v;uval;link;,五、广义链表,广义表的概念 定义：广义表是n(n=0)个
9、元素a1,a2,an的有限 序列，其中ai或者是原子或者是一个广义表。表的深度：表展开后所含括号的层数。递归表：允许递归的表。再入表：允许结点共享的表。纯表：与树对应的表。线性表：,通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。这里，我们仅讨论广义表的两个特殊的基本运算：取表头和取表尾。,把与树对应的广义表称为纯表（表中成分不能共享和递归），把允许结点共享的表称为再入表，把允许递归的表称为递归表。递归表 再入表 纯表 线性表,任何一个非空广义表的表头是表中的第一个元素，它可以是原子，也可以是子表；而其表尾必定是子表。L=
10、(a,b)B=(A,y)head(L)=a tail(L)=(b)head(B)=A tail(B)=(y)head(tail(L)=b tail(tail(L)=(),广义表的存储,广义表链式存储的结点说明单链表示typedef struct node int atom;struct node*link;union struct node*slink;datatype data;element;lists;,广义表链式存储的结点说明双链表示typedef struct node datatype data;struct node*link1,*link2;lists;,工 资,应发工资,扣除,实发工资,基本工资,工龄工资,奖金,房租水电,国库卷,其它,扣除,房水电,实发工资,国库卷,其它,工龄工资,奖金,基本工资,head L,工资收入,link CREATELINKMAT()link*p,*q,*l,*cpsmax;int i,j,m,n,t,s;datatype v;scanf(“%d%d%d”,cps=x=1;,
