第四章 串答案52450
第四章串
注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串
是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长
为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，
长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*
（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”
无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。
二、判断题
三．填空题
1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数
2．字符
3．任意个连续的字符组成的子序列4．5 5.O(m+n)
6．01122312 7．01010421 8．(1)模式匹配 (2)模式串
9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且
两串中对应位置的字符也相等
10．两串的长度相等且两串中对应位置的字符也相等。
11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’
13．（1）char s[ ] (2) j++ (3) i >= j
14．[题目分析]本题算法采用顺序存储结构求串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)0
17.程序中递归调用
（1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符
（2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。（3）answer：=true
（4）answer：=false
（5）read（ch）
（6）ch=endch
18．（1）initstack（s） /／栈s初始化为空栈。
(2) setnull (exp) //串exp初始化为空串。
(3) ch in opset //判取出字符是否是操作符。
(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 ］=
?????=<<=-+--其它情况当此集合不空时‘且
时当1
}'...''... j k 1 |k max{101111j k j k p p p p j
7．解法同上题6，其next 和nextval 值分别为0112123422和010*******。
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 第一趟匹配：aabaabaabaac
aabaac(i=6,j=6)
aabaac(i=6,j=6)
第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac
aa(i=3,j=2) (aa)baac 第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac
a(i=3,j=1) (成功) (aa)baac
第四趟匹配： aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配： aabaabaabaac
aa(i=6,j=2)
第六趟匹配： aabaabaabaac
a(i=6,j=1)
第七趟匹配： aabaabaabaac
(成功) aabaac(i=13,j=7)
15．（1）p的nextval函数值为0110132。（p的next函数值为0111232）。
（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功) 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值应满足条件1 （3）在上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第1个字符开始与主串第i个字符比较，以便不致丢失可能的匹配。 21．这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第6题。 进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。 该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。 22．失败函数（即next）的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，假定主串不回溯，模式串用第k（即next[j]）个字符与第i个相比，有‘ p1…p k-1’=‘p j-k+1…p j-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。 23．仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。24．（1）s1和s2均为空串；（2）两串之一为空串；（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。 25、题中所给操作的含义如下： //：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j 个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 本题有多种解法，下面是其中的一种： （1） s1=substr（s,3,1） //取出字符：‘y’ （2） s2=substr（s,6,1） //取出字符：‘+’ （3） s3=substr（s,1,5） //取出子串：‘(xyz)’ （4） s4=substr（s,7,1） //取出字符：‘*’ （5） s5=replace（s3,3,1,s2）//形成部分串：‘（x+z）’ （6） s=s5//s4//s1 //形成串t即‘（x+z）*y’ 五、算法设计 1、[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j 的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0=t0，则i和j指针增加1，若在某个位置s i!=t j，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。 int index(char s[],t[],int m,n) //字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。 {int i=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);}//匹配成功 else return(0); //匹配失败 }//算法index结束 main ()//主函数 {char s[],t[]; int m,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.［问题分析］在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。 int CountInt（） // 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。 ｛int i=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=０；j ｛printf（“%6d”，a[j]）； if（（j+1）％10==0）printf（“\n”）；} // 每10个数输出在一行上 ｝// 算法结束 ［算法讨论］假定字符串中的数均不超过32767，否则，需用长整型数组及变量。 3、[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。 int LongestString(char s[],int n) //串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。 {int index=0,max=0; //index记最长的串在s串中的开始位置，max 记其长度 int length=1,i=0,start=0; //length记局部重复子串长度，i 为字符数组下标 while(i if(s[i]==s[i+1]) {i++; length++;} else //上一个重复子串结束 {if(max i++;start=i;length=1; //初始化下一重复子串的起始位置和长度 } printf(“最长重复子串的长度为%d，在串中的位置%d\n”，max,index); return(max); }//算法结束 [算法讨论]算法中用i 算法的时间复杂度为O(n），每个字符与其后继比较一次。 4、[题目分析]教材中介绍的串置换有两种形式：第一种形式是replace（s,i,j,t），含义是将s串中从第i个字符开始的j个字符用t 串替换,第二种形式是replace(s,t,v)，含义是将s串中所有非重叠的t 串用v代替。我们先讨论第一种形式的替换。因为已经给定顺序存储结构，我们可将s串从第（i+j-1）到串尾（即s.curlen）移动t.curlen-j绝对值个位置（以便将t串插入）：若j>t.curlen，则向左移；若j int replace(strtp s,t,int i,j) //s和t是用一维数组存储的串，本算法将s串从第i个字符开始的连续j个字符用t串置换，操作成功返回1，否则返回0表示失败。 {if(i<1 || j<0 || t.curlen+s.curlen-j>maxlen) {printf(“参数错误\n”);exit(0);} //检查参数及置换后的长度的合法性。 if(j for(k=s.curlen-1;k>=i+j-1;k--) s.ch[k+t.curlen-j]=s.ch[k]; else if (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;k if(j>t.curlen) s.curlen=s.curlen-(j-t.curlen);else s.curlen=s.curlen+(t.curlen-j); }//算法结束 [算法讨论]若允许使用另一数组，在检查合法性后，可将s的第i个（不包括i）之前的子串复制到另一子串如s1中，再将t串接到s1串后面,然后将s的第i+j直到尾的部分加到s1之后。最后将s1串复制到s。主要语句有： for(k=0;k for(k=0;k l=s.curlen+t.curlen-j-1; for(k=s.curlen-1;k>i-1+j;k--);//将子串第i+j-1个字符以后的子串复制到s1 s1.ch[l--]=s.ch[k] for(k=0;k 下面讨论replace（s,t,v）的算法。该操作的意义是用串v替换所有在串s中出现的和非空串t相等的不重叠的子串。本算法不指定存储结构，只使用串的基本运算。 void replace(string s,t,v) //本算法是串的置换操作，将串s中所有非空串t相等且不重复的子串用v代替。 {i=index(s,t);//判断s是否有和t相等的子串 if(i!=0)//串s中包含和t相等的子串 {creat(temp,”); //creat操作是将串常量（此处为空串）赋值给temp。 m=length(t);n=length(s); //求串t和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)); //将串s 中串后的部分形成新的s串 n=n-(i-1)-m; //求串s 的长度 i=index(s,t); //在新s 串中再找串t的位置 } assign(s,contact(temp,s)); //将串temp和剩余的串s连接后再赋值给s }//if结束 }//算法结束 5、[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s 的第pos位置后。 对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。 void insert(char *s,char *t,int pos) //将字符串t插入字符串s的第pos个位置。 {int i=1,x=0; char*p=s,*q=t; //p，q分别为字符串s和t的工作指针 if(pos<1) {printf(“pos参数位置非法\n”);exit(0);} while(*p!=’\0’&&i //若pos小于串s长度，则查到pos位置时，i=pos。 if(*p == '/0') {printf("%d位置大于字符串s的长度",pos);exit(0);} else //查找字符串的尾 while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。 while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上 [算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。 6.[题目分析]本题属于查找，待查找元素是字符串（长4），将查找元素存放在一维数组中。二分检索（即折半查找或对分查找），是首先用一维数组的“中间”元素与被检索元素比较，若相等,则检索成功，否则，根据被检索元素大于或小于中间元素，而在中间元素的右方或左方继续查找，直到检索成功或失败（被检索区间的低端指针大于高端指针）。下面给出类C语言的解法 typedef struct node {char data[4];//字符串长4 }node; 非递归过程如下： int binsearch(node string [];int n;char name[4]) //在有n个字符串的数组string中，二分检索字符串name。若检索成功，返回name在string中的下标，否则返回-1。 {int low = 0,high = n - 1;//low和high分别是检索区间的下界和上界 while(low <= high) {mid = (low + high) /2; //取中间位置 if(strcmp(string[mid],name) ==0) return (mid); //检索成功 else if(strcmp(string[mid],name)<0) low=mid+1; //到右半部分检索 else high=mid-1; //到左半部 分检索 } return 0; //检索失败 }//算法结束 最大检索长度为log2n。 7. [题目分析]设字符串存于字符数组X中，若转换后的数是负数，字符串的第一个字符必为 '-'，取出的数字字符，通过减去字符零（'0'）的ASCII值，变成数，先前取出的数乘上10加上本次转换的数形成部分数，直到字符串结束，得到结果。 long atoi(char X[]) //一数字字符串存于字符数组X中，本算法将其转换成数{long num=0; int i=1; //i 为数组下标 while(X[i]!= '\0') num=10*num+(X[i++]-'0');//当字符串未到尾，进行数的转换 if(X[0]=='-') return (-num); //返回负数 else return ((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中。 void format (char *s1,*s2,*s3) //将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n 且两端对齐 {char *p=s1, *q=s2; int i=0; while(*p!= '\0' && *p== ' ') p++;//滤掉s1左端空格 if(*p== '\0') {printf("字符串s1为空串或空格串\n");exit(0); } while( *p!='\0' && i if(*p =='\0'){ printf("字符串s1没有%d个有效字符\n",n); exit(0);} if(*(--q)==' ' ) //若最后一个字符为空格，则需向后找到第一个非空格字符 {p-- ; //p指针也后退 while(*p==' '&&*p!='\0') p++;//往后查找一个非空格字符作串s2的尾字符 if(*p=='\0') {printf("s1串没有%d个两端对齐的字符串\n",n); exit(0); } *q=*p; //字符串s2最后一个非空字符 *(++q)='\0'; //置s2字符串结束标记 } *q=s3;p++; //将s1串其余部分送字符串s3。 while (*p!= '\0') {*q=*p; q++; p++;} *q='\0'; //置串s3结束标记 } 9.[题目分析]两个串的相等，其定义为两个串的值相等，即串长相等，且对应字符相等是两个串相等的充分必要条件。因此，首先比较串长，在串长相等的前提下，再比较对应字符是否相等。 int equal(strtp s,strtp t) //本算法判断字符串s和字符串t是否相等，如相等返回1，否则返回0 {if (s.curlen!=t.curlen) return (0); for (i=0; i if (s.ch[i]!= t.ch[i])return (0); return (1); //两串相等 }//算法结束 10.［问题分析］由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符‘0’的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符‘A’的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。 void Count（） //统计输入字符串中数字字符和字母字符的个数。 ｛int i，num[36]； char ch； for（i＝0；i<36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符 else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符 for（i=0；i<10；i++） // 输出数字字符的个数 printf（“数字％d的个数＝％d\n”，i，num[i]）； for（i＝10；i<36；i++）// 求出字母字符的个数 printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）； ｝// 算法结束。 11.[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[]) //字符串逆序存储的递归算法。 { char ch; static int i = 0;//需要使用静态变量 scanf ("%c",&ch); if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A); A[i++] = ch;//字符串逆序存储 } A[i] = '\0'; //字符串结尾标记 }//结束算法InvertStore。 12. 串s'''可以看作由以下两部分组成：'caabcbca...a'和'ca...a'，设这两部分分别叫串s1和串s2，要设法从s,s' 和s''中得到这两部分，然后使用联接操作联接s1和s2得到s''' 。 i=index(s,s'); //利用串s'求串s1在串s中的起始位置 s1=substr(s,i,length(s) - i + 1); //取出串s1 j=index(s,s''); //求串s''在串s中的起始位置，s串中'bcb'后是'ca...a') s2=substr(s,j+3,length(s) - j - 2); //形成串s2 s3=concat(s1,s2); 13．[题目分析]对读入的字符串的第奇数个字符，直接放在数组前面， 对第偶数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。限于篇幅，这里编写算法，未编程序。 void RearrangeString() //对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。 {char ch,s[],stk[]; //s和stk是字符数组（表示字符串）和字符栈 int i=1,j; //i和j字符串和字符栈指针 while((ch=getchar())!=’#’)// ’#’是字符串结束标志 s[i++]=ch; //读入字符串 s[i]=’\0’; //字符数组中字符串结束标志 i=1;j=1; while(s[i]) //改造字符串 {if(i%2==0) stk[i/2]=s[i]; else s[j++]=s[i]; i++; }//while i--; i=i/2; //i先从’\0’后退，是第偶数字符的个数 while(i>0) s[j++]=stk[i--] //将第偶数个字符逆序填入原字符数组 } 14.[题目分析]本题是对字符串表达式的处理问题，首先定义4种数据结构：符号的类码，符号的TOKEN 表示，变量名表NAMEL和常量表CONSL。这四种数据结构均定义成结构体形式，数据部分用一维数组存储，同时用指针指出数据的个数。算法思想是从左到右扫描表达式，对读出的字符，先查出其符号类码：若是变量或常量，就到变量名表和常量表中去查是否已有，若无，则在相应表中增加之，并返回该字符在变量名表或常量表中的下标；若是操作符，则去查其符号类码。对读出的每个符号，均填写其TOKEN表。如此下去，直到表达式处理完毕。先定义各数据结构如下。 struct // 定义符号类别数据结构 {char data[7]; //符号 char code[7]； //符号类码 }TYPL； typedef struct //定义TOKEN的元素 {int typ； //符号码 int addr； //变量、常量在名字表中的地址 }cmp； struct {cmp data[50]；//定义TOKEN表长度<50 int last； //表达式元素个数 }TOKEN； struct {char data[15]； //设变量个数小于15个 int last； //名字表变量个数 }NAMEL； struct {char data[15]； //设常量个数小于15个 int last； //常量个数 }CONSL； int operator（char cr） //查符号在类码表中的序号 {for（i=3；i<=6；i++） if（TYPL.data[i]==cr）return（i）； } void PROCeString（） //从键盘读入字符串表达式（以‘#’结束），输出其TOKEN表示。 {https://www.sodocs.net/doc/4713746459.html,st=https://www.sodocs.net/doc/4713746459.html,st=https://www.sodocs.net/doc/4713746459.html,st=0； //各表元素个数初始化为0 TYPL.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； //变量类码为0 for（i=1；i<=https://www.sodocs.net/doc/4713746459.html,st；i++） if（NAMEL.data[i]==ch）break；//已有该变量，i记住其位置 if（i>https://www.sodocs.net/doc/4713746459.html,st）{NAMEL.data[i]=ch； https://www.sodocs.net/doc/4713746459.html,st++；}//变量加入 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<=https://www.sodocs.net/doc/4713746459.html,st；i++） if（CONSL.data[i]==ch）break；////已有该 常量，i记住其位置 if（i>https://www.sodocs.net/doc/4713746459.html,st）｛CONSL.data[i]=ch； https://www.sodocs.net/doc/4713746459.html,st++；｝//将新常量加入 default: //处理运算符 TY＝operator（ch）；//类码序号 i=’\0’； //填入TOKEN的addr域（期望输出空白） }//结束switch，下面将ch填入TOKEN表 TOKEN.data［++https://www.sodocs.net/doc/4713746459.html,st］.typ=TY；TOKEN.data ［https://www.sodocs.net/doc/4713746459.html,st］.addr=i； scanf（“％c”，&ch）； //读入表达式的下一符号。 }//while }//算法结束 [程序讨论]为便于讨论，各一维数组下标均以1开始，在字符为变量或常量的情况下，将其类码用TY记下，用i记下其NAMEL表或CONSL表中的位置，以便在填TOKEN表时用。在运算符（‘+’，‘*’，‘（’，‘）’）填入TOKEN表时，TOKEN表的addr域没意义，为了程序统一，这里填入了’\0’。本题是表达式处理的简化情况（只有3个单字母变量，常量只有0..9，操作符只4个），若是真实情况，所用数据结构要相应变化。 实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 四、程序流程图、算法及运行结果 3-1 #include return -1; } int main() { char s[MAXSIZE]; char t[MAXSIZE]; int answer, i; printf("S String -->\n "); gets(s); printf("T String -->\n "); gets(t); printf("%d",StrIndex_BF(s,t)); /*验证*/ if((answer=StrIndex_BF(s,t))>=0) { printf("\n"); printf("%s\n", s); for (i = 0; i < answer; i++) printf(" "); printf("%s", t); printf("\n\nPattern Found at location:%d\n", answer); } else printf("\nPattern NOT FOUND.\n"); getch(); return 0; } 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 第四章串习题及答案 一、基础知识题 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 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))的返回值是什么? 4.3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时,请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 二、算法设计题： 4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度,则插入不执行。 4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4.6 以HString为存储表示,写一个求子串的算法。 4.7 一个文本串可用事先给定的字母映射表进行加密。例如,设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z 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 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法,将输入的已加密的文本串进行解密后输出。 4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。 4.9 将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S,这里S和P的长度不一定相等。 4.11 若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找出S中第一个不在T中出现的字符。 答案： 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：空串是指不包含任何字符的串,它的长度为零。 空白串是指包含一个或多个空格的串,空格也是字符。 串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串的子串,而包含子串的串就称为主串。 静态分配的顺序串是指串的存储空间是确定的,即串值空间的大小是静态的,在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间,在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定,也是顺序存储空间)。 目标串和模式串:在串匹配运算过程中,将主串称为目标串,而将需要匹配的子串称为模式串,两者是相对的。 有效位移和无效位移：在串定位运算中,模式串从目标的首位开始向右位移,每一次合法位移后如果模式串与目标中相应的字符相同,则这次位移就是有效位移(也就是从此位置开始的匹配成功),反之,若有不相同的字符存在,则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 4、2 解：(1) stchr(*s,c)函数的效用是查找字符c在串s中的位置,若找到,则返回该位置,否则返回NULL。 因此: 执行p=stchr(s1,'t');后p的值是指向字符t的位置, 也就是p==&s1[5]。 执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。 执行p=strchr(s2,'6');之后,p的返回值是NULL。 (2)strcpy函数效用是串拷贝,strcat函数的效用是串联接。所以: 在执行strcpy(s3,s1); 后,s3的值是"Stocktom,CA" 在执行strcat(s3,","); 后,s3的值变成"Stocktom,Ca," 在执行完strcat(s3,s2);后,s3的值就成了"Stocktom,Ca,March 5,1999" 习题四参考答案 一、选择题 1．下面关于串的叙述中，哪一个是不正确的？（B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2．串的长度是指( A ) A. 串中包含的字符个数 B. 串中包含的不同字符个数 C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串B．联接C．模式匹配D．求串长 4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( C )。 A. O(m) B. O(n) C. O(n + m) D. O(n×m) 5. 串也是一种线性表，只不过( A )。 A. 数据元素均为字符 B. 数据元素是子串 C. 数据元素数据类型不受限制 D. 表长受到限制 6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素， 其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 7. 有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组占用的存储空间大小是（D ）个字节。 A. 48 B. 96 C. 252 D. 288 8.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序 为主序顺序存放，则数组元素 A[5，8]的存储首地址为( B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 9. 稀疏矩阵的三元组存储表示方法( B ) A. 实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可 B. 矩阵的非零元素个数和位置在操作过程中变化不大时较有效 C. 是一种链式存储方法 D. 比十字链表更高效 10. 用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有( A )域的结点表示。 A.5 B.4 C. 3 D. 2 二、填空题 1. 一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。2．串长度为0的串称为空串，只包含空格的串称为空格串。 3. 若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。 4. 寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。 5. 模式串t="ababaab"的next[]数组值为-1001231，nextval[]数组值为-10-10-130。 6. 设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序 存储，则元素A[5,5]的存储地址为1140。 《数据结构》课程设计报告 题目：模式匹配算法KMP及其应 用 学院 （系）： 班级： 学生学 号： 姓名： 指导教 师： 日期： 目录 摘要 (1) 一、绪论 (2) 1. 课程设计的背景 (2) 2. 课程设计的意义 (3) 3. 开发平台及其简介 (3) 二、需求分析 (3) 三、可行性分析 (5) 四、概要设计 1. 功能设计要求 (5) 2. 总体结构设计 (6) 3. 抽象数据类型串的定义 (9) 4. 函数调用关系 (10) 5. 主程序调用 (11) 五、详细设计 (12) 1. 宏定义 (12) 2. 数据元素结构定义 (13) 3. 功能具体实现 (13) 4. 主程序和菜单设计 (29) 六、设计和调试分析 (31) 七、测试结果 (33) 八、设计心得体会 (37) 九、用户手册 (37) 一十、附录 (43) 一十一、参考文献 (44) 摘要 本程序主要是通过获取一个子串，或新建一个新的文本文件，或和已有的文本文件进行匹配，分别利用了串的朴素模式匹配算法、串的模式匹配KMP算法、串的模式匹配改进算法等数据结构中学的知识实现了，在和文本文件中的主串进行匹配后返回子串在文本文件中出现的次数和出现位置所在的行的行号。 本程序除了实现串在定长顺序存储结构下的三种模式匹配算法，还实现了串在单链表存储结构下的模式匹配KMP算法，通过比较了串的不同存储结构下串的模式匹配算法，进一步加强了对串的理解及串的各类模式算法的掌握。 在使用串的定长存储结构时，考虑到书本上实现串的KMP算法时，储存串的数组下标是从1开始，为了进一步理解串，本程序另辟蹊径，特地定义了一个结构体，结构体中用来存储串的数组下标是从0开始，实现了串的模式匹配KMP算法。 第四章串 教学目的与要求 本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。 重点和难点 本章重点是掌握串上实现的模式匹配算法，其也是本章难点。 教学内容 第一节串的基本概念 ４.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; 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 读书破万卷下笔如有神 《一定能摸到红球吗？》说课稿 林银花 教材说明：一、１、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是 义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验, 收集，分析,帮助他们直观形象地感知。 第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长 4．已知串S=‘aaab’,其Next数组值为（）。 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘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 ) 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： 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)的返回值是什么? 第四章串作业 参考答案： 1、简述空串和空格串（或称空格符串）的区别？ 1）空串是指不包括任何字符的串，空格串指包含若干个空格字符的字符串； 2）空串长度为零，空格串长度为所包括的空格字符的个数。2、设s=‘I AM A STUDENT ’,t=‘GOOD’,q=‘WORKER’.求： 1）StrLength（s） 2）StrLength（t） 3）SubString（s，8，7） 4）SubSting（t，2，1） 5）Index（s，’A’） 6）index（s，t） 7）Replace（s，’STUDENT’，q） 8）Concat（SubString（s，6，2）,Concat（t，SubString （s，7，8））） 答： 1)StrLength（s）=14 2)StrLength（t）=4 3)SubString（s，8，7） = ‘STUDENT’ 4)SubSting（t，2，1） = ‘O’ 5)Index（s，’A’）= 3 6)index（s，t） = 0 7)Replace（s，’STUDENT’，q） = ‘I AM A WORKER ’ 8)Concat（SubString（s，6，2）,Concat（t，SubString（s， 7，8））） = ‘A GOOD STUDENT’ 3、若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),subs tr(S4,index(S2,‘8’),length(S2)))其结果是多少？ 答：ABC###G1234 4、下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。请将空格处填上正确的语句。 void maxcomstr(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) ___; 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). 实验内容与要求 内容： 问题描述：从键盘输入一个目标串S，并输入要匹配的模式串T，利用串的简单的模式匹配和KMP算法，定位模式串在主串中的位置。 要求： 设计要求 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 主控菜单设计要求：程序运行后，显示一个标题“模式匹配算法”，标题下方给出6个菜单项的内容和输入提示： 1．输入一个主串S 2．输入一个模式串T 3. 计算模式串T的next函数值 4．实现简单模式匹配 5．实现KMP模式匹配 6. 继续/否？（y/n?） #include j=next[j]; } } void printNext(String T) { int i; for(i=1;i<=T[0];i++) { printf("next[%d]:%d ",i,next[i]); } printf("\n"); } int KMP_INDEX(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) { if(j==0||S[i]==T[j]) { i++; j++; } else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; } int Index(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) { 第4章数组 选择题 1．以下对一维数组 a 的定义正确的是（ C ）。 （A）int n = 5, a[n]; （B）int a(5); （C）const int N = 5; int a[N]; （D）int n; cin>>n; int a[n]; 2．下列数组定义语句中，不合法的是（ A ）。 （A）int a[3] = { 0, 1, 2, 3 }; （B）int a[] = { 0, 1, 2 }; （C）int a[3] = { 0, 1, 2 }; （D）int a[3] = { 0 }; 3．已知 int a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, p = a;，不能 ．．表示数组 a 中元素的式子是（ C ）。 （A） a （B）p （C）a （D）a[ p a ] 4．已知 int a[] = { 0,2,4,6,8,10 }, p = a+1; 其值等于0的表达式是（ D ）。 （A） (p++) （B）(++p) （C）(p) （D）(p) 5．以下不能对二维数组a进行正确初始化的语句是（ C ）。 （A）int a[2][3] = { 0 }; （B）int a[][3] = { { 0,1 }, { 0 } }; （C）int a[2][3] = { { 0, 1 }, { 2, 3 }, { 4, 5 } }; （D）int a[][3] = { 0, 1, 2, 3, 4, 5 }; 6．已知int a[][3] = { { 0, 1 }, { 2, 3, 4 }, { 5, 6 }, { 7 } }; 则 a[2][1]的值是（ C ）。 （A）0 （B）2 （C）6 （D）7 7．已知int a[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 不能表示数组元素a[2][1]的地址是（ B ）。 （A）&a[2][1] （B）(a[2]+1) （C）a[2]+1 （D）(a+2)+1 8．已知char a[]={ "fortran", " basic", "pascal", "java", "c++" };，则 cout< 第四章串 一、内容提要 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); Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 《一定能摸到红球吗？》说课稿 林银花 一、教材说明： １、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验,收集，分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力，所以本节课中，应多为学生创造自主学习、 实验四顺序串的各种模式匹配 一、实验目的 熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。 二、实验内容 由用户随意输入两个串：主串S和模式串T，设S=‘s1s2…sn’，T=‘t1t2…tm’，且0 s->next=p->next; p->next=s; } void main(){ int num,e,x,y,count=-1,c=0,e1,t=-2147483648; bool mark=false; lin* L,* tx,* p,* q; L=(lin*)malloc(sizeof(lin)); L->next=NULL; cout<<"输入个数>=2"< //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; }实验三 串的模式匹配
模式匹配的KMP算法详解
第四章-串-习题及答案.doc
第4章 串与数组 习题参考答案
串的模式匹配
数据结构第04章 串
字符串的模式匹配算法
严蔚敏数据结构c语言版习题集答案第四章串
第四章：串
数据结构课后习题答案第四章
第4章串 作业(参考答案)
串的模式匹配算法实验报告
串的模式匹配
第四章习题答案
第四章 串
字符串匹配算法总结
严蔚敏《数据结构(c语言版)习题集》答案第四章串
串的模式匹配
串的朴素模式匹配算法(BF算法)