数据结构(C语言)第四章 字符串课件.ppt

《数据结构(C语言)第四章 字符串课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、字符串(String)字符串:是n(0)个字符的有限序列，记作S:“c1c2c3…cn”其中，S是串名字“c1c2c3…cn”是串值ci是串中字符n是串的长度。例如,S=“TsinghuaUniversity”空串：零个字符的串称为空串记作“Ø”子串：串中任意个连续的字符组成的子序列主串：包含子串的串字符在串中的位置：字符在序列中的序号子串在串中的位置：子串的第一个字符在主串中的位置串的基本运算串插入串赋值求串长串比较串联接求子串串定位串删除置换StrAssign(T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCmp(S,T)初始条件

2、：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCmp(“data”,“state”)<0StrCmp(“cat”,“case”)>0StrLen(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Strcat(S1,S2)初始条件：串S1和S2存在。操作结果：返回由S1和S2联接而成的新串。例如：Strcat(man,kind)求得S1=mankindSubStr(S,i,j)初始条件：操作结果：返回串S的第i个字符起长度为j的子串。串S存在，1≤i≤StrLen(S)且0≤j≤St

3、rLen(S)-i+1。例如：SubStr(commander,4,3)子串为“串”中的一个字符子序列求得sub=man;SubStr(commander,1,9)SubStr(commander,9,1)求得sub=r求得sub=commanderSubStr(“commander”,4,7)sub=?SubStr(“beijing”,7,2)=?sub=?SubStr(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串Index(S,T)初始条件：串S和T存在，T是非空串操作结果：若主串S中存在和串T值相同的

4、子串,则返回它在主串S中第一次出现的位置，否则函数值为0。假设S=abcaabcaaabc,T=bcaIndex(S,T)=2;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。Replace(S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的子串。例如：假设S=abcaabcaaabca,T=bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=abcabcaabcInsert(S,i,T)初始条件：串S和T存在，1≤i≤StrLength(S

5、)操作结果：在串S的第i个字符之后插入串T。例如：S=chater，T=rac，则执行Insert(S,4,T)之后得到S=chatracerDelete(S,i,j)初始条件：串S存在1≤i≤StrLen(S)-j+1。操作结果：从串S中删除第i个字符起长度为j的子串。对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函

6、数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串的存储结构一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharString[MAXSTRLEN+1];//0号单元存放串的长度一、串的定长顺序存储表示按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”串的实际长度可在这个予

7、定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”特点:typedefstruct{char*ch;//若是非空串，则按串实用长度分配//存储区，否则ch为NULLintcurlen;//串长度}String;二、串的堆分配存储表示通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值