严蔚敏数据结构课件第四章.ppt

第四章 串,4.1 串的抽象数据类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,4.1 串的抽象数据类型的定义如下：,ADT String {,数据对象：,D＝{ ai |ai∈CharacterSet, i=1,2,.,n, n≥0 },数据关系：,R1＝{ | ai-1, ai ∈D, i=2,.,n },串是有限长的字符序列，由一对双引号相括，如:  a string ,基本操作：,,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (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),ClearString (&S),,} ADT String,StrAssign (&T, chars) 初始条件：chars 是字符串常量。

操作结果：把 chars 赋为 T 的值StrCopy (&T, S) 初始条件：串 S 存在 操作结果：由串 S 复制得串 TDestroyString (&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, state) 0,,StrLength (S) 初始条件：串 S 存在 操作结果：返回 S 的元素个数， 称为串的长度Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在 操作结果：用 T 返回由 S1 和 S2 联接而成的新串例如： Concate( T, man, kind) 求得 T = mankind,,SubString (&Sub, S, pos, len) 初始条件： 操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。

串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1例如： SubString( sub, commander , 4, 3),子串为“串”中的一个字符子序列,求得 sub = man  ;,SubString( sub, commander  , 1, 9),SubString( sub, commander , 9, 1),求得 sub = r ,求得 sub = commander ,SubString(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。

假设 S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Index(S, T, 3) = 6;,Index(S, T, 8) = 0;,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序Replace (&S, T, V) 初始条件：串S, T和 V 均已存在， 且 T 是非空串 操作结果：用 V 替换主串 S 中出现 的所有与（模式串）T 相等的不重叠的子串例如：,假设 S = abcaabcaaabca, T = bca ,若 V = x , 则经置换后得到 S = axaxaax ,若 V = bc , 则经置换后得到 S = abcabcaabc,bca,bca,bca,,StrInsert (&S, pos, T) 初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1 操作结果：在串S的第pos个字符之前 插入串T例如：S = chater ，T = rac ， 则执行 StrInsert(S, 4, T) 之后得到 S = character ,,StrDelete (&S, pos, len) 初始条件：串S存在 1≤pos≤StrLength(S)-len+1。

操作结果：从串S中删除第pos个字符 起长度为len的子串ClearString (&S) 初始条件：串S存在 操作结果：将S清为空串对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；,例如：C语言函数库中提供下列串处理函数：,串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集在上述抽象数据类型定义的13种操作中，,即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子 集上实现例如，可利用串比较、求串长和求子串等操作实现定位函数 Index( S, T, pos )。

StrCompare(SubString(S, i, StrLength(T)), T ),S 串,T 串,,,,T 串,,,i,pos,,n-m+1,算法的基本思想为：,? 0,int Index (String S, String T, int pos) { // T为非空串若主串S中第pos个字符之后存在与 T相等的子串， // 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos 0) { } // if return 0; // S中不存在与T相等的子串 } // Index,n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) { } // while,SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ;,又如串的置换函数：,S 串,T 串,V 串,,,,,V 串,,pos,,pos,sub,,i,news 串,sub,= i+m,,pos,,,n-pos+1,void replace(String& S, String T, String V) { },while ( pos = n-m+1 }//if }//while,SubString(sub, S, pos, n-pos+1); // 剩余串 Concat( S, news, sub );,n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别 性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象在程序设计语言中，串只是 作为输入或输出的常量出现，则只 需存储此串的串值，即字符序列即 可但在多数非数值处理的程序中， 串也以变量的形式出现4.2 串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”,特点:,,,Status Concat(SString S1, SString S2, SString } // Concat,例如：串的联接算法中需分三种情况处理：,T[1S1[0]] = S1[1S1[0]]; T[S1[0]+1S1[0]+S2[0]] = S2[1S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; },if (S1[0]+S2[0] = MAXSTRLEN) {// 未截断,else if (S1[0] MAXSTRSIZE) { // 截断,else { // 截断(仅取S1),T[1S1[0]] = S1[1S1[0]]; T[S1[0]+1MAXSTRLEN] = S2[1MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; },T[0MAXSTRLEN] = S1[0MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; },typedef struct { char *ch; // 若是非空串，则按串实用长度分配 //存储区，否则 ch 为NULL int length; // 串长度 } HString;,二、串的堆分配存储表示,通常，C语言中提供的串类型就是以这种存储方式实现的。

系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆” C语言中的串以一个空字符为结束符， 串长是一个隐含值这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制Status Concat(HString } // Concat,Status SubString(HString } // SubString,… …,if(!(Sub.ch = new char[len])) return ERROR; Sub.ch[0len-1] = S.ch[pos-1pos+len-2]; Sub.length = len;,,void StrInsert (Hstring // 暂存 S if (tlen0) // T 非空，则为S重新分配空间并插入T { } } // 。