已阅读5页,还剩7页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第四章 串 习题及答案一、基础知识题4.1 简述下列每对术语的区别:空串和空白串;串常量和串变量;主串和子串;静态分配的顺序串和动态分配的顺序串;目标串和模式串;有效位移和无效位移。4.2 假设有如下的串说明:char s130=Stocktom,CA, s230=March 5 1999, s330, *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(&s15,ton)的返回值是什么?(5)调用函数stlen(strcat(s1,s2)的返回值是什么?4.3 设T0.n-1=adaabaabcaabaa,P0.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个字符。若istrlen(S),则没有字符被删除;若i+mstrlen(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=&s15。执行p=strchr(s2,9);后p的值是指向s2串中第一个9所在的位置,也就是p=&s29。执行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(3) 函数strcmp(串1,串2)的功能是串比较,按串的大小进行比较,返回大于0,等于0或小于0的值以表示串1比串2 大,串1等于串2 ,串1小于串2。因此在调用函数strcmp(s1,s2)后,返回值是大于0的数(字符比较是以ascii码值相比的)(4) 首先,我们要知道&s15是一个地址,当放在函数strcmp中时,它就表示指向以它为首地址的一个字符串,所以在strcmp( &s15,ton)中,前一个字符串值是tom,CA,用它和ton比较,应该是后者更大,所以返回值是小于0的数。(5)strlen是求串长的函数,我们先将s1,s2联接起来,值是Stocktom,CAMarch 5,1999,数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。4、3解:所有的有效位移i的值如下:2,5,9。算法NaveStrMatch(T,P)的返回值是第一个有效位移,因此是2。二、算法设计题: 4.4 解:算法如下:void StrInsert(char *S, char *T, int i)/将串T插入到串S的第i个位置上char *Temp;Temp=(char *)malloc(sizeof(charMaxsize);/ 设置一个临时串if(i=strlen(S)strcpy(Temp,&Si);/将第i位起以后的字符拷贝到临时串中strcpy(&Si, T);/将串T拷贝到串S的第i个位置处,覆盖后面的字符strcat(S,Temp);/把临时串中的字符联接到串S后面free( Temp );/以下提供验证程序#include string.h#include stdio.h#include malloc.h#define Maxsize 50/假设静态顺序串的空间长度为100void StrInsert(char *S, char *T, int i);void main()char AMaxsize=I am a boy.;char BMaxsize=very cool ;StrInsert( A,B,7);printf(%s,A);void StrInsert(char *S, char *T, int i)/将串T插入到串S的第i个位置上char *Temp;Temp=(char *)malloc(sizeof(charMaxsize);/ 设置一个临时串if(i=strlen(S)strcpy(Temp,&Si);/将第i位起以后的字符拷贝到临时串中strcpy(&Si, T);/将串T拷贝到串S的第i个位置处,覆盖后面的字符strcat(S,Temp);/把临时串中的字符联接到串S后面free( Temp );/程序结束4.5 解:算法如下:void StrDelete(char *S, int i ,int m)/串删除char TempMaxsize;/定义一个临时串if(i+m=strlen(S)& istrlen(S)strcpy(&Si,0);/把位置i的元素置为0,表示串结束/以下是验证程序#include string.h#include stdio.h#define Maxsize 40void StrDelete(char *S,int i, int m);void main()char AMaxsize=Are you a very beautiful girl?;StrDelete( A, 40, 10);printf(n%s,A);StrDelete( A, 10,15);printf(n%s,A);StrDelete( A, 7,50);printf(n%sn,A);void StrDelete(char *S, int i ,int m)char TempMaxsize;/定义一个临时串if(i+m=strlen(S)& istrlen(S)strcpy(&Si,0);/把位置i的元素置为0,表示串结束4.6 解:HString 是指以动态分配顺序串为存储表示,其定义为:typedef struct char *ch;int length;HString/*要进行这个算法设计,我们考虑到字符串是以指针的形式表示的,匹配时,用双重循环来实现,外循环用于进行合法位移(即令一指针沿目标串的元素向右移位)内循环进行字符匹配(即令两指针同时沿着目标串和模式串的元素进行移动并比较。直到第一次匹配成功或最终匹配失败。*/char* StringMatch( HString *T, HString *P)/串匹配char *t, *p;int m, n;for ( m=0; mlength-P-length; m+)/进行合法位移 t=&(T-chm);/指针t指向目标串的当前字符 p=&(P-ch0);/指针q指向模式串的第一个字符 for (n=0 ; nlength & pn=tn; n+ );/进行匹配,若有不同字符则进行下一次位移if (n=P-length) return &(T-chm);/返回第一次有效位移的地址return NULL;/匹配失败/以下是验证程序#include stdio.h#include typedef struct char *ch;int length;HString;char * StringMatch( HString *T, HString *P);void main()HString A=I am your friend.,17;HString B=am,2;printf(%sn,A.ch);printf(%sn,B.ch);printf(n%s,StringMatch( &A,&B);char* StringMatch( HString *T, HString *P)/串匹配char *t, *p;int m, n;for ( m=0; mlength-P-length; m+)/进行合法位移 t=&(T-chm);/指针t指向目标串的当前字符 p=&(P-ch0);/指针q指向模式串的第一个字符 for (n=0 ; nlength & pn=tn; n+ );/进行匹配,若有不同字符则进行下一次位移if (n=P-length) return &(T-chm);/返回第一次有效位移的地址return NULL;/匹配失败4.7解:加密算法可以用两个串中字符的一一对应关系来实现,当输入一个字符时,由算法在串1中查找其位置,然后用串2中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相返。/包括含算法的测试程序如下:#include #include typedef char SeqString27;/定义串类型int StrMatch(SeqString , char);void Encrypt(SeqString, SeqString , char *);void Decipher(SeqString, SeqString ,char *);#define Maxlen 100/以下两句设置加密及解密映射表/SeqString Original=abcdefghijklmnopqrstuvwxyz;SeqString Cipher =ngzqtcobmuhelkpdawxfyivrsj;void main( )char InMaxlen;printf(nEnter a String:(len %d),Maxlen);scanf(%s, &In);Encrypt(Original, Cipher, In);printf(nEnter a encrypted string:(len %d),Maxlen);scanf(%s,&In);Decipher(Original, Cipher,In);int StrMatch( SeqString S,char c)/串匹配(子串只有一个字符)int i;for (i=0; i strlen(S); i+)if (c=Si) return i;/匹配成功,返回位置return NULL;/映射表中没有相应字符/以下是题目要求的算法/void Encrypt( SeqString Original, SeqString Cipher, char *T)/加密int i,m;printf(n);for (i=0; i strlen(T); i+)m=StrMatch( Original, Ti);if(m!=NULL)Ti=Cipherm;printf(%s,T);void Decipher(SeqString Original , SeqString Cipher, char* T)/解密int i , m ;printf(n);for (i=0; i strlen(T); i+)m=StrMatch(Cipher ,Ti);if(m!=NULL)Ti=Originalm;printf(%s,T);4.8 解:由于S和P的长度不一定相等,所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。/算法如下:void StrReplace (char *T, char *P, char *S)/串替换int i , m;m=strlen (P);/取得子串长度i=StrMatch(T,P);/取得串匹配位置StrDelete( T,i,m);/删除匹配处子串StrInsert( T, S,i);/将S串插入到匹配位置处4.9解:书中第56页有明显提示,只要把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下:void NaveStrMatch (SeqString T, SeqString P) int i,j,k;int m=P.lenth;/模式串长度int n=T.length;/目标串长度for (i=0; in-m; i+)/ 确定合法位移j=0; k=i;while(jm&T.chk=P.chj)k+;j+;if(j=m) printf(n%d,i);/endforprintf(Search End.);4.10 解:这个算法是具有实用性的,但是做起来比较难,简单的算法应是这样的,利用4.9的算法在串T中找到一个P的匹配成功,马上进行串替换,然后从替换后的下一个位置进行匹配,直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。算法如下:void StrReplaceAll(char *T, char *P, char *S)/全部替换int i, j, k ;int m=strlen(P);/ 串P长度int n=strlen(T);/串T长度int l= strlen(S);int x=n-m;for(i=0; i=x; i+)/合法位移j=0; k=i;while(Tk=Pj)/进行匹配k+;j+;if(j=m)/匹配成功StrDelete( T,i,m);/删除匹配处子串StrInsert( T, S,i);/将S串插入到匹配位置处i+=l; /将查找位置移到替换后的下一个字符处,避免重复替换x+=l;/endif/endfor/end-/以下给出验证程序#include #include #include #define Maxsize 100void StrDelete(char* , int ,int);void StrInsert(char* , char* , int );void StrReplaceAll(char* , char* , char* );void main( )/验证程序char AMaxsize=A good boy is a good comrade.;char B=good;char C=very cool;printf(The original string is: %s,A);printf(n%s-%s,B,C);StrReplaceAll( A,B,C);printf(nThe new String is:%s,A);void StrDelete(char *S, int i ,int m)char TempMaxsize;/定义一个临时串if(i+m=strlen(S)& istrlen(S)strcpy(&Si,0);/把位置i的元素置为0,表示串结束void StrInsert(char *S, char *T, int i)/将串T插入
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 服装出口合同常用英文句子
- 五年级上册数学培优奥数讲义-第16讲 估算与近似值
- 2021-2022学年吉林省榆树一中五校联考高一物理第二学期期末调研试题含解析
- 2021-2022学年吉林省白城市洮南第十中学物理高一第二学期期末达标检测试题含解析
- 2021-2022学年湖南省怀化市中方县第二中学物理高一下期末教学质量检测试题含解析
- 2021-2022学年湖北省武汉市新洲三中物理高一下期末统考试题含解析
- 2021-2022学年河北南和一中高一物理第二学期期末复习检测模拟试题含解析
- 柯桥区七年级下学期语文期末考试卷
- 安徽省安庆市名校联考2023-2024学年八年级上学期期中考试英语试题
- 【课件】家的意味+课件-统编版道德与法治七年级上册
- 统编版四年级上册语文第二单元 习作:我的家人 课件
- (正式版)HG∕T 21633-2024 玻璃钢管和管件选用规定
- 特种设备使用单位日管控、周排查、月调度示范表
- 唐僧师徒摘桃子小学三年级数学PPT
- 排痰机简介临床版
- [医学]胃癌护理优秀教案
- 服务业产业内贸易理论探究
- 莱茵FMEA培训教材(第四版)PPT优秀课件
- 志书编写的基本步骤
- 苏教版三年级数学上册第二单元《千克和克》教材分析及全部教案(共3课时)
- 幼儿园园长月度工作计划表(精选篇)
评论
0/150
提交评论