文档介绍：第4章串
数据结构(C++描述)
目录
串的存储结构
串的运算的实现
结束放演
基本概念
串( string) 是由零个或多个字符组成的有限序列,记作s=“a1a2…an”,其中s为串的名字,用成对的双引号括起来的字符序列为串的值,但两边的双引号不算串值,不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数,称为串的长度。
不含任何字符的串称为空串,它的长度n=0,记为s=“”。
含有一个空格的串,称为空白串,它的长度n=1,记为s=“”或s=“ø”。
、主串
若一个串是另一个串中连续的一段,则这个串称为另一个串的子串,而另一个串相对于该串称为主串。例如,串s1=“abcdefg”,s2=“fabcdefghxyz”,则s1为s2的子串,s2相对于s1为主串。
另外,空串是任意串的子串,任意串是自身的子串。若一个串的长度为n,则它的子串数目为+1,真子串个数为(除串本身以外的子串都称为真子串)。
串的运算
为描述方便,假定用大写字母表示串名,小写字母表示组成串的字符。
1. 赋值 assign(&S,T)
表示将T串的值赋给S串。
2. 联接 concat(&S,T)
表示将S串和T串联接起来,使T串接入S串的后面。
3. 求串长度 length (T)
求T串的长度。
substr(S,i,j,&T)
表示截取S串中从第i个字符开始连续j个字符,作为S的一个子串,存入T串。
strcmp(S,T)
比较S串和T串的大小,若S<T,函数值为负,若S=T,函数值为零,若S>T,函数值为正。
6. 串插入 insert (&S,i,T)
在S串的第i个位置扦入T串。
7. 串删除 delete(&S,i,j)
删除串S中从第i个字符开始连续j个字符。
8. 求子串位置 index(S,T)
求T子串在S主串中首次出现的位置,若T串不是S串的子串,则位置为零。
9. 串替换 replace (&S,i,j,T)
将S串中从第i个位置开始连续j个字符,用T串替换。
串的抽象数据类型描述
串的抽象数据类型可描述为:
ADT strings IS
Data: 含有n个字符a1,a2,a3,…,an
Operation:
Void assign(&S,T) //表示将T串的值赋给S串
Void concat(&S,T) //表示将S串和T串联接起来,使T串接入S串的后面。
int length(T) //求T串的长度。
Void substr(S,i,j,&T) //表示截取S串中从第i个字符开始连续j个字符,作为S的一个子串,存入T串中。
int strcmp(S,T) //比较S串和T串的大小,若S<T,函数值为负,S=T,函数值为零,S>T,函数值为正。
Void insert(&S,i,T) //在S串的第i个位置扦入T串。Void delete(&S,i,j) //删除S中从第i个字符开始连续j个字符。
int index(S,T) //求T子串在S主串中首次出现的位置,若T串不是S串的子串,则位置为零。
Void replace(&S,i,j,T) //将S串中从第i个位置开始连续j个字符,用T串替换。
End strings
串的存储结构
顺序存储
串的顺序存储结构,也称为顺序串,与第二章介绍的顺序表类似。但由于串中元素全部为字符,故存放形式与顺序表有所区别。
一个存储单元中只存储一个字符,和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1,设串S=“How do you do”。