第四章 串 习题及答案
更新时间:2024-02-27 11:14:01 阅读量: 综合文库 文档下载
第四章 串 习题及答案 一、基础知识题
4.1 简述下列每对术语的区别:
空串和空白串;串常量和串变量;主串和子串;静态分配的顺序串和动态分配的顺序串;目标串和模式串;有效位移和无效位移。 4.2 假设有如下的串说明:
char s1[30]=\
(1)在执行如下的每个语句后p的值是什么?
p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');
(2)在执行下列语句后,s3的值是什么?
strcpy(s3,s1); strcat(s3,\
(3)调用函数strcmp(s1,s2)的返回值是什么?
(4)调用函数strcmp(&s1[5],\的返回值是什么?
(5)调用函数stlen(strcat(s1,s2))的返回值是什么?
4.3 设T[0..n-1]=\当用模式串匹配目标串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
则字符串\被加密为\试写一算法将输入的文本串进行加密后输出;另写一算法,将输入的已加密的文本串进行解密后输出。
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的值是\在执行strcat(s3,\后,s3的值变成\
在执行完strcat(s3,s2);后,s3的值就成了\
(3) 函数strcmp(串1,串2)的功能是串比较,按串的大小进行比较,返回大于0,等于0或小于0的值以表示串1比串2 大,串1等于串2 ,串1小于串2。因此在调用函数strcmp(s1,s2)后,返回值是大于0的数(字符比较是以ascii码值相比的)
(4) 首先,我们要知道&s1[5]是一个地址,当放在函数strcmp中时,它就表示指向以它为首地址的一个字符串,所以在strcmp( &s1[5],\中,前一个字符串值是\用它和\比较,应该是后者更大,所以返回值是小于0的数。
(5)strlen是求串长的函数,我们先将s1,s2联接起来,值是\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(char[Maxsize]));// 设置一个临时串 if(i<=strlen(S)) { strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处,覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } }
//以下提供验证程序 #include \#include \#include \
#define Maxsize 50 //假设静态顺序串的空间长度为100 void StrInsert(char *S, char *T, int i); void main() { char A[Maxsize]=\ char B[Maxsize]=\ StrInsert( A,B,7); printf(\}
void StrInsert(char *S, char *T, int i) { //将串T插入到串S的第i个位置上 char *Temp; Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 if(i<=strlen(S))
{ strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处,覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 } free( Temp ); }//程序结束 4.5
解:算法如下:
void StrDelete(char *S, int i ,int m) { //串删除 char Temp[Maxsize];//定义一个临时串 if(i+m //以下是验证程序 #include \#include \#define Maxsize 40 void StrDelete(char *S,int i, int m); void main() { char A[Maxsize]=\ StrDelete( A, 40, 10); printf(\ StrDelete( A, 10,15); printf(\ StrDelete( A, 7,50); printf(\} void StrDelete(char *S, int i ,int m) { char Temp[Maxsize];//定义一个临时串 if(i+m 解:HString 是指以动态分配顺序串为存储表示,其定义为: typedef struct { char *ch; int length; }HString /*要进行这个算法设计,我们考虑到字符串是以指针的形式表示的,匹配时,用双重循环来实现,外循环用于进行合法位移(即令一指针沿目标串的元素向右移位)内循环进行字符匹配(即令两指针同时沿着目标串和模式串的元素进行移动并比较。直到第一次匹配成功或最终匹配失败。*/ char* StringMatch( HString *T, HString *P) { //串匹配 char *t, *p; int m, n; for ( m=0; m<=T->length-P->length; m++)//进行合法位移 { t=&(T->ch[m]);//指针t指向目标串的当前字符 p=&(P->ch[0]);//指针q指向模式串的第一个字符 for (n=0 ; n //以下是验证程序 #include \#include typedef struct { char *ch; int length; }HString; char * StringMatch( HString *T, HString *P); void main() { HString A={\ HString B={\ printf(\ printf(\ printf(\} char* StringMatch( HString *T, HString *P) { //串匹配 char *t, *p; int m, n; for ( m=0; m 4.7解:加密算法可以用两个串中字符的一一对应关系来实现,当输入一个字符时,由算法在串1中查找其位置,然后用串2中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相返。 //包括含算法的测试程序如下: #include typedef char SeqString[27];//定义串类型 int StrMatch(SeqString , char); void Encrypt(SeqString, SeqString , char *); void Decipher(SeqString, SeqString ,char *); #define Maxlen 100 //以下两句设置加密及解密映射表//// SeqString Original=\SeqString Cipher =\void main( ) { char In[Maxlen]; printf(\ scanf(\ Encrypt(Original, Cipher, In); printf(\ scanf(\ Decipher(Original, Cipher,In); } int StrMatch( SeqString S,char c) { //串匹配(子串只有一个字符) int i; for (i=0; i< strlen(S); i++) {if (c==S[i]) return i;}//匹配成功,返回位置 return NULL;//映射表中没有相应字符 } /////////////以下是题目要求的算法////////// void Encrypt( SeqString Original, SeqString Cipher, char *T) { //加密 int i,m; printf(\ for (i=0; i < strlen(T); i++) { m=StrMatch( Original, T[i]); if(m!=NULL) T[i]=Cipher[m]; } printf(\ } void Decipher(SeqString Original , SeqString Cipher, char* T) { //解密 int i , m ; printf(\ for (i=0; i < strlen(T); i++) { m=StrMatch(Cipher ,T[i]); if(m!=NULL) T[i]=Original[m]; } printf(\} 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; i 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(T[k]==P[j]) //进行匹配 {k++;j++;} if(j==m){ //匹配成功 StrDelete( T,i,m);//删除匹配处子串 StrInsert( T, S,i);//将S串插入到匹配位置处 i+=l; //将查找位置移到替换后的下一个字符处,避免重复替换 x+=l;}//endif }//endfor }//end ---------------------------------------- //以下给出验证程序 #include #define Maxsize 100 void StrDelete(char* , int ,int); void StrInsert(char* , char* , int ); void StrReplaceAll(char* , char* , char* ); void main( ) { //验证程序 char A[Maxsize]=\ char B[]=\ char C[]=\ printf(\ printf(\ StrReplaceAll( A,B,C); printf(\} void StrDelete(char *S, int i ,int m) { char Temp[Maxsize];//定义一个临时串 if(i+m void StrInsert(char *S, char *T, int i) { //将串T插入到串S的第i个位置上 char *Temp; Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 if(i<=strlen(S)) { strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处,覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 } free( Temp ); } 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(T[k]==P[j]) //进行匹配 {k++;j++;} if(j==m){ //匹配成功 StrDelete( T,i,m);//删除匹配处子串 StrInsert( T, S,i);//将S串插入到匹配位置处 i+=l; //将查找位置移到替换后的下一个字符处,避免重复替换 x+=l;}//endif }//endfor }//end 4.11 解:查找过程是这样的,取S中的一个字符(结点),然后和T中所有的字符一一比较,直到比完仍没有相同的字符时,查找过程结束,否则再取S中下一个字符,重新进行上述过程。算法如下: char SearchNo( LinkString S, LinkString T) { //查找不在T中出现的字符 LinkStrNode *p,*q; p=S; q=T; while (p) { //取S中结点字符 while(q&&p->data!=q->data)//进行字符比较 q=q->next; if(q==NULL)return p->data;//找到并返回字符值 q=T; //指针恢复串T的开始结点 p=p->next; } printf(\ return NULL; } 4.11 解:查找过程是这样的,取S中的一个字符(结点),然后和T中所有的字符一一比较,直到比完仍没有相同的字符时,查找过程结束,否则再取S中下一个字符,重新进行上述过程。算法如下: char SearchNo( LinkString S, LinkString T) { //查找不在T中出现的字符 LinkStrNode *p,*q; p=S; q=T; while (p) { //取S中结点字符 while(q&&p->data!=q->data)//进行字符比较 q=q->next; if(q==NULL)return p->data;//找到并返回字符值 q=T; //指针恢复串T的开始结点 p=p->next; } } printf(\return NULL;
正在阅读:
第四章 串 习题及答案02-27
《绕着地球去旅行》读后感10篇12-12
各类压力试验机校准方法03-27
个人建军大业观后感多篇04-17
《进入新时代,改革开新篇》读后感12-12
《最后的姿势》教学设计506-23
个人红楼梦读后感多篇04-17
我和我的父辈观后感范本参考04-17
保险公司工作总结范本参考04-17
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- 第四章
- 习题
- 答案
- 西山沙漠化土地综合改造治理项目可行性研究报告
- 浅谈中国当代的教育问题
- 皮革上光剂项目可行性研究报告(目录) - 图文
- 2014年芜湖市进口汽车保有量排名分析报告 - 图文
- 濠河的导游词
- 小学英语有效课题结题报告
- 数据仓库环境下ERP系统内部控制新视角
- 关于电网工程前期管理工作的探讨
- 关于乡村建设规划的几点思考-精选模板
- 2016年春人教版七年级地理下册第七章 我们邻近的地区和国家第一
- 新课程阶段达标测试三年级语文下册4(1)
- 旅游学概论
- 遗失的梦
- 肉干项目可行性研究报告(目录) - 图文
- 最新-学习贯彻残疾人事业发展意见的思考 精品
- 食品学院2011-2012学年度(下)学生德育加分公示
- 《高级英语视听说》课程评估体系的多模态式构建
- 应聘个人工作简历模板(32)
- 四川省棠湖中学2019届高三周练(一)试题(解析版)- 副本
- 基子道德决策模型的高职会计诚信教育反思