《数据结构ds-5》由会员分享，可在线阅读，更多相关《数据结构ds-5（33页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表,普通数组的定义和表示 特殊矩阵的压缩存储 稀疏矩阵的存储和运算 广义表的定义、存储和运算,5. 1 数组的概念,数组：是一种线性数据结构，它是有限个相同类型数据元素的有序集合。 数组的数据元素是值和下标的偶对，对每个有定义的下标，都有一个相关连的值。a11 a12 a1n Amxn a21 a22 a2n am1 am2 amn,基本操作：两种主要的运算：（1）给定一组下标，读取相应的数据元素；GetValue( A, &e, i, j ) （2）修改元素值。ChangeValue(A, e , i , j ) 数组一般不作插入和删除操作。,5. 2 数组的顺序表示和实现
2、,逻辑多维到存储一维的映射，即寻找多维下标和一维下标的关系。 存储方式 行序为主序的存储方式 以列序为主序的存储方式,数组元素的存储位置是其下标的线性函数，存取数组中任一元素的时间相等，所以，数组是随机的存储结构。,计算一维下标 以二维数组Anm为例，计算数组元素Aij 的存储空间下标 w: 以行序为主序的存储方式w=i*m+j 以列序为主序的存储方式w= j*n+i 有三维数组A345,计算数组元素A233的存储空间下标：以行序为主w=2*(4*5)+3*5+3=58,数组的顺序存储表示和实现 typedef structElemType *base;int dim ;int *bounds
3、 ; /数组维界基址int *constants ;/数组映象函数(Page93的式(5-2) Array; 常量Ci 基址，Cn=L=1,Ci -1 =bi*Ci;,5. 3 特殊矩阵的压缩存储,特殊矩阵：数值相同的元素或零元素在矩阵中的分布有一定规律。 例：对称矩阵的压缩存储：以行序为主序存储下三角中的元素，包括对角线上的元素。aij = aji 1= i, j =0) Ak=e; return OK;else return ERROR; ,(5)输出打印对称矩阵的算法:void PrintPro( ET A , int n)for(i=1;i=n;i+)printf(“n”);for(j
4、=1;j=0)个元素的集合。LS=(d1 , d2 , d3 , , dn ) LS为表名 diD0时，称di为单元素(用小写字母表示)； diLists时,称di为子表(用大写字母表示)； n为表的长度，当长度为0时称为空表； n0时,第一个元素d1为表头; n0时,(d2,dn)称为表尾。,. 广义表的长度和深度 长度n:是广义表的元素个数； 深度k:广义表的元素之间除了存在次序关系外，还存在层次关系。广义表中元素的最大层次为表的深度。提示：元素的层次就是包括该元素的括号对的数目。,广义表举例： A= ( ) n= 0 , k =1 B=(e) n=1 , k=1 C=(a,(b,c,d)
5、 n=2 , k =2 D=( A , B , C ) n=3 , k = 3 即D=(),(e),(a,(b,c,d) E=(a , E ) n=2 , k = 定义一个无限表(a,(a,(a,) Gethead(C )=a Gethead(D)=AGettail(C)=(b,c,d) Gettail(B)=( ),5.5 广义表的链式存储结构,结点结构： typedef struct GLNint tag;union AtomType atom;struct GLN *hp; ;struct GLN *tp;*Glist ;广义链表表头表尾结点表示法 (Page 110),tag=1 hp tp,tag=0 atom tp,原子结点,表结点,例：画广义表的存储结构 C=(a,(b,c,(d) ; n=2 ; k=3,C,1 ,0 a,1 ,0 b,0 c,0 d ,广义表：F=(e,C,( ) , 长度：n=3; 深度：k=4,F,1 ,0 e,1,1 ,1 ,
