第四、五章 串 数组和广义表.ppt

1、第四章 串,4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配,4.1 串类型的定义,串（也称字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s =“ a1 a2 a3 ai an ” ( n0 )。,字母、数字或其他字符,必须有！,不属于串！,作用：避免与变量名或数的常量混淆。,例：x = “123” x = 123,test =“test”,基本概念,空串：不含任何字符的串，串长度 = 0，用符号 表示。,空格串：仅由一个或多个空格组成的串。,子串：由串中任意个连续的字符组成的子序列。,例：S=“JINAN” S1=“”、S2=“NA”、S=“JINAN”,主串

2、：包含子串的串。,位置：字符在序列中的序号。 子串在主串中的位置是子串的首字符在主串中的位置。, 子串。,S4=“JAN”, 非子串（非串 S 中的连续字符所组成）。,在 S 中的位置：3,在 S 中的位置：1,串相等的条件：当两个串的长度相等且各个对应位置的字符都 相等时才相等。,例：S=“JINAN” S1=“JI NAN” S S1,空串是任意串的子串，任意串是其自身的子串。,串的逻辑结构：和线性表极为相似。,串的基本操作：和线性表有很大差别。,区别：串的数据对象约定是字符集。,在线性表的基本操作中，大多以“单个元素” 作为操作对象；,在串的基本操作中，通常以“串的整体”作为 操作对象。

3、例如：在串中查找某个子串、求 取一个子串、在串的某个位置上插入一个子 串以及删除一个子串等。,串的抽象数据类型的定义,ADT String 数据对象：D ai |aiCharacterSet, i = 1, 2, ., n, n0 数据关系：R1 | ai-1, ai D, i = 2, ., n 基本操作：StrAssign ( m = StrLength(T); / 求串长 i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / 找到和

4、T 相等的子串 / while / if return 0; / S 中不存在满足条件的子串 / Index,4.2 串的表示和实现,因为串是特殊的线性表，故其存储结构与线性表的存储结构 类似，只不过组成串的结点是单个字符。,4.2.1 定长顺序存储表示,定长顺序存储表示，也称为静态存储分配的顺序串。它是 用一组地址连续的存储单元来依次存放串中的字符序列。,“定长”、“静态”的意思可简单地理解为一个确定的存储空 间，它的长度是不变的。,可直接使用定长的字符数组来定义一个串，数组的上界 预先给出：,#define maxstrlen 255 / 可在 255 以内定义最大串长。 typedef

5、unsignde char sstringmaxstrlen+1; / 0 号单元存放串的长度。,串的实际长度可在这个预定义长度的范围内随意设定， 超过预定义长度的串值则被舍去，称之为“截断”。,例：对于串 ch = “This is a dog.” 用上述一方法表示为：,串长的两种表示方法：,一：是在串的存贮区首地址显式地记录串的长度。,二：是隐式的，在串之后加入一个串的结束标志。,PASCAL 语言中的串类型就采用这种方法。,如 C 中使用 “0”，“0” 不计入串长。,同样对于串 ch = “This is a dog.” 用上述二方法表示为：,定长顺序存储表示时串的操作的实现,1、串联

6、接 Concat( int length; HString;,/若非空串，按串长分配空间；否则ch=NULL,/串长度,4.2 串的表示和实现,例：用堆分配存储方式实现串插入操作(参见教材P75),Status StrInsert(HString /pos不合法则警告,if (T.length)/只要串T不空，就需要重新分配S空间，以便插入T return OK;,if(!(S.ch=(char)*realloc(S.ch,(S.length+T.length)*sizeof(char) exit(OVERFLOW); /若开不了新空间，则退出,for(i=S.length-1;i=pos-1

7、;-i) / 为插入T而腾出pos之后的位置，即从S的pos位置起全部字符均后移 S.chi+T.length=S.chi;,S.chpos-1.pos+T.length-2=T.ch0.T.length-1; /插入T S.length+=T.length; /刷新S串长度,4.2 串的表示和实现,4.2.3 串的块链存储表示,例：S=ABCDEFGHI, 链表结点大小为1, 链表结点大小为4,法1存储密度为1/2；法2存储密度为9/15=3/5,4.2 串的表示和实现,4.3 串的模式匹配算法,模式匹配 ：子串定位运算。 (串匹配) 就是在主串中找出子串出现的位置。,用函数 Index(S

8、, T, pos) 实现。,在串匹配中，将主串 S 称为目标(串)，子串 T 称为模式(串)。,如果在主串 S 中能够找到子串 T， 则称匹配成功，返回第一 个和子串 T 中第一个字符相等的字符在主串 S 中的序号；否则， 称匹配失败，返回 0。,当用模式依次从目标的头部往后移，移到的位置就 叫位移，每次移动后要看模式里的字符和目标中相应的 字符是否相等，若都相等，这次位移就叫有效位移（其 实就是从这个位置开始的匹配成功），否则叫无效位移。,模式匹配是各种处理系统中最重要的操作之一，也 是一个比较复杂的串操作。模式匹配的算法不同，效率 将有很大差别。同一算法应用不同，效率亦有很大差别。,朴素的

9、模式匹配算法,算法思想： 从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较之， 若相同，则继续比较后续字符；否则从主串 S 的下一个字符起再 重新和模式 T 的字符比较之。,例：S = JINANSHI，T = NAN。,匹配,匹配,3,第一趟匹配,第二趟匹配,第三趟匹配,第四趟匹配,第五趟匹配,第六趟匹配,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b

10、c a b c a c b a b,a b c a c,a b c a c,a b c a c,a b c a c,a b c a c,a b c a c,4.3.1 （BF）匹配算法,算法思想： 用子串T中的字符依次与主串S中的字符比较： 若不匹配，将T右移一个字符，从头开始与S中字符依次比较； 如此反复执行，直到匹配成功或者一直将T移到无法与S继续比较为止，则匹配失败。,子串T,主串S,当采用定长顺序存储结构时，实现此操作的算法如下： int Index(SString S, SString T, int pos) / 返回子串 T 在主串 S 中第 pos 个字符之后的位置。 / 若不存

11、在，则函数值为 0。 / 其中，T 非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i -T0; else return 0; / Index,KMP算法的时间复杂度可以达到O(m+n),二、KMP 算法,模式匹配：子串T(模式p）在主串S中的定位操作(mn)。 S= s1 s2 sn 主串 P= p1 p2 pm 模式 (同子串T) 从主串S中查找与模式P完全相同子串的过程。,第一趟匹配,第二趟匹配,第三趟匹配,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a

12、b c a b c a c b a b,a b c a c,a b c a c,(a)b c a c,KMP算法匹配情况：,pjsi 下一步p中哪个字符和si比较？(i不回溯） Pk 1kj,设主串S=“ababcabcacbab”, 模式串P=“abcac”。,k值仅依赖于P本身的前个j-1字符，于目标S无关；,当 si pj 时， 已经得到的结果：si-j+1.si-1 = p1.pj-1 若已知 p1.pk-1 = pj-k+1.pj-1 则有 si-k+1.si-1 = p1.pk-1,定义：模式串的next函数,int Index_KMP(SString S, SString T,

13、int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1 = 0；,假设：nextj = k；又 Tj = Tk,则： nextj+1 = k+1,若： Tj Tk 则需往前回朔，检查 Tj = T ？,void get_next(SString T,int next) / 求模式串T的next函数值并存入数组nex

14、t。算法4.7 int i=1,j=0; next1=0; / T的第1个字符与主串“失配”时，主串的下一字符与T的第1个字符比较 while(i1时，next2=1 if(j=0|Ti=Tj) / 初态或两字符相等 +i; / 各+1继续向后比较 +j; nexti=j; / 主串和T在第i个字符不匹配时，前j-1个字符是匹配的，只须与第j个字符比较 else / 两字符不等 j=nextj; / j减小到前面字符相等之处 ,还有一种特殊情况需要考虑： 例如： S = aaabaaabaaabaaabaaab T = aaaab,nextvalj=00004,nextj=01234,void

15、 get_nextval(SString / get_nextval,1. 熟悉串的七种基本操作的定义，并能利用这些基本操作 来实现串的其它各种操作的方法。,2. 熟练掌握串的定长顺序存储结构及其实现串的各种操作 的基本方法。,3. 了解串的堆存储结构及其实现串的各种操作的基本方法。,教学要求,4. 掌握朴素的模式匹配算法。,1、试问执行以下函数会产生怎样的输出结果？ void demonstrate() StrAssign(s, THIS IS A BOOK); Replace(s,SubString(s,3,7), ESE ARE); StrAssign(t,Concat(s, S); S

16、trAssign(u, XYXYXYXYXYXY); StrAssign(v,SubString(u,6,3); StrAssign(w, W); Printf(“t=%s,v=%s,u=%s”, t, v, Replace(u,v,w); ,练习, 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构, 元素的值并非原子类型，可以再分解，表中元素也是 一个线性表 所有数据元素仍属于同一数据类型。,数组和广义表是线性表的扩充：,第5章 数组和广义表,注：, 数组中的元素都具有统一的类型; 数组元素的下标一般都具有固定的上界和下

17、界，即数组一旦 被定义，它的维数和维界就不再发生改变； 数组的基本操作简单：初始化、销毁、存取元素和修改元素值, 一维数组的特点：1个下标，ai是ai+1的直接前驱 二维数组的特点：2个下标，每个元素aij受两个关系 （行关系和列关系）的约束；,数组： 由一组名字相同、下标不同的变量构成,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,5.1 数组的定义,存储单元是一维结构，而数组是个多维结构, 则用一组连续存储单元存放数组的数据元素就有 个次序约定问题。,二维数组可有两种存储方式： 1）以行序为主序 ； 2）以列序为主序。,a00 a01 a0,n-1 a10 a11 a1

18、,n-1 am-1,0 am-1,1 am-1,n-1,5.2 数组的顺序表示和实现,（以行序为主序为例） 假设每个数据元素占L个存储单元，则二维数组Ab1b2中任一元素aij的存储位置可由下式确定：,LOC（i，j）=LOC（0，0）+（b2 * i + j）* L,对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。,数组基址,总列数，即第2维长度,aij本行前面的元素个数,每个元素所占的存储单元,若是N维数组Ab1b2bn，其中任一元素的地址:,LOC(j1,j2,jn)= LOC(0,0,0)+(j1b2bn+ j2b3

19、bn+ jn-1bn+ jn ) L,5.2 数组的顺序表示和实现,注意：,2.以“列优先顺序”存储 二维数组中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1)m+(j-1)l (5-1) i=1,2, ,n j=1,2, ,m,1.以“行优先顺序”存储： 由此可知，二维数组中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1)n +(j-1)l (5-1) i=1,2, ,m j=1,2, ,n,例1：一个二维数组A，行下标的范围是1到6，列下标的范围 是0到7，每个数组元素用相邻的6个字节存储，存储器 按字节编址。那么，这个数组的体积是 个字节。,例

20、2：设数组a160,170的基地址为2048，每个元素2个存 储单元，若以列序为主序顺序存储，则元素a32,58 的 存储地址为 。,288,8950,例3：已知二维数组M的每个元素占4个存储单元，数组行下标 i的范围从0到4，列下标j的范围从0到5，数组M按行存 储时，元素M35的地址和M按列存储时，元素_ 的地址相同。 A. M24 B. M34 C. M35 D. M44,5.2 数组的顺序表示和实现,压缩存储： 为多个值相同的元素分配一个存储空间；对零元素不 分配空间。,具备压缩条件的矩阵包括： 对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。,稀疏矩阵： 矩阵中非零元素的个数较少（一般小于5

21、%）。,5.3 矩阵的压缩存储,矩阵下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0。,一、三角矩阵,（1）上三角矩阵,矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0。,（2）下三角矩阵,5.3.1 特殊矩阵,（3）下三角矩阵的压缩存储,矩阵中共有n(n+1)/2个非零元素，共需要n(n+1)/2+1个存储空间。若将其存放到一维向量空间S0.Sn(n+1)/2中，则SK与aij的对应关系为：,当ij时，aij是非零元素， aij前面有i行，共有1+2+3+i=i(i+1)/2个非零元素，aij前面有j列，共j个非零元素，即k=i(i+1)/2+

22、j；当ij时，aij是零元素，存放在最后一个存储单元Sn(n+1)/2中。,5.3.1 特殊矩阵,（4）上三角矩阵的压缩存储,矩阵中共有n(n+1)/2个非零元素，共需要n(n+1)/2+1个存储空间。若将其存放到一维向量空间S0.Sn(n+1)/2中，则SK与aij的对应关系为：,当i j时,aij是非零元素, aij前面有i行,共有n+(n-1)+(n-2)+(n-(i-1) =i(n+n-(i-1)/2=i*n-i(i-1)/2个元素，aij前面有j列，共j-i个非零元素， 即k=i*n-i(i-1)/2+j-i；当ij时，aij是零元素，存放在最后一个存储单元Sn(n+1)/2中。,5

23、.3.1 特殊矩阵,二、对称矩阵,在一个n阶方阵A中，若元素满足下述性质： aij=aji （0i，jn-1） 则称A为对称矩阵。,1、对称矩阵的定义,5.3.1 特殊矩阵,2、对称矩阵的压缩存储,对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。在下三角矩阵中，元素的总个数为1+2+n=n(n+1)/2。 按行优先顺序存储主对角线(包括对角线)以下的元素,5.3.1 特殊矩阵,2、对称矩阵的压缩存储,元素aij的存放位置 aij元素前有i-1行(从第1行到第i-1行)，一共有： 1+2+(i-1)=(i

24、-1)(1+(i-1)2= i(i-1)/2个元素; 在第i行上，aij之前恰有j-1个元素(即ai1，ai2，ai,j-1)，因此有：aij之前共有i(i-1)2+(j-1)个元素 aij和sk之间的对应关系：,5.3.1 特殊矩阵,三、对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。,一个77的三对角矩阵,5.3.1 特殊矩阵,对角矩阵的压缩存储 我们仅讨论三对角矩阵的压缩存储。 在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。

25、 故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，,sk与aij的对应关系为：,5.3.1 特殊矩阵,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,解决的办法： 只存储非零元素。在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。 因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15),

26、(6,4,-7) 和矩阵维数（6,7）唯一确定,稀疏矩阵的存储：,如何表示非零元素的位置信息,每个元素用一个三元组（i，j，v）来表示。,1. 三元组表：,1 2 12,1 3 9,3 1 -3,3 5 14,4 3 24,5 2 18,6 1 15,6 4 -7,注意：为更可靠描述，通常再加一个“总体”信息：即总行数、总列数、非零元素总个数。,5.3.2 稀疏矩阵,例：试还原出下列三元组所表示的稀疏矩阵。,64,0 2 0 0,12 0 0 0,3 0 0 0,0 0 0 4,0 0 6 0,16 0 0 0,5.3.2 稀疏矩阵,1、顺序存储结构 （1）三元组表 对矩阵中的每个非零元素用三

27、个域分别表示其所在的行号、列号和元素值。 #define MAXSIZE 12500 typedef struct int i, j; / 该非零元的行下标和列下标 ElemType e; /非零元素的值 Triple; / 三元组类型 typedef struct Triple dataMAXSIZE + 1; / 非零元三元组表，data0未用 int mu, nu, tu; / 矩阵的行数、列数和非零元个数 TSMatrix; / 稀疏矩阵类型,稀疏矩阵的压缩存储方法,2. 十字链表：,i j v,down right,指向同一列中下一非零元素,指向同一行中下一非零元素,0 0 5 0

28、1 0 0 2 0 0 0,5.3.2 稀疏矩阵,typedef struct OLNode / 结点结构定义int i, j; / 该非零元的行和列下标ElemType e;struct OLNode *right, *down; / 该非零元所在行表和列表的后继链域 QNode,*OLink;typedef struct / 链表结构定义OLink *rhead, *chead; / 行和列链表头指针向量基址由CreateSMatrix分配int mu,nu,tu;/ 稀疏矩阵的行数、列数和非零元个数 CrossList;,十字链表,1、定义,广义表是线性表的推广，也称为列表（lists）

29、。 记为：LS=（a1，a2，an）,广义表名,n是表长,在广义表中约定：, ai可以是单个元素，也可以是广义表，分别称为原子和子表; 用小写字母表示元素，用大写字母表示列表名称； 当LS非空时，称第一个元素为表头(Head)，其余元素组成的表 (a2，an)为表尾(Tail)。 任何一个非空表，表头可能是原子，也可能是列表，但 表尾一定是列表。,5.4 广义表的定义,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),5.4 广义表的定义,广义表是一个多层次的线性结构,

30、例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,5.4 广义表的定义,广义表 LS = ( 1, 2, , n )的结构特点:,1) 广义表中的数据元素有相对次序；,2) 广义表的长度定义为最外层包含元素个数；,3) 广义表的深度定义为所含括弧的重数； 例如，A=(b,c)的深度为1， B=(A,d)的深度为2， C=(f,B,h)的深度为3。 注意：“原子”的深度为 0 “空表”的深度为 1,4) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。,如：E=(a,E),5.4 广义表的定义,例：求下

31、列广义表的长度。,(1) A=( ) (2) B=(e) (3) C=(a，(b，c，d) (4) D=（A ，B，C） (5) E=(a，E),n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表,D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表,E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表,n=3，3个元素都是子表,n=2，a 为原子，E为子表,表中元素个数,5.4 广义表的定义,例如: D = ( E, F ) = (a, (b, c)，F ),Head( D ) = E Tail( D ) = ( F ),H

32、ead( E ) = a Tail( E ) = ( ( b, c) ),Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( ),Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ),Head( ( c ) ) = c Tail( ( c ) ) = ( ),5.4 广义表的定义,5) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为表头 GetHead(LS) = 1 和表尾 GetTail(LS) = ( 2, , n)两部分。,广义表两种特殊的基本操作：,GetHead 【 L 】取表头（可能是原

33、子或列表） GetTail 【 L 】 取表尾（一定是列表）,（1）GetTail【 (b，k，p，h ) 】 = （2）GetHead 【(a,b)，(c,d) 】= （3）GetTail 【(a,b)，(c,d) 】= （4）GetTail 【GetHead 【(a,b)，(c,d) 】 】= （5）GetTail 【(e) 】= （6）GetHead 【( ) 】= （7）GetTail 【( ) 】=,(k,p,h),(a,b),(c,d),(b),( ),( ),( ),5.4 广义表的定义,利用GetHead和GetTail操作，把原子banana分别从下列广义表中分离出来。 (1

34、) L1=(apple,pear,banana,orange) (2) L2=(apple,pear),(banana,orange) (3) L3=(apple),(pear),(banana),(orange),GetHead【GetTail 【 GetTail 【 L1 】 】 】,GetHead【GetHead 【 GetTail 【 L2 】 】 】,GetHead【GetHead 【 GetTail 【 GetTail 【 GetHead 【 L3 】,练习,由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构，通常用链式结构，每个元素用一个结点表示。,注意：列表的元素可以是原子或列表，所以结点可能有两种形式,1. 原子结点：表示原子，设2个域,标志域,数值域,0,2.