《第4章串剖析》由会员分享，可在线阅读，更多相关《第4章串剖析（59页珍藏版）》请在金锄头文库上搜索。
1、第四章 串,1,4.1. 串类型的定义 4.2 串的表示与实现 4.3 串的模式匹配算法 4.4 串操作应用举例。,教学内容,2,4.1 串类型的定义,串（字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s = a1 a2 a3 ai an ( n0 )。,字母、数字或其他字符,必须有！,不属于串！,作用：避免字符串与变量名或数的常量混淆。,基本概念,3,例：x = 123 x = 123,test =test,作用：避免字符串与变量名或数的常量混淆。,空串：不含任何字符的串，长度 = 0，用符号 表示。,空格串：仅由一个或多个空格组成的串。,子串：由串中任意个连续的字符组成的子序
2、列。,主串：包含子串的串。,位置：字符在序列中的序号。 子串在主串中的位置：子串的首字符在主串中的位置。,4,例：S=JINAN S1= S2=NA S=JINAN, 均为 S 的子串。,S4=JAN, 非 S 的子串 （非串 S 中的连续字符所组成）。,在 S 中的位置：3,在 S 中的位置：1,串相等的条件：当两个串的长度相等且各个对应位置 的字符都相等时才相等。,例：S=JINAN S1=JI NAN S S1,空串是任意串的子串，任意串是其自身的子串。,5,串的逻辑结构：和线性表极为相似。,串的基本操作：和线性表有很大差别。,区别：串的数据对象约定是字符集。,线性表的基本操作：大多以“
3、单个元素”作为操作对象；,串的基本操作：通常以“串的整体”作为操作对象。,例：在串中查找某个子串； 在串的某个位置上插入一个子串； 删除一个子串等。,6,串的抽象数据类型的定义,ADT String 数据对象：D ai |aiCharacterSet, i = 1, 2, ., n, n0 数据关系：R1 | ai-1, ai D, i = 2, ., n 基本操作： StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。,7,De
4、stroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty (S) 初始条件：串 S 存在。 操作结果：若 S 为空串，则返回 TRUE， 否则返回 FALSE。 StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若 S T，则返回值 0； 若 S = T，则返回值 = 0； 若 S T，则返回值 0。,“串值大小” 是按 “词典次序” 进行比较的，如： StrCompare(“data”, “stru”)0,8,StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数，称为串的长度。 Co
5、ncat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 SubString (&Sub, S, pos, len) 初始条件：串 S 存在，1posStrLength(S) 且 0lenStrLength(S) pos + 1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起长度 为 len 的子串。,9,Index (S, T, pos) 初始条件：串 S 和 T 存在，T 是非空串， 1posStrLength(S)。 操作结果：若主串 S 中存在和串 T 值相同的子串， 则返回它在主串 S 中第 po
6、s 个字符之后 第一次出现的位置；否则函数值为 0。 Replace (&S, T, V) 初始条件：串 S、T 和 V 存在，T 是非空串。 操作结果：用 V 替换主串 S 中出现的所有与 T 相等 的不重叠的子串。,假设 S=“abcacabcaca“， T=“abca“ V=“ab“， 则置换之后的 S=“abcabca“， 而不是 “abbcaca”。,10,StrInsert (&S, pos, T) 初始条件：串 S 和 T 存在，1posStrLength(S)+1。 操作结果：在串 S 的第 pos 个字符之前插入串 T。 StrDelete (&S, pos, len) 初始
7、条件：串 S 存在，1posStrLength(S)-len+1。 操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串。 ClearString (&S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。 ADT String,11,串赋值 StrAssign 串联接 Concat 求串长 StrLength 串比较 StrCompare 求子串 SubString,例如，可利用求串长、求子串和串比较等操作 实现定位函数 Index(S, T, pos) 。,串类型的最小操作子集,这些操作不可能利用 其他串操作来实现。,12,int Index (String S, S
8、tring T, int pos) if (pos 0) n = StrLength(S); m = StrLength(T); / 求串长 i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / 找到和 T 相等的子串 / while / if return 0; / S 中不存在满足条件的子串 / Index,定位函数 Index(S, T, pos),13,4.2 串的表示和实现,因为串是特殊的线性表，故其存储结构与线性表的 存储结构类
9、似，只不过组成串的结点是单个字符。,4.2.1 定长顺序存储表示,定长顺序存储表示，也称为静态存储分配的顺序串。 即用一组地址连续的存储单元依次存放串中的字符序列。,“定长”、“静态”的意思可编译时刻来确定 存储空间，它的长度是不变的。,14,#define maxstrlen 255 / 可在 255 以内定义最大串长。 typedef unsigned char SSTRINGmaxstrlen+1; / 0 号单元存放串的长度。,直接使用定长的字符数组来定义一个串，数组的上界先给出; 串的实际长度可在这个预定义长度的范围内随意设 定，超过预定义长度的串值则被舍去，称之为“截断”。,15,
10、例：串 “This is a dog.” 的长度的表示方法：,串长的表示方法,在串的存贮区首地址 显式地记录串的长度。,在串之后加结束标志。,如：PASCAL 语言。,如：C 使用 “0”。,显式,隐式,16,定长顺序存储表示时串的操作的实现,1、串联接 Concat(&T, S1, S2),假设串 T 是由串 S1 联结串 S2 得到的，则只要进行 相应的“串值复制”操作即可，需要时进行“截断”。,串 T 值,S10+S20 MAXSTRLEN,S10 MAXSTRLEN,S10 = MAXSTRLEN,结果正确,结果 S2 被“截断”,结果 T=S1,17,Status Concat(SS
11、tring / Concat,串联接 Concat 算法描述,18,2、求子串 SubString(&Sub, S, pos, len),求子串的过程即为复制字符序列的过程，将串 S 中的第 pos 个字符开始的长度为 len 的字符串复制到 串 Sub 中。,注：1)、不会出现“截断”的情况。 2)、可能出现“参数非法”的情况，应返回 ERROR。,19,Status SubString(SString / SubString,求子串 SubString 算法描述,20,定长顺序存储表示时串操作的缺点,1、需事先预定义串的最大长度， 这在程序运行前是很难估计的。,2、由于定义了串的最大长度，
12、使得 串的某些操作受限（截尾），如 串的联接、插入、置换等运算。,克服办法：不限定最大长度 动态分配串值的存储空间。,21,4.2.2 堆分配存储表示,堆存储结构的特点：仍以一组空间足够大的、地址 连续的存储单元依次存放串值字符序列，但它们的存储 空间是在程序执行过程中动态分配的。,通常，C 语言中提供的串类型就是以这种存储方式 实现的。由动态分配函数 malloc() 分配一块实际串长所 需要的存储空间（“堆”），如果分配成功，则返回此空 间的起始地址，作为串的基址。由 free( ) 释放串不再需 要的空间。,22,用堆存放字符串时，其结构用 C 语言定义如下： typedef struc
13、t char *ch; / 若非空则按串长分配存储区， / 否则 ch 为 NULL int length; /串长度 HString;,23,Status Concat(HString / Concat,串联接 Concat 算法描述,24,C实现,25,int Concat(HString *t, HString s1, HString s2) if(t-length != s1.length + s2.length) free(t-ch); if(t-ch = (char*)malloc(s1.length + s2.length) = NULL) return false; int i
14、 = 0; for(; ichi = s1.chi; for(; ichi = s2.chi-s1.length; t-length = s1.length + s2.length; ,typedef struct String char *ch; / 字符串存储的基址 int length; / 字符串长度 HString;,Status SubString(HString / SubString,求子串 SubString 算法描述,26,status Strcopy(HString Strcopy,串复制 Strcopy 算法描述：,27,status StrAssign(HString
15、 StrAssign,串赋值 StrAssign 算法描述：,28,int StrCompare(HString S, HString T) for (i=0; iS.length / StrCompare,串比较 StrCompare 算法描述：,29,status ClearString(HString ClearString,清空串 ClearString 算法描述：,30,串插入操作 StrInsert(&S, pos, T) 的实现算法为： 1、为串 S 重新分配大小等于串 S 和串 T 长度之和 的存储空间； 2、进行串值的复制。,31,Status StrInsert (Hstring /StrInsert,例：S=ABCDE T=XY pos=4,A B C D E,A B C D E,S.ch,E,D,typedef struct char *ch; int length; HString;,X Y,X Y,32,堆存储结构的优点：堆存储结构既有顺序存储 结构的特点，处理（随机取子串）方便，操作中对 串长又没有任何限制，更显灵活，因此在串处理的 应用程序中常被采用。,定长顺序存储表示和堆分配存储表示通常为高 级程序设计语言所采用。,33
