第四章 串
教学目的与要求
本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。
重点和难点
本章重点是掌握串上实现的模式匹配算法，其也是本章难点。 教学内容
第一节 串的基本概念 ４.1.1 基本概念
串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为串的长度。
空串：长度为0的串称为空串，它不包含任何字符。
空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空白串的区别。
子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。
子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符对应的主串中的序号定义为子串在主串中的位置。 ２．串的基本运算
（１）求串的长度（Length） （２）串复制 (Copy)： （３）串联接 (Concat)
（４）串比较 (Compare) （５）字符定位(Index)
除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等操作。这些操作，一般可由这些基本操作实现。 第二节 串的存储结构 4.2.1串的顺序存储 1.静态存储分配的顺序串
顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义形式为
# define maxstrsize 256
typedef char Seqstring[maxstrsise];
利用类型描述符Seqstrsring可定义数组变量存储串，利用特定字符表示串的结束(Ｃ语言用转义字符’\\0’) 。例如Seqstrstring s; 变量s可存储长度不超过255个字符的字符串，以’\\0’作为串的结束。
顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组的基础上，引入描述长度的成员。其定义形式为 # define maxstrsize 256 typedef struct {
char ch[maxstrsise]; int length; }Sqestring;
(2)动态存储分配的顺序串(堆)
上述两种方式的共同缺点是主串值的存储空间是静态分配的是定长的。动态分配则克服了上述缺点，其余定义形式为 typedef struct {
char *ch; int length; }Hstring;
成员ch为指针型，若串非空，按实际需要动态分配存储空间，ch指向其起始地址，否则ch为FULL。成员length存储串长度。 (3)串的链式存储
用单链表的方式来存储串值，就是串的链式存储，简称为链串。每个结点可以存储一个字符(数据域data为字符型)，也可以存储多个字符(数据域data定义为字符型数组)。 3．基本运算的实现
串匹配算法很多，这里只讨论的是一种简单的朴素的串匹配算法。
在串匹配中，一般将主串称为目标（串），子串称为模式（串）。设T为目标串，设P为模式串。串匹配实际上是对合法的位置0≤i≤n-m，依次将目标串中的子串T[i..i+m-1]和模式串P[0..m-1]进行比较，若相等，则称从位置i开始的匹配成功，否则，则称从位置i开始的匹配失败。位置i称为位移，匹配成功时，位置i称为有效位移，匹配失败时，位置i称为无效位移。
(1) 顺序串上的子串的定位运算(模式匹配) 算法思想：
通过一个循环依次检查n-m+1个合法的位移i(0≤i≤n-m)是否为有效位移。i初值为0，终值为n-m，其确定了目标串中子串的起始位置，每趟匹配结束后通过i值加1（i++）使i指向下一合法位移。 Ｃ语言算法：
Int naivestrmatch(Seqstring T, Seqstring P)
{//查找模式P在目标T中首次出现位置，成功时返回有效位移i,失败返回-1
int i,j,k;
int m=P.length, n=T.length;//模式和目标串的长度
for (i=0;i<=n-m;i++) //循环控制匹配的趟数，其由合法位移的个数确定
{ j=0;k=i; //确定模式串起始位置j、目标串动中子串的起始位置k，即合法位移i
while (j if (j==m) //退出while循环若j==m说明匹配成功 return(i); } return –1; //退出外循环，说明没有有效位移，匹配失败 } 算法时间复杂度为O（n-m+1）m) (2)链串上的子串的定位运算(模式匹配) 算法思想： 算法思想与顺序串上的子串的定位运算完全相同。但应注意，存储结构不同将导致算法实现时具体操作的不同。 Ｃ语言算法： Linkstrnode *linkstrmatch(Linkstring T,Linkstring P) { //查找模式P在目标T中首次出现位置，成功时返回有效位移shift,失败返回NULL Linkstrnode *shift,*t1,*p1; Shift=T; t1=shift;p1=P;//工作变量初始设置t1指向子串的起始位置，p1指向模式的起始位置 while (t1&&p1) //循环控制匹配 p1为NULL 匹配成功,t1为NULL且 p1不为NULL 匹配失败 {if (t1->data==p1->data) {t1=t1->next; p1=p1->next; } else { shift=shift->next; t1=shift;p1=P;} } //对应结点字符相等,t1,p1后移指向下一结点，否则，合法 位移shift后移指向下一子串，t1、p1重新定位开始下趟匹配。 if (p1==NULL) return shift; else return NULL; }//退出循环后，判定匹配成功与否 算法时间复杂度与顺序串上的子串的定位运算相同。 分析： 顺序串和链串上实现串的模式匹配，算法思想相同，但应注意，存储结构不同所导致的算法实现时具体操作上的区别。在顺序串上位移为整数，链串上位移为结点的地址；子串与模式匹配时工作变量后移在顺序串上通过加1实现，链串上靠指针变量后移实现；匹配成功与否的判令条件顺序串上为j==m，链串上为p==NULL。 对于不同的存储结构能够写出算法这是学习数据结构的基本要求，改变存储结构要求应写出算法这也是一个重点。这一点大家应给予足够的重视。 应用举例 算法阅读题 １．下列算法的功能是比较两个链串的大小，其返回值为： -1 s1 请在空白处填入适当的内容。〖2001〗 int comstr(linkstring s1,linkstring s2) {//s1和s2为两个链串的头指针 while(s1&&s2) { if(s1->data if( ③ ) return –1; if( ④ ) return 1; ⑤ ; } 〖分析〗该题考核点是串的比较操作。While型循环通过指针s1、s2将两个串中字符逐一比较，若发现不等字符，则不等字符的大小就是两个串的大小；若所比较字符均相等，直到有串被扫描完为止，退出循环。然后判断，若某个串未被扫描完，则其值大，若两个串同时被扫描完，则两个串相等。 〖答案〗① s1=s1->next; ② s2=s2->next; ③ s2(或s2!=NULL) ④ s1(或s1!=NULL) ⑤ return 0 ２． 编写算法实现现两个串的连接。 算法如下: void stringcat(Hstring S,Hstring T) {char *p,*q; p=S.ch+S.length; q=t.ch; while(p if(q ３． 删除主串中所有指定子串。 算法如下： void delsubstring(Hstring S,Hstring T) {int i=0,j,k; while(i {for(j=i,k=0;k break; if(k>=T.length) {while(j S.length=S.length-T.length;} else i++; } } 【历届试题分析】 一、选择题 1． 下所述中正确的是（ ）〖2001〗 A． 串是一种特殊的线性表 B． 串的长度必须大于零 C． 串中元素只能是字母 D． 空串就是空白串 〖答案〗A 2．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）〖2001〗 A．O(n/3) B．O(n) C．O(n2) D．O(n3) 〖分析〗最坏情况下模式匹配的时间复杂度为O((n-[n/3]+1)*[n/3]),由于n和[n/3]是同阶的，所以，时间复杂度可写为O(n2)。 〖答案〗C 3．设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）〖2003〗 A．联接 B．求子串 C．字符定位 D．子串定位 〖分析〗该题考核点是串的基本操作。 〖答案〗D 4．为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ） 〖2002〗 A．插入 B．删除 C．串联接 D．子串定位 〖答案〗D 5．已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=\，则调用函数Scopy(P,Sub(S,1,7))后得到( )〖2002〗 A．P=\ B．P=\ C．S=\ D．S=\ 〖分析〗该题考核点是串的基本操作，函数Scopy(P,Sub(S,1,7))将串中子串″SCIENCE″复制到P中，而串S值未变。正确答案为A。 〖答案〗A 二、填空题 6．在串S=\中，以t为首字符的子串有 12 个。〖2001〗 〖分析〗该题考核点是子串的概念。其中存在两个长度为1的子串。 〖答案〗12 7．串S=\I am a worker\的长度是________。〖2002〗 〖分析〗该题考核点是串长度的概念。 〖答案〗13 8．设S1=\\，则S1，S2和S3依次联接后的结果是____________。〖2003〗 〖分析〗该题考核点是串的连接操作及空白串的概念。 〖答案〗\book\ 三、算法阅读题 9．下列算法的功能是比较两个链串的大小，其返回值为： -1 s1 1 s1>s2 请在空白处填入适当的内容。〖2001〗 int comstr(linkstring s1,linkstring s2) {//s1和s2为两个链串的头指针 while(s1&&s2) { if(s1->data if( ③ ) return –1; if( ④ ) return 1; ⑤ ; } 〖分析〗该题考核点是串的比较操作。While型循环通过指针s1、s2将两个串中字符逐一比较，若发现不等字符，则不等字符的大小就是两个串的大小；若所比较字符均相等，直到有串被扫描完为止，退出循环。然后判断，若某个串未被扫描完，则其值大，若两个串同时被扫描完，则两个串相等。 〖答案〗① s1=s1->next; ② s2=s2->next; ③ s2(或s2!=NULL) ④ s1(或s1!=NULL) ⑤ return 0 同步练习题 一、 选择题 1．下列有关字符串的描述，正确的是（ A ） A. B. C. D. 字符串是0个或多个字符构成的有限序列； 字符串是0个或多个字母不同的有限序列； 字符串中最少要有一个子符； 字符串中不能有空格字符。 2． 字符串S=＂string＂中，包含的子串的个数是（C ）(空串) A. 20 B. 21 C. 22 D. 23 3．目标串为T=＂this is a string＂,模式串P=＂string＂,进行模式匹配，有效位移是（C ）（起始位置为0）。 A. 9 B. 10 C. 11 D. 12 4．已知串S= ＂string＂，T=＂this＂,执行运算strlen(strcopy(S,T))的结果是（A ） A. 4 B. 6 C. 10 D. 2 5．目标串为T=＂this is a string＂,模式串P=＂string＂,进行模式匹配，所有的无效位移数是（ B ） A. 6 B. 10 C. 16 D. 11 6．下列命题正确的是（C ） A. 空串就是空白串； B. 空串不是串； C. 空串是长度为0的字符串 D. 串相等指的是长度相等 7．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为（D ） A. 50% B. 25% C. 75% D. 20% 8．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数（C ） A . n B. n*m C. (n-m+1)*m D. m 9．当目，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数（B ） A. n B. m C. n+m D n-m 10．字符串是一种特殊的线性表，它与一般线性表的区别是（ ） A. 字符串是一种线性结构； B. 字符串可以进行复制操作； C. 字符串由字符构成并且通常作为整体参与操作； D. 字符串可以顺序存储也可以链式存储。 二、填空题 1．空串的长度为 0 ，空格串（空白串）的长度为 空格数 。 2．子串的定位运算又称为 ，通常把主串又称为 目标 子串又称为 模式 。 3．成功匹配的起始位置称为 有效位移 ，匹配失败的起始位置称为 无效位移 。 4．设目标串为T=＂abccdadeef＂，模式串P=＂ade＂，则第 6 趟匹配成功。 5．已知串T=＂abccdadeef＂，P=＂abccyde＂,函数strcmp(T,P)的运算结果是 <0 。 6．串朴素的模式匹配算法在顺序串和链串上运行，时间复杂度o(m+n) 。 7． 已知串T=＂abccdadeef＂,T中包含以b打头的子串有 9 个。 8．通常在程序设计中，串分为 串常量 和 串变量 。 9．按存储结构通常分为 顺序 和 链式 。 10．设s1=＂GOOD＂,s2=＂ ＂ ,s3=＂BYE!＂，则s1,s2,和s3连接后的结果是 。 三．阅读程序题 1． 指出程序功能 int stringcmp(Hstring S,Hstring T) {int i=0,tag=1; if (S.length!=T.length) tag=0; else while(i if (S.ch[i]==T.ch[i]) i++; else tag=0; return tag; } 2．阅读程序 int stringpatindex (Hstring S,Hstring T) {int i,j,k; for(i=0;i {for(j=i,k=0;k break; if(k>=T.length) return i; } return –1; } （1）指出程序功能； （2）设S中存储＂there are a string＂ ，T中存储＂??r＂函数的返回值是什么？ 3．阅读程序指出程序功能 void restring(Hstring S) {char *p,*q,c; p=S.ch;q=S.ch+S.length-1; while(p p++;q--; } } 四、程序设计题 1． 编写算法实现两个串的连接。 2． 设计算法删除主串中所有指定子串 3． 编写算法判断串是否为回文 同步练习题答案 一、选择题 1．A 2．C 3．C 4．A 5．B 6．C 7．D 8．C 9．B 10．C 二、 填空题 1．0， 包含空格的的数；2．模式匹配，目标串，模式串；3．有效位移，无效位移； 4．6； 5．＜0； 6．O(m+n); 7．9； 8．串常量，串变量； 9．顺序串，链串； 10．GOOD BYE! 三．阅读程序题 1．【答案】判断两个串是否相等，若相等返回1，否则返回0。 2．【答案】（1）带通配符？的子串定位函数；（2）返回值为1。 3．【答案】将一个串逆置。 四、程序设计题 ４．实现两个串的连接算法: void stringcat(Hstring S,Hstring T) {char *p,*q; p=S.ch+S.length; q=t.ch; while(p if(q ５．删除主串中所有指定子串算法： void delsubstring(Hstring S,Hstring T) {int i=0,j,k; while(i {for(j=i,k=0;k break; if(k>=T.length) {while(j S.length=S.length-T.length;} else i++; } } 3．判断串是否为回文算法： int tringcomp(Hstring S,Hstring T) {char *p,*q; p=S.ch;q=S.ch+S.length-1; while(p if(p>=q) return 1; return 0; } 课后习题解答 基础知识题 1． 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串5、目标考核模式串；有效位移和无效位移。 【答案】略 2．假设有如下的串说明char s1[30]=＂Stocktom,CA＂,s2=＂March 5,1999＂,s3[30],*p; (1) 在执行下列语句后，P的值是什么？ p=strchr(s1,＇t＇); p=str(s3,＇9＇); p=strchr(s2,＇6＇); (2) 在执行下列语句后，S3的值是什么？ strcpy(s3,s1); strcat(s3,＂,＂); strcat(s3,s2); (3) 调用函数strcmp(s1,s2)的返回值是什么？ (4) 调用函数strcmp(&s1[5],＂tom＂)的返回值是什么？ (5) 调用函数strlen(strcat(s1,s2))的返回值是什么？ 【答案】 （1）p的值依次为字符t在串s1中的位置,字符9在串s3中的位置，字符6在串s2中的位置。 （2）执行语句strcpy(s3,s1); 后，S3的值是：＂Stocktom,CA＂ 执行语句strcat(s3,＂,＂); 后，S3的值是：＂Stocktom,CA,＂ 执行语句strcat(s3,s2); 后，S3的值是：＂Stocktom,CA,March 5,1999＂ （3）调用函数strcmp(s1,s2)的返回值是：大于0； （4）调用函数strcmp(&s1[5],＂tom＂)的返回值是：大于0 （5）调用函数strlen(strcat(s1,s2))的返回值是：s1和s2联接后的串长度：23 3． T[0..n-1]=＂abaabaabcaabaa＂，P[0..m-1]=＂aab＂。当用模式串P匹配目标串，请给出所有的有效位移。 算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 【答案】所有的有效位移依次为：2，5，9；算法NaiveStrMatch(T,P)返回的位移是：2 算法设计题 4． 利用C的库函数strlen,strcpy和strcat写一个算法void strinsert(char *S，char *T,int i)，将串T插入到串 S的第i个位置上。若i大于S的长度，则插入不执行。 【答案】 #include ＂string.h＂ #defin maxsize 256 void strinsert(char *S，char *T,int i) {int slen; char sbuf[maxsize]; slen=strlen(S); if (i<0||i>slen) printf(＂invalid para i\\n＂); else { strcpy(sbuf1,S,i); strcat(sbuf1,T); strcpy(sbuf2,S+i); strcat(sbuf1,sbuf2); strcpy(S,sbuf1); printf(＂string S：%s＂,S); } } 5．利用Ｃ的库函数strlen,strcpy和strcat写一个算法void strdelete(char *S,int i,int m)，删去串S中从第i个字符开始的连续m个字符。若i≥strlen(S)，则没有字符被删除，若i+m≥strlen(S)，。则将串S中从第i个字符开始直到末尾的字符删去。 【答案】 #defin maxsize 256 #include ＂string.h＂ void strdelete(char *S,int i,int m) {int slen; char sbuf1[maxsize],sbuf2[maxsize]; slen=strlen(S); if (i<0||i>=slen) printf(＂invalid para i\\n＂); else { if (i+m-1>=slen) S[i]=＇\\0＇; else {strcpy(sbuf1,S,i); strcpy(sbuf2,S+i+m); strcat(sbuf1,sbuf2); strcpy(S,sbuf1); } printf(＂string S：%s＂,S); } } 6． Hstring 为存储表示，写一个求子串的算法。 【答案】 #defin maxsize 256 #include ＂string.h＂ void substr(Hstring S,Hstring *T,int i,int len) {int k; if (i<0||i+len-1>=S.length) printf(＂invalid para i\\n＂); else {T->ch=(char *)malloc(maxsize*sizeof(char)); for(k=0;k T->ch[k]=S.ch[i+k]; T->length=len;} } } 7．一个文本串可用事先给定的字符映像表进行加密。例如，设字符映像表为： abcdefghijklmnopqrstuvwxyz ngzqtcobmuhelkpdawxfyivrsj 则字符串＂encrypt＂被加密为＂tkzwsdf＂。试写一算法将输入的文本串进行加密后输出；另写一算法将输入的已加密的文本串进行解密后输出。 【答案】 char key[ ]={＂ngzqtcobmuhelkpdawxfyivrsj＂}； void f1(char *s) {int j=0; while(s[j]!=＇\\0＇) {if (s[j]>=＇a＇&&s[j]<=＇z＇) s[j]=key[s[j]-＇a＇]； j++; } void f2(char *s) {int j=0,k; while(s[j]!=＇\\0＇) {if (s[j]>=＇a＇&&s[j]<=＇z＇) {k=0; while(s[j]!=key[k]) k++; s[j]=＇a＇+k；} j++; } } 8．写一算法void strreplace(char *T,char *P,char *S)，将T中首次出现的子串P替换为串S。注意S和T的长度不一定相等。可以使用已有的串操作。 【答案】 void strreplace(char *T,char *P,char *S) { int tlen,plen; int i,j,k; tlen=strlen(T); plen=strlen(P); if(plen>tlen) printf(＂invalid p string\\n＂); else {for(i=0;i<=tlen-plen;i++) for(j=0,k=i;j {k++,j++;} if(j>=plen) {strdelete(T,i,plen); strinsert(T,s,i); break;} else printf(＂no p string in t string\\n＂); } } 9．将NaiveStrMatch(T,P)改写为输出目标串中所有与模式串匹配的有效位移。 【答案】 void NaiveStrMatch(Seqstrint T,Seqstring P,int offs[ ]) {int i,j,k,n=0; for(i=0;i<=T.length-P.length;i++) { for(j=0,k=i;j {k++,j++;} if(j>=P.length) offs[++n]=i; } offs[0]=n; } 10．写一算法void strreplaceall(char *T,char *P,char *S)，将T中出现的所有与P相等的不重叠子串替换S，这里S和P的长度不一定相等。 【答案】 void strreplaceall(char *T,char *P,char *S) {int i,j,k,n=0; i=0 while(i<=T.length-P.length) { for(j=0,k=i;j {k++,j++;} if(j>=P.length) {sstrdelete(T,i,plen);//具有修改串T长度的功能 sstrinsert(T,S,i); //具有修改串T长度的功能 i=i+S.length;} else i++; } } 11．若S和T是用结点大小为1的单链表存储的两个串，是设计一个算法找出S中第一个不在T中出现的字符。 【答案】 Linkstrnode *find(Linkstring T,Linkstring S) { Linkstrnode *p,*q; int tag=1; p=S;q=T; while (p&&tag) {q=T; while(q&&p->data!=q->data) q=q->next; if (q==NULL) tag=0; else p=p->next; } return p; } 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构第04章 串在线全文阅读。
相关推荐：
