第5章串和数组2.ppt
1,第5章 串和数组2,串也可以看作是一种线性表，只是其操作通常是按成组的元素来进行的。数组可以认为是线性表在维数上的一种拓展。串和数组依然属于线性结构，但在存储结构的实现方面较线性表为复杂。 值得注意的是，串和数组是在高级语言层面已经实现的数据类型，在数据结构中再讨论它们是为了深入理解实现它们的基础技术。 讲授本章课程大约需4课时。,2,5.5 数组 5.6 矩阵的压缩存储,3,5.5 数 组,4,数组的定义:,数组是线性表的一种扩充，一维数组即为线性表，二维数组定义为“其数组元素为一维数组”的线性表:,i = 0,1,m-1,其中,5,也可视为一个由m行n列构成的一个阵列,Am×n =,多维数组可以此类推,6,数组的基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Value(A, &e, index1, ., indexn),Assign(&A, e, index1, ., indexn),7,InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。,8,DestroyArray(&A) 操作结果：销毁数组A。,9,Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。,10,Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。,11,数组的顺序表示和实现,类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。,12,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2×ij)×,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,13,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。,其中 cn = L，ci-1 = bi ×ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,在高级语言的层次，计算地址的任务已由编译系统解决，可以通过多维的数组下标直接存取元素，例如A2, 5, 8。,14,5.6 矩阵的压缩存储,15,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储,何谓稀疏矩阵？,16,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。,17,1) 尽可能少存或不存零值元素；,解决问题的原则:,2) 尽可能减少没有实际意义的运算；,3) 操作方便。 即： 能尽可能快地找到与下标值(i, j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。,18,1) 特殊矩阵 非零元在矩阵中的分布有一定规则例如: 三角矩阵 对角矩阵,2) 随机稀疏矩阵 非零元在矩阵中随机出现,有两类稀疏矩阵：,19,随机稀疏矩阵的压缩存储方法:,一、 三元组顺序表,二、 十字链表,20,const MAXSIZE =1000; typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,一、三元组顺序表,typedef struct Triple dataMAXSIZE + 1; /data0未用 int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,21,原稀疏矩阵,三元组表示的稀疏矩阵,22,三元组表示的稀疏矩阵节省了空间，便于实现矩阵运算吗？,通常三元组在序列中的排列顺序以行序为主序。,23,如何求转置矩阵？,24,用常规的原二维数组时的转置算法,其时间复杂度为: O(mu×nu),for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,25,简单调换行值和列值将破坏有序性,不可行,用三元组实现同样功能的办法,26,用“三元组”表示时如何实现？,27,首先应该确定每一行的第一个非零元在三元组中的位置。 用数组numcol表示原矩阵M中第col列元素的数目，刚好是转置矩阵T中第col行元素的数目。用rposcol表示转置矩阵T中第col行元素的第一个元素在三元组T中的位置。则,28,const MAXMN=100; /矩阵行或列的最大值 int num100,rpos100; void createRpos(TSMatrix M) for(col=1;colM.nu;+col) numcol=0; for(t=1;t=M.tu;+t) +numM.datat.j; /求M中每一列所含非零元素个数 rpos1=1; for(col=2;col=M.nu;+col) rposcol=rposcol-1+numcol-1; /createRpos,29,void FastTransposeSMatrix(TSMatrix M, TSMatrix /准备该行col的一下个元素位置 /for / if / FastTransposeSMatrix,30,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) ,31,二、 十字链表,M.chead,M.rhead,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,32,十字链表的类型描述: typedef struct OLNode int i, j; / 该非零元的行和列下标 ElemType e; struct OLNode *rnext, *cnext; / 该非零元所在行表和列表的后继链域 OLNode; *OLink;,33,typedef struct OLink *rhead, *chead; / 行和列链表头指针向量基址 / 在建立存储结构时分配. int mu, nu, tu; / 稀疏矩阵的行数、列数和非零元个数 CrossList;,34,void CrossSearch(CrossList / 继续查找本行的下一个结点 / else /while / CrossSearch,35,本章学习要点,36,1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。 2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其上实现串操作的基本方法。 4. 了解串操作的应用方法和特点。,37,5. 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 6. 了解对特殊矩阵进行压缩存储时的下标变换公式。 7. 熟悉稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,38,第13次上机作业 (1)实现算法5.8，并输出原三元组及矩阵换置后的三元组 *(2)从三元组矩阵输出正常矩阵，输出时补充必须的0。,
