数据结构语言第四章字符串正规版资料.ppt

数据结构(sh j ji u)语言第四章字符串第一页，共28页。空串：零个字符的串称为空串空串：零个字符的串称为空串空串：零个字符的串称为空串空串：零个字符的串称为空串 记作记作记作记作“子串：串中任意个连续子串：串中任意个连续子串：串中任意个连续子串：串中任意个连续(linx)(linx)的字符组成的子序列的字符组成的子序列的字符组成的子序列的字符组成的子序列主串：包含子串的串主串：包含子串的串主串：包含子串的串主串：包含子串的串字符在串中的位置：字符在序列中的序号字符在串中的位置：字符在序列中的序号字符在串中的位置：字符在序列中的序号字符在串中的位置：字符在序列中的序号子串在串中的位置：子串的第一个字符在主串中的位置子串在串中的位置：子串的第一个字符在主串中的位置子串在串中的位置：子串的第一个字符在主串中的位置子串在串中的位置：子串的第一个字符在主串中的位置第二页，共28页。串的根本串的根本(gnbn)运算运算 串插入串插入 串赋值串赋值 求串长求串长 串比较串比较 串联接串联接 求子串求子串 串定位串定位 串删除串删除(shnch)置换置换第三页，共28页。StrAssign(T,chars)初始条件：chars 是字符串常量。操作(cozu)结果：把 chars 赋为 T 的值。第四页，共28页。StrCmp(S,T)初始条件：串初始条件：串 S 和和 T 存在。存在。操作结果操作结果(ji gu)：假设：假设S T，那么，那么返回值返回值 0；假设假设S T，那么返回，那么返回值值 0；假设假设S T，那么返回值，那么返回值 0。例如例如(lr)：StrCmp(“data,“state)0第五页，共28页。串 S 存在(cnzi)，1iStrLen(S)且 0jStrLen(S)-i+1。进行(jnxng)串值的复制。数据结构(sh j ji u)语言第四章字符串SubStr(student,5,0)=一、串的定长顺序存储表示(biosh)词汇 在模式匹配中，子串称为模式，串称为目标。假设(jish)S=abcaabcaaabc,T=bca#define CHUNKSIZE 80 /可由用户定义块大小例如 目标 T:“Beijingsub=?SubStr(“commander,4,7)在程序设计语言中，串只是(zhsh)起始位置和子串长度之间存在(cnzi)约束关系Replace(S,T,V)初始条件：串S,T和 V 均已存在，且 T 是非空串。SubStr(commander ,1,9)操作结果：从串S中删除(shnch)第i个字符 起长度为j的子串。StrLen(S)初始条件：串 S 存在。操作结果：返回(fnhu)S 的元素个数，称为串的长度。第六页，共28页。Strcat(S1,S2)初始条件：串 S1 和 S2 存在。操作结果(ji gu)：返回由 S1 和 S2 联接而成的新串。例如例如(lr)：Strcat(man,kind)求得求得 S1=mankind 第七页，共28页。SubStr(S,i,j)初始条件：操作(cozu)结果：返回串 S 的第 i个字符起 长度为 j的子串。串串 S 存在存在(cnzi)，1iStrLen(S)且且 0jStrLen(S)-i+1。第八页，共28页。例如例如(lr)：SubStr(commander ,4,3)子串为子串为“串中的一个串中的一个(y)(y)字符子序列字符子序列求得 sub=man ;SubStr(commander ,1,9)SubStr(commander,9,1)求得 sub=r 求得 sub=commander 第九页，共28页。SubStr(“commander,4,7)sub=?SubStr(“beijing,7,2)=?sub=?SubStr(student,5,0)=起始位置和子串长度之间存在起始位置和子串长度之间存在(cnzi)约束关系约束关系长度长度(chngd)为为 0 的子串为的子串为“合法串合法串第十页，共28页。Index(S,T)初始条件：串初始条件：串S和和T存在，存在，T是非是非空串空串操作结果：操作结果：假设主串假设主串 S 中存在和中存在和串串 T 值值 相同的子串相同的子串,那么那么返回它在主串返回它在主串 S 中第一次出现中第一次出现(chxin)的位置，否那么函数值的位置，否那么函数值为为0。第十一页，共28页。假设假设(jish)S=abcaabcaaabc ,T=bca Index(S,T)=2;“子串在主串中的位置意指(y zh)子串中的第一个字符在主串中的位序。第十二页，共28页。Replace(S,T,V)初始条件：串S,T和 V 均已存在，且 T 是非空串。操作(cozu)结果：用 V 替换主串 S 中出现 的所有与模式串T 相等的子串。第十三页，共28页。例如例如(lr)：假设假设(jish)S=abcaabcaaabca,T=bca 假设假设(jish)V=x ,那么经置换后得到那么经置换后得到 S=axaxaax 假设假设 V=bc ,那么经置换后得到那么经置换后得到 S=abcabcaabc 第十四页，共28页。Insert(S,i,T)初始条件：串初始条件：串S和和T存在，存在，1iStrLength(S)操作操作(cozu)结果：在串结果：在串S的第的第i个字符之后个字符之后 插入串插入串T。例如：例如：S=chater ，T=rac ，那么执行那么执行 Insert(S,4,T)之后之后(zhhu)得到得到 S=chatracer 第十五页，共28页。Delete(S,i,j)初始条件：串初始条件：串S存在存在 1iStrLen(S)-j+1。操作结果：从串操作结果：从串S中删除中删除(shnch)第第i个字符个字符 起长度为起长度为j的子串。的子串。第十六页，共28页。对于串的根本操作集可以有不同的定义方法，在使用(shyng)高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联(chunlin)接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如例如(lr)(lr)：C C语言函数库中提供以下串处理函数：语言函数库中提供以下串处理函数：第十七页，共28页。在程序设计语言中，串只是在程序设计语言中，串只是(zhsh)作为输入或输出的常量出现，那么只作为输入或输出的常量出现，那么只 需存储此串的串值，即字符序列即需存储此串的串值，即字符序列即 可。但在多数非数值处理的程序中，可。但在多数非数值处理的程序中，串也以变量的形式出现。串也以变量的形式出现。4.2 串的存储串的存储(cn ch)结构结构第十八页，共28页。一、串的定长顺序存储表示一、串的定长顺序存储表示(biosh)二、串的堆分配存储二、串的堆分配存储(cn ch)表示表示三、串的块链存储三、串的块链存储(cn ch)表示表示第十九页，共28页。#define MAXSTRLEN 255 /用户用户(yngh)可在可在255以内定义最大串长以内定义最大串长 typedef unsigned char String MAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度一、串的定长顺序存储表示一、串的定长顺序存储表示(biosh)第二十页，共28页。按这种串的表示方法(fngf)实现的串的运算时，其根本操作为“字符序列的复制 串的实际长度可在这个予定义长度的串的实际长度可在这个予定义长度的范围内随意设定，超过范围内随意设定，超过(chogu)予定义予定义长度的串值那么被舍去，称之为长度的串值那么被舍去，称之为“截断截断 特点特点(tdin):第二十一页，共28页。typedef struct char*ch;/假设是非空串，那么按串实用长度分配假设是非空串，那么按串实用长度分配(fnpi)/存储区，否那么存储区，否那么 ch 为为NULL int curlen;/串长度串长度 String;二、串的堆分配存储二、串的堆分配存储(cn ch)表示表示第二十二页，共28页。通常，C语言中提供的串类型(lixng)就是以这种存储方式实现的。系统利用函数malloc()和 free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为:先为新生成的串分配一个存储空间，然后 进行(jnxng)串值的复制。第二十三页，共28页。三、串的块链存储三、串的块链存储(cn ch)表示表示也可用链表来存储串值，由于串的数据也可用链表来存储串值，由于串的数据元素是一个字符，它只有元素是一个字符，它只有 8 位二进制数，位二进制数，因此用链表存储时，通常因此用链表存储时，通常(tngchng)一一个结点中存放的不是一个字符，而是一个结点中存放的不是一个字符，而是一个子串。个子串。存储密度存储密度=数据元素(yun s)所占存储位实际分配的存储位第二十四页，共28页。#define CHUNKSIZE 80 /可由用户定义块大小 typedef struct Chunk /结点结构 char chCUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表结构 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前(dngqin)长度 LString;第二十五页，共28页。也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常(tngchng)一个结点中存放的不是一个字符，而是一个子串。数据结构(sh j ji u)语言第四章字符串操作(cozu)结果：用 V 替换主串 S 中出现 的所有与模式串T 相等的子串。Chunk*head,*tail;/串的头和尾指针char chCUNKSIZE;int curlen;/串长度那么执行 Insert(S,4,T)之后(zhhu)得到StrLen(S)初始条件：串 S 存在。SubStr(“commander,4,7)StrLen(S)初始条件：串 S 存在。StrCmp(“cat,“case)0StrCmp(“cat,“case)0gets(str)输入一个串；串 S 存在(cnzi)，1iStrLen(S)且 0jStrLen(S)-i+1。S=abcabcaabc串定位 串删除(shnch)例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行(yxng)是一个子串，构成一个结点。即:同一行(yxng)的串用定长结构(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置实际应用时，可以根据问题所需来设置结点结点(ji din)的大小。的大小。第二十六页，共28页。串的模式匹配串的模式匹配n定义定义 在串中寻找在串中寻找(xnzho)子串第子串第一个字符在串中的位置一个字符在串中的位置n词汇词汇 在模式匹配中，子串称为模式，在模式匹配中，子串称为模式，串称为目标。串称为目标。n例如例如 目标目标 T:“Beijingn 模式模式 P:“jinn 匹配结果匹配结果=3 第二十七页，共28页。第第1趟趟 T a b b a b a 穷举的模式穷举的模式(msh)P a b a 匹配过程匹配过程 第第2趟趟 T a b b a b a P a b a 第第3趟趟 T a b b a b a P a b a第第4趟趟 T a b b a b a P a b a 第二十八页，共28页。