第四章串 第1页
第 1 页
第四章串 串也叫字符串,它是由零个或多个字符组成的的字符序列。 基本内容 串的有关概念串的基本操作 2串的顺序存储结构,堆分配存储结构,链式存储结构 3串的基本操作算法 4串的模式匹配算法 学习要点 解串的基本操作,了解利用这些基本操作实现串的其它操作的方法; 2掌握在串的堆分配存储结构下,串的基本操作算法; 3掌握在串的模式匹配算法; 第2页
第 2 页 第 四 章 串 学习要点 1 了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法； 2 掌握在串的堆分配存储结构下，串的基本操作算法； 3 掌握在串的模式匹配算法； 串也叫字符串，它是由零个或多个字符组成的的字符序列。 基本内容 1 串的有关概念 串的基本操作 2 串的顺序存储结构，堆分配存储结构,链式存储结构； 3 串的基本操作算法； 4 串的模式匹配算法；
第四章串 第四章串 4.1串的基本概念 4.2串存储结构 4.3串的基本运算实现 4.3串的匹配算法 第3页
第 3 页 第 四 章 串 第四章 串 4.1 串的基本概念 4.2 串存储结构 4. 3 串的基本运算实现 4.3 串的匹配算法
4.1串的基本概念 1什么是串 串是一种特殊的线性表,它是由零个或多个字符组成的有限序列, 般记作s=“a1,a2,a 其中s-串名,a1a2,a3.…a1-串值 串的应用非常广泛,许多高级语言中都把串的作为基本数据类型。在 事务处理程序中,顾客的姓名、地址货物的名称、产地可作为字符串处 理,文本文件中的每一行字符等也可作为字符串处理。 第4页
第 4 页 1 什么是串 串是一种特殊的线性表，它是由零个或多个字符组成的有限序列， 一般记作 s = “a1 ,a2, a3, ... an” 其中 s----串名， a1 ,a2, a3, ... an ----串值 串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在 事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处 理，文本文件中的每一行字符等也可作为字符串处理。 4. 1 串的基本概念
4.1串的基本概念 下面是一些串的例子: (1)a=“ This is a string” (2)b=“ string (3)c=““ (4)d=“” (5)e=“你好” 说明: 1)串中包含的字符个数,称为串的长度。长度为0的串称为空串,它不 包括任何字符; 2)串中所包含的字符可以是字母、数字或其他字符,这依赖于具体计算 机所允许的字符集。 第5页
第 5 页 下面是一些串的例子： （1）a = “This is a string” （2）b = “string” （3）c = “ “ （4）d = “” （5）e = “你好” 说明： 1) 串中包含的字符个数，称为串的长度。长度为0的串称为空串，它不 包括任何字符; 2) 串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算 机所允许的字符集。 4. 1 串的基本概念
4.1串的基本概念 2串的有关术语 1)子串 串中任意连续的字符组成的子序列称为该串的子串; 例:c=“ DATA STRUCTURE”,f=“DATA”f是c的子串 2)子串的位置 子串t在主串S中的位置是指主串s中第一个与T相同的子串的首字母 在主串中的位置; 例:s=“ ababcabcac”,t“abc”子串T在主串S中的位置为3 3)串相等 两个串相等,当且仅当两个串长度相同,并且各个对应位置的字符都 相同; 第6页
第 6 页 2 串的有关术语 1）子串 串中任意连续的字符组成的子序列称为该串的子串; 例：c = “ DATA STRUCTURE”，f=“DATA” f是c的子串 2）子串的位置 子串t 在主串S中的位置是指主串s 中第一个与T相同的子串的首字母 在主串中的位置; 例：s=“ababcabcac” , t=“abc” 子串T 在主串S中的位置为3 3）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都 相同； 4. 1 串的基本概念
4.1串的基本概念 3串的基本操作 串的逻辑结构与线性表一样,都是线性结构。但由于串的应用与 线性表不同,串的基本操作与线性表有很大差别。 1)串赋值操作 assign(S,t)功能:将串t的值赋给串变量s; 2)串相等判断 equal(s,t)函数 3)串的联接操作 concat(s,t)把串t接在串s后面 4)求串长操作 lenght(s) 5)求子串操作sub(s, start,len,t)若 O<=start<length(s) 0<=len<=length(s)-start 则t中值为从串s的第 start-个字符,起长度为len的字符序列,并且函数 返回值为1,否则为0; 6)求子串位置操作 index(s,t) 功能:如果s中存在与t相同的子串,则返回s中第1个这样的子串的位 置,若不存在返回0 第7页
第 7 页 3 串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与 线性表不同，串的基本操作与线性表有很大差别。 1）串赋值操作assign( s, t) 功能：将串t 的值赋给串变量s ； 2）串相等判断equal(s,t) 函数 3) 串的联接操作concat( s , t ) 把串t 接在串 s 后面 4) 求串长操作lenght(s) 5) 求子串操作sub ( s, start, len, t) 若 0<=start<length(s) 0<=len<=length(s)-start 则t 中值为从串s 的第start个字符, 起长度为len 的字符序列, 并且函数 返回值为1, 否则为0； 6）求子串位置操作index( s, t ) 功能：如果s中存在与t 相同的子串, 则返回s中第1个这样的子串的位 置，若不存在返回0 4. 1 串的基本概念
4.1串的基本概念 7)替换操作 replace(s,t,v) 功能:由串v替换串s中出现的所有和t相同的不重叠子串; 8)复制串操作 strcopy(s,t) 功能:由串变量s复制得到串变量t; 9)判空操作 empty(s) 功能:若为空串,则返回1,否则返回0 10)串置空操作 ClearString(s) 功能:将s清为空串 11)串插入操作 Strlnsert(s, start,t) 功能:将串t插入到串s的第 start字符之前 12)串删除操作 StrDeleter(s, start,len) 功能:从串s中删除第 start个字符起长度len为的子串 第8页
第 8 页 4. 1 串的基本概念 7） 替换操作 replace( s, t ,v ) 功能：由串v 替换串s 中出现的所有和t 相同的不重叠子串； 8）复制串操作strcopy(s, t) 功能：由串变量s 复制得到串变量t ； 9）判空操作empty( s ) 功能：若为空串，则返回1，否则返回0 10）串置空操作ClearString( s ) 功能：将s 清为空串 11) 串插入操作StrInsert( s, start , t) 功能：将串t 插入到串s 的第start 字符之前 12）串删除操作StrDelete( s, start , len) 功能：从串s 中删除第 start 个字符起长度len 为的子串
4.2串存储和实现 顺序存储结构 顺序存储结构类似于C语言的字符数组,以一组地址连续的存储单元存放 串值字符序列,其类型说明如下: #define max 255 char ch MAxI chd ta Structured』□ 01234567891011 14..MAX-1 在数组ch中以字符“0表示字符串的结束.特点是访问容易, 但删除或插入麻烦 第9页
第 9 页 4.2 串存储和实现 1 顺序存储结构 顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放 串值字符序列，其类型说明如下： #define MAX 255 char ch[MAX] 0 1 2 3 4 5 6 7 8 9 10 11 14… MAX-1 ch d a t a s t r u c t u r e \0 在数组ch中以字符‘\0’表示字符串的结束. 特点是访问容易, 但删除或插入麻烦
4.2串存储和实现 2链式存储结构 链式存储结构类似线性链表,由于串结构的特殊性,要考虑每个结点 是存放一个字符还是多个字符。一个字符的,插入、删除、求长度非常 方便,但存储效率低 多个字符的,改善了效率,在处理不定长的大字符串时很有效,但插 入、删除不方便,可用特殊符号来填满未充分利用的结点。 id la tla still cture♀♀♀人 head d a t e head 第10页
第 10 页 4.2 串存储和实现 2 链式存储结构 链式存储结构类似线性链表，由于串结构的特殊性, 要考虑每个结点 是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常 方便，但存储效率低。 多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插 入、删除不方便，可用特殊符号来填满未充分利用的结点。 d a t a s t r u c t u r e♀♀♀ head d a t e head