next[j] = max { k | 0<k<j 且使得 1…tk-1=tj-k+1…tj-1} 当集合不空 且使得t 1
首页
其他情况
上页 下页 退出
第四章
§4.4 串的应用
一、文本编辑 二、建立索引表
思考题： 思考题： 试写出判串S是否是回文的算法。 1、试写出判串S是否是回文的算法。 若串S= S=‘ STRING’以块链存储， 2、若串S=‘THIS IS A STRING’以块链存储，结点大小 链指针占4个字节， 32位 问存储密度是多少？ 为4，链指针占4个字节，即32位，问存储密度是多少？ 是两个但单链表存储的串，试设计一个算法， 3、若X和Y是两个但单链表存储的串，试设计一个算法， 找出X中第一个不在Y中出现的字符来。 找出X中第一个不在Y中出现的字符来。
首页
上页
下页
退出
第四章
§4.1 串类型的定义
三、C语言常用的字符串处理的标准函数： 语言常用的字符串处理的标准函数：
int strlen(char s); int strcmp(chars1,char s2); char strcpy(char to,char from); char strcat(char to,char from) 但在抽象数据类型定义的13种操作中， 13种操作中 但在抽象数据类型定义的13种操作中，串赋值 StrAssign、串复制StrCopy、串比较StrCompare、求串 StrAssign、串复制StrCopy、串比较StrCompare、 StrCopy StrCompare StrLength、串联接Concat以及求子串SubString Concat以及求子串SubString等 长StrLength、串联接Concat以及求子串SubString等6 种操作构成串类型的最小操作子集。 种操作构成串类型的最小操作子集。 例如，可利用判等、 例如，可利用判等、求串长和求子串等操作实现串 的定位函数 Index(S,T,pos) 和串的置换操作 Replace(S,T,V)。 。 换句话说，如果在高级程序设计语言中设有"串类 换句话说，如果在高级程序设计语言中设有 串类 的话， 种操作， 型"的话，提供的基本操作不能没有这 种操作，因为它 的话 提供的基本操作不能没有这6种操作 首页 上页 下页 退出 们不能通过其它串操作实现。 们不能通过其它串操作实现。
第四章
串
——数据类型特殊的线性表 数据的表示和实现 4.3 串的模式匹配 4.4 串的应用
第四章
§4.1 串类型的定义
一、串的特点：数据元素为字符或字符串的线性表叫做串。 串的特点：数据元素为字符或字符串的线性表叫做串。 是由零个或多个字符组成的有限序列。 是由零个或多个字符组成的有限序列。 基本术语：长度、空串、空格串、位置、相等、主串、 基本术语：长度、空串、空格串、位置、相等、主串、 子串等。 子串等。 ADT定义 定义： 二、ADT定义：
第四章
int Index (String S, String T, int pos) { // T为非空串。若主串 中第 pos 个字符之后存在与 相等的子串， 为非空串。 个字符之后存在与T相等的子串 相等的子串， 为非空串 若主串S中第 // 则返回第一个这样的子串在 中的位置，否则返回 。 则返回第一个这样的子串在S中的位置 否则返回0。 中的位置， if (pos > 0) { n = StrLength(S); m = StrLength(T); // 求得串长 i = pos; while ( i <= n-m+1) { SubString (sub, S, i, m); // 取得从第 i 个字符起长度为 m 的子串 if (StrCompare(sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } // while } // if return 0; // S 中不存在满足条件的子串 } // Index 实现Index(S,T,pos)算法的基本思想 算法的基本思想为：从主串S中取“第 i 个字符起、 算法的基本思想 长度和串T相等的子串”和串T比较，若相等，则求得函数值为 i，否 则 i 值增1直至找到和串T相等的子串或者串S中不存在和T相等的子 串为止。即求使下列等式 StrCompare(SubString(S,i,StrLength(T)),T)==0 成立的 i 值。i 的初值应为 pos，在找不到的情况下，i 的终值应该是 n-m+1，其中，n 为S串的长度，m 为T串的长度。
首页
上页
下页
退出
第四章
个字符的有限序列。 串（string，或称字符串）是 n 个字符的有限序列。通常记作 ，或称字符串） s = " … " (n≥0) 其中， 是串的名 用双引号括起来的字符序列是串的值。 是串的名， 其中，S是串的名，用双引号括起来的字符序列是串的值。串 称为串的长度。含零个字符的串称为空串(null 中字符的数目 n 称为串的长度。含零个字符的串称为空串 string)，它的长度为零。在各种应用中，空格通常是串的字符集合 ，它的长度为零。在各种应用中， 中的一个元素，可以出现在其他字符之间。 中的一个元素，可以出现在其他字符之间。由一个或多个空格组成 的串称为空格串(blank string)，例如 的串称为空格串 ， " "，" "和" " ， 是三个空格串，它们的长度为串中空格字符的个数，分别为1， 是三个空格串，它们的长度为串中空格字符的个数，分别为 ， 5和8。为了清楚起见，以下将用符号 表示"空格符 和 。为了清楚起见，以下将用符号"Φ"表示 空格符 。 表示 空格符"。 串值必须用一对双引号括起来，但双引号本身不属于串， 串值必须用一对双引号括起来，但双引号本身不属于串，它 的作用只是为了避免与变量或数的常量混淆而已。 的作用只是为了避免与变量或数的常量混淆而已。
一、求子串位置的定位函数Index(S,T,pos)（BF方法） 求子串位置的定位函数Index(S,T,pos)（BF方法 方法） 算法：int Index(SString S,SString T, int pos) {
i=pos; j=1; while(i<=S[0] && j<=T[0]) { if (S[i]==T[j]) { ++i ; ++j ; } else { i=i-j+2 ; j=1 ;} } if (j>T[0]) return i-T[0]; else return 0; }
首页
上页
下页
退出
首页 上页 下页 退出
第四章
§4.2 串的表示和实现
1、定长顺序存储
表示： #define MAXSTRLEN 255 typedef unsigned Sstring[MAXSTRLEN+1]; 实现： Concat(&T,S1,S2) SubString(&Sub,S,pos,len)
类似于线性表的顺序存储结构， 类似于线性表的顺序存储结构，可用一组地址连续的 存储单元存储串值的字符序列。例如C和 存储单元存储串值的字符序列。例如 和C++语言中串不是 语言中串不是 预定义的数据类型，而是以字符数组来表示串。 预定义的数据类型，而是以字符数组来表示串。如声明 char str[10]; 是一个串变量。 语言中还规定了一个 语言中还规定了一个“串的 表明 str 是一个串变量。C语言中还规定了一个 串的 称为空终结符）， 结束标志 ‘\0’”（字符 ‘\0’称为空终结符），即数组中在该 （ 称为空终结符），即数组中在该 结束标志之前的字符是串变量的有效字符， 结束标志之前的字符是串变量的有效字符，但结束标志本 身要占一个字符的空间， 的值（字符序列） 身要占一个字符的空间，因此串变量 str 的值（字符序列） 的实际长度可在这个定义范围内随意，但最大不能超过9。 的实际长度可在这个定义范围内随意，但最大不能超过 。
数据对象：D={ai |ai ∈ CharacterSet , i=1,2,…,n, n>=0} 数据对象 数据关系：R1={<ai-1,ai>|ai-1,a i ∈ D} 数据关系 基本操作：(部分) 基本操作 StrAssign(&T,chars) StrCopy(&T,S) StrCompare(S,T) StrLength(S) Concat(&T,S1,S2) SubString(&Sub,S,pos,len) Index(S,T,pos) Replace(&S,T,V) StrInsert(&S,pos,T) StrDelete(&S,pos,len)
首页
上页
下页
退出
第四章
由于在一般情况下， 由于在一般情况下， 串的操作都是从前往后进 3、串的块链存储 行的， 行的，因此串的链表通常 #define CHUNKSIZE 80 不设双链，也不设头结点， 不设双链，也不设头结点， typedef struct Chunk { 但为了便于进行诸如串的 char ch[CHUNKSIZE]; 联接等操作，链表中还附 联接等操作， struct Chunk *next; 设有尾指针， 设有尾指针，并且由于串 }Chunk; 的长度不一定是结点大小 的整数倍（ 的整数倍（链表中最后一 typedef struct{ 个结点中的字符非都是有 Chunk *head, *tail; 效字符）， ），因此还需要一 效字符），因此还需要一 int curlen; 个指示串长的域。 个指示串长的域。称如此 } LString; 定义的存储结构为串的块 存储密度：串值所占的存储位 链存储结构 实际分配的存储位 以块链作存储结构时实现串的操作很不方便，如在串中 插入一个子串时可能需要分割结点，联接两个串时，若第一 个串的最后一个结点没有填满时还需要添加其它字符等等。 但在应用程序中，可将串的链表存储结构和串的定长结构结 合使用。 首页 上页 下页 退出