清华大学数据结构课件3串

《清华大学数据结构课件3串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DataStructuresandAlgorithmsLecturenotesforStringJiangLihongShanghaiJiaotongUniversitySpring2001DataStructureLecturenotesMainTopic4.1串的基本概念4.2串的运算及其实现4.3串的存储结构4.4串的模式匹配Spring20012DataStructureLecturenotes4.1串的基本概念串（或字符串），是由零个或多个字符组成的有限序列。一般记为：s='a1a2...an'(n>=0)Spring20

2、013DataStructureLecturenotes串的例子S1=“ab123”//长度为5的串S2=“100”//长度为3的串S3=""//含两个空格字符的串长度为2S4=“”//空串长度为0a='BEI',b='JING',c='BEIJING',d='BEIJING'串长分别为3,4,7,8,且a,b都是c,d的子串。称两个串是相等的，当且仅当这两个串的值相等。Spring20014DataStructureLecturenotesa=``称为空白串。它的长度为1。由于空白串本身是一个字符，因此它可以出现在其它字符中间，例

3、如“beijing”。为清楚起见，下文中的空白字符用“σ”表示。a=``称为空串。它的长度为0。空串中无任何字符Spring20015DataStructureLecturenotes4.2串的运算及实现串的抽象数据类型的定义：ADTString{数据对象：D={ai

4、ai(-CharacterSet,i=1,2,...,n,n>=0}数据关系：R1={

5、ai-1,ai(-D,i=2,...,n}Spring20016DataStructureLecturenotes基本操作：StrAssign(&T,chars)

6、//////////chars是字符常量。生成一个其值等于chars的串T。StrCopy(&T,S)串S存在则由串S复制得串TStrEmpty(S)串S存在则若S为空串,返回真否则返回假StrCompare(S,T)///////////串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S

7、at(&T,S1,S2)//////////////串S1和S2存在用T返回由S1和S2联接而成的新串SubString(&Sub,S,pos,len)/////////////串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1Index(S,T,pos)串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0Replace(&S,T,V)串S,T和V存在,T是非空串,

8、用V替换主串S中出现的所有与T相等的不重叠的子串StrInsert(&S,pos,T)串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串DestroyString(&S)串S存在,则串S被销毁}ADTStringSpring20018DataStructureLecturenotes4.3串的存储结构(一)串的定长存储用一组地址连续的存储单元存

9、储串值的字符序列.#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1]//0号单元存放串长Spring20019DataStructureLecturenotes超过予定义长度的串值则被舍去串长可用下标为0的数组元素存储,也可在串值后设特殊标记Spring200110DataStructureLecturenotes串联接的实现Concat(&T,S1,S2)假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值

10、相等,串T的值的后一段和串S2的值相等,则只要进行相应的"串值复制"操作即可,对超长部分实施"截断"操作以下是串联接可能出现的三种情况:S1,S2串长和小于最大值S1,S2串长和超过最大串长S1串长已等于最大串长Spring20011