第四章数组、串与广义表PPT课件

1、第第四四章章 数组、串与广义表数组、串与广义表东南大学计算机学院东南大学计算机学院 方效林方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件本章主要内容本章主要内容n多维数组的概念与存储多维数组的概念与存储n特殊矩阵特殊矩阵n稀疏矩阵稀疏矩阵n字符串字符串2多维数组的概念与存储多维数组的概念与存储n多维数组是一维数组的扩展多维数组是一维数组的扩展3二维数组二维数组三维数组三维数组多维数组的概念与存储多维数组的概念与存储n多维数组存储在连续的空间中多维数组存储在连续的空间中n存储地址计算方法（假设数组首地址为存储地址计算方法（假设数组首地址为a ，元，元素大小为素大小为 l）r一

2、维数组：一维数组：am1r二维数组：二维数组：am1m2r三维数组：三维数组：am1m2 m3rn维数组：维数组： am1m2 mn4Loc(i)= a + i*lLoc(i, j)= a + ( i*m2 + j )*lLoc(i, j, k)= a + ( i*m2*m3 + j*m3 + k )*l特殊矩阵特殊矩阵n二维数组也称为矩阵二维数组也称为矩阵n特殊矩阵是指非零元素或零元素的分布有一定特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。规律的矩阵。r对称矩阵对称矩阵r三对角矩阵三对角矩阵n利用特殊矩阵的性质，节省存储空间利用特殊矩阵的性质，节省存储空间511nn12n11n10n

3、12n22212011n12111010n020100aaaaaaaaaaaaaaaaA11nn21nn12nn22nn32nn2322211211100100aa0000aaa00000aaa0000aaa0000aaA对称矩阵对称矩阵三对角矩阵三对角矩阵特殊矩阵特殊矩阵n对称矩阵的压缩存储对称矩阵的压缩存储r设有一个设有一个 n n 的矩阵的矩阵 A。如果在在矩阵中，。如果在在矩阵中，aij = aji，则此矩阵是对称矩阵。，则此矩阵是对称矩阵。r只保存对称矩阵的对角线和对角线以上只保存对称矩阵的对角线和对角线以上 (或以下或以下) 的元素，则称此为对称矩阵的压缩存储的元素，则称此为对称矩

4、阵的压缩存储r压缩存储方式：用一维数组存储压缩存储方式：用一维数组存储611nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaaA特殊矩阵特殊矩阵n对称矩阵的压缩存储对称矩阵的压缩存储r下三角阵存储：下三角阵存储： 用一维数组用一维数组B存储对称矩阵存储对称矩阵A中中对对角线及对角线角线及对角线以下以下的元素的元素矩阵矩阵A中元素中元素aij对应一维数组对应一维数组B中的下标为中的下标为711nn12n11n10n222120111000aaaaaaaaaaA(i+1)*i/2 + j, i jLoc(i, j) =(j+1)*j/2 +

5、 i, i jLoc(i, j) =a00 a01 a02 a0n-1 a11 a12 a1n-1 a22 an-1n-1 0 1 2 n-1 n n+1 2n-2 2n-1 n(n+1)/2-1B稀疏矩阵稀疏矩阵n设矩阵设矩阵 A 中有中有 s 个非零元素，若个非零元素，若 s 远远小于远远小于矩阵元素的总数（即矩阵元素的总数（即s mn），则称），则称 A 为为稀疏矩阵。稀疏矩阵。r稀疏因子：稀疏因子： = s/(mn)r一般一般 0.05可称为稀疏可称为稀疏9稀疏矩阵表示稀疏矩阵表示 5200800000190090017000000006000000110030000200A76稀疏矩

6、阵稀疏矩阵n用三元组用三元组(i, j, aij)表示稀疏矩阵一个元素表示稀疏矩阵一个元素aij10三元组表示三元组表示稀疏矩阵表示稀疏矩阵表示 5200800000190090017000000006000000110030000200A76稀疏矩阵稀疏矩阵n三元组表示的稀疏矩阵转置的直观方法三元组表示的稀疏矩阵转置的直观方法r按列从小到大排序按列从小到大排序r行列交换行列交换11稀疏矩阵稀疏矩阵n三元组表示的稀疏矩阵转置的扫描方法三元组表示的稀疏矩阵转置的扫描方法r假设假设A有有Cols列，则扫描列，则扫描Cols趟趟r第第k趟扫描在表中找列号为趟扫描在表中找列号为k的三元组，取出，交的三

7、元组，取出，交换行列号换行列号12扫描列号为扫描列号为0的三元组的三元组扫描列号为扫描列号为1的三元组的三元组扫描列号为扫描列号为2的三元组的三元组扫描列号为扫描列号为3的三元组的三元组扫描列号为扫描列号为4的三元组的三元组扫描列号为扫描列号为5的三元组的三元组扫描列号为扫描列号为6的三元组的三元组6 5 -525 3 -174 4 193 5 -83 2 -63 1 -112 0 21 4 90 1 3稀疏矩阵稀疏矩阵n三元组表示的稀疏矩阵转置的快速方法三元组表示的稀疏矩阵转置的快速方法r统计各列非零数统计各列非零数rowSize(扫描三元组表扫描三元组表)r计算各列在转置三元组中的索引位置

8、计算各列在转置三元组中的索引位置rowStartr扫描三元组表，放入相应索引位置，相应索引加扫描三元组表，放入相应索引位置，相应索引加1 5200800000190090017000000006000000110030000200A76rowSize111311 1rowStart012367 86 5 -525 3 -174 4 193 5 -83 2 -63 1 -112 0 21 4 90 1 345321678 9字符串字符串n字符串字符串rn(n0)个字符的一个有限序列，简称为串个字符的一个有限序列，简称为串r记为记为S = “a0 a1 a2 an-1”rn是串的长度，是串的长度，

9、n等于等于0的串叫空串的串叫空串n子串子串r串中连续若干个字符组成的串串中连续若干个字符组成的串rS=“maintenance”，P=“ten”是是S的子串，的子串，P在在S中的位置为中的位置为4（从第（从第0个字符开始）个字符开始）14字符串字符串n字符串的一些基本操作字符串的一些基本操作r复制复制strcpyr连接连接strcatr比较比较strcmpr长度长度strlen15typedef struct char chmaxSize; int length; SeqString;字符串字符串n字符串的穷举模式匹配算法字符串的穷举模式匹配算法r匹配失败时，目标串匹配失败时，目标串T回溯，模

10、式串回溯，模式串P从头开始从头开始16PTp2p3pm-3pm-2pm-1p1p0t2t3tm-3tm-2tm-1t1t0tn-1p2p3pm-3pm-2pm-1p1p0p2p3pm-3pm-2pm-1p1p0PP第第1趟趟第第2趟趟第第3趟趟时间复杂度时间复杂度O(m*n)字符串字符串n字符串的穷举模式匹配算法字符串的穷举模式匹配算法r匹配失败时，目标串匹配失败时，目标串T回溯，模式串回溯，模式串P从头开始从头开始17PTabaababbaPTabaababbaPTabaababbaPTabaababba第第1趟趟第第2趟趟第第3趟趟第第4趟趟字符串字符串n字符串的改进模式匹配算法字符串的改

11、进模式匹配算法18PTPcdabcdbaecdabcdbae例子：例子：P中重复出现中重复出现abcd，但是，但是e和和x不匹配时，不匹配时，可直接向右滑动可直接向右滑动4个字符开始匹配，可少匹配个字符开始匹配，可少匹配4趟趟cdabcdbax字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法19PTp2p3pj-3pj-2pj-1pjp1p0ts+2ts+3ts+j-3ts+j-2ts+j-1ts+jts+1ts=p2p3pj-3pj-2p1p0p2p3pj-3p1p0设设Ts, s+j-1 = P0, j-1，但但Ts, s+j P0, jPP若若P0, j-2 P1, j-1

12、，可少匹配，可少匹配1趟趟若又若又P0, j-3 P2, j-1，可少匹配，可少匹配2趟趟p2pj-4p1p0P若又若又P0, j-4 P3, j-1，可少匹配，可少匹配3趟趟类推直到前缀类推直到前缀P0, k+1 后缀后缀Pj-k-2, j-1但是前缀但是前缀P0, k =后缀后缀 Pj-k-1, j-1 时，时，可少匹配可少匹配 j-k-1 趟，趟，相当于相当于P直接向右滑动直接向右滑动 j-k-1 个字符个字符字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符20-1，当，当 j = 0k

13、+1，当，当 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况Pcdabcdbae下标下标j234567108next(j)0001230-14next(j)直观含义：直观含义：0, j-1 中前缀和后缀相等的最大长度中前缀和后缀相等的最大长度next(j)直观作用：直观作用：可滑过可滑过j-next(j)位不用匹配位不用匹配字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符21-1，当，当 j = 0k+1，当，当

14、 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况PTPcdabcdbaecdabcdbaecbnext(j)=-1表示匹配失败时，表示匹配失败时，T的指针加的指针加1，P的指针指向的指针指向p0next(j)=k+1表示匹配失败时，表示匹配失败时，P的指针指向的指针指向pk+1，next(j)=0表示匹配失败时，表示匹配失败时，P的指针指向的指针指向p0此例中模式串此例中模式串P的的next0=-1，T指针加指针加1，P指向指向p0，即，即T中中c与与P中中p0=a进行比较进行比较字符串字符串n字符串的改进模式匹

15、配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符22-1，当，当 j = 0k+1，当，当 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况PTPcdabcdbaecdabcdbaecdabcdbaxnext(j)=-1表示匹配失败时，表示匹配失败时，T的指针加的指针加1，P的指针指向的指针指向p0next(j)=k+1表示匹配失败时，表示匹配失败时，P的指针指向的指针指向pk+1，next(j)=0表示匹配失败时，表示匹配失败时，P的指针指向的

16、指针指向p0此例中模式串此例中模式串P的的next8=4，T中中x直接与直接与P中中p4=a比较比较字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符23-1，当，当 j = 0k+1，当，当 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况PTPcdabcdbaecdabcdbaecxbanext(j)=-1表示匹配失败时，表示匹配失败时，T的指针加的指针加1，P的指针指向的指针指向p0next(j)=k+1表示匹

17、配失败时，表示匹配失败时，P的指针指向的指针指向pk+1，next(j)=0表示匹配失败时，表示匹配失败时，P的指针指向的指针指向p0此例中模式串此例中模式串P的的next3=0，T中中x直接与直接与P中中p0=a比较比较字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符24-1，当，当 j = 0k+1，当，当 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况可按定义直接计算可按定义直接计算next，下面介绍一种快

18、速的计算，下面介绍一种快速的计算next的方法的方法假设已知假设已知next(j)=x，现在计算，现在计算next(j+1)若若px=pj，则，则next(j+1) = x+1 = next(j)+1否则，设否则，设next(x)=h，(此时有此时有p0,h-1=px-h,x-1=pj-h,j-1) 若若ph=pj，则，则next(j+1) = h+1 否则，令否则，令next(h)=t, (此时有此时有p0,t-1=ph-t,h-1=pj-t,j-1) 继续判断是否继续判断是否pt=pj，直到找到或者到，直到找到或者到next(0) = -1 j=0;k=-1;next0=-1;while(jpLength) if(k=-1 | chj=chk) j+;k+;nextj=k; else k = nextk;字符串字符串n字符串的改进模式匹配算法字符串的改进模式匹配算法r对模式串对模式串P进行预处理，计算可以滑过多少个字符进行预处理，计算可以滑过多少个字符25-1，当，当 j = 0k+1，当，当 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大数的最大数next( j ) =0，其他情况，其他情况可按定义直接计算可按定义直接计算next，下面介绍一种快速的计算，下面介绍一种快速的计算next的方法的方法j=0;k=-1;next0=