文档介绍：第5章串第5章串数据结构( C描述) 目录 串的定义及运算 串的存储结构 串的运算的实现结束放演 串的定义及运算 基本概念 ( string) 是由零个或多个字符组成的有限序列, 记作 s=“a 1a 2…a n”,其中 s 为串的名字,用成对的双引号括起来的字符序列为串的值,但两边的双引号不算串值, 不包含在串中。 a i (1≤i≤n) 可以是字母、数字或其它字符。 n为串中字符的个数,称为串的长度。 ,它的长度 n=0 ,记为 s= “”。 ,称为空格串,它的长度是空格的个数。若串中含有空格,在计算串长时,空格应计入串的长度中,如: s=“I’ m a student ”的长度为 13。 、主串子串是指串中任意个连续字符组成的子序列,而包含该子串的串称为主串。例如,串 s1= “ abcdefg ”, s2= “ fabcdefghxyz ”,则 s1为 s2 的子串, s2相对于 s1为主串。另外,空串是任意串的子串,任意串是自身的子串。除串本身以外的子串都称为真子串。 串的运算为描述方便,假定用大写字母表示串名,小写字母表示组成串的字符。 1. 联接 concat(&S,T) 表示将 S串和 T串联接起来,使 T串接入 S串的后面。 2. 求串长度 length (T) 求T串的长度。 3. 串比较大小 strcmp(S,T) 比较 S串和 T串的大小,若 S<T ,函数值为负,若 S=T , 函数值为零,若 S>T ,函数值为正。 substr(S,i,j,&T) 表示截取 S串中从第 i个字符开始连续 j个字符,作为 S的一个子串,存入 T串。 5. 串插入 insert (&S,i,T) 在S串的第 i个位置扦入 T串。 6. 串删除 delete(&S,i,j) 删除串 S中从第 i个字符开始连续 j个字符。 串的存储结构 顺序存储串的顺序存储结构,也称为顺序串,与第三章介绍的顺序表类似,用一组地址连续的存储单元存储串值。不同的计算机,存储器编址的方式不同,主要有字节编址和字编址。一个字符只占 1个字节,一个字(即一个存储单元)占多个字节,因此结合具体计算机顺序存储结构有三种不同的实现方式: H o w d o y o u d o图4-2 S 串的紧缩存储(设一个字有 4个字符位置) ,尽可能将多个字符存放在一个字中。假设一个字(即一个存储单元)可存储 4个字符,则紧缩存储具体形式见下图。 ,即使一个单元可以存放4个字符。具体形式见图 4-1, 设串 S= “ How do you do ”。可见,紧缩存储能够节省大量存储单元,但对串的单个字符操作(插入或删除)很不方便,要花费较多的处理时间。 Howdoyoudo图4- 1 S 串的非紧缩存储