数据结构C语言05.pptx

复习提问1.设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，42.设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。A.5 1 2 3 4 B.4 5 1 3 2 C.4 3 1 2 5 D.3 2 1 5 43.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop4.表达式a*(b+c)-d的后缀表达式是()。Aabcd*+-B.abc+*d-C.abc*+d-D.-+*abcd5.栈和队列都是线性表，只是在插入和删除时受到了一些限制。6.设Q0.N-1为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为_。第1页/共91页复习提问1.下面关于串的的叙述中，哪一个是不正确的？（）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A求子串 B联接 C匹配 D求串长3.若串S=software,其子串的数目是（）。A8 B37 C36 D94.KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）5.设模式串的长度为m,目标串的长度为n，当nm且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）第2页/共91页复习提问1.已知串S=aaab,其Next数组值为（）。A0123 B1123 C1231 D12112.串 ababaaababaa 的next数组为（）。A012345678999 B012121111212 C011234223456 D01230123223453.串是一种数据对象和操作都特殊的线性表。（）4.串的长度是指（）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数5.两个字符串相等的充分必要条件是_。第3页/共91页内容和要求 内容和要求 数组和广义表的概念、存储结构和矩阵的压缩存储方法。要求对数组和广义表有较深刻的了解。掌握数组和广义表的概念，熟悉它们的存储结构及基本应用。重点 数组和广义表的存储特性，稀疏矩阵存储。第4页/共91页多维数组的定义 一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。有一个直接前驱和一个直接后继二维数组二维数组可以看成是向量的推广。有两个直接前驱和两个直接后继第5页/共91页多维数组的定义 三维数组最多可有三个直接前驱和三个直接后继多维数组把三维以上的数组称为多维数组，可有多个直接前驱和多个直接后继是一种非线性结构。第6页/共91页多维数组的定义 在C语言中的描述typedef int datatype;datatype array1N;datatype array2MN;datatype array3XYZ;数组一旦被定义，它的维数和维界就不再改变。因此，数组只有存取元素和修改元素值的操作。第7页/共91页二维数组的逻辑结构二维数组的逻辑结构二维数组的逻辑结构二维数组的逻辑结构 数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：数组和广义表可以看成是线性表在下述含义上的扩展：即线性表中的数据元素本即线性表中的数据元素本即线性表中的数据元素本即线性表中的数据元素本身也是一个数据结构。身也是一个数据结构。身也是一个数据结构。身也是一个数据结构。类似于线性表，一个二维数组的逻辑结构可形式地表示为类似于线性表，一个二维数组的逻辑结构可形式地表示为类似于线性表，一个二维数组的逻辑结构可形式地表示为类似于线性表，一个二维数组的逻辑结构可形式地表示为 2-Array=(D,R)(5-1)2-Array=(D,R)(5-1)2-Array=(D,R)(5-1)2-Array=(D,R)(5-1)其中其中其中其中 D=aD=aD=aD=aij ijij ij|i=c|i=c|i=c|i=c1 11 1,c,c,c,c1 11 1+1,d+1,d+1,d+1,d1 11 1，j=cj=cj=cj=c2 22 2,c,c,c,c2 22 2+1,d+1,d+1,d+1,d2 22 2,a,a,a,aij ijij ij D DD D0 00 0 R=Row,Col /R=Row,Col /R=Row,Col /R=Row,Col /行关系，列关系行关系，列关系行关系，列关系行关系，列关系 Row=aRow=aRow=aRow=|c|c|c|c1 11 1idididid1 11 1,c,c,c,c2 22 2jdjdjdjd2 22 2-1,a-1,a-1,a-1,aij ijij ij,a,a,a,ai ii i,j+1j+1j+1j+1 DDDD Col=a Col=a Col=a Col=|c|c|c|c1 11 1idididid1 11 1-1,c-1,c-1,c-1,c2 22 2jdjdjdjd2 22 2,a,a,a,aij ijij ij,a,a,a,ai+1i+1i+1i+1,j jj j DDDD D D D D0 00 0为某个数据对象，为某个数据对象，为某个数据对象，为某个数据对象，c cc c1 11 1,c cc c2 2 2 2,d dd d1 1 1 1,d dd d2 22 2均为整数。均为整数。均为整数。均为整数。数组的逻辑结构数组的逻辑结构第8页/共91页 若c1=1,d1=m,c2=1,d2=n,则有 D=aij|i=1,2,m,j=1,2,n,D0 R=Row,Col Row=|i=1,2,m,j=1,2,n-1,aij,ai,j+1D Col=|i=1,2,m-1,j=1,2,n,aij,ai+1,j D记作Amn，即A为m行n列的二维数组(起始下标为1)。说明：1)用于二维数组的抽象可称之为矩阵，它是对向量的推广，其元素个数为mn个。数组的逻辑结构数组的逻辑结构数组的逻辑结构数组的逻辑结构第9页/共91页 2)二维数组也可以看作是这样一个线性表：它的每一个数据元素是一个线性表。从而对二维数组可以进行递归定义，即它是数据元素为一维数组的线性表。可把Amn看成是由m个行向量所组成的向量（线性表），也可以看成是n个列向量所组成的向量。Amn=(1,2,p)(p=m或n)若 i为行向量：i=(ai1,ai2,ain)1im若 j为列向量：j=(a1j,a2j,amj)1jn 数组的逻辑结构数组的逻辑结构数组的逻辑结构数组的逻辑结构 3)二维数组中的每个元素都属于两个向量：第i行的行向量和第j列的列向量（对元素aij而言）。4)每个元素aij有两个前趋结点ai-1,j和ai,j-1(2im,2jn)，两个后继结点ai+1,j和ai,j+1(1im-1,1jn-1)，其中a11无前趋，amn无后继。边界上的结点a1j(j=2,n)，amj(j=1,n-1)和ain(i=1,m-1)都只有一个后继结点或者只有一个前趋结点。第10页/共91页n(n2)维数组的逻辑结构维数组的逻辑结构n维数组的逻辑结构的形式定义说明：说明：1）n维数组的元素个数为n1n2 nn=ni.2）n维数组中每个数据元素都属于n个向量（受n个关系制约），除边界上的元素外，均可以有n个前趋和n个后继。数组的逻辑结构数组的逻辑结构数组的逻辑结构数组的逻辑结构第11页/共91页N N维数组的递归定义维数组的递归定义 在这递归定义中，一个在这递归定义中，一个kk维数组是其数据元素为维数组是其数据元素为k-1k-1维数组的线性表，维数组的线性表，ccn-k+1n-k+1和和ddn-k+1n-k+1是是第第kk维下标的一对界偶。维下标的一对界偶。nn维数组是一种较复杂的数据结构，但它可以由简单的数据结构维数组是一种较复杂的数据结构，但它可以由简单的数据结构线性表辗转合成线性表辗转合成而得。而得。数组的逻辑结构数组的逻辑结构第12页/共91页数组的操作数组的操作 一个数组中所有的数据元素都必须属于同一数据类型。一个数组中所有的数据元素都必须属于同一数据类型。对于数组，通常只有两种基本操作：对于数组，通常只有两种基本操作：1 1）给定一组下标，存取相应的数据元素。）给定一组下标，存取相应的数据元素。2 2）给定一组下标，修改相应数据元素中的某一个或）给定一组下标，修改相应数据元素中的某一个或几个数据项的值。几个数据项的值。注注.对于二维数组的抽象即矩阵，可包含取值、赋值对于二维数组的抽象即矩阵，可包含取值、赋值和初始化等操作。编译程序用线性存储器来实现矩阵。和初始化等操作。编译程序用线性存储器来实现矩阵。数组的逻辑结构数组的逻辑结构第13页/共91页 数组的顺序存储结构数组的顺序存储结构两种顺序存储方式行优先顺序将数组元素按行排列在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列在FORTRAN语言中，数组就是按列优先顺序存储的。推广到多维数组的情况：行优先顺序：先排最右下标，从右到左，最后排最左下标列优先顺序：先排最左下标，从左向右，最后排最右下标。第14页/共91页 数组的顺序存储结构：用一组连续的存储单元顺序地存放数组中的诸数组元素。数据元素的存放次序问题：解决存储单元是一维结构，而数组是个多维结构的矛盾。（指多维数组）二维数组元素间次序的排列方法：行优先与列优先序。行优先序：按以行序为主序进行排列，就是把数组元素按行表次序、第i+1行的元素紧跟在第i行元素后面进行存储。（列）（列）（列）（列）（列）（列）（j+1j+1列）列）（jj列）列）数组的顺序存储结构数组的顺序存储结构第15页/共91页 示例:w是一个3*4的整数数组（起始下标从1开始）。设二维数组变量w的诸数据组元素值如下表所示 1 2 3 4 1 0 -1 4 5 2 8 2 0 -3 3 -5 1 2 0以列序为主序的存储方式列优先序以行序为主序的存储方式行优先序0088-5-5-1-1221144002255-3-300第1列第2列第3列第4列00-1-14455882200-3-3-5-5112200第1行第2行第3行C,Pascal,BASIC,PL/1,COBOL等中采用FORTRAN中采用下面讨论的是按行为主序规则存储的情形。数组的顺序存储结构数组的顺序存储结构数组的顺序存储结构数组的顺序存储结构第16页/共91页 同样，对于n维数组也有上述两种不同的顺序存储方式：以左下标为主序的存储方式和以右下标为主序的存储方式。把n维数组的元素按上述方式顺序存放在存储单元中，则每个元素的存储地址可以用一个公式计算出来，这个公式称为“地址公式”。计算存储地址：对于A1.m,1.n，设每个数组元素占L个存储单元。ijaijLOC1,1注.以左下标为主序，指主序变化最慢（实现时为最外层循环）数组的顺序存储结构数组的顺序存储结构数组的顺序存储结构数组的顺序存储结构 不同程序设计语言中数组的起始下标不完全相同，C语言起始下标为0，Pascal为1，某些4GL则允许定义起始下标。第17页/共91页 记a11的存储地址为LOC1,1，它即是二维数组A的起始存储位置，或称基地址（首地址）,L为元素所占的单元数。记aij(1im,1jn)的存储地址为LOCi,j，则LOCi,j=LOC1,1+n*(i-1)+(j-1)*L.以二维数组为例，先讨论简化情况（c1=1，d1=m，c2=1，d2=n），再讨论一般情况（下标分别为c1，d1，c2，d2）.数组的顺序存储结构数组的顺序存储结构一般地，对于Ac1.d1，c2.d2，则有 Loci,j=Locc1,c2+(d2-c2+1)(i-c1)+(j-c2)*L其中LOCc1,c2是二维数组A的基地址。C语言起始下标从0开始，则Loci,j=Loc0,0+(n*i+j)*LijaijLOC1,1第18页/共91页LOCj1,j2,j3=LOCc1,c2,c3+(d2-c2+1)(d3-c3+1)(j1-c1)+(d3-c3+1)(j2-c2)+(j3-c3)*L对于三维数组Ac1.d1，c2.d2，c3.d3，设基地址为LOCc1,c2,c3,则 数组的顺序存储结构数组的顺序存储结构第19页/共91页上已推导出，对于三维数组Ac1.d1，c2.d2，c3.d3，设基地址为LOCc1,c2,c3，则 第20页/共91页计算机如何实现数组元素的随机存取？按上述两种方式顺序存储的序组，只要知道：开始结点的存放地址（即基地址），维数每维的上、下界每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。如何计算数组元素的地址？如何计算数组元素的地址？第21页/共91页一维数组二维数组三维数组内存0ListSize-1a0 a1 a2 an a00 a01 a0n-1 a10 a11 a1n-1.am-1 0 am-1 1 am-1 n-1 a00 a01 a0n-1 a10 a11 a1n-1.am-1 0 am-1 1 am-1 n-1 a0a1an内存a00a0na10a1n如何计算数组元素的地址？第22页/共91页假设数组各维的下界是1,按“行优先顺序”存储,假设每个元素占用d个存储单元。二维数组Amn，aij的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)*n+j-1*d三维数组Amnp，aijk的地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d第23页/共91页更一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是1。aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d 第24页/共91页最基本的原理Ai1in的起始地址=第一个元素的起始地址该元素前面的元素个数单位长度+第25页/共91页程序员试题程序员试题第26页/共91页2006-1对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。(40)A5 B10 C15D25 20032003设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为_(11)_。(11)Aa-118+2i+28j Ba-116+2i+28j Ca-144+2i+28j Da-146+2i+28j第27页/共91页2001二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,则该数组的体积为_(6)_个字节,若已知 X 的最后一个元素的起始字节地址为382,则 X 的首地址(即第一个元素的起始字节地址)为 _(7)_,记为 Xd。若按行存储,则 X1,5 的起始地址是 _(8)_,结束字节地址是 _(9)_。若按列存储,则 X4,8的起始字节地址为_(10)_。(6):A.210 B.240 C.288 D.294(7):A.0 B.6 C.94 D.100(8):A.Xd+24 B.Xd+72 C.Xd+78 D.Xd+144(9):A.Xd+29 B.Xd+77 C.Xd+83 D.Xd+147(10):A.Xd+186 B.Xd+234 C.Xd+270 D.Xd+276第28页/共91页矩阵：在科学研究和工程计算中经常用到的一种数学工具，是研究的主要数学对象之一。矩阵的存储：一般情况下，可用二维数组实现。二维数组，通常也就称为矩阵，是数学上的一种重要数据结构。mn 矩阵压缩存储的概念矩阵压缩存储的概念第29页/共91页 矩阵的压缩存储：对于一些结构比较特殊的矩阵可采用压缩存储方式，即只存储矩阵中的部分元素而不丢失矩阵中任何信息的存储方式。同时，还需保证矩阵的各种运算能有效地进行。在矩阵阶数很高且矩阵中有许多值相同的元素或零元素时，为多个值相同的元素分配一个存储空间，对零元素不分配空间，从而可以大量节省存储空间。特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律。稀疏矩阵：矩阵中非零元素较之零元素要少得多，且非零元素的分布没有一定规律。矩阵压缩存储的概念矩阵压缩存储的概念第30页/共91页 所谓共享存储空间是指aij与 aji 经计算后都指向同一个存储单元 研究对称矩阵、三角矩阵（上三角矩阵、下三角矩阵），对角矩阵（三对角矩阵、带状矩阵）等特殊矩阵的压缩存储问题。（1）对称矩阵的压缩存储 定义 若一个n阶矩阵（方阵）A中的元素满足下述性质aij=aji(1i,jn)则称A为n阶对称矩阵。示例 一个5阶对称矩阵1 5 1 3 75 0 8 0 01 8 9 2 63 0 2 5 17 0 6 1 3 对称矩阵中的元素关于主对角线对称，故仅需存储矩阵中上三角或下三角中的元素，让每一对对称的元素共享一个存储空间。特殊矩阵的压缩存储特殊矩阵的压缩存储第31页/共91页1 5 1 3 75 0 8 0 01 8 9 2 63 0 2 5 17 0 6 1 3a11a21 a22a31 a32 a33a41 a42 a43 a44a51 a52 a53 a54 a55对称矩阵以行为主序存储下三角矩阵的元素a11a21 a22a31 a32 a33 an1 an2 an3 ann对称矩阵Ann以行为主序存储下三角矩阵的元素 对于Ann所对应的下三角矩阵中（见右下图），第i(1in)行恰有i个元素，故元素总数为aij 特殊矩阵的压缩存储特殊矩阵的压缩存储第32页/共91页 设以一维数组sa（1:n(n+1)/2）作为n阶对称矩阵A的存储结构，令sak aij，则有如下之一一对应关系 特殊矩阵的压缩存储特殊矩阵的压缩存储a11a21 a22a31 a32 a33 an1 an2 an3 amnaij第33页/共91页由上述推导可得由上述推导可得 特殊矩阵的压缩存储特殊矩阵的压缩存储第34页/共91页1234523456345674567856789对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1，则称A为对称矩阵。特征：元素关于主对角线对称压缩存储的办法：只存矩阵中上三角或下三角中的元素。所需空间：第35页/共91页（2）三角矩阵的压缩存储以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。a11 a12 a1n c a22 a2n c c anna11 c ca21 a22 c an1 an2 ann上三角矩阵下三角矩阵在多数情况下，三角矩阵的常数c为零。故可将三角矩阵表示为a11 a12 a1n a22 a2n anna11 a21 a22 an1 an2 ann上三角矩阵(c=0)下三角矩阵(c=0)n阶三角矩阵A的压缩存储sa1.n(n+1)/2+1，其中n(n+1)/2个存储空间存放上（或下）三角矩阵的元素，1个存储空间存放常数C。特殊矩阵的压缩存储特殊矩阵的压缩存储第36页/共91页a11 a12 a1n 第1行n个元素 a22 a2n 第2行n-1个元素 第i-1行n-i+2个元素 aii aij ain 第i行n-i+1个元素 ann 第n行1个元素 下三角矩阵的压缩存储和对称矩阵类似，sak和aij的对应关系是上三角矩阵的压缩存储（2）三角矩阵的压缩存储）三角矩阵的压缩存储 特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储第37页/共91页（3）对角矩阵的压缩存储 对角矩阵亦称带状矩阵，其特点是：所有的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和分别位于主对角线上、下的若干条相同数目的次对角线上的元素外，其它的所有元素均为零。示例 三对角矩阵五对角矩阵 亦可用一个一维数组存储其带状区域内的元素，具体存储方法可以以行的顺序依次存放各个元素（与三角矩阵的存储方式类似），也可以顺次存放各条对角线上的元素。8 34 5 7 6 6 2 2 7 1 4 76 2 87 2 3 73 6 4 2 5 7 7 8 5 0 4 1 4 7 9 8 0 5 0 3 1 7 4 5 5 7 2 特殊矩阵的压缩存储特殊矩阵的压缩存储第38页/共91页 三对角矩阵的压缩存储 An*nsa(1:3n-2)若令aij=sak，则易得 k=3(i-1)-1+j-(i-1)+1 =2(i-1)+j.(-1 i-j 1)这就是三对角矩阵压缩存储的地址公式。a11 a12a21 a22 a23 a32 a33 a34 an-1,n-2 an-1,n-1 an-1,n an,n-1 ann ijaij问：如何用k表示i,j?（课外作业5.8(选作)）（2）三角矩阵的压缩存储）三角矩阵的压缩存储 特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵的压缩存储第39页/共91页 定义 设矩阵Amn（不必为方阵）中有S个非零元素，若S(mn)，则称A为稀疏矩阵(Sparse matrix).示例0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0 0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 -70 0 0 0 0 0 0 0 14 0 0 00 0 0 0 0 0稀疏矩阵M67和N76下面研究稀疏矩阵的逻辑结构、存储结构以及有关稀疏矩阵的运算M=N=稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表第40页/共91页 稀疏矩阵的压缩存储方法主要有两种稀疏矩阵的压缩存储方法主要有两种三元组表与十字链表三元组表与十字链表。三元组表的一般表示方法三元组表的一般表示方法 稀疏矩阵的非零元稀疏矩阵的非零元 三元组三元组(i,j,a(i,j,aijij)若将表示稀疏矩阵的非零元素的三元组按行优先（或若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，称作三元组表均是三元组的线性表，称作三元组表(List of 3-tuples).(List of 3-tuples).因因此，三元组表是稀疏矩阵的此，三元组表是稀疏矩阵的一种顺序存储结构一种顺序存储结构。以下假定。以下假定三元组是按以行序为主序的顺序排列的。三元组是按以行序为主序的顺序排列的。采用三元组表，以一个一维数组来存储矩阵中的非零采用三元组表，以一个一维数组来存储矩阵中的非零元素，元素，数组中的每个元素都是一个记录数组中的每个元素都是一个记录，用以存放矩阵中，用以存放矩阵中一个非零元素的行、列位置及其元素值。另外，一个非零元素的行、列位置及其元素值。另外，还必须存还必须存储该矩阵的行、列数以及非零元素的个数储该矩阵的行、列数以及非零元素的个数。稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表第41页/共91页 稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表表示三元组的线性表的顺序存储结构#define maxnum 1000 /大于非零元个数的某个常量typedef struct int i,j;elemtp v;tuple3;typedef struct int mu,nu,tu;/mu:行值；nu:列值；tu:非空元个数 tuple3 datamaxnum+1;TSMatrix;TSMatrix a,b;注.data域中表示非零元的三元组是以行序为主序顺序排列的，这样做有利于进行矩阵运算，data0未用。第42页/共91页0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0 示例 分别写出矩阵M和N的三元组表：M=0 0 -3 0 0 150 0 -3 0 0 1512 0 0 0 18 0 12 0 0 0 18 0 9 0 0 24 0 0 9 0 0 24 0 0 0 0 0 0 0 -70 0 0 0 0 -70 0 14 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 N=M67N76i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 4 14稀疏矩阵M和它的三元组表a.data稀疏矩阵N和它的三元组表b.data第43页/共91页1)求稀疏矩阵的转置矩阵0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0 M=0 0 -3 0 0 150 0 -3 0 0 1512 0 0 0 18 012 0 0 0 18 09 0 0 24 0 09 0 0 24 0 00 0 0 0 0 -70 0 0 0 0 -70 0 0 0 0 0 0 0 0 0 0 0 0 0 14 0 0 00 0 14 0 0 00 0 0 0 0 00 0 0 0 0 0 N=一般矩阵的转置算法trans_mat(elemtp Mmn,elemtp&Nnm)for(int col=1;col=n;n+)for(int row=1;row=m;row+)Ncolrow=Mrowcol;/trans_mat 时间复杂度O(mn).定义定义 一个mn矩阵M的转置矩阵N是一个nm矩阵，且有 N(i,j)=M(j,i)(1in,1jm)示例 如下之矩阵M，N互为转置矩阵 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表第44页/共91页i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 4 14以M的行为主序依次排列 a.data关健一步：求稀疏矩阵M的转置矩阵N的问题转化为：如何由a得到b?用三元组表实现稀疏矩阵的转置矩阵的算法思想1）将矩阵的行、列值互相交换，即从m行n列改为n行m列；2）将三元组中每个i和j互相交换；3）重排三元组之间的次序。i j v2 1 123 1 91 3 -36 3 143 4 242 5 181 6 154 6 -7将三元组中的每个i和j互相调换 重排三元组之间的次序，以N的 行（M的列）为主序依次排列 b.data 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表由于M中i从小到大排列，故转换i,j后，对N中的i而言，同样的i其j值必是从小到大顺序排列第45页/共91页转置算法一：按照a的列序进行转置 对于原矩阵的每一列，逐个取其元素(i,j,v)，交换i,j的位置，并按顺序放置在转置矩阵三元组的当前位置上。trans_sparmat(TSMatrix&b,TSMatrix a)/*a和b分别表示M和N，N是M的转置矩阵，现由a求b.程序中p和q分别指示a.data和 b.data中三元组的序号；col指示M的列号（即N的行号）*/b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;/M*N N*M if(b.tu0)q=1;for(col=1;col=a.nu;col+)/扫描a.data a.nu遍 for(p=1;p=a.tu;p+)if(a.datap.j=col)/若三元组中列号为所寻列，则置换之 b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;q+;/trans_sparmat 算 法 5.1 时间复杂度O(nutu).适用于tumunu的情况。由a直接导出b.稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表第46页/共91页转置算法二：按照a的行序进行转置（快速转置）分析 按三元组a的顺序进行转置，将转置后的三元组置入b中恰当的位置。若能预知a中每一列（即b中每一行）的第一个非零元素在b中应有的位置，则对a依次作转置时，便可直接放到b中恰当的位置。为确定这些位置，转置前应做 1）求a中每一列非零元素个数，记为numcol；2）求a中每一列第一个非零元素在b中的位置，记为cpotcol。显然，有 cpot1=1 cpotcol=cpotcol-1+numcol-1 2cola.nu (5-7)col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9矩阵M的向量cpot的值 稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表第47页/共91页快速转置算法fast_transpos(TSMatrix&b,TSMatrix a)/将三元组表a表示的稀疏矩阵转置为三元组表b表示的稀疏矩阵 b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu 0)for(col=1;col=a.nu;col+)numcol=0;/初始化 for(t=1;t=a.tu;t+)numa.datat.j+;/求M中每一列非零元个数 cpot1=1;for(col=2;col=a.nu;col+)cpotcol=cpotcol-1+numcol-1;/求第col列中第一个非零元在b.data中的序号 for(p=1;p=a.tu;p+)/转置 col=a.datap.j;q=cpotcol;b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;cpotcol+;/fast_transpos 算 法 5.2 时间复杂度O(nu+tu).稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表第48页/共91页2)稀疏矩阵的矩阵相乘对于一般矩阵，设Mm1n1，Nm2n2 则当n1=m2时有 Qm1n2=Mm1n1Nm2n2经典算法 for(i=1;i=m1;i+)for(j=1;j=n2;j+)Qij=0;for(k=1;k=n1;k+)Qij+=Mik*Nkj;时间复杂度O(m1n1n2).对于用三元组表作存储结构的稀疏矩阵，如 3 0 0 5 0 2 0 6 0 -1 -2 0 1 0 3 -8 2 0 -1 0 -2 4 2 0 0 0M=N=Q=i j vi j v1 1 31 1 31 4 51 4 52 2 -12 2 -12 3 -22 3 -23 1 23 1 23 3 -13 3 -1a.dataa.datai j vi j v1 2 21 2 22 1 12 1 13 1 -23 1 -23 2 43 2 4b.datab.datai j vi j v1 2 1 2 6 62 1 32 1 32 2 -82 2 -83 1 23 1 2c.datac.data 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表第49页/共91页 稀疏矩阵的矩阵相乘算法 分析 分几点考虑 1）如何求c的值？为求c.data中的一个值，需要在a.data和b.data中找到相应的各对元素（即a.data中的j(列)值和b.data中的i(行)值相等和各对元素）相乘。为了得到非零的乘积，只要对a.dataa.tu中的每个元素(i,k,Mi,k)(1im1,1kn1),找到b.data 中所有相应的元素(k,j,Nk,j)(1km2,1jn2)相乘即可。根据上述思想，可用手算方法实现由a.data和b.data求得c.data：i j v1 1 31 4 52 2 -12 3 -23 1 23 3 -1a.datai j v1 2 22 1 13 1 -23 2 4b.datai j v1 2 62 1 32 2 -83 1 2c.data 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表第50页/共91页 为了便于在b.data中寻找N中第k行的所有非零元，特附设两个向量num1.m2和rpos1.m2，num1.m2存放N中各行非零元素的个数，而rpos满足如下公式 rpos1=1 rposrow=rposrow-1+numrow-1 (2rowm2)(5-10)矩阵N的向量num和rpos的值如下表所示 row 1 2 3 4 numrow 1 1 2 0 rposrow 1 2 3 5 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表三元组表三元组表rposrow表示N的第row行中第一个非零元在b.data中的序号第51页/共91页2）稀疏矩阵相乘的基本操作 对于a中每个元素a.datap(p=1,2,a.tu)，找到b中所有满足条件a.datap.j=b.dataq.i的元素b.dataq，求得a.datap.v和b.dataq.v的乘积，作为累计和Qi,j中的一部分。为了便于操作，应对每个元素设一累计和的数组变量ctemp(1:c.nu)，其初值均为0.3）情况讨论 (a)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵；(b)即使每个分量值Mi,kNk,j不为零，其累加值Qi,j也可能为零。对于乘积矩阵中的零元，应不放入结果三元组表中；(c)Q中元素的行（列）号和M(N)中元素的行(列)号一致，而a中元素是以M的行号为主序，故可对Q进行逐行处理。当求得ctemp的一个非零累计和值时，连同行号、列号一起压缩存储到c.data中去.稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表第52页/共91页 求稀疏矩阵乘积的算法multiply_sparmat(TSMatrix a,TSMatrix b,TSMatrix&c)/*a和b分别表示稀疏矩阵M和N，本算法求c表示M和N的乘积Q，假设a.nu=b.mu*/if(a.tu*b.tu0)for(row=1;row=b.mu;row+)numrow=0;/初始化 for(t=1;t=b.tu;t+)numb.datat.i+;/求N中每一行中非零元个数 rpos1=1;for(row=2;row=b.mu+1;row+)rposrow=rposrow-1+numrow-1;/rposrow指示N中第brow行第一个非零元在b中的序号 c.mu=a.mu；/c的行数=a的行数 c.nu=b.nu；/c的列数=b的列数 c.tu=0；/c的非零元个数=0(初始化)稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组表三元组表第53页/共91页 p=1；/三元组表a的指示器初始值 do crow=a.datap.i;/crow指示当前处理的行号 for(k=1;k=c.nu;k+)Ctempk=0；/crow行至多有c.nu个非零元，它们将由累加求和而得，其初始值均设为0