|
简述下列每对术语的区别空串和空白串串常量和串变量主串和子串静态分配的顺序串和动态分配的顺序串目标串和模式串有效位移和无效位移 答 ●空串是指不包含任何字符的串它的长度为零 空白串是指包含一个或多个空格的串空格也是字符 ●串常量是指在程序中只可引用但不可改变其值的串 串变量是可以在运行中改变其值的 ●主串和子串是相对的一个串中任意个连续字符组成的串就是这个串的子串而包含子串的串就称为主串 ●静态分配的顺序串是指串的存储空间是确定的即串值空间的大小是静态的在编译时刻就被确定 动态分配的顺序串是在编译时不分配串值空间在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定也是顺序存储空间) ●目标串和模式串:在串匹配运算过程中将主串称为目标串而将需要匹配的子串称为模式串两者是相对的 ●有效位移和无效位移在串定位运算中模式串从目标的首位开始向右位移每一次合法位移后如果模式串与目标中相应的字符相同则这次位移就是有效位移(也就是从此位置开始的匹配成功)反之若有不相同的字符存在则此次位移就是无效位移(也就是从此位置开始的匹配失败) 假设有如下的串说明 char s[]=StocktomCA s[]=March s[] *p; ()在执行如下的每个语句后p的值是什么? p=stchr(st); p=strchr(s); p=strchr(s); ()在执行下列语句后s的值是什么? strcpy(ss); strcat(s); strcat(ss); ()调用函数strcmp(ss)的返回值是什么? ()调用函数strcmp(&s[]ton)的返回值是什么? ()调用函数stlen(strcat(ss))的返回值是什么? 解 () stchr(*sc)函数的功能是查找字符c在串s中的位置若找到则返回该位置否则返回NULL 因此: 执行p=stchr(st);后p的值是指向第一个字符t的位置 也就是p==&s[] 执行p=strchr(s);后p的值是指向s串中第一个所在的位置也就是p==&s[] ` 执行p=strchr(s);之后p的返回值是NULL ()strcpy函数功能是串拷贝strcat函数的功能是串联接所以: 在执行strcpy(ss); 后s的值是StocktomCA 在执行strcat(s); 后s的值变成StocktomCa 在执行完strcat(ss);后s的值就成了StocktomCaMarch ()函数strcmp(串串)的功能是串比较按串的大小进行比较返回大于等于或小于的值以表示串比串 大串等于串 串小于串因此在调用函数strcmp(ss)后返回值是大于的数(字符比较是以ascii码值相比的) ()首先我们要知道&s[]是一个地址当放在函数strcmp中时它就表示指向以它为首地址的一个字符串所以在strcmp( &s[]ton)中前一个字符串值是tomCA用它和ton比较应该是后者更大所以返回值是小于的数 ()strlen是求串长的函数我们先将ss联接起来值是StocktomCAMarch 数一数有几个字符?是不是个(空格也是一个)? 所以返回值是 设T[n]=adaabaabcaabaaP[m]=aab当用模式串匹配目标串T时请给出所有的有效位移算法NaiveStrMatch(TP)返回的位移是哪一个位移 解 所有的有效位移i的值为 算法NaveStrMatch(TP)的返回值是第一个有效位移因此是 利用C的库函数strlenstrcpy和strcat写一算法void StrInsert(char *S char *T int i)将串T插入到串S的第i个位置上若i大于S的长度则插入不执行 解 算法如下 void StrInsert(char *S char *T int i) {//将串T插入到串S的第i个位置上 char *Temp; if(i<=strlen(S)) { Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 strcpy(Temp&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i] T);//将串T拷贝到串S的第i个位置处覆盖后面的字符 strcat(STemp);//把临时串中的字符联接到串S后面 free( Temp ); } } 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *Sint i int m)删去串S中从位置i开始的连续m个字符若i≥strlen(S)则没有字符被删除若i+m≥strlen(S)则将S中从位置i开始直至末尾的字符均删去 解 算法如下 void StrDelete(char *S int i int m) { //串删除 char Temp[Maxsize];//定义一个临时串 if(i+m<strlen(S)) { strcpy (Temp &S[i+m]);//把删除的字符以后的字符保存到临时串中 strcpy( &S[i]Temp);//用临时串中的字符覆盖位置i之后的字符 } else if(i+m>=strlen(S)&& i<strlen(S)) { strcpy(&S[i]\);//把位置i的元素置为\表示串结束 } } 以HString为存储表示写一个求子串的算法 解 HString 是指以动态分配顺序串为存储表示其定义为 typedef struct { char *ch; int length; }HString; void *substr( HString *subHString *sint posint len) {//用sub返回串s的第pos个字符起长度为len的子串sub初始时为一空串 //pos的合法位置为<=pos<=s>length int i; if (pos<||pos>s>length||len<=) Error(parameter error!);//参数不合法子串为空串 if (s>length<pos+len)//s串中没有足够的元素 sub>len=s>lengthpos;//设置子串的串长 else sub>length=len; //设置子串的串长 sub>ch=(char *)malloc(len*sizeof(char));//为sub>ch申请结点空间 for(i=;i<sub>length;i++)//将s串中pos位置开始的共sub>length个字符复制到sub串中 sub>ch[i]=s>ch[pos+i]; } 一个文本串可用事先给定的字母映射表进行加密例如设字母映射表为 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试写一算法将输入的文本串进行加密后输出另写一算法将输入的已加密的文本串进行解密后输出 解 加密算法可以用两个串中字符的一一对应关系来实现当输入一个字符时由算法在串Original中查找其位置然后用串Cipher中相应位置的字符去替换原来的字符就可以了解密算法则恰恰相返 设字母映射表的存储结构如下 #define MaxStrSize typedef struct{ char Original[MaxStrSize]; //可容纳个字符并依次存储在Original[n]中 char Cipher[MaxStrSize]; //可容纳个字符并依次对应Original表中的密码 int length; }SeqString; void Encrypt( SeqString codetable) {//加密算法 char ch; int i; while((ch=getchar())!=\) { i=; while (i<codetablelength&&ch!=codetableOriginal[i]) i++; if (i>=codetablelength) Error(data error!); else printf(%ccodetableCipher[i]); } printf(\n); } void Decipher(SeqString Original SeqString Cipher char* T) {//解密算法 char ch; while((ch=getchar())!=\) { i=; while (i<codetablelength&&ch!=codetableCipher[i]) i++; if (i>=codetablelength) Error(data error!); else printf(%ccodetableOriginal[i]); } printf(\n); } 写一算法void StrReplace(char *T char *P char *S)将T中首次出现的子串P替换为串S注意S和P的长度不一定相等可以使用已有的串操作 解 由于S和P的长度不一定相等所以在替换时可能要移动字符元素我们可以用到前面设计的一系列算法算法如下 void StrReplace (char *T char *P char *S) {//串替换 int i m; m=strlen (P);//取得子串长度 i=StrMatch(TP);//取得串匹配位置 StrDelete( T |
