第4章串( String 4.1串 4.2串的存储结构 4.3串基本操作的实现算法 4.4串的模式匹配算法
1 第4章 串（String） 4.1 串 4.2 串的存储结构 4.3 串基本操作的实现算法 4.4 串的模式匹配算法
4.1串 般是字母、数学、标点符 号等可屏幕显示的字符 串的基本概念 串(又称字符串)是由n(n≥0)个字符组成的有限序列 (它是数据元素为单个字符的特殊线性表。) 记为:s=“s0,s1, ······ 隐含结束符“0’, 串名串值(用“”括起来)即Asc码NU 为何要单独讨论“串”类型 1)字符串操作比其他数据类型更复杂(如拷贝、连接操作) 2)程序设计中,处理对象很多都是串类型
2 记为： s =“s0,s1, ……,sn-1” (n≥0 ) 串名 串值（用“”括起来） 一、串的基本概念 １、串（又称字符串）是由n(n ≥0)个字符组成的有限序列。 （它是数据元素为单个字符的特殊线性表。） 4.1 串 隐含结束符‘\0’ ， 即ASCII码NUL 为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型。 一般是字母、数学、标点符 号等可屏幕显示的字符
2、串长串中字符的个数(n≥0)。 3、空串串中字符的个数为0时称为空串。 4、空白串由一个或多个空格符组成的串 5、子串串S中任意个连续的字符序列叫S的子串;S叫主串。 6、子串位置子串的第一个字符在主串中的序号。 7、字符位置字符在串中的序号。 8、串相等串长度相等,且对应位置上字符相等。(即两个 串中的字符序列一一对应相等。) 问:空串和空白串有无区别? 答:有区别。 空串(Nu! String)是指长度为零的串 而空白串 Blank String)是指包含一个或多个空白字 符′′(空格键)的字符串
3 ２、串长 串中字符的个数（n≥0）。 ３、空串 串中字符的个数为0 时称为空串 。 ４、空白串 由一个或多个空格符组成的串。 ５、子串 串S中任意个连续的字符序列叫S的子串; S叫主串。 ６、子串位置 子串的第一个字符在主串中的序号。 ７、字符位置 字符在串中的序号。 ８、串相等 串长度相等，且对应位置上字符相等。（即两个 串中的字符序列一一对应相等。） 问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字 符‘ ’(空格键)的字符串
例1:现有以下4个字符串: a=“BEIb=“JING”c=“ BEJJING”d=“ BEI JING” 问:①他们各自的长度?a=3,b=4,c=7,d-8 ②a是哪个串的子串?在主串中的位置是多少? a是c和d的子串,在c和d中的位置都是1 ③空串是哪个串的子串?a是不是自己的子串? 空串是任意串的子串;任意串S都是S本身的子 串,除S本身外,S的其他子串称为S的真子串。 注:串与字符的区别 串,长度为1的串。(它不仅要存储字符 还要存储该串的长度数据1) a字符a。(只存储字符a”)
4 例1：现有以下4个字符串： a =“BEI” b =“JING” c = “BEIJING” d = “BEI JING” 问：① 他们各自的长度？ a是c和d的子串，在c和d中的位置都是1 ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 ③ 空串是哪个串的子串？a是不是自己的子串？ 空串是任意串的子串；任意串S都是S本身的子 串，除S本身外，S的其他子串称为S的真子串。 注：串与字符的区别 “a” 串，长度为１的串。（它不仅要存储字符‘a’， 还要存储该串的长度数据１） ‘a’ 字符a。(只存储字符‘a’)
串的抽象数据类型 数据集合:串的数据集合可以表示为字符序列s0,1 n-1,每 个数据元素的数据类型为字符类型。 操作集合: (1)初始化串 Initiate(S) (2)赋值 assign(S,T) (3)求串长度 Length(S) (4)比较 Compare(S,T (5)插入 Insert(S,pos,T) (6)删除 Delete(S, pos,len) (7)取子串 Substring(Spos,len (8)查找子串 Search(S, start,T (9)替换子串 Replace(S, start,T,v)
5 数据集合：串的数据集合可以表示为字符序列s0,s1, ……,sn-1，每 个数据元素的数据类型为字符类型。 操作集合： (1)初始化串 Initiate(S) (2)赋值 Assign(S,T) (3)求串长度 Length(S) (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) 二、串的抽象数据类型
C语言的串函数 注:用C处理字符串时,要调用标准库函数# nclude< 串长度: int strlen(char*s); 串比较: Int strcmp(char*strl,char*str2) 串拷贝:char* strep(char*srl,char*st2) 串连接: char x stra(char* strl char *str2); 子串T定位: char *strchr( char *str, char ch); 子串查找:char* 'strstr(char*sl,char*s2);
6 三、C语言的串函数 串长度：int strlen(char *s); 串比较：int strcmp(char *str1,char *str2); 串拷贝：char * strcpy(char *str1,char *str2); 串连接：char * strcat(char *str1,char *str2); 子串T定位：char *strchr(char *str,char ch); 子串查找 ： char *strstr(char *s1,char *s2); …… 注：用C处理字符串时，要调用标准库函数#include
例1:设s=“ IAM A STUDENT”,t=“GOOD”, q=“ WORKER”。求: Length(s) 14 Length(t) Substring(s, 7,7)= STUdENT Substring( t, 2, 1) Replace(s, 0, STUDENT,, q=IAMA WORKER
7 设 s =“I AM A STUDENT”, t =“GOOD”, q=“WORKER”。求： 例1： Length(s) ＝ Length(t) ＝ SubString( s, 7, 7)= SubString( t, 2, 1)= Replace( s,0,‘STUDENT’, q )= 14 4 ‘STUDENT’ ‘O’ ’I AM A WORKER’
例2:设s=4 AM A STUDENT”,t=“GooD”,求: Concat( SubString(s, 5, 2), Concat( t, SubString(s, 7, 8)))=? 解:因为 Substring(s,6,2)=‘A’; Substring(s, 7, 8)=STUDENT strcat(,t, SubString(s, 7, 8))= GOOD STUDENT 所以: strcat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8))
8 解：因为 SubString(s,6,2)＝‘A’； SubString(s,7,8)＝‘ STUDENT’ strcat(,t,SubString(s,7,8))＝’GOOD STUDENT’ 所以： strcat(,SubString(s,6,2), Concat(t,SubString(s,7,8))) ＝‘AGOOD STUDENT’ 例2：设 s =“I AM A STUDENT” , t =“GOOD” ,求： Concat( SubString(s,5,2), Concat( t,SubString(s,7,8) ) ) ＝？
4.2串的存储结构 首先强调:串与线性表的运算有所不同,是以“串的整体”作 为操作对象,例如查找某子串,在主串某位置上插入一个子串 串有两种机内表示方法: 定长顺序存储表示(静态数组结构) 顺序 用一组地址连续的存储单元存储串值的字 存储 符序列,属静态存储方式。 堆分配存储表示(动态数组结构) 用一组地址连续的存储单元存储申值的字 符序列但存储空间是在程序执行过程中动态 链式 分配而得。 存储。串的链式存储表结构
9 4.2 串的存储结构 • 定长顺序存储表示（静态数组结构） ——用一组地址连续的存储单元存储串值的字 符序列，属静态存储方式。 • 堆分配存储表示（动态数组结构） ——用一组地址连续的存储单元存储串值的字 符序列,但存储空间是在程序执行过程中动态 分配而得。 • 串的链式存储表结构 首先强调：串与线性表的运算有所不同，是以“串的整体”作 为操作对象，例如查找某子串，在主串某位置上插入一个子串 等。 串有两种机内表示方法： 顺序 存储 链式 存储
1、定长顺序存储特点:用一组连续的存储单元来存 放串,直接使用定长的字符数组来定义,数组的上界预先 给出,故称为静态存储分配。 串的静态数组结构体可定义为: typedef struct i char str MaxSizeli int length: SString:
10 1、定长顺序存储特点：用一组连续的存储单元来存 放串，直接使用定长的字符数组来定义，数组的上界预先 给出，故称为静态存储分配。 串的静态数组结构体可定义为： typedef struct { char str[MaxSize]; int length; }String;