数据结构串的性质和基本操作本ppt课件.ppt

数据结构串的性质和基本操作本ppt课件.ppt

ID:59470425

大小:332.50 KB

页数:24页

时间:2020-09-14

数据结构串的性质和基本操作本ppt课件.ppt_第1页
数据结构串的性质和基本操作本ppt课件.ppt_第2页
数据结构串的性质和基本操作本ppt课件.ppt_第3页
数据结构串的性质和基本操作本ppt课件.ppt_第4页
数据结构串的性质和基本操作本ppt课件.ppt_第5页
资源描述:

《数据结构串的性质和基本操作本ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章 串的性质和基本操作为什么要学习字符串?计算机在处理非数值数据时基本是字符串。串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。然而,串的基本操作和线性表有很大的差别。串操作中,通常以“串的整体”作为操作对象。也就是说,串是一种特殊的线性表,其特殊性体现在数据元素是一个字符。串是一种内容受限的线性表。本章内容4.1串的定义4.2串的表示和实现4.3串的模式匹配算法1.串的顺序存储结构2.串的链式存储结构1.朴素的模式匹配算法2.KMP算法串的定义和相关概念串(String):由零个或多个字符组成的

2、有限序列。记为:s=’a1a2…an’(n≥0)1.串的定义2.相关概念s为串名,’a1a2…an’为串值,n为串的长度。ai,约束为字符集中的字符。空串(NullString):n=0,记为:Ф。空格串(blankstring):串中仅包含空格字符。子串:串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串被称为主串。子串在主串中的位置:以子串的第一个字符在主串中的位置来表示。串相等:当且仅当两个串的串值相等(两个串的长度相等,并且各个对应的字符也都相等)。串的抽象数据类型定义ADTString{数据对象:D

3、={ai

4、ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系:R={

5、ai-1,ai∈D,i=2,...,n}基本操作:……}串是有限长的字符序列,由一对单引号相括,如:astring串的操作串赋值:StrAssign(&S,chars)求串长:StrLength(S)串判等:StrCompare(S,T)串联接:Concat(&T,S1,S2)求子串:SubString(&sub,S,pos,len)子串定位:Index(S,T,pos)置换:Replace(&S,T,V)

6、插入子串:StrInsert(&S,pos,T)删除子串:StrDelete(&S,pos,len)(其中,前5个操作为基本操作构成最小操作子集。)对于串的基本操作集可以有不同的定义方法,在使用高级程序设计语言中的串类型时,应以该语言的参考手册为准。gets(str)输入一个串;puts(str)输出一个串;strcat(str1,str2)串联接函数;strcpy(str1,str2,k)串复制函数;strcmp(str1,str2)串比较函数;strlen(str)求串长函数;例如:C语言函数库中提供下列串处理函数

7、:例如,可利用串判等、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,pos,StrLength(T)),T)?0S串T串T串iposn-m+1算法的基本思想为:intIndex(StringS,StringT,intpos){if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elseret

8、urni;}//while}//ifreturn0;//S中不存在与T相等的子串}//IndexT为非空串。若主串S中第pos个字符之后存在与T相等的子串,则返回第一个这样的子串在S中的位置,否则返回0。又如串的置换函数:S串T串V串V串pospossubinews串subS串串运算举例1.求子串SubString(&sub,S,pos,len)SubString(sub,commander,4,3)求得sub=;?manSubString(sub,commander,1,9)求得sub=;?comman

9、derSubString(sub,commander,9,1)求得sub=;?r串运算举例起始位置和子串长度之间存在约束关系SubString(sub,commander,4,7)求得sub=;?manderSubString(sub,beijing,7,2)求得sub=;?gSubString(sub,student,5,0)求得sub=;?串运算举例2.子串定位Index(S,T,pos)假设S=abcaabcaaabc,T=bca求得Index(S,T,1)=;?2求得I

10、ndex(S,T,3)=;?6求得Index(S,T,8)=;?0串运算举例3.替换子串Replace(&S,T,V)假设S=abcaabcaaabca,T=bca,若V=x,则经置换后得到S=;?axaxaax若V=bc,则经置换后得到S=;?abcabcaabc串运算举例4.插入子串StrInsert(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。