1、串和数组-PPT精选文档v 5.5 数组数组v 5.6 矩阵的压缩存储矩阵的压缩存储 数组数组的定义的定义:数组是线性表的一种扩充，一维数组即为线性表，二维数组定义为“其数组元素为一维数组”的线性表:),.,()1(1)1(1)1(0)2(mAAAA),.,(1,1,0,)1(niiiiaaaAi=0,1,m-1其中 也可视为一个由m行n列构成的一个阵列Amn=1,01,0,0 ,.,niaaa1,11,10,1 ,.,naaa1,11,10,1,.,nmmmaaa 多维数组可以此类推数组数组的基本操作：的基本操作：InitArray(&A,n,bound1,.,boundn)DestroyA
2、rray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果：若维数 n 和各维长度合法，则构造相应的数组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为元素变量，随后是
3、n 个下标值。操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。数组数组的的顺序表示顺序表示和实现和实现 类型特点类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是 一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：称为基地址基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推广到一般
4、情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n 在高级语言的层次，计算地址的任务已由编译系统解决，可以通过多维的数组下标直接存取元素，例如A2,5,8。假设 m 行 n 列的矩阵含 t 个非零元素，则称为稀疏因子稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。nmt稀疏矩阵的压缩存储稀疏矩阵的压缩存储何谓稀疏矩阵？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1)零值元素占了很大空间
5、;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i,j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。1)特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则例如:三角矩阵 对角矩阵2)随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、一、三元组顺序表三元组顺序表二二、十字链表十字链表 const MAXSIZE=1000;typedef struct int i,
6、j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型一、三元组顺序表一、三元组顺序表typedef struct Triple dataMAXSIZE+1;/data0未用 int mu,nu,tu;TSMatrix;/稀疏矩阵类型00070015000001800000240001400003000000000009120原稀疏矩阵原稀疏矩阵三元组表示的稀疏矩阵三元组表示的稀疏矩阵1 2 121 3 93 1 -33 6 141234504 3 245 2 186 1 156 4 1767 三元组表示的稀疏矩阵节三元组表示的稀疏矩阵节省了空间，便于
7、实现矩阵运省了空间，便于实现矩阵运算吗？算吗？通常三元组在序列中的排列通常三元组在序列中的排列顺序以行序为主序。顺序以行序为主序。如何求转置矩阵？如何求转置矩阵？028003600070500140005280000007143600用常规的原二维数组时的转置算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;简单调换行值和列值将破坏有序性不可行不可行用三元组实现同样功能的办法1 2 121 3 93 1 -33 6 141234504 3 245 2 186 1 156 4
8、17672 1 123 1 91 3 -36 3 141234503 4 242 5 181 6 154 6 1767用“三元组”表示时如何实现？1 2 121 3 93 1 -33 6 141234504 3 245 2 186 1 156 4 17671 3 -31 6 15 2 1 122 5 1812345067 首先应该确定每一行的第一个非零元在三元组中的位置。用数组numcol表示原矩阵M中第col列元素的数目，刚好是转置矩阵T中第col行元素的数目。用rposcol表示转置矩阵T中第col行元素的第一个元素在三元组T中的位置。则 1.2 ,1 1 1 ,1 muMcolcolnu
9、mcolrposcolcolrposconst 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;/createRposvoid FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.
10、nu=M.mu;T.tu=M.tu;if(T.tu)createRpos(M);for(p=1;p=M.tu;+p)col=M.datap.j;q=rposcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+rposcol;/准备该行准备该行col的一下个元素位置的一下个元素位置 /for /if/FastTransposeSMatrix 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+col)for(t=1;t=
11、M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p)二二、十字链表十字链表M.cheadM.rhead3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 1 2 十字链表十字链表的类型描述的类型描述:typedef struct OLNode int i,j;/该非零元的行和列下标 ElemType e;struct OLNode*rnext,*cnext;/该非零元所在行表和列表的后继链域 OLNode;*OLink;typedef struct OLink*rhead,*chead;/行和列链表头指针向量基址 /在建立
12、存储结构时分配.int mu,nu,tu;/稀疏矩阵的行数、列数和非零元个数 CrossList;void CrossSearch(CrossList&M,ElemType x)/在十字链表中查找所有值为x的元素并输出（i,j）i=0;/从第1行开始扫描 p=*(M.rhead+i);/p指向第1行的第一个十字链表结点 while(iM.mu)/对所有的行 if(!p)i+;p=*(M.rhead+i);/到达行尾则换下一行 /p指向下一行 的第一个非零元结点 else if(p.e=x)cout(i,j)rnext;/继续查找本行的下一个结点/else /while/CrossSearch
13、1.熟悉熟悉串的七种基本操作基本操作的定义，并能利用这些基本操作来实现串的其它各种串的其它各种操作操作的方法。2.熟练掌握熟练掌握在串的定长顺序存储结构定长顺序存储结构上实现串的各种操作的方法。3.了解了解串的堆存储结构堆存储结构以及在其上实现串操作的基本方法。4.了解了解串操作的应用方法和特点。5.了解了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址地址计算方法计算方法。6.了解了解对特殊矩阵进行压缩存储时的下下标变换公式标变换公式。7.熟悉熟悉稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀三元组表示稀疏矩阵疏矩阵时进行矩阵运算采用的处理方法。第13次上机作业(1)实现算法5.8，并输出原三元组及矩阵换置后的三元组*(2)从三元组矩阵输出正常矩阵，输出时补充必须的0。
