数据结构(C描述)电子教案.pptVIP

* 第4章 串 数据结构（C++描述） 目录 4.1串的定义及运算 4.2 串的存储结构 4.3 串的运算的实现 结束放演 4.1串的定义及运算 4.1.1 基本概念 1．串的定义 串( string) 是由零个或多个字符组成的有限序列，记作s=“a1a2…an”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。 2．空串 不含任何字符的串称为空串，它的长度n=0，记为s=“”。 3．空白串 含有一个空格的串，称为空白串，它的长度n=1，记为s=“ ” 或s=“ ?”。 4．子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。 另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为 +1，真子串个数为 (除串本身以外的子串都称为真子串)。 4.1.2 串的运算 为描述方便，假定用大写字母表示串名，小写字母表示组成串的字符。 1. 赋值 assign(S,T) 表示将T串的值赋给S串。 2. 联接 concat(S,T) 表示将S串和T串联接起来，使T串接入S串的后面。 3. 求串长度 length (T) 求T串的长度。 4.子串 substr(S,i,j,T) 表示截取S串中从第i个字符开始连续j个字符，作为S的一个子串，存入T串。 5．串比较大小 strcmp(S,T) 比较S串和T串的大小，若ST，函数值为负，若S=T，函数值为零，若ST，函数值为正。 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串替换。 4.1.3 串的抽象数据类型描述 串的抽象数据类型可描述为： 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串的大小,若ST,函数值为负,S=T,函数值为零,ST,函数值为正。 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.2 串的存储结构 4.2.1 顺序存储 串的顺序存储结构，也称为顺序串，与第二章介绍的顺序表类似。但由于串中元素全部为字符,故存放形式与顺序表有所区别。 1．串的非紧缩存储 一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1,设串S=“How do you do”。 2．串的紧缩存储 根据各机器字的长度，尽可能将多个字符存放在一个字中。假设一个字可存储4个字符，则紧缩存储具体形式见图4-2。 从上面介绍的两种存储方式可知，紧缩存储能够节省大量存储单元，但对串的单个字符操作很不方便，需要花费较多的处理时间。而非紧缩存储的特点刚好相反，操作方便，但将占用较多的内存单元。 3．串的字节存储 前两种存储方法都是以字编址形