算法与数据结构课件PPT第九章

第9章 字符串

9.1 字符串的基本知识

字符串：简称串，是由双引号“”括号括起来的零个或多个字符组成的有限序列

集。串是一种特殊的线性表，串中所包含的元素个数为串的长度。

模式匹配：串S中任意连续的字符组成的子序列S1称为主串S的子串。子串在主串

中的位置是子串中的第一个字符在主串中的位置。在主串S中查找子串S1的过程称

为模式匹配。如果匹配成功，返回T在S中的位置，如果失败返回-1。

模式匹配应用场景：比如编辑软件中进行查找替换操作，病毒检测软件检测病毒

码，垃圾邮件过滤等等。不同的应用需求不同，在编辑软件中查找特定的字符串

1

2

3

4

5

6

7

8

9

10

ADT String is

operations

List SetNullString(viod)//创建一个空串

int StrLen(String s)//求串的长度

int StrInsertPre(String s,position p,char x)

//在串s中的第p个位置之前插入字符x

int StrInsertPost(List list,position p,char x)

//在串s中的第p个位置之后插入字符x

String StrConcat(String s,String t)//将串t放在串s的后面连接成一个新串s

String StSub(String s,int i,int j)

函数声明 函数说明 返回值

char * strcat(char * dest,char * src) 将参数src字符复制到dest字符串末尾

返回参数dest字符串的起始

地址

若找到则返回字符地址；若

未找到则返回NULL

若s1=s2则返回0；若s1>s2

返回s中开头连续不含字符

串reject内容的字符数目

返回字符串指针