数据结构4

数据结构DataStructurePage22020/2/26第四章串学习目标理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。理解串类型的各种存储表示方法。重点和难点本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。知识点串的类型定义、串的存储表示DataStructurePage32020/2/26串（字符串），是计算机非数值处理的主要对象之一。如，在汇编和编译程序中，源程序和目标程序都是串；如，在事务处理程序中，顾客的姓名和地址，以及货物的名称、产地和规格等，通常也都作为串处理。由于我们现今使用的计算机的硬件结构主要是面向数值计算的需要，基本上没有提供对串进行操作的指令，因此需要用软件来实现串数据类型。DataStructurePage42020/2/26串由零个或多个字符组成的有限序列。记作S=’a1a2…an’（n0）串名：S；串值：用单引号括起来的字符序列。长度：串中字符的数目。空串：含零个字符的串，表示。空格串：由一个或多个空格组成的串。子串：串中任意个连续的字符组成的子序列。字符在串的位置：字符在序列中的序号。子串在串的位置：子串的第一个字符在串中的位置。相等：当且仅当两个串的值相等。4.1串类型的定义串值必须用一对单引号括起来空串与空格串的区别？DataStructurePage52020/2/26a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’长度分别为3、4、7、8；a和b都是c和d的子串；a在c和d中的位置都是1；b在c和d中的位置是4和5；a、b、c、d彼此不相等。DataStructurePage62020/2/26串与线性表区别串的数据对象约束为字符集。串的基本操作与线性表有很大差别线性表的基本操作中，大多以“单个元素”作为操作对象，如查找某个元素、在某个位置上插入一个元素和删除一个元素。串的基本操作中，通常以“串的整体”作为操作对象。如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串。DataStructurePage72020/2/26串的抽象数据类型ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)初始条件：chars是串常量。操作结果：赋于串T的值为chars。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DataStructurePage82020/2/26DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。DataStructurePage92020/2/26StrLength(S)初始条件：串S存在。操作结果：返回串S序列中的字符个数，即串的长度。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。DataStructurePage102020/2/26SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。DataStructurePage112020/2/26Replace(&S,T,V)初始条件：串S，T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。}ADTStringDataStructurePage122020/2/26算法4.1定位函数基本思想：从主串S中取“第i个字符起、长度和串T相等的子串”和串T比较，若相等，则求得函数值为i，否则i值增1直至找到相等的子串或者不存在和T相等的子串为止。intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，//则返回第一个这样的子串在S中的位置，否则返回0。if(pos0){n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1){SubString(sub,S,i,m);//取从第i个起长度为m的子串if(StrCompare(sub,T)!=0)++i;elsereturni;//找到和T相等的子串}//while}//ifreturn0;//S中不存在满足条件的子串}//IndexDataStructurePage132020/2/26定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列。可用定长数组描述。#defineMAXSTRLEN255；typedefunsignedcharSString[MAXSTRLEN+1]；串长有两种表示方法SString[0]表示；串值后面加一个不计入串长的结束标记“\0”。4.2串的表示和实现DataStructurePage142020/2/26定长顺序存储表示串操作的实现：设串的最大长度为10，S1=‘ABCDEF’S2=‘GHIJ’S3=‘KLMNOP’S4=‘QRSTUVWXYZ’S1连接S2，结果‘ABCDEFGHIJ’。S1连接S3，结果‘ABCDEFKLMN’，S3的‘OP’部分被截断。S4连接S1，结果‘QRSTUVWXYZ’，S1全部被截断。DataStructurePage152020/2/26StatusConcat(SString&T,SStringS1,SStringS2){//以T返回由S1和S2联接而成的新串，若未截断，返回TRUE，否则FALSEIf(S1[0]+S2[0]=MAXSTRLEN){//未截断T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]MAXSTRSIZE){//截断T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{//截断(仅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}//ConcatDataStructurePage162020/2/26StatusSubString(SString&Sub,SStringS,intpos,intlen){//以Sub带回串S中第pos个字符起长度为len的子串//其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1if(pos1||poss[0]||len0||lens[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1]；Sub[0]=len；returnOK;}//SubStringDataStructurePage172020/2/26系统开辟一个串值存储空间（串值可利用空间），同时建立一个符号表；建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、串长度等信息。堆分配存储表示长度位置串名符号表串值存储空间DataStructurePage182020/2/2631a长度位置串名符号表IEB串值存储空间DataStructurePage192020/2/2644b31a长度位置串名符号表GNIJIEB串值存储空间DataStructurePage202020/2/2688c44b31a长度位置串名符号表IAHGNAHSGNIJIEB串值存储空间DataStructurePage212020/2/26616d88c44b31a长度位置串名符号表NIBRAHIAHGNAHSGNIJIEB串值存储空间DataStructurePage222020/2/26用链表方式存储串值，每个结点大小相同。结点分为两个域data域next域串的块链存储表示结点大小为1的链表ABCDEFhead结点大小为4的链表headDCBA##FE#占满存储密度=串值所占的存储位/实际分配的存储位。DataStructurePage232020/2/26本章小结数据元素都是字符，因此它的存储结构和线性表有很大不同。多数情况下，实现串类型采用的是“堆分配”的存储结构。串的基本操作通常以串的整体作为操作对象，而不像线性表是以数据元素作为操作对象。DataStructurePage242020/2/26基础知识题简述空串和空格串(或称空格符串)的区别。设s=‘IAMASTUDENT’,t=‘GOOD’,q=‘WORKER’。求：StrLength(s)StrLength(t)SubString(s,8,7)SubString(t,2,1)Index(s,'A')Index(s,t),Replace(s,'STUDENT',q),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))DataStructurePage252020/2/26已知下列字符串a='THIS‘f='ASAMPLE‘c=’GOOD‘d=’NE’b=‘‘s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2))))t=Replac(f,SubString(f,3,6),c)u=Concat(SubString(c,3,1),d)g=‘IS’v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),试问:s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么?DataStructurePage262020/2/26试问执行以下函数会产生怎样的输出结果?voiddemonstrate(){StrAssign(s,'THISISABOOK');Replace(s,SubString(s,3,7),'ESEARE');StrAssign(t,Concat(s,'S'));StrAssign(u,'XYXYXYXYXYXY');StrAssign(v,SubString(u,6,3));StrAssign(w,'W');printf('t=',t,'v=',v,'u=',Replace(u,v,w));}//demonstrateDataStr