数据结构课件数据结构第4章.pptx

数据结构;第四章串;?串（字符串），是计算机非数值处理的主要对象之一。;?串

由零个或多个字符组成的有限序列。

记作S=’a1a2…an’（n 0）

串名：S；;a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’

长度分别为3s4s7s8；a和b都是c和d的子串；

a在c和d中的位置都是1；b在c和d中的位置是4和5；asbscsd彼此不相等。;串的抽象数据类型

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。;DestroyString(S)初始条件：串S存在。

操作结果：串S被销毁。

StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE，否则返回FALSE

StrCompare(S,T)

初始条件：串S和T存在。

操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。;StrLength(S)

初始条件：串S存在。

操作结果：返回串S序列中的字符个数，即串的长度。

ClearString(S)

初始条件：串S存在。

操作结果：将S清为空串。

Concat(T,S1,S2)

初始条件：串S1和S2存在。

操作结果：用T返回由S1和S2联接而成的新串。;SubString(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。;DataStructure;串与线性表区别;算法4.1定位函数;?定长顺序存储表示

用一组地址连续的存储单元存储串值的字符序列。

可用定长数组描述。#define MAXSTRLEN 255；

typedef unsigned char SString[MAXSTRLEN +1]；

串长有两种表示方法

SString[0]表示；

串值后面加一个不计入串长的结束标记“\0”。;定长顺序存储表示串操作的实现：;克服这种截断弊端的方法是不限定串的最大长度，即采用动态存储结构。;Status SubString (SString Sub,SString S,int pos,int len ){;堆分配存储表示;符号表

串名 位置 长度a 1 3;3

4;串名;对串操作时，首先为串重新分配空间，然后释放以前占用的空间。因此，“移动”是不可避免的。;结点大小的选择很重要，它直接影响串的处理效率。

链式存储结构总的来说，不如前面两种顺序存储结构灵活，存储量大，且操作复杂。;本章小结

?数据元素都是字符，因此它的存储结构和线性表有很大不同。

?多数情况下，实现串类型采用的是“堆分配”的存储结构。

?串的基本操作通常以串的整体作为操作对象，而不像线性表是以数据元素作为操作对象。;基础知识题

?简述空串和空格串(或称空格符串)的区别。

?设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)

DataStr)uc)ture;?已知下列字符串a=THIS‘f=A SAMPLE‘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,