第四章 串答案.doc

'第四章串一、选择题1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。二、判断题1.√2.√3.√          三．填空题1．(1)由空格字符（ASCII值32）所组成的字符串(2)空格个数2．字符3．任意个连续的字符组成的子序列4．55.O(m+n)6．011223127．010104218．(1)模式匹配(2)模式串9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等10．两串的长度相等且两串中对应位置的字符也相等。11．’xyxyxywwy’12．*s++=*t++或（*s++=*t++）!=‘’13．（1）chars[](2)j++(3)i>=j14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len)AND(s[i+k]=t[j+k]) //如果在s和t的长度内，对应字符相等，则指针k后移（加1）。（2）con:=false//s和t对应字符不等时置标记退出（3）j:=j+k//在t串中，从第j+k字符再与s[i]比较（4）j:=j+1//t串取下一字符（5）i：=i+1//s串指针i后移（加1）。　程序（b）：(1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k]//所有注释同上（a）(2)con=0(3)j+=k(4)j++(5)i++15．（1）0（2）next[k]16．（1）i：=i+1（2）j:=j+1(3)i:=i-j+2(4)j:=1;(5)i-mt（或i:=i-j+1）(6)017.程序中递归调用（1）ch1<>midch//当读入不是分隔符&和输入结束符$时，继续读入字符（2）ch1=ch2//读入分隔符&后，判ch1是否等于ch2，得出真假结论。（3）answer：=true（4）answer：=false（5）read（ch）（6）ch=endch18．（1）initstack（s）/／栈s初始化为空栈。 　(2)setnull(exp)//串exp初始化为空串。(3)chinopset//判取出字符是否是操作符。(4)push(s,ch)//如ch是运算符，则入运算符栈s。(5)sempty(s)//判栈s是否为空。(6)succ:=false//若读出ch是操作数且栈为空，则按出错处理。(7)exp(8)ch//若ch是操作数且栈非空，则形成部分中缀表达式。(9)exp(10)gettop(s)//取栈顶操作符。(11)pop(s)//操作符取出后，退栈。　　(12)sempty(s)　//将pre的最后一个字符（操作数）加入到中缀式exp的最后。 四．应用题 　１．串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。　２．空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。　３．最优的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度，一般情况下，T(m,n)=O(m*n)。　４．朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m＊n），KMP算法有一定改进，时间复杂度达到Ｏ（m＋n）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。　５．KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出．　６．模式串的next函数定义如下：　　　next［j］=根据此定义，可求解模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]0110213011057．解法同上题6，其next和nextval值分别为0112123422和0102010422。8．解法同题6，t串的next和nextval函数值分别为0111232和0110132。9．解法同题6，其next和nextval值分别为011123121231和011013020131。10．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：0121123和0021002。11．next数组值为011234567改进后的next数组信息值为010101017。12．011122312。 13．next定义见题上面6和下面题20。串p的next函数值为：01212345634。14．（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)15．（1）p的nextval函数值为0110132。（p的next函数值为0111232）。（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)16．KMP算法的时间复杂性是O（m+n）。p的next和nextval值分别为01112212321和01102201320。17．（1）p的nextval函数值为01010。（next函数值为01123）（2）利用所得nextval数值，手工模拟对s的匹配过程，与上面16题类似，为节省篇幅，故略去。18．模式串T的next和nextval值分别为0121123和0021002。19．第4行的p[J]=p[K]语句是测试模式串的第J个字符是否等于第K 个字符，如是，则指针J和K均增加1，继续比较。第6行的p[J]=p[K]语句的意义是，当第J个字符在模式匹配中失配时，若第K个字符和第J个字符不等，则下个与主串匹配的字符是第K个字符；否则，若第K个字符和第J个字符相等，则下个与主串匹配的字符是第K个字符失配时的下一个（即NEXTVAL[K]）。该算法在最坏情况下的时间复杂度O（m2）。20．（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模式串中第一字符进行比较。（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。intindex(chars[],t[],intm,n)//字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。{inti=0,j=0;while(i<=m-n&&j<=n-1)if(s[i]==t[j]){i++;j++;}//对应字符相等，指针后移。else{i=i-j+1;j=0;}//对应字符不相等，I回溯，j仍为0。if(i<=m-n&&j==n){printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功elsereturn(0);//匹配失败}//算法index结束main()//主函数{chars[],t[];intm,n,i;scanf(“%d%d”,&m,&n);//输入两字符串的长度 scanf(“%s”,s);//输入主串scanf(“%s”,t);//输入子串i=index(s,t,m,n);}//程序结束[程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。2.［问题分析］在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。　intCountInt（）//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。｛inti=0，a[]；//整数存储到数组a，i记整数个数　scanf（“％c”，&ch）；//从左到右读入字符串　while（ch!=‘#’）//‘#’是字符串结束标记　　if（isdigit（ch））//是数字字符　　｛num=０；//数初始化　　　while（isdigit（ch）&&ch!=‘#’）//拼数　　　｛num=num＊10+‘ch’-‘０’；　　　　scanf（“％c”，&ch）；　　　｝　　　a[i]=num；i++；　　　if（ch!=‘#’）scanf（“%c”，&ch）；//若拼数中输入了‘#’，则不再输入　　｝//结束while（ch！＝‘#’）　printf（“共有%d个整数，它们是：”i）； 　for（j=０；jt.curlen，则向左移；若jmaxlen){printf(“参数错误n”);exit(0);}//检查参数及置换后的长度的合法性。if(j=i+j-1;k--)s.ch[k+t.curlen-j]=s.ch[k];elseif(j>t.curlen)//s串中被替换子串的长度小于t串的长度。for(k=i-1+j;k<=s.curlen-1;k++)s.ch[k-(j-t.curlen)]=s.ch[k];for(k=0;kt.curlen)s.curlen=s.curlen-(j-t.curlen);elses.curlen=s.curlen+(t.curlen-j);}//算法结束[算法讨论]若允许使用另一数组，在检查合法性后，可将s的第i个（不包括i）之前的子串复制到另一子串如s1中，再将t串接到s1串后面,然后将s的第i+j直到尾的部分加到s1之后。最后将s1串复制到s。主要语句有：for(k=0;ki-1+j;k--);//将子串第i+j-1个字符以后的子串复制到s1s1.ch[l--]=s.ch[k] for(k=0;k=pos;j--){*(p+x)=*p;p--;}//串s的pos后的子串右移，空出串t的位置。q--;//指针q回退到串t的最后一个字符for(j=1;j<=x;j++)*p--=*q--;//将t串插入到s的pos位置上[算法讨论]串s的结束标记("")也后移了，而串t的结尾标记不应插入到s中。6.[题目分析]本题属于查找，待查找元素是字符串（长4），将查找元素存放在一维数组中。二分检索（即折半查找或对分查找），是首先用一维数组的“中间”元素与被检索元素比较，若相等,则检索成功，否则，根据被检索元素大于或小于中间元素，而在中间元素的右方或左方继续查找，直到检索成功或失败（被检索区间的低端指针大于高端指针）。下面给出类C语言的解法typedefstructnode{chardata[4];//字符串长4}node;非递归过程如下：intbinsearch(nodestring[];intn;charname[4])//在有n个字符串的数组string中，二分检索字符串name。若检索成功，返回name在string中的下标，否则返回-1。{intlow=0,high=n-1;//low和high分别是检索区间的下界和上界while(low<=high){mid=(low+high)/2;//取中间位置if(strcmp(string[mid],name)==0)return(mid);//检索成功elseif(strcmp(string[mid],name)<0)low=mid+1;//到右半部分检索elsehigh=mid-1;// 到左半部分检索}return0;//检索失败}//算法结束最大检索长度为log2n。7.[题目分析]设字符串存于字符数组X中，若转换后的数是负数，字符串的第一个字符必为"-"，取出的数字字符，通过减去字符零（"0"）的ASCII值，变成数，先前取出的数乘上10加上本次转换的数形成部分数，直到字符串结束，得到结果。longatoi(charX[])//一数字字符串存于字符数组X中，本算法将其转换成数{longnum=0;inti=1;//i为数组下标while(X[i]!="")num=10*num+(X[i++]-"0");//当字符串未到尾，进行数的转换if(X[0]=="-")return(-num);//返回负数elsereturn((X[0]-"0")*10+num);//返回正数，第一位若不是负号，则是数字}//算法atoi结束[算法讨论]如是负数，其符号位必在前面，即字符数组的x[0]，所以在作转换成数时下标i从1开始，数字字符转换成数使用X[i]-"0",即字符与"0"的ASCII值相减。请注意对返回正整数的处理。8.[题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。voidformat(char*s1,*s2,*s3)//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐{char*p=s1,*q=s2;inti=0;while(*p!=""&&*p=="")p++;//滤掉s1左端空格if(*p==""){printf("字符串s1为空串或空格串n");exit(0);}while(*p!=""&&i0)s[j++]=stk[i--]//将第偶数个字符逆序填入原字符数组}14.[题目分析]本题是对字符串表达式的处理问题，首先定义4种数据结构：符号的类码，符号的TOKEN表示，变量名表NAMEL和常量表CONSL。这四种数据结构均定义成结构体形式，数据部分用一维数组存储，同时用指针指出数据的个数。算法思想是从左到右扫描表达式，对读出的字符，先查出其符号类码：若是变量或常量，就到变量名表和常量表中去查是否已有，若无，则在相应表中增加之，并返回该字符在变量名表或常量表中的下标；若是操作符，则去查其符号类码。对读出的每个符号，均填写其TOKEN表。如此下去，直到表达式处理完毕。先定义各数据结构如下。struct//定义符号类别数据结构{chardata[7];//符号charcode[7]；//符号类码}TYPL；typedefstruct//定义TOKEN的元素{inttyp；//符号码intaddr；//变量、常量在名字表中的地址}cmp；struct{cmpdata[50]；//定义TOKEN表长度<50intlast；//表达式元素个数 }TOKEN；struct{chardata[15]；//设变量个数小于15个intlast；//名字表变量个数}NAMEL；struct{chardata[15]；//设常量个数小于15个intlast；//常量个数}CONSL；intoperator（charcr）//查符号在类码表中的序号{for（i=3；i<=6；i++）if（TYPL.data[i]==cr）return（i）；}voidPROCeString（）//从键盘读入字符串表达式（以‘#’结束），输出其TOKEN表示。{NAMEL.last=CONSL.last=TOKEN.last=0；//各表元素个数初始化为0TYPL.data[3]=‘*’；TYPL.data[4]=‘+’；TYPL.data[5]=‘（’；TYPL.data[6]=‘）’；//将操作符存入数组TYPL.code[3]=‘3’；TYPL.code[4]=‘4’；TYPL.code[5]=‘5’；TYPL.code[6]=‘6’；//将符号的类码存入数组scanf（“%c”，&ch）；//从左到右扫描（读入）表达式。while（ch！=‘#’）//‘#’是表达式结束符{switch（ch）of{case‘A’:case‘B’:case‘C’://ch是变量TY=0；//变量类码为0for（i=1；i<=NAMEL.last；i++）if（NAMEL.data[i]==ch）break；//已有该变量，i记住其位置if（i>NAMEL.last）{NAMEL.data[i]=ch；NAMEL.last++；}//变量加入case‘0’:case‘1’:case‘2’:case‘3’:case‘4’:case‘5’://处理常量case‘6’:case‘7’:case‘8’:case‘9’:TY=1；//常量类码为1　　for（i=1；i<=CONSL.last；i++）if（CONSL.data[i]==ch）break；////已有该常量，i记住其位置 　if（i>CONSL.last）｛CONSL.data[i]=ch；CONSL.last++；｝//将新常量加入　default://处理运算符　TY＝operator（ch）；//类码序号　i=’’；//填入TOKEN的addr域（期望输出空白）}//结束switch，下面将ch填入TOKEN表TOKEN.data［++TOKEN.last］.typ=TY；TOKEN.data［TOKEN.last］.addr=i；scanf（“％c”，&ch）；//读入表达式的下一符号。}//while}//算法结束[程序讨论]为便于讨论，各一维数组下标均以1开始，在字符为变量或常量的情况下，将其类码用TY记下，用i记下其NAMEL表或CONSL表中的位置，以便在填TOKEN表时用。在运算符（‘+’，‘*’，‘（’，‘）’）填入TOKEN表时，TOKEN表的addr域没意义，为了程序统一，这里填入了’’。本题是表达式处理的简化情况（只有3个单字母变量，常量只有0..9，操作符只4个），若是真实情况，所用数据结构要相应变化。'