下载文档原格式
《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。
4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。
一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。
２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。
包含子串的串相应地称为主串。
子串的位置：子串的第一个字符在主串中的序号称为子串的位置。
串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。
4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。
4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。
如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。
如图4.1所示。
s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。
习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“softwa re”,其子串的个数是（）。
A．8 B．37 C．36 D．9二、填空题1．含零个字符的串称为______串。
任何串中所含______的个数称为该串的长度。
2．空格串是指__ __，其长度等于__ __。
3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。
一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。
4．INDEX（‘DATAST RUCTU RE’，‘STR’）=________。
5．模式串P=‘abaabc ac’的next函数值序列为________。
6．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)__ ______){int i=0,j=0;while(s[j])(2)___ _____;for(j--; i<j && s[i]==s[j]; i++,j--);return((3)___ ____)}7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
第四章答案4.1 简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。
答：●空串是指不包含任何字符的串，它的长度为零。
空白串是指包含一个或多个空格的串，空格也是字符。
●串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。
●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。
●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。
4.2 假设有如下的串说明：char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;(1)在执行如下的每个语句后p的值是什么?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);(3)调用函数strcmp(s1,s2)的返回值是什么?(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。
第四章串一、内容提要1、是数据元素为字符的线性表，串的定义及操作。
2、串的基本操作，编制算法求串的其它操作。
3、串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。
静态和动态（块链结构，堆结构）存储的优缺点。
4、朴素模式匹配算法及改进（KMP）算法。
二、学习重点1、串的基本操作，编写串的其他操作（如index,replace等）。
2、在串的模式匹配中，求匹配串的nextval 函数值。
3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。
KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。
5、串操作在存储结构下的实现。
三、例题解析1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法replace(string &s,string t, string v)//本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。
{i=INDEX(s,t);{判s中有无t}IF (i!=0){CREATE (temp, ‘’);{t为临时串变量，存放部分结果}m=LENGTH(t);n=LENGTH(s);WHILE (i!=0){ ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v));//用v替换t形成部分结果ASSIGN (s,SUBSTR(s, i+m,n-i-m+1)); //t串以后形成新s串n= n-(i-1)-m;i=INDEX(s,t);}ASSIGN (s,CONCAT(temp,s)); //将剩余s连接临时串t再赋给s}}int index(string s,string t)//本算法求串t在串s中的第一次出现。
结果是：若t在s中，则给出串t的第一个字符在串s中的位置，若不存在，则返回0{j=1;m=length(s); n=length(t); eq=true;WHILE((j<=m-n+1)&& eq )IF equal(substr(s,j,n),t)eq=false;ELSEj=j+1；IF( j<=m+n-1)return(j);Return(0);}【讨论】本题是用给定的基本操作，编写其它操作的算法。
这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构。
否则，即使全对，也很难得分。
2 设目标为t=’abcaabbabcabaacbacba’,模式串p=’abcabaa’;(1)计算P的NEXTVAL函数值；(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；【解答】【讨论】为写NEXTVAL方便，可先写出NEXT函数值，在由此求NEXTVAL.3、字符串s 满足下式，其中HEAD 和 TAIL的定义同广义表类似，如HEAD(‘XYZ’)=’X’,TAIL(‘XYZ’)=’YZ’,则S=concat(head(tail(s)),head(tail(tail(s))))=’dc’求字符串s。
可供选择的答案是（A） abcd(B) acbd(C) acdb(D) adcb正确答案是（D）。
四、基本题（一）选择题1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,inde x(S2,‘8’),length(S2)))其结果为（）【北方交通大学1999一、5（25/7分）】A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。
【西安电子科技大学 1996 一、7 （2分）】A．0123B．1123C．1231D．12115．串‘ababaaababaa’ 的next数组为（）。
【中山大学 1999 一、7】A．012345678999 B．012121111212C．011234223456D．01230123223456．字符串‘ababaabab’ 的nextval 为（）A．(0,1,0,1,04,1,0,1)B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1)D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。
A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1【北京邮电大学 1998 二、3 （2分）】8．若串S=’software’,其子串的数目是（）。
【西安电子科技大学 2001应用一、2（2分）】A．8B．37C．36D．99．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。
【中科院计算所 1997 】A．2n-1B．n2C．(n2/2)+(n/2)D．(n2/2)+(n/2)-1E. (n2/2)-(n/2)-1F.其他情况10．串的长度是指（）【北京工商大学 2001一、6 （3分）】A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数（二）判断题1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。
（）【北京邮电大学 2002 一、4 （1分）】2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
（）【长沙铁道学院 1998 一、1 (1分)】3．串是一种数据对象和操作都特殊的线性表。
（）【大连海事大学 2001 1、L(1分)】（三）填空题1．空格串是指__(1)__，其长度等于___(2)__。
【西安电子科技大学 2001软件一、4（2分）】2．组成串的数据元素只能是________。
【中山大学 1998一、5 （1分）】3．一个字符串中________称为该串的子串。
【华中理工大学 2000 一、3（1分）】4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。
【福州大学 1998 二、4 (2分)】5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。
【重庆大学 2000 一、4】6．模式串P=‘abaabcac’的next函数值序列为________。
【西安电子科技大学 2001软件一、6（2分）】7．字符串’ababaaab’的nextval函数值为________。
【北京邮电大学 2001 二、4 （2分）】8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__(1)__，又称P为__(2)__。
【西安电子科技大学 1998 二、5 （16/6分）】9．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。
【中国矿业大学 2000 一、3 （4分）】10．两个字符串相等的充分必要条件是_______。
【西安电子科技大学 1999软件一、1 （2分）】11．知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；ASSIGN（m，‘ww’）求REPLACE（S，V，m）= ________。
【东北大学 1997 一、1(5分)】12．实现字符串拷贝的函数 strcpy为：void strcpy(char *s , char *t) /*copy t to s*/{ while(________)}【浙江大学1999一、5(3分)】13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)________){inti=0,j=0;while (s[j])(2)________;for(j--; i<j&& s[i]==s[j]; i++,j--);return((3)_______)}【浙江大学1999一、6 (3分)】14．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
voidmaxcomstr(orderstring *s,*t; int index, length){int i,j,k,length1,con;index=0;length=0;i=1;while (i<=s.len){j=1;while(j<=t.len){ if (s[i]= =t[j]){ k=1;length1=1;con=1;while(con)if (1) _ { length1=length1+1;k=k+1; }else (2) __;if (length1>length) { index=i;length=length1; }(3)____;}else (4) ___;}(5) __}}【上海大学 2000 一、2 （10分）】15．完善算法：求KMP算法中next数组。
