第四章 串

nullnull4.1 串的抽象数据类型的定义4.2 串的表示和实现4.3 串的模式匹配算法第四章 串null4.1 串的抽象数据类型的定义如下： ADT String { 数据对象：D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }串是有限长的字符序列，由一对单引号相括，如: a stringnull 基本操作： StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)nullSubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S)} ADT Stringnull StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。null DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty(S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。 StrEmpty(S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。 表示空串，空串的长度为零。 StrCompare(S,T) 初始条件：串 S 和 T 存在。 操作结果：若S  T，则返回值  0； 若S  T，则返回值  0； 若S  T，则返回值  0。 StrCompare(S,T) 初始条件：串 S 和 T 存在。 操作结果：若S  T，则返回值  0； 若S  T，则返回值  0； 若S  T，则返回值  0。例如：StrCompare(data, state) < 0 StrCompare(cat, case) > 0 StrLength(S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。 StrLength(S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如： Concate( T, man, kind) 求得 T = mankindnull SubString (&Sub, S, pos, len) 初始条件： 串 S 存在，1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。null例如： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9) 求得 sub = commander； SubString( sub, commander, 9, 1) 求得 sub = r；子串为“串”中的一个字符子序列nullSubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(student, 5, 0) = 起始位置和子串长度之间存在约束关系长度为 0 的子串为“合法”串 Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。 Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。 null假设 S = abcaabcaaabc, T = bcaIndex(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0； “子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。Index(S,T,pos)返回子串T在主串 S 中第pos个字符之后第一次出现的位置null Replace(&S,T,V) 初始条件：串S, T和 V 均已存在，且 T 是非空串。 操作结果：用V替换主串S中出现的所有与（模式串）T 相等的不重叠的子串。例如：假设 S = abcaabcaaabca，T = bca若 V = x， 则经置换后得到 S = axaxaax若 V = bc， 则经置换后得到 S = abcabcaabcnull StrInsert (&S, pos, T) 初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前 插入串T。例如：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = characternull StrDelete (&S, pos, len) 初始条件：串S存在 1≤pos≤StrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。 ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。 ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。 null 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；例如：C语言函数库中提供下列串处理函数：null在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。null 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。 StrCompare(SubString(S, i, StrLength(T)),T ) ? 0 S 串 T 串 T 串iposn-m+1算法的基本思想为：nullint Index (String S, String T, int pos) { // T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 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 ; } // while } // if return 0; // S中不存在与T相等的子串 } // Indexnull又如串的置换函数： S 串 T 串 V 串 V 串pospos subinews 串subnull 串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。null 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2 串的表示和实现null一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示null #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度一、串的定长顺序存储表示特点: 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。null Status Concat(SString S1, SString S2, SString &T) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; } // Concat例如：串的联接算法中需分三种情况处理： 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; } if (S1[0]+S2[0] <= MAXSTRLEN) {// 未截断 else if (S1[0] S.length || len < 0 || len > S.length-pos+1) return ERROR; if (Sub.ch) free (Sub.ch); // 释放旧空间 if (!len) { Sub.ch = NULL; Sub.length = 0; } // 空子串 else { } // 完整子串 return OK; } // SubString… …null Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch[0..len-1] = S[pos-1..pos+len-2]; Sub.length = len;null三、串的块链存储表示由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构，为了便于操作，再增加一个尾指针。块链结构可定义如下： #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;例题见P78 图4.2null 例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。null 这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。4.3 串的模式匹配算法 null初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。 操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数值为0。 首先，回忆一下串匹配(查找)的定义:INDEX (S, T, pos)null 下面讨论以定长顺序结构 表示串时的几种算法。一、简单算法二、首尾匹配算法三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法null第一趟匹配第二趟匹配第三趟匹配第四趟匹配第五趟匹配第六趟匹配a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b c a ca b c a ca b c a c一、简单算法（朴素匹配算法）算法思想： 用子串T中的字符依次与主串S中的字符比较： 若不匹配，将T右移一个字符，从头开始与S中字符依次比较； 如此反复执行，直到匹配成功或者一直将T移到无法与S继续比较为止，则匹配失败。子串T主串Snullint Index(SString S, SString T, int pos) { // 返回子串T在主串S中第pos个字符之后的位置。若不存在， // 则函数值为0。其中，T非空，1≤pos≤StrLength(S)。 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; } // Index一、简单算法算法简单，易于理解，但效率不高，主要原因是执行中有回溯在一般情况下m＜＜n ，O(m*n)null 先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个到 第n-1个字符。二、首尾匹配算法主串： “000000000000000000000000000000000000000000001” 模式串： “00000001”null int Index_FL(SString S, SString T, int pos) { sLength = S[0]; tLength = T[0]; i = pos; patStartChar = T[1]; patEndChar = T[tLength]; while (i <= sLength – tLength + 1) { if (S[i] != patStartChar) ++i; //重新查找匹配起始点 else if (S[i+tLength-1] != patEndChar) ++i; // 模式串的“尾字符”不匹配 else { } } return 0; }// 检查中间字符的匹配情况null k = 1; j = 2; while ( j < tLength && S[i+k] == T[j]) { ++k; ++j; } if ( j == tLength ) return i; else ++i; // 重新开始下一次的匹配检测nullKMP算法的时间复杂度可以达到O(m+n)三、KMP(D.E.Knuth, V.R.Pratt,J.H.Morris) 算法模式匹配：子串T(模式p）在主串S中的定位操作(m< pj 时， 已经得到的结果：si-j+1..si-1 == p1..pj-1 若已知 p1..pk-1 == pj-k+1..pj-1 则有 si-k+1..si-1 == p1..pk-1null定义：模式串的next函数null int Index_KMP(SString S, SString T, int pos) { // 1≤pos≤StrLength(S) i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if (j = =0 || S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符 else j = next[j]; // 模式串向右移动 } if (j > T[0]) return i-T[0]; // 匹配成功 else return 0; } // Index_KMPnull这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串求next函数值的过程是一个递推过程，分析如下:已知：next[1] = 0；假设：next[j] = k；又 T[j] = T[k]则： next[j+1] = k+1若： T[j]  T[k] 则需往前回朔，检查 T[j] = T[ ？]nullvoid get_next(SString T,int next[]) { // 求模式串T的next函数值并存入数组next。算法4.7 int i=1,j=0; next[1]=0; // T的第1个字符与主串“失配”时，主串的下一字符与T的第1个字符比较 while(i1时，next[2]=1 if(j==0||T[i]==T[j]) // 初态或两字符相等 { ++i; // 各+1继续向后比较 ++j; next[i]=j; // 主串和T在第i个字符不匹配时，前j-1个字符是匹配的，只须与第j个字符比较 } else // 两字符不等 j=next[j]; // j减小到前面字符相等之处 }null还有一种特殊情况需要考虑： 例如： S = aaabaaabaaabaaabaaab T = aaaabnextval[j]=00004next[j]=01234null void get_nextval(SString &T, int &nextval[]) { i = 1; nextval[1] = 0; j = 0; while (i < T[0]) { if (j = 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) nextval [i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } // get_nextvalnull 1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它操作的方法。 2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其上实现串操作的基本方法。本章学习要点 4. 理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值。