第4章串 串的基本概念和C语言的串函数 主串的存储结构 要知识点 动态数组实现的顺序串 串的模式匹配算法BF算法
第4章 串 主 要 知 识 点 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法
41串 串的基本概念 1)串(又称字符串)是由n(n≥0个字符组成的有限序列。(它 是数据元素为单个字符的特殊线性表。) 记为 s=s0,S1, sn-1(n≥0) 串名串值(用“”括起来)
4.1 串 1、串的基本概念 1)串(又称字符串)是由n(n≥0)个字符组成的有限序列。（它 是数据元素为单个字符的特殊线性表。） 记为： s =“s0,s1, ……,sn-1” (n≥0 ) 串名 串值（用“ ”括起来）
2)长串中字符的个数(n≥0)。 3)空串串中字符的个数为0时称为空串Q 4)空白串由一个或多个空格符组成的串。 5)子串串S中任意个连续的字符序列叫s的子串S叫主 串。 6)子串位置子串的第一个字符在主串中的序号。 7)字符位置字符在串中的序号。 8)串相等串长度相等,且对应位置上字符相等。(即 两个串中的字符序列一一对应相等。)
２)串长 串中字符的个数（n≥0）。 ３)空串 串中字符的个数为0 时称为空串 。 ４)空白串 由一个或多个空格符组成的串。 ５)子串 串S中任意个连续的字符序列叫S的子串; S叫主 串。 ６)子串位置 子串的第一个字符在主串中的序号。 ７)字符位置 字符在串中的序号。 ８)串相等 串长度相等，且对应位置上字符相等。（即 两个串中的字符序列一一对应相等。）
向:空串和空白串有无区别? 答:有区别。 空串(Nu! String)是指长度为零的串; 而空白串 Blank String)是指包含一个或多个空白字 符‘′(空格键)的字符串 注:串与字符的区别 a”串,长度为1的串。(它不仅要存储字符‘a 还要存储该串的长度数据1 a’字符a。(只存储字符“a”)
问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字 符‘ ’(空格键)的字符串. 注：串与字符的区别 “a” 串，长度为１的串。（它不仅要存储字符‘a’ ， 还要存储该串的长度数据１） ‘a’ 字符a。(只存储字符‘a’)
2、串的抽象数据类型 数据集合:串的数据集合可以表示为字符序列s0.s1,….5n-1, 每个数据元素的数据类型为字符类型。 操作集合: (1)初始化串 Initiate(S) (2)赋值 Assign(ST (3)求串长度 Length(S)
数据集合：串的数据集合可以表示为字符序列 s0,s1, ……,sn-1， 每个数据元素的数据类型为字符类型。 操作集合： (1)初始化串 Initiate(S) (2)赋值 Assign(S,T) (3)求串长度 Length(S) 2、串的抽象数据类型
(4)比较 Compare(S,T):有相等和不相等两种比较 结果,还有大于、等于和小于三种比较结果 (5)插入 Insert(S,pos,T) (6)删除 Delete(S, pos,len) (7)取子串 SubString(S,pos,en) 68)查找子串 Search(S,star,n) (9)替换子串 Replace(S,tart,r,v)
(4)比较 Compare(S,T) :有相等和不相等两种比较 结果，还有大于、等于和小于三种比较结果 (5)插入 Insert(S,pos,T) (6)删除 Delete(S,pos,len) (7)取子串 SubString(S,pos,len) (8)查找子串 Search(S,start,T) (9)替换子串 Replace(S,start,T,V)
3、串和线性表的比较 相同之处:都是线性结构 不如之处: (1)线性表的数据元素类型为任意类型;而串的数据元素类 型为字符类型 (2)线性表的插入和删除操作都是只对一个数据元素;而串 的插入和删除操作都是对一个子串进行的 (3)串还有一些不同于线性表的其他操作 因此,专门设计串为一个专门的数据结构。 现有的所有高级程序设计语言,如C++,Java等,都提是供了 专门的串操作函数或串类
相同之处：都是线性结构 不如之处： （1）线性表的数据元素类型为任意类型；而串的数据元素类 型为字符类型 （2）线性表的插入和删除操作都是只对一个数据元素；而串 的插入和删除操作都是对一个子串进行的 （3）串还有一些不同于线性表的其他操作 因此，专门设计串为一个专门的数据结构。 现有的所有高级程序设计语言，如C++，Java等，都提供了 专门的串操作函数或串类。 3、串和线性表的比较
3、c语言的串函数 注:用C语言处理字符串时,要调用标准库函数 #includesstring.h> 串长度: int strlen(char*str); 串拷贝:char* strep(char*sr,char*sr2); 串比较: int strcmp( char *strl,char*str2); 字符定位:char* strchr(char*sr; char ch 子串查找: char *strstr((char*s,char*2); 串连接:char* strcat( char *str1, char *str2)
3、C语言的串函数 串长度：int strlen(char *str); 串拷贝：char *strcpy(char *str1,char *str2); 串比较：int strcmp(char *str1,char *str2); 字符定位：char *strchr(char *str,char ch); 子串查找: char *strstr(char *s1,char *s2); 串连接：char *strcat(char *str1,char *str2); …… 注：用C语言处理字符串时，要调用标准库函数 #include
例:名和姓的对换问题。英国和美国人的姓名是名在前姓在 后,但在有些情况下,需要把姓名写成姓在前名在后中间加· 个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示 法转换成姓在前名在后中间加一个逗号的姓名表示法。 算法思想:因为C语言自动在串末尾添加结束标记\0所 以实现方法是首先把把原姓名串name的空格改写为\0(注 意此时\0后边,即指针p+1指示的是原字符串name的姓 部分;此时的name表示的是原name的名部分),再把原 name的姓、逗号和名逐步添加到 newname中,最后再恢复 name为开始时的状态 设计函数如下:
例:名和姓的对换问题。英国和美国人的姓名是名在前姓在 后，但在有些情况下，需要把姓名写成姓在前名在后中间加一 个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示 法转换成姓在前名在后中间加一个逗号的姓名表示法。 算法思想：因为C语言自动在串末尾添加结束标记‘\0‘ ,所 以实现方法是:首先把把原姓名串name的空格改写为‘\0‘(注 意此时‘\0‘后边，即指针p+1指示的是原字符串name的姓 部分；此时的name表示的是原name的名部分)，再把原 name的姓、逗号和名逐步添加到newName中，最后再恢复 name为开始时的状态。 设计函数如下：
void ReverseName(char *name, char *newName) char p; p=strchr(name, p指在空格'位置 p=NULL;/把空格换为NULL,因此name的长度只包括名 strcpy( newName,p+1); newName等于name的姓 strcat(newName,,)3 ); //newName等于姓加逗号 stra( newName,name);∥/ newName等于姓加逗号加名 /恢复name为开始时的状态
void ReverseName(char *name, char *newName) { char *p; p = strchr(name, ' '); //p指在空格' '位置 *p = NULL; //把空格换为NULL，因此name的长度只包括名 strcpy(newName, p+1); //newName等于name的姓 strcat(newName, ","); //newName等于姓加逗号 strcat(newName, name); // newName等于姓加逗号加名 *p =' '; //恢复name为开始时的状态 }