《数据结构》课程教学课件（讲稿，C语言描述）第4章 串

串第4章数据结构J（C描述）

第4章 串 数据结构（C描述）

目录4.1串的定义及运算串的存储结构4.24.3串的运算的实现结束放演

目 录 4.1 串的定义及运算 4.2 串的存储结构 4.3 串的运算的实现 结束放演

4.1串的定义及运算4.1.1 基本概念串的定义1.串（string）是由零个或多个字符组成的有限序列，记作s=aja2..a，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中。a(1<i<n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2． 空串，它的长度n=0，记为不含任何字符的串称为空串，S=0般用Φ来表示“空串

4.1串的定义及运算 4.1.1 基本概念 1．串的定义 串( string) 是由零个或多个字符组成的有限序列，记作 s=„a1 a2.an ‟ ，其中s为串的名字，用成对的单引号括起来 的字符序列为串的值，但两边的单引号不算串值，不包 含在串中。ai (1≤i≤n)可以是字母、数字或其它字符。n为 串中字符的个数，称为串的长度。 2．空串 不含任何字符的串称为空串，它的长度n=0，记为 s=„‟。 一般用Ф来表示“空串

3. 空格串含有一个空格的串，称为空格串，它的长度n=1，记为S=4.子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=abcdefg’，s2=fabcdefghxyz’，则s1为s2的子串s2相对于s1为主串

3．空格串 含有一个空格的串，称为空格串，它的长度n=1，记为 s=„ ‟ 。 4．子串、主串 若一个串是另一个串中连续的一段，则这个串称为另 一个串的子串，而另一个串相对于该串称为主串。例 如,串s1=„abcdefg‟，s2=„fabcdefghxyz‟，则s1为s2的子串， s2相对于s1为主串

4.1.2 串的运算为描述方便，假定用大写字母表示串名，小写字母表示组成串的字符赋值1.assign(&S,T)表示将T串的值赋给S串。联接2.concat(&S,T)表示将S串和T串联接起来，使T串接入S串的后面3. 求串长度length (T)求T串的长度

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个字符开始连续i个字符，作为S的一个子串，存入T串二5． 串比较大小 strcmp(S,T)比较S串和T串的大小，若ST，函数值为正。串插入6.insert (&S,i,T)在S串的第i个位置托入T串。串删除7.delete(&S,i,i)删除串S中从第i个字符开始连续i个字符

4.子串 substr(S,i,j,&T) 表示截取S串中从第i个字符开始连续j个字符，作为 S的一个子串，存入T串。 5．串比较大小 strcmp(S,T) 比较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个位置开始连续i个字符，用T串替换，4.1.3串的抽象数据类型描述串的抽象数据类型可描述为：ADTstrings {Data:含有n个字符a,a2,a3...,a,Operation:Void assign(&S,T)//表示将T串的值赋给S串

8. 求子串位置 index(S,T) 求T子串在S主串中首次出现的位置，若T串不是S串 的子串，则位置为零。 9. 串替换 replace (&S,i,j,T) 将S串中从第i个位置开始连续j个字符，用T串替换。 4.1.3 串的抽象数据类型描述 串的抽象数据类型可描述为： ADT strings { Data: 含有n个字符a1 ,a2 ,a3 ,.,an Operation: Void assign(&S,T) //表示将T串的值赋给S串

Void//表示将S串和T串联接起来，使Tconcat(&S,T)串接入S串的后面/求T串的长度intlength(T)Void substr(S,ij,&T）//表示截取S串中从第i个字符开始连续i个字符，作为S的一个子串，存入T串中。//比较S串和T串的大小,若ST,函数值为正//在S串的第i个位置插入T串Void insert(&S,i,T)Void delete(&S,i,i) //删除S中从第i个字符开始连续i个字符int/求T子串在S主串中首次出现的位置index(S,T)若T串不是S串的子串，则位置为零。Voidreplace(&S,i,i,T)//将S串中从第i个位置开始连续i个字符，用T串替换。↑ADT strings;

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,函数值为正。 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串替换。 }ADT strings；

4.2串的存储结构4.2.1 顺序存储串的顺序存储结构，也称为顺序串，与第二章介绍的顺序表类似。但由于串中元素全部为字符,故存放形式与顺序表有所区别串的非紧缩存储一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1,设串S=Howdo you do

4.2 串的存储结构 4.2.1 顺序存储 串的顺序存储结构，也称为顺序串，与第二章介绍的 顺序表类似。但由于串中元素全部为字符,故存放形式 与顺序表有所区别。 1．串的非紧缩存储 一个存储单元中只存储一个字符，和顺序表中一个元素 占用一个存储单元类似。具体形式见图4-1,设串S=“How do you do

H0Wd0y0ud0图 4-1S 串的非紧缩存储

H o w d o y o u d o 图 4-1 S 串的非紧缩存储