下载文档原格式
串串（String）又叫做字符串，是一种特殊的线性表的结构，表中每一个元素仅由一个字符组成。
随着计算机的发展，串在文字编辑、词法扫描、符号处理以及定理证明等诸多领域已经得到了越来越广泛的应用。
第一节串的定义和表示1、串的逻辑结构定义串是由零个到任意多个字符组成的一个字符序列。
一般记为：S=’ a1a2a3……a n’(n>=0)其中S为串名，序列a1a2a3……a n为串值，n称为串的长度，我们将n=0的串称为空串(null string)。
串中任意一段连续的字符组成的子序列我们称之为该串的子串，字符在序列中的序号称为该字符在串中的位置。
在描述中，为了区分空串和空格串(s=‘’)，我们一般采用来表示空串。
2、串的基本操作串一般包含以下几种基本的常用操作：1、length(S)，求S串的长度。
2、delete(S,I,L)，将S串从第I位开始删除L位。
3、insert(S,I,T)，在S的第I位之前插入串T。
4、str(N,S)，将数字N转化为串S。
5、val(S,N,K)，将串S转化为数字N；K的作用是当S中含有不为数字的字符时，K记录下其位置，并且S没有被转化为N。
3、串的储存结构一般我们采用以下两种方式保存一个串：1、字符串类型，描述为：const n=串的最大长度type strtype=string[n]这里由于tp的限制，n只能为[1..255]。
在fp或者delphi中，我们还可以使用另外一种类型，描述为：const n=串的最大长度type strtype=qstring[n]这里的n就没有限制了，只要空间允许，开多大都可以。
2、数组来保存，描述为：const n=串的最大长度type strtype=records:array[1..n] of char;len:0..n;end;第二节模式匹配问题与一般的线性表不同，我们一般将串看成一个整体，它有一种特殊的操作——模式匹配。
串类型定义串表示和实现串模式匹配算法串操作应用举例串类型的定义串的表示和实现串的模式匹配算法串操作应用举例 4.1 串类型的定义基本概念 ADT串的定义 4.2 串的表示和实现堆分配存储结构表示时的（只含最小操作子集）基本操作的算法描述 4.3 串的模式匹配算法 4.4 串操作应用举例 else T[0..STRLEN] S1[0..STRLEN];// T[0] S1[0] STRLEN uncut FALSE; return uncut; // Concat 在串的顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于字符序列的长度。
二、串的堆分配存储表示堆分配存储类似于线性表的顺序存储结构，仍以一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。
在C语言中是由动态分配函数malloc 和free 来管理一个称之为“堆（heap）”的自由存储区的。
该存储结构类型描述如下： typedef struct char *ch ; // 若是非空串，则按串长分配存储区，//否则ch为NULL int length; // 串长度一个串值的确定是通过串在堆中的起始位置和串的长度实现的。
HString; 这类串操作实现的算法为: 先为新生成的串（若该串已存在,则先释放其所占空间）分配一个长度适当的存储空间，然后进行串值的复制。
这种存储结构表示时的串操作仍基于“字符序列的复制”进行的。
为此，串名与串值之间要建立一个对照表。
0 1 2 3 4 5 6 7 8 9 HString a,b ; 42012 b 4 2000 a 长度 ??length 基址 ??ch 串名 k o o B e r u t c u r t S a t a D ……16 2000＋串插入算法 Status StrInsert Hstring &S, intpos, Hstring T //在串S的第pos个字符之前插入串T S.ch 0 1 pos-1 T.length if pos 1 || pos S.length+1 return ERROR； ifT.length //T非空，则重新分配空间，插入T if ! S.ch char * ralloc S.ch , S.length +T.length *sizeof char exitOVERELOW ； for i S.length-1;i pos - 1;--i //插入T而腾出位置 S.ch[i +T.length] S.ch[i] ； S.ch[pos - 1.. pos+T.length - 2] T.ch[0.. T.length - 1]; //插入TS.length ＋ T.length; return OK ; Status StrAssignHString &T,char *chars //生成一个其值等于串常量chars的串T if T.ch free T.ch ; //若串T已存在,释放其所占空间 for i0, c chars ; c ; ++i, ++c ; if ! i T.ch null; T.length 0;else if ! T.ch char * malloc i*sizeof charexit OVERFLOW ; T.ch[0..i-1] chars[0..i-1]; T.lengthi; return OK ; int StrLength HString s return s.length; int StrCmpare HString S , HString T for i 0; i S.length && iT.length; ++i if S.ch[i]! T.ch[i] returnS.ch[i] －T.ch[i] ; return S.length－T.length;Status ClearString HString &S if S.ch free S.ch ; s.ch null;S.length 0; return OK; Status Concat HString &T,HString S1, HString S2 // 用T返回由S1和S2联接而成的新串 if T.ch free T.ch ; // 释放旧空间 if ! T.ch char * malloc S1.length+S2.length *sizeof char exit OVERFLOW ; T.ch[0..S1.length-1] S1.ch[0..S1.length-1];T.length S1.length + S2.length; T.ch[S1.length..T.length-1]S2.ch[0..S2.length-1]; return OK; // Concat Status SubStringHString &Sub, HString S, int pos, int len if pos 1 || posS.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 // 完整子串 Sub.ch char * malloc len*sizeof char ; Sub.ch[0..len-1] S[pos-1..pos+len-2];Sub.length len; return OK; // SubString 三、串的块链存储表示?? 可采用链表方式存储串值，每个结点可以存放一个字符，也可以存放多个字符（如图所示）。
