数据结构_字符串操作原理讲述.pptx

CH4 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 教学目标 熟悉串的有关概念，串和线性表的关系。 掌握串的各种存储结构，比较它们的优、缺点，从而学会在何时选用何种存储结构为宜。 熟练掌握串的七种基本运算，并能利用这些基本运算实现串的其它各种运算。 教学难点 串运算的实现，特别是顺序串上子串定位的运算（又称串的模式匹配或串匹配）。 4.1 串类型的定义 一、串的基本概念 串(String)的定义 s＝“a1a2…an” 其中： s为串的名字， 串的值 ai(1≤i≤n)一般是字母、数学、标点符号等可屏幕显示的字符。 串的长度n。 4.1 串类型的定义 字符串与一般的线性表的区别： 串的数据元素约束为字符集； 串的基本操作通常针对串的整体或串的一个部分进行。 问题：为何要单独讨论“串”类型？ 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 程序设计中，处理对象很多都是串类型。 4.1 串类型的定义 空串和空白串： 长度为零的串称为空串(Empty String)，它不包含任何字符。 空格（白）串:仅由一个或多个空格组成的串称为空白串(Blank String) 子串和主串 eg: A＝“This is a string” B＝“is” 特别地： 空串是任意串的子串，任意串是其自身的子串。 串的相等 二、串的抽象数据类型定义 ADT String{ 数据对象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0} 数据关系：S＝{ ai-1 , ai | ai-1， ai ∈D, i ＝ 2,…,n} 基本操作： StrAssign(T,chars) StrLength(S) SubString(Sub,S,pos,len) StrCopy(T,S) Index(S,T,pos) StrEmpty(S) Replace(S,T,V) StrCompare(S,T) StrInsert(S,pos,T) Concat(T,S1,S2) StrDelete(S,pos,len) } ADT String 三、C语言的串函数 用C处理字符串时，要调用标准库函数 #includestring.h 串长度：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); …… 4.2 串的表示和实现 串的机内表示方法： 串的块链存储表示 4.2 串的表示和实现 4.2.1 定长顺序存储表示 用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 存储表示一： #define MAXSTRLEN 255 typedef char SString[MAXSTRLEN +1]; SString s; 串的结束标志的设置 （1）一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。 例如：C语言中以字符‘\0’表示串值的终结。 （2）可以不设终结符 typedef struct{ char ch[MAXSTRLEN]; int length; } SString; （3）还可以用数组的0号单元存储串的长度。 算法4.2（串的连接算法） Status Concat(SString T,SString S1,SString S2){ if (S1[0]+S2[0]=MAXSTRLEN){ T[1 …S1[0]]=S1[1 …S1[0]]; T[S1[0]+1 …S1[0]+S2[0]]=S2[1 …S2[0]]; T[0]=S1[0]+S2[0]; uncut=TRUE;} else if (S1[0]MAXSTRLEN){ T[1 …S1[0]]=S1[1 …S1[0]]; T[S1[0]+1 …MAXSTRLEN]=S2[1…MAXSTRLEN-S1[0]];