数据结构-第四章-串.pptVIP

;第四章字符串/串(string);(2)空串：不含字符的串/长度为零的串。

PASCAL语言:s=

C语言:s=

(3)空格串：仅含空格字符’’的串。

例s1=?s2=??

s1=s2=’

(4)子串：串s中任意个连续的字符组成的子序列称为串s的子串。

主串---包含某个子串的串。

例st=ABC123A123CD

s1=ABCs3=123As4=ABCA

s2=ABC12s5=ABCEs6=321CBA

;

2.串变量、字符变量的定义与使用

例1串变量

charst[]=abc\*123；

gets(st)；scanf(%s,st)；

strcpy(st,data)；

puts(st)；printf(“st=%s\n”,st)；

例2字符变量

charch=A；

ch=’B’；ch=getchar()；

scanf(%c,ch)；printf(ch=%c\n,ch)；;3.串的根本操作与串函数;(4)strcmp(s1,s2)---比较s1和s2的大小

假设s1s2,返回负整数如：ABCabc

假设s1=s2,返回0如：如：abc=abc

假设s1s2,返回正整数如：ABCDABC“

(5)strstr(s1,s2)----假设s2是s1的子串，那么指向s2在s1中第1次出现时的第1个字符的位置；否那么返回NULL。

设s1=ABE123*DE123bcd

s2=E123

有strstr(s1,s2)=3

s1=ABE123*DE123

;(6)Replace(s,t,v)----置换

用v代替主串s中出现的所有与t相等的不重叠的子串

设s=abc123abc*ABC,t=abc,v=OK

执行：Replace(s,t,v)；

有：s=OK123OK*ABC,t=”abc”,v=OK

设A=abcaaaaaABC,B=aa,C=aaOK

执行：Replace(A,B,C)；

有：A=abcaaOKaaOKaABC,B=aa,C=aaOK“

(7)StrInsert(s,i,t)----将t插入s中第i个字符之前。

设s=ABC123

执行:StrInsert(s,4,**)；

有:s=ABC**123;(8)用Replace(s,t,v)实现删除

设s=ABC//123

执行：Replace(s,//,)

有：s=ABC123

(9)用Replace(s,t,v)实现插入

设s=ABC123

执行：Replace(s,123,**123)

有：s=ABC**123;4.2串的存储表示和实现

4.2.1串的定长顺序存储表示

给每个定义的串分配一个固定长度的存储区

#defineMAXSTRLEN255//用户可在255以内定义最大长度

typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放

//串的长度

PASCAL:下标为0的分量存放串的实际长度

012255

C:在串值后加串结束标记‘\0’,串长为隐含值

012255

;

1.顺序存储----用一维字符数组表示一个串的值。

例1charst1[80]=”ABC123”；;\0;(3)t的最大长度s1的长度：;4.2.2串的堆分配存储表示

提供一个足够大的连续存储空间，存放字符串的值。;;;intStrAssign(HString*T,char*chars)

{char*c;inti;

if(T-ch)free(T-ch);/*释放T原有空间*/

for(i=0,c=chars;*c;i++,++c);/*求chars的串长i*/

if(!i)

{T-ch=NULL;T-length=0;}/*当chars为空串时*/

else{

if(!