for（i=1;i<=t1->length;i++）S->ch[i]=t1->ch[i];
for（i=1;i+t2->length<=n;i++）S->ch[i+t1->length]=t2->ch[i];
S->length=n;
}
else{//第三种情况
for（i=1;i<=n;i++）S->ch[i]=t1->ch[i];
S->length=n;
}
}//Concat
2.求子串操作
SqString*SubString（SqString*S,intpos,intlen）
{//返回S串中的第pos个字符起长度为len的子串
SqString*sub;
inti;
if（pos<1||pos>S->length||len<0||len>S->length-pos+1）{
printf（“参数错误”）;
sub->length=0;
}
else{
for（i=1;i<=len;i++）sub->ch[i]=S->ch[pos+i-1];
sub->length=len;
}
returnsub;
}//SubString
顺序串有一个缺点，就是串空间的大小都是静态的，这种定长的串空间难以适应插入、联接等操作。
在实际应用中常采用一种称为堆结构的动态存储结构，下面介绍堆分配存储结构的串。
4.3串的堆分配存储结构及其运算
4.3.1串的堆分配存储结构
串的堆分配存储结构仍以一组地址连续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的。
利用函数malloc（）为每一个新产生的串分配一块实际需要的存储空间，若分配成功，则返回一个指针，指向串的起始地址。
串的堆分配存储结构描述如下：
typedefstruct
{char*ch;
intlength;
}HString;
4.3.2串的堆分配存储结构的基本操作
1.联接操作
voidConcat_h（HString*S,HString*t1,HString*t2）
{//将串t1和串t2联接而成的新串存入S中
inti;
S->ch=（char*）malloc（（t1->length+t2->length）*sizeof（char））;
for（i=1;i<=t1->length;i++）S->ch[i]=t1->ch[i];
for（i=1;i<=t2->length;i++）S->ch[i+t1->length]=t2->ch[i];
S->length=t1->length+t2->length;
}//Concat_h
2.求子串操作
HString*SubString_H（HString*S,intpos,intlen）
{//返回S串中的第pos个字符起长度为len的子串
HString*sub;
inti;
if（pos<1||pos>S->length||len<0||len>S->length-pos+1）{
sub->ch=NULL;sub->length=0;
}
else{
sub->ch=（char*）malloc（len*sizeof（char））;
for（i=1;i<=len;i++）sub->ch[i]=S->ch[i+pos-1];
sub->length=len;
}
returnsub;
}//SubString_H
4.4串的链接存储结构
和线性表类似，串也可采用链式方式存储串值。
由于串结构非常特殊，它结构中的每个数据元素都是一个字符，那么用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。
例如图4-2（a）是结点大小为4（即每个结点存放4个字符）的链表，图4-2（b）是结点大小为1的链表。
当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“＃”或其他的非串值字符。
（a）结点大小为4的链表
（b）结点大小为1的链表
图4-2串值的链表存储方式
串的链式数据类型中结点大小为1的结点描述如下：
typedefstructNode
{chardata;
structNode*next;
}LinkString;
串值的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的说来不如另外两种存储结构灵活，它占用存储量大且操作复杂。
串值在链式存储结构时串操作的实现和线性表在链式存储结构中的操作类似，故在此不作详细讨论。
4.5应用举例及分析
例4_1在串的顺序定长存储结构上实现子串的定位Index（S,T）操作。
子串的定位操作通常称作串的模式匹配（其中T称为模式），是各种串处理系统中最重要的操作之一。
下面算法是利用判等、求子串等操作来实现函数Index（S,T）的。
算法的思路是：
在主串S中从i=1开始取一长度和串T长度相等的子串与串T进行比较，若相等，则函数返回i；否则i增加1，从i＝2开始取一长度和串T长度相等的子串与串T进行比较，重复上述的过程，直至确定在串S中取不到和串T长度相等的子串为止，函数返回0。
或在S中取到一个和串T相等的子串，函数返回i。
操作过程如4-3图所示：
图4-3串的定位操作示意图
intIndex（SqString*S,SqString*t）
{inti,n,m,flag;
n=S->length;
m=t->length;
flag=0;
i=1;
while（i<=n-m+1&&（!
flag））{
if（StrCompare（SubString（S,i,m）,t））flag=1;
elsei++;
}
if（flag）returni;
elsereturn0;
}//Index
如不调用其他的串操作函数，算法如下：
intIndex_2（SqString*S,SqString*t）
{inti=1,j=1;
while（i<=S->length&&j<=t->length）
if（S->ch[i]==t->ch[i]）{
i++;j++;
}
else{
i=i-j+2;
j=1;
}
if（j>t->length）returni-t->length;
elsereturn0;
}//Index_2
例4_2一个文本串可用事先给定的字母映射表加密。
例如，设字母映射表为：
abcdefghijklmnopqrstuvwxyz
ngzqtcobmuhelkpdawxfyivrsj
则字符串"encrypt"被加密为"tkzwsdf"。
试写一算法将输入的文本串加密后输出，以及另一算法解密后输出。
Charkey[26]={‘n’,‘g’,‘z’,‘q’,‘t’,‘c’,‘o’,‘b’,‘m’,‘u’,‘h’,‘e’,‘l’,‘k’,‘p’,‘d’,‘a’,‘w’,‘x’,‘f’,‘y’,‘i’,‘v’,‘r’,‘s’,‘j’,}
voidEncrypt（char*S）
{inti=0,k=0;
while（S[i]!
=NULL）{
k=（int）（S[i]!
=NULL）
S[i]=key[k];
i++;
}
}//Encrypt
voidDecrypt（char*S）
{inti=0;k;
while（S[i]!
=NULL）{
k=0;
while（S[i]!
=key[k]）k++;
S[i]='a’+k;
i++;
}
}//Decrypt
4.6上机实验
4.6.1实验目的
⑴掌握字符串的基本操作。
⑵加深对字符串的理解，逐步培养解决实际问题的编程能力。
4.6.2实验内容
⑴采用顺序结构存储串，编写一个函数SubStr（str1,str2），用于判定str2是否为str1的子串。
设str1="a0a1…am"，str2="b0b1…bn"。
从str1中找与b0匹配的字符ai，若ai=b0，则判定ai+1=b1，…ai+n=bn；若都相等，则结果是子串，否则继续比较ai之后的字符。
⑵编写一个函数，实现在两个已知字符串中找出所有非空最长公共子串的长度和最长公共子串的个数。
设两个字符串的首结点指针分别为str1和str2，它们的长度分别记为length1和length2。
设有length1>length2，则它们最长的公共子串长度不超过length2。
本章小结
⑴串又称为字符串，是一类特殊的线性表，它的每个元素仅由一个字符组成。
⑵一个串可以包含若干个子串。
子串是指由串中任意个连续字符组成的子序列，串的最大子串是它自身，最小子串是空串（长度为零的串）。
对串的操作，往往针对一组连续的字符进行。
⑶空串与空格串是不相同的，空串的长度为0，空格串的长度是指包含的空格个数。
⑷两个串相等的充分必要条件是它们的长度相等且对应位置上的字符相同。
⑸本章讨论字符串的基本概念，存储方法和串的基本操作。
练习题
一、选择题
1.串是由0个或多个字符组成的有限序列，它是一种特殊的线性表，其特殊性表现在（ ）。
A.可以采用顺序和链式存储B.每一个元素都只有一个前驱和后继
C.删除和插入操作只能在一端进行D.每一个数据元素都是一个字符
2.空格串是指（ ）。
A.一个字符也没有的字符串B.由若干个任意字符组成的字符串
C.由零个字符组成的字符串D.只含空格字符的字符串
3.设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）。
A.插入子串B.连接子串C.模式匹配D.替换子串
4.在字符串的替换操作中，设替换前的字符串为str="ABCDEFG",把从第2个字符开始的连续3个字符替换成"abcd"，则替换后str="（ ）"。
A.AabcEFGB.AabcBCDEFGC.AabcdEFGD.AabcdBCDEFG
5.下列对串的存储结构叙述不正确的是（ ）。
A.串可以采用顺序存储也可以采用链式存储
B.顺序串可以采用静态数组来存储也可以采用动态数组来存储
C.串在存储时需附加存储一个结束标志
D.串中的每一个数据元素都是一个字符，故串只能采用字符数组来存储
二、填空题
1.串的两种最基本的存储方式是 和 。
2.两个串相等的充分必要要件是 。
3.空串是 ，其长度等于 。
4.空格串是 ，其长度等于 。
5.设S="I└┙AM└┙A└┙TEACHER",其长度是 。
6.设S1="GOOD",S2="└┙",S3="BYE!
",则S1、S2和S3连接后的结果是 。
7.已知substr（s,i,len）函数的功能是返回串s中第i个字符开始长度为len的子串，strlen（s）函数的功能是返回串s的长度。
若s="ABCDEFGHIJK"，t="ABC"，则执行strlen（t）后的返回值为 ，执行substr（s,strlen（t）,strlen（t））后的返回值为（）。
8.已知s1="I’mastudent",s2="student",s3="teacher",则StrLength（s1）的结果是 ；Concat（s2,s3）的结果是；StrDelete（s1,4,10）的结果是 。
三、问答题
1.串是由字符组成的有限序列，长度为1个串与单个字符是否等同？
2.串有哪几种存储结构？
3.串是由字符构成的特殊线性表、串的操作与线性表的操作主要不同之处是什么？
4.分别写出串的静态数组存储结构和串的动态数组存储结构的定义。
5.简述空格串的定义及其长度。
四、算法及程序设计题
1.若X和Y是两个单链表存储的串，试设计一个算法，找出X中第一个不在Y中出现的字符来。
2.在链串中，设计一个算法把最先出现的子串"ab"改为"xyz"。
升级会员 