版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第四章 串、数组和广义表2 学时第四章 串、数组和广义表2 学时教学目标了解串的存储方法,理解串的两种模式匹配算法,重点掌握BF算法。 明确数组和广义表这两种数据结构的特点,掌握数组地址计算方法,了解几种特殊矩阵的压缩存储方法。 掌握广义表的定义、性质及其GetHead和GetTail的操作。教学目标了解串的存储方法,理解串的两种模式匹配算法,重点掌握数据结构串第一节数据结构串第一节补充:C语言中常用的串运算调用标准库函数 #include串比较,strcmp(char s1,char s2) 串复制,strcpy(char to,char from)串连接,strcat(char to,ch
2、ar from) 求串长,strlen(char s) 补充:C语言中常用的串运算调用标准库函数 #include4.1.1 串的基本概念串(String):零个或多个字符组成的有限序列。串名串值串长n空串n=04.1.1 串的基本概念串(String):零个或多个字符4.1.1 串的基本概念a=BEI, b=JING c=BEIJING d=BEI JINGa和b是c和d的子串a在c和d中的位置是1。b在c中的位置是4,在d中的位置为5。 是空格串子串字符位置主串子串位置串相等空格串4.1.1 串的基本概念a=BEI, 4.1.2 串的抽象数据类型ADT String数据对象:D = ai|
3、aiCharacterSet, i=1,2,n, n 0 数据关系:R = | ai-1, aiD, i=2,3,n 基本操作: StrLength (s):求串s的长度。 StrAssign (s1, s2):赋值,将s2的值赋值给串s1。 StrConcat (s1, s2, s):连接,将串s2放在串s1的后面连接成一个新串s。 SubStr (s, i, len):求子串,返回从串s的第i个字符开始取长为 len 的子串。4.1.2 串的抽象数据类型ADT String4.1.2 串的抽象数据类型 StrCmp (s1, s2):串比较,若s1=s2,返回0;若s1s2, 返回1。 S
4、trIndex (s, t):定位,返回子串t在主串s中首次出现的位置。若t不是s的子串,则返回0。 StrInsert (s, i, t):插入,将串t插入到串s中的第i个位置。 StrDelete (s, i, len):删除,在串s中删除从第i个字符开始的连续len个字符。 StrRep (s, t, r):替换,在串s中用串r替换所有与串t相等的子串。ADT String4.1.2 串的抽象数据类型 StrCmp (s1,4.1.2 串的抽象数据类型求子串操作SubStr(s, i, len)示例a b c d e f g ei = 3, len = 3i = 7, len = 4c
5、d ea b c d e f g eg e空串4.1.2 串的抽象数据类型求子串操作SubStr(s, 4.1.3 串与线性表的比较逻辑结构 串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。 基本操作在线性表的基本操作中,大多以“单个元素”作为操作对象;在串的基本操作中,通常以“串的整体”作为操作对象。4.1.3 串与线性表的比较逻辑结构4.1.4 串的存储结构 串是一种特殊的线性表,其存储表示和线性表类似,但又不完全相同。串的存储方式取决于将要对串所进行的操作。串在计算机中有3种表示方式:定长顺序存储表示:将串定义成字符数组,利用串名可以直接访问串值。用这种表示方式,串的存
6、储空间在编译时确定,其大小不能改变。堆分配存储方式:仍然用一组地址连续的存储单元来依次存储串中的字符序列,但串的存储空间是在程序运行时根据串的实际长度动态分配的。 块链存储方式:是一种链式存储结构表示。4.1.4 串的存储结构 串是一种特殊的线性表,其存储表示4.1.4 串的存储结构串的定长顺序存储表示 这种存储结构又称为串的顺序存储结构。是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构,是直接使用定长的字符数组来定义,数组的上界预先确定。特点:串的实际长度可在这个予定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为“截断” 。按这种串的表示方法实现的串的运算时,其
7、基本操作为 “字符序列的复制”。定长顺序存储结构定义为: #define MAX_STRLEN 256 typedef struct char strMAX_STRLEN ; int length; StringType ; 4.1.4 串的存储结构串的定长顺序存储表示4.1.4 串的存储结构方案1:用一个变量来表示串的实际长度。 如何表示串的长度?0 1 2 3 4 5 6 Max-1 a b c d e f g9空 闲0 1 2 3 4 5 6 7 Max-1 a b c d e f g 0空 闲方案2:在串尾存储一个不会在串中出现的特殊字符作为串的终结符,表示串的结尾。 方案3:用数组的
8、0号单元存放串的长度,从1号单元开始存放串值。0 1 2 3 4 5 6 7 Max-1 9 a b c d e f g空 闲4.1.4 串的存储结构方案1:用一个变量来表示串的实际长4.1.4 串的存储结构串的联接算法中需分三种情况处理:Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE,否则FALSE。 if (S10+S20 = MAXSTRLEN) / 未截断T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20;
9、 uncut = TRUE; else if (S10 MAXSTRLEN) / s2截断,s1未截断T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; else / s1截断(仅取S1) T1.MAXSTRLEN = S11.MAXSTRLEN; T0 = MAXSTRLEN uncut = FALSE; return uncut; / Concat4.1.4 串的存储结构串的联接算法中需分三种情况处理:4.1.4 串的存储结构串的堆分配存储表示实现方法:系统提供一个空间足够大
10、且地址连续的存储空间(称为“堆”)供串使用。可使用C语言的动态存储分配函数malloc()和free()来管理。特点:仍然以一组地址连续的存储空间来存储字符串值,但其所需的存储空间是在程序执行过程中动态分配,故是动态的,变长的。串的堆式存储结构的类型定义 typedef struct char *ch; /* 若非空,按长度分配,否则为NULL */ int length; /* 串的长度 */ HString ;4.1.4 串的存储结构串的堆分配存储表示4.1.4 串的存储结构串的链式存储表示 串的链式存储结构和线性表的串的链式存储结构类似,采用单链表来存储串,结点的构成是: data域:存
11、放字符,data域可存放的字符个数称为结点的大小; next域:存放指向下一结点的指针。 若每个结点仅存放一个字符,则结点的指针域就非常多,造成系统空间浪费,为节省存储空间,考虑串结构的特殊性,使每个结点存放若干个字符,这种结构称为块链结构first a b ge f gfirsta b c d4.1.4 串的存储结构串的链式存储表示first a b4.1.4 匹配模式模式匹配:给定主串S=s1s2sn和模式T=t1t2tm,在S中寻找T 的过程称为模式匹配。如果匹配成功,返回T 在S中的位置,如果匹配失败,返回0。基本思想:从主串S的第一个字符开始和模式T 的第一个字符进行比较,若相等,则
12、继续比较两者的后续字符;否则,从主串S的第二个字符开始和模式T 的第一个字符进行比较,重复上述过程,直到T 中的字符全部比较完毕,则说明本趟匹配成功;或S中字符全部比较完,则说明匹配失败。模式匹配问题的特点: 算法的一次执行时间不容忽视:问题规模通常很大,常常需要在大量信息中进行匹配; 算法改进所取得的积累效益不容忽视:模式匹配操作经常被调用,执行频率高。4.1.4 匹配模式模式匹配:给定主串S=s1s2sn4.1.4 匹配模式BP算法 si 主串S模式T tjji 回溯 回溯4.1.4 匹配模式BP算法 4.1.4 匹配模式BP算法 si 主串S模式Tji tj4.1.4 匹配模式BP算法
13、4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bi=3,j=3失败;i“回溯”到2,j回溯到1ij第 1趟a b c a c 4.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 1趟a b c a c i=3,j=3失败;i“回溯”到2,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,
14、模式T=abcaca b a b c a b c a c b a bij第 2趟a b c a c i=2,j=1失败;i“回溯”到3,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 2趟a b c a c i=2,j=1失败;i“回溯”到3,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a b
15、i=7,j=5失败;i“回溯”到4,j回溯到1ij第 3趟a b c a c 4.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 3趟a b c a c i=7,j=5失败;i“回溯”到4,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 4趟a b c a c i=4,j=1失败;i“回溯”到5,
16、j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 4趟a b c a c i=4,j=1失败;i“回溯”到5,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 5趟a b c a c i=5,j=1失败;i“回溯”到6,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1
17、.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 5趟a b c a c i=5,j=1失败;i“回溯”到6,j回溯到14.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法例:主串S=ababcabcacbab,模式T=abcaca b a b c a b c a c b a bij第 6趟a b c a c i=11,j=6,T中全部字符都比较完毕,匹配成功。4.1.4 匹配模式BP算法例:主串S=ababca4.1.4 匹配模式BP算法算法描述在串S和串T中设比较的起始下标i
18、和j;循环直到S或T的所有字符均比较完; 如果Si=Tj,继续比较S和T的下一个字符; 否则,将i和j回溯,准备下一趟比较;如果T中所有字符均比较完,则匹配成功,返回匹配的起始比较下标;否则,匹配失败,返回0;4.1.4 匹配模式BP算法算法描述4.1.4 匹配模式BP算法int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 / 其中,T非空,1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i-T0; else r
19、eturn 0; / Indexijj-1i-1i-j+2i-j+1124.1.4 匹配模式BP算法int Index(SSt4.1.4 匹配模式BP算法时间复杂度: 设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况: 最好情况:不成功的匹配都发生在串T的第一个字符。 例如:S=aaaaaaaaaabcdccccc T=bcd 设匹配成功发生在si处,则在i-1趟不成功的匹配中共比较了i-1次,第i趟成功的匹配共比较了m次,所以总共比较了i-1+m次,所有匹配成功的可能情况共有n-m+1种,则: )(2)()1(11mnOmnmipmnii+=+=+-+-=4.1.4 匹配模
20、式BP算法时间复杂度: )(24.1.4 匹配模式BP算法时间复杂度: 设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况: 最坏情况:不成功的匹配都发生在串T的最后一个字符。 例如:S=aaaaaaaaaaabccccc T=aaab 设匹配成功发生在si处,则在i-1趟不成功的匹中共比较了(i-1)m次,第i趟成功的匹配共比较了m次,所以总共比较了im次,因此(一般地,mn)4.1.4 匹配模式BP算法时间复杂度:4.1.4 匹配模式BP算法为什么BF算法时间性能低? 在每趟匹配不成功时存在大量回溯,没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯? 主串不回溯,模
21、式就需要向右滑动一段距离。如何确定模式的滑动距离?4.1.4 匹配模式BP算法为什么BF算法时间性能低?4.1.4 匹配模式KMP算法i=3,j=3失败; s2=t2;t1t2t1s2a b a b c a b c a c b a bij第 1趟a b c a c a b a b c a b c a c b a b第 2趟a b c a c 4.1.4 匹配模式KMP算法i=3,j=3失败; s4.1.4 匹配模式KMP算法i=3,j=3失败; s2=t2;t1t2t1s2a b a b c a b c a c b a bij第 1趟a b c a c a b a b c a b c a c
22、b a ba b c a c 第 3趟4.1.4 匹配模式KMP算法i=3,j=3失败; s4.1.4 匹配模式KMP算法a b a b c a b c a c b a ba b c a c 第 3趟iji=7,j=5失败s4=t2;t1t2t1s4a b a b c a b c a c b a ba b c a c 第 4趟4.1.4 匹配模式KMP算法a b a 4.1.4 匹配模式KMP算法a b a b c a b c a c b a ba b c a c 第 3趟iji=7,j=5失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 第
23、 5趟4.1.4 匹配模式KMP算法a b a 4.1.4 匹配模式KMP算法a b a b c a b c a c b a ba b c a c 第 3趟iji=7,j=5失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 第 6趟匹配成功4.1.4 匹配模式KMP算法a b a 4.1.4 匹配模式KMP算法结论: i可以不回溯,模式向右滑动到的新比较起点k (使si和tk继续进行匹配),并且k 仅与模式串T有关! 需要讨论两个问题:如何由当前部分匹配结果确定模式向右滑动的新比较起点k?模式应该向右滑多远才是最高效率的?4.1.4 匹配模式
24、KMP算法结论: i可以不回溯,模4.1.4 匹配模式KMP算法请抓住部分匹配时的两个特征:两式联立可得:T1Tk-1Tj-(k-1) Tj-1(2)则Tj-(k-1) Tj-1 Si-(k-1) Si-1iS=a b a b c a b c a c b a bT=a b c a cjk(1)设模式滑动到第k个字符,则T1Tk-1 Si-(k-1) Si-1 S=a b a b c a b c a c b a bT=a b c a cikS=a b a b c a b c a c b a bT=a b c a cikj4.1.4 匹配模式KMP算法请抓住部分匹配时的两个特4.1.4 匹配模式K
25、MP算法T1Tk-1Tj-(k-1) Tj-1说明了什么?(1) k 与 j 具有函数关系,由当前失配位置 j ,可以计算出滑动位置 k(即比较的新起点);(2)滑动位置k 仅与模式串T有关。T1Tk-1Tj-(k-1) Tj-1的物理意义是什么?模式应该向右滑多远才是最高效率的?kmax k |1kj 且T1Tk-1Tj-(k-1) Tj-1 从第1位往右经过k-1位从j-1位往左经过k-1位4.1.4 匹配模式KMP算法T1Tk-1Tj-(4.1.4 匹配模式KMP算法next j 0 当j1时 /不比较max k | 1k1时,nextj的值为:模式串的位置从1到j-1构成的串中所出现的
26、首尾相同的子串的最大长度加1。 当无首尾相同的子串时nextj的值为1。 /nextj=1表示从模式串头部开始进行字符比较4.1.4 匹配模式KMP算法计算nextj的方法4.1.4 匹配模式KMP算法 模 式 串 T: a b a a b c a c 可能失配位 j: 1 2 3 4 5 6 7 8新匹配位k=nextj :01122312j=1时, nextj 0;j=2时, nextj 1;j=3时, t1t2,因此,k=1;j=4时, t1t3,因此,k=2;j=5时, t1t4,因此,k=2;j=6时, t2t5,因此,k=3;j=7时, t3 t6, t1t6,因此,k=1;j=8
27、时, t1t7,因此,k=2课堂练习:已知T=“ababac”求模式T的nextj。4.1.4 匹配模式KMP算法 4.1.4 匹配模式KMP算法KMP算法:在串S和串T中分别设比较的起始下标i和j;循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 如果Si=Tj,继续比较S和T的下一个字符;否则 将j向右滑动到nextj位置,即j=nextj; 如果j=0,则将i和j分别加1,准备下一趟比较;如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回0;4.1.4 匹配模式KMP算法KMP算法:数据结构数组 第二节数据结构数组 第二节本节所讨论的数组与高级语言中的数组区别:高级语
28、言中的数组是顺序结构;而本章的数组既可以是顺序的,也可以是链式结构,用户可根据需要选择。本节所讨论的数组与高级语言中的数组区别:4.2.1 数组的抽象数组类型ADT Array数据对象:ji= 0,1,bi-1 , 1,2, ,n ; D = aj1j2jn | n0称为数组的维数,bi是数组第i维的长度, ji是数组元素第i维的下标,aj1j2jnElemSet 数据关系:R = R1, R2, , Rn Ri=|0jkbk-1 , 1kn且ki,0jibi-2, aj1j2 ji+1jnD 基本操作: (1) InitArray (&A,n,bound1, boundn) /构造数组A (
29、2) DestroyArray (&A) / 销毁数组A (3) Value(A,&e,index1,indexn) /取数组元素值 (4) Assign (A,&e,index1,indexn) /给数组元素赋值 ADT Array4.2.1 数组的抽象数组类型ADT Array4.2.2 一维数组35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(i) = LOC(i-1)+l = a+i*lLOC(i) = LOC(i-1)+l = a+i*l, i 0 a, i = 0 a+i*la4.2.2
30、一维数组35 27 49 18 4.2.3 二维数组4.2.3 二维数组4.2.3 二维数组以行序为主序C, PASCAL4.2.3 二维数组以行序为主序C, PASCAL4.2.3 二维数组以列序为主序FORTRAN4.2.3 二维数组以列序为主序FORTRAN4.2.3 二维数组二维数组的行序优先表示 anm设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k4.2.3 二维数组二维数组的行序优先表示 anm4.2.4 三维数组按页/行/列存放,页优先的顺序存储 4.2.4 三维数组按页/行/列存放,页优先的顺序存储4.2.4 三维数
31、组am1m2 m3 各维元素个数为 m1, m2, m3下标为 i1, i2, i3的数组元素的存储位置: LOC ( i1, i2, i3 ) = a + i1* m2 * m3 + i2* m3 + i3前i1页总元素个数第i1页的前i2行总元素个数第 i2 行前 i3 列元素个数4.2.4 三维数组am1m2 m3 各维元素个4.2.5 n维数组 各维元素个数为 m1, m2, m3, , mn 下标为 i1, i2, i3, , in 的数组元素的存储位置: 4.2.5 n维数组 各维元素个数为 m1, m2, m3练习设有一个二维数组Amn按行优先顺序存储,假设A00存放位置在644
32、(10),A22存放位置在676(10),每个元素占一个空间,问A33(10)存放在什么位置?脚注(10)表示用10进制表示。答:设数组元素Aij存放在起始地址为Loc ( i, j ) 的存储单元中 Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. n = ( 676 - 2 - 644 ) / 2 = 15 Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.练习设有一个二维数组Amn按行优先顺序存储,假设A练习设有二维数组A10,20,其
33、每个元素占两个字节, A00存储地址为100,若按行优先顺序存储,则元素A6,6的存储地址为 ,按列优先顺序存储,元素A6,6的存储地址为 。 答:(6*20+6)*2+100=352 (6*10+6)*2+100=232352232练习设有二维数组A10,20,其每个元素占两个字节, A4.2.6 特殊矩阵的压缩存储1. 什么是压缩存储? 若多个数据元素的值都相同,则只分配一个元素值的存储空间,且零元素不占存储空间。2. 什么样的矩阵能够压缩? 一些特殊矩阵,如:对称矩阵,对角矩阵,三角矩阵,稀疏矩阵等。3. 什么叫稀疏矩阵? 矩阵中非零元素的个数较少(一般小于5%)4.2.6 特殊矩阵的压缩存储1. 什么是压缩存储?数据结构广义表第三节数据结构广义表第三节3.3.1 广义表的基本概念
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024买卖房产合同样本
- 女装批量采购合同
- 医院劳动合同书2024年
- 房屋合同法律效力分析
- 2024年小区物业管理系统合同
- 2024年度XX房地产营销代理合同
- 工程代理加盟居间合同样本
- 旅游客运车辆包车合同
- 2024代理商分销合同探讨与研究
- 2024养猪场荒山租赁合同
- 十字相乘法解一元二次方程练习100题及答案
- 中外合作办学规划方案
- 厂房屋顶光伏分布式发电项目建议书
- 2024年人教版初一道德与法治上册期中考试卷(附答案)
- 2024年第九届“鹏程杯”六年级语文邀请赛试卷(复赛)
- 国开2024年《建筑结构#》形考作业1-4答案
- DL-T1475-2015电力安全工器具配置与存放技术要求
- 漏检分析改善措施
- 新制定《公平竞争审查条例》学习课件
- TD/T 1060-2021 自然资源分等定级通则(正式版)
- 完整加快发展新质生产力课件
评论
0/150
提交评论