数据结构PPT教学课件-第4章串.ppt

4.1 串的基本概念 4.2 串的存储结构 4.3 串的运算 4.4 文本编辑,第4章 串,返回主目录,第4章 串,4.1 串的基本概念 串(string)是由n(n0)个字符组成的有限序列, 一般记为 s= c1 c2 cn 其中: s是串名; 串中的ci(0in)是单个字符, 它可以是字母、 数字或其它字符; 用单引号括起来的字符序列是串的值, 但单引号并不属于串, 它只是用来标识一个串的起始和终止; n为串的长度, 即串中所包含的字符个数。若n=0, 则称s为空串(null string), 空串是不含有任何字符的串。通常, 用两个相邻的单引号来表示空串。一个串也可以只包含空白符, 称为空白串。 一个串的子串是这个串中任一连续的子序列。下面给出一些串的例子：,a=speak english b=string c=speak d=ing e= f=,中a、 b、 c、 d的长度分别是13、 6、 5、 3; c是a的子串; d是b的子串; e是空白串,长度是1; f是空串, 长度是0。 串与其它数据类型一样, 也有两种串可供使用, 一种是串常量, 一种是串变量。 串常量具有固定值, 而串变量的值是可以改变的, 同样, 我们必须用标识符命名串变量。例如在c语言中字符串可以定义为,4.2串的存储结构,4.2.1 串的顺序存储 串的顺序存储就是把串所包含的字符序列, 依次存入连续的存储单元中去。顺序存储又常用紧缩格式、非紧缩格式和以单字节为单位的存储格式来实现。 1) 紧缩格式 有的系统的一个存储单元可以存放多个字符, 如果一个字符占用一个存储单元, 就要浪费许多存储空间。 采用紧缩格式则可以充分利用存储空间。,例: 设某系统的一个存储单元可以存放4个字符, 则对于字串(this is a flag), 连同该串长度14, 共需4个存储单元, 存放的直观表示如表 4.1 所示。 在紧缩存放格式中, 字符串的长度是显式的, 虽然它占用了额外的存储空间, 但总的来说, 存储利用率还是高的。 2) 非紧缩格式 非紧缩格式是以一个存储单元为单位, 也就是一个存储单元中仅放一个字符。 在一个程序中使用的串变量较少, 且各串变量的长度又都较短时，如果希望该程序处理字符的速度尽可能快, 那么选择非紧缩格式比较合适。 在这种存储格式中, 串的长度是隐式的, 串所占用存储单元的个数即为串长。 ,例: 假设一存储单元可以存放4个字符, 同样对于字串(this is a flag), 共需14个存储单元, 其存放的直观表示如表 4.2。 这种存储格式对存储空间的利用率仅为25%, 但如上所述, 该方法在字符加工处理方面会节省时间。 3) 以单字节为单位的存储格式 某些计算机(如一般的微型计算机), 是以字节为存取单位的, 一个字符通常又占用一个字节, 这就自然形成了每个存储单位存放一个字符的分配方式。这种方式一般不需要存放串长的存储单元, 而需要以程序中各变量值所不包含的字符作为结束符。 例: 在c语言中, 字符串存放在一个连续的存储单元中, 一个字符占一个字节。对于字符串string, 在微机中只需 7 个存储单元。直观表示如下: ,在c语言中, 字符串没有紧缩与非紧缩存储格式, 字符串本身是顺序存储的, 并可以定义静态分配和动态分配。若是静态分配, 则字符串在重新定义时, 串长不允许大于原串长。 若是动态分配, 则字符串在重新定义时, 系统将重新分配空间, 串长也就不受原串长的限制。 由此, 我们知道在以字节为单位的计算机上, 顺序分配字符串是比较理想的。而在大于字节为单位的机器上, 则无论以紧缩格式, 还是以非紧缩格式进行顺序分配, 都有不足之处。 我们必须根据具体的计算机和实际需要来正确选择分配格式。,3) 以单字节为单位的存储格式 某些计算机(如一般的微型计算机), 是以字节为存取单位的, 一个字符通常又占用一个字节, 这就自然形成了每个存储单位存放一个字符的分配方式。 这种方式一般不需要存放串长的存储单元, 而需要以程序中各变量值所不包含的字符作为结束符。 例: 在c语言中, 字符串存放在一个连续的存储单元中, 一个字符占一个字节。 对于字符串string, 在微机中只需 7 个存储单元。 直观表示如下: 在c语言中, 字符串没有紧缩与非紧缩存储格式, 字符串本身是顺序存储的, 并可以定义静态分配和动态分配。若是静态分配, 则字符串在重新定义时, 串长不允许大于原串长。,4.2.2 串的链表存储 由于各种串运算与串的存储方式有密切关系, 若要随机存取串中第k个字符, 顺序存储显得比较方便; 若要对串进行插入、 删除等操作, 顺序存储就显得比较繁琐, 而链表存储则显示出明显的优越性。 链表存储是把可利用的存储空间分成一系列大小相同的结点(若干连续的存储单元), 每个结点含有两个域: data域和next域。 data域用来存放字符; next域用来存放指向下一个结点(首地址)的指针。 结点的大小是指data域中可以存放字符的个数, next域的大小则取决于寻址的范围。 例如, 设链表中每个结点只存放一个字符, 则在c语言中可使用如下说明: ,struct list struct list * next; /* 指向下一个结点的指针 */ char data; /* 字符 */ * point; /* point为结构类型的指针, 指向第一结点 */ 根据上述说明, 字符串string的链表存储可用图4.1表示。 如果链表中每个结点可存放4个字符, 则结点结构为: struct list struct list * next; char data4; /* 在一个结点中可放4个字符 */ * point; 根据上述说明, 字符串string的链表存储可用图4.2表示。,4.2.3串变量的存储映象 串变量的存储映象是建立了串名和串值之间对应关系的符号表。表中的项目可根据实际需要来设置, 以能区分出串并能方便地存取串值为原则。 例如, 有3个串: a=speak; b=english; c=string; 假定一个单元仅存放1个字符, 则其串值存储如图4.3所示。,若符号表的每一行包含有串名和串值的始、 尾地址, 如表4.3(a)所示, 则任意一个串的长度等于尾地址与始地址之差加1。 当然也可以直接将串的长度值存放到符号表中, 这时不必设立尾指针, 如表4.3(b)所示, 而串值的存储方式如图4.3所示。 对于链表存储串值的存储方式, 若要建立串变量的符号表, 则只要存入一个链表的表头指针就可以了。 ,4.3 串的运算,4.3.1串的运算简介 串定义后, 还需要经常对其进行运算操作。下面先介绍几种串的基本运算。我们尽可能用c语言中的库函数表示, 若没有库函数, 则用自定义函数说明。 1) 求字符串的长度 strlen(string)求字符串string的长度(不包括0), 函数的值是一个非负整数。 若string是一个空串, 则函数的返回值为0。该函数可用如下形式说明: sizet strlen(string) char * string;,2) 字符串的联接 strcat(string1,string2)将源串string2的值联接到目标串string1的尾部, 返回指向string1的指针。此时string1的值为两个字符串的联接值。 例: string1为fgh , string2为jkl, 经过联接运算后, srting1的值为fghjkl。字符串联接函数可用如下形式说明: char * strcat(string1, string2) char * string1; char * string2;,3) 两个字符串的比较 strcmp(string1,string2)比较两个字符串。 若string1等于string2, 返回值为0; 若string1大于string2, 返回值为正数; 若string1小于string2, 返回值为负数。两个字符串比较函数可用如下形式说明: int strcmp(string1, string2) char * string1; char * string2;,4) 子串的查询 strstr(string1,string2)找出要查询的子串string2在被查询的主串string1中首次出现的位置, 并返回该指针。若在string1中未找到string2, 则返回值为null。子串查询函数可用如下形式说明: char * strstr(string1, string2) char * string1; char * string2;,5) 字符串的拷贝 strcpy(string1,string2)将字符串string2复制到字符串string1中, 并返回指向string1的指针。字符串拷贝函数可用如下形式说明: char * strcpy(string1, string2) char * string1; char * string2; 6) 字符串插入操作 将字符串string2插入到字符串string1的第i个字符开始的位置称为字符串的插入操作。,设string1=program, string2=ex11, 若要求将字符串string2插入到string1的第i个字符的位置, 以取得插入后新的string1=programex11, 其插入算法如下: 算法 4.1 void insert( char *string1, *string2, int i) n=strlen( string1 ); m=strlen( string2 ); if(in1) printf(no! ); else for (j=n; j=i; j) string1j+m=string1j; for (j=i; ji+m; j+) string1j=string2ji; ,7) 字符串的删除 通过字符串的删除操作, 可以在字符串string1中第i个字符后删除由j个字符组成的字符串string2。字符串删除操作中, 先要进行串匹配, string1包含string2则进行删除;否则不进行。串匹配运算将在下面详细介绍。这里假设string1中含string2, 则删除算法如下: 算法4.2 /* (abcdefgh , abcgh ,i=3, j=3 */ /* 初态 结果 */ void delstr( *string1, int i, int j) , if( istrlen(string1) printf(no! ); else k=i; while (string1k+j!= 0) string1k=string1k+j; k+; string1k= 0; ,8) 求子串的运算 在串运算中, 有时需要从一个字符串中取出该串第i个字符开始到第j个字符截止的连续子序列, 其中0ij串长, 这就是取子串操作。 在c语言中, 假设从字符串sor中取出任一子串, 放入字符串des中, 子串在主串sor中的起始位置为start, 结束位置为end。 若串sor和des采用紧缩数组存储，则取子串操作就是将 sorstart1,sorstart,sorstart+1, sorstart+2, , sorend1, 依次赋给des0, des1, des2, , desendstart。 (注意: c语言中数组下标是从0开始的)根据上述思想, 求子串算法如下: ,算法4.3 int getsubstr(char * sor,char * des,int start,int end) if (startstrlen(sor) return(1); /* 返回1为失败 */ point=0; while (sorstart1!= /* 返回0为成功 */ ,4.3.2串的匹配运算 假设t和p是两个给定的串, 在t中寻找与p相同的子串的过程称为模式匹配, 一般t称为正文(text), p称为模式(pattern), t的长度大于p的长度。 如果在t中找到等于p的子串, 则匹配成功, 否则匹配失败。串的匹配运算可以运用c语言中库函数strstr来完成, (见子串的搜索)。 这里主要介绍串匹配的实现过程。 为了叙述方便, 下面的串都采用紧缩数组存储。字串t为tn, 字串p为pm, 其中 n、 m分别为字串t和p的长度。 实现模式匹配的简单算法: 对于i=1,2, ,nm+1, 依次进行下面的匹配步骤, 最多进行nm+1次。 ,匹配步骤: 用p1, p2 , pm依次与ti, ti+1, , ti+m-1进行比较, 如果p1=ti, p2=ti+1, , pm=ti+m-1, 那么匹配成功, 整个算法结束; 否则, 一定存在着某个整数k, 1kn, 使得pkti+k-1, 一旦出现这种情况, 立即中止后面的比较, 然后执行下一步的匹配步骤。 如果执行n-m+1次匹配步骤之后, 在t中没有找到等于p的子串, 那么匹配失败。 下面给出实现上面所述的简单匹配算法simp(t,p), 在串t中寻找串p。,算法4.4 int simp(char *t, char *p ) n=strlen(t); m=strlen(p); i=0; bool=1; while (i=nm) /* bool=1,返回0,表示串p不存在 */ ,在最坏的情况下, 算法4.4程序运行过程的字符比较总次数为m(nm+1)。 如果用次数来衡量算法的运行时间, 那么算法4.4的运行时间为(m(nm)。若nm, 则运行时间为(mn)。 一般说来, 在执行简单匹配算法的字符比较过程中, 一旦出现pjti(1in,1jm)时, 即 t1t2 ti-j+1 ti-j+2 ti-1 ti p1 p2 pj1 pj (4.1) 那么, 一定要从模式p的第一个字符开始与正文t中第ij+2个字符开始依次进行比较, 即,p1 p2 pj-k+1 pj-k+2 pj-1 pj pj+1 ? p1 p2 pj2 pk pk+1 那么, 由式(4.1)和式(4.2)可得 t1 t2 ti-j-1 ti-k+1 ti-1 ti ti+1 p1 pi-k+1 pj-1 pjpj+1 ? p1 pk1 pkp-k+1,因此, 只要从模式p中的pk开始, 与正文t中的ti开始依次继续进行比较, 就可以减去前面的k1次比较。 如果满足式(4.2)的k有多个, 那么一定要取最大的k, 否则可能会错过匹配成功的机会。 例如, 对于 t: aaaabcde p: aaabc 在执行匹配时出现了如下的状态: t: a a a a b c d e a a a b 因p4t4, 此时满足式(4.2), k可取1,2,3。 如果取k=1, 那么在执行下面的匹配时, 将出现如下的比较序列: ,t: a a a a b c d e p: a a a b c 这时将错过匹配成功的机会。 如果取k=2, 那么在执行下面的匹配时, 将出现如下的比较序列: t: a a a a b c d e p: a a a b c 这时, 也错过匹配成功的机会。如果取k=3, 那么在执行下面的匹配时, 将出现如下的比较序列: ,t: a a a a b c d e p: a a a b c ,比较结果得到一个成功的匹配。在这里, 让pk与ti(也就是让p3与t4)开始依次连续比较, 可以减少比较次数, 提高效率。 由上述分析可知, 在执行匹配比较的过程中, 一旦出现pjti时, 必须找到满足式(4.2)的最大k, 我们称这样的k为pj的失败链接值。我们发现, 寻找模式p中各个字符的失败链接值与正文t无关, 只依赖于模式p本身。 因此, 在进行匹配之前, 我们可以预先为模式p的每个字符找出满足式(4.2)的失败链接值。 在这里, 我们用数组 flink1 m依次存放模式p中m个字符的失败链接值。首先置flink1=0, 然后依次求出flink2, flink3, , flinkm。,现在假设在求flinkj(2jm)之前, flink1, flink2, , flinkj-1已依次被求出, 如果flinkj-1=k, 那么应有 pj-k pj-k+1 pj-2 pj-1 pj ? p1 p2 pk1 pk (4.3) 如果pk=pj-1, 那么式(4.3)中的两个序列增加一个相同的字符, 得, pj-k pj-k+1 pj-2 pj-1 pj p1 p2 pk1 pk 因此我们有下面的规则, 如果pk=pj-1, 则flinkj为flinkj-1+1; 如果pkpj1, 那么k=flinkk, 此时应有 pj-k pj-k pj-2 pj-1 pj p1 pkk+1 pk1 pk ? p1 pk1 pk ,如果pk=pj1, 置flinkj为k+1; 如果pkpj1, 则必须依据pk的失败链接值再试一次。 这个过程一直做下去, 直到找到一个失败链接值k, 使得pk=pj1, 或者k=0。 无论哪种情况, 都置flinkj为k+1。 下面给出寻找模式p中各个字符的失败链接值的函数定义。 首先定义flink为全程变量: int flinkmaxm, 其中maxm在预定义中定义为: define maxm 1000, faillink子函数为: 算法4.5,利用上面的程序过程, 我们可以得到模式p=ababcb中各个字符的失败链接值分别为0, 1, 1, 2, 3, 1。 ,void faillink(char * p) int j=2,k; flink1=0; while (j=m) k=flinkj1; while (k!=0) ,现在让我们分析一下算法4.5的程序运行时间。 因为, 通过内循环一次做一次比较, 通过外循环一次至少做一次比较。 因此, 运行时间可用比较次数来表示。 我们称pk=pj-1为比较成功, 称pkpj-1为比较不成功。 在每次成功的比较之后, j加1, 最多做m1次成功的比较。在每次不成功的比较之后, k减少(因为kflinkk)k的初值为0, k只在外循环中增加, 每次增加1, 共增加m-1次, k不可能小于0, 所以 k在内循环中减少的次数不会大于m-1次。因此, 不成功的比较次数最多为m-1, 连同k0的比较计算在内, 比较次数最多为2(m-1)。 因此, 整个过程的比较次数总共是3(m1), 所以, 整个过程的执行时间为(m)。 在预先计算出flink1 m之后, 我们可以给出执行时间比函数simp(t,p)少的函数 kmpmatch(t, p, flink)的定义。 ,算法4.6 int kmpmatch(int * t,int * p,int *flink) n=strlen(t); m=strlen(p); int i=0, j=0, succ=false; /* false定义如前 */ while (i=n) /* flink定义如前 */,if (j=m) succ=true; return (im+1); elsei=i+1; j=j+1; if (!succ) return（0）; ,4.4 文本编辑,文本编辑是字符串处理的最常见的应用之一。 它广泛地应用于源程序与文稿的编辑加工。一个源程序或一篇文稿都可以看成是有限字符序列, 称之为文本。文本编辑的实质就是利用串的基本运算, 完成对文本的添加、删除和修改等操作。 例如, 有下面