数据结构(C语言版)数组.ppt

《数据结构(C语言版)数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法5.6广义表操作的递归函数5.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn

2、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{

3、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:二维数组的定义:数据对象:D

4、={aij

5、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={

6、0≤i≤b1-2,0≤j≤b2-1}COL={

7、0≤i≤b1-1,0≤j≤b2-2}基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n

8、和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作

9、；2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<

10、in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑cijii=1n假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。5.3稀疏矩阵的压缩存储何谓稀疏矩阵？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列

11、的非零值元。1)特殊矩阵非零元在矩阵中的分布有一定规则例如:三角矩阵对角矩阵2)随机稀疏矩阵非零元在矩阵中随机出现有两类稀疏矩阵：随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、十字链表#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//该非零元的值}Triple;//三元组类型一、三元组顺序表typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//稀疏矩阵类型如何求转置

12、矩阵？用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];用“三元组”表示时如何实现？121415-522-731363428211451-522-713364328首先应该确定每一行的第一个非零元在三元组中的位置。cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];StatusFastTransp

13、oseSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;