strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中
strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 }
else if(i+m>=strlen(S)&& i strcpy(&S[i],\把位置i的元素置为'\\0'，表示串结束 } } 关闭 4.6 以HString为存储表示，写一个求子串的算法。 解： HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error(\参数不合法，子串为空串 if (s->length sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间 for(i=0;i 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 则字符串\被加密为\试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。 解： 加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串Original中查找其位置，然后用串Cipher中相应位置的字符去替换 原来的字符就可以了。解密算法则恰恰相返。 设字母映射表的存储结构如下： #define MaxStrSize 26 typedef struct{ char Original[MaxStrSize]; //可容纳26个字符，并依次存储在Original[0..n]中 char Cipher[MaxStrSize]; //可容纳26个字符，并依次对应Original表中的密码 int length; }SeqString; void Encrypt( SeqString codetable) {//加密算法。 char ch; int i; while((ch=getchar())!='\\0') { i=0; while (i if (i>=codetable.length) Error(\ else printf(\ } printf(\ } void Decipher(SeqString Original , SeqString Cipher, char* T) {//解密算法。 char ch; while((ch=getchar())!='\\0') { i=0; while (i if (i>=codetable.length) Error(\ else printf(\ } printf(\ } 关闭 4.8 写一算法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(T,P);//取得串匹配位置 StrDelete( T,i,m);//删除匹配处子串 StrInsert( T, S,i);//将S串插入到匹配位置处 } 关闭 4.9 将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。 解： 把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下： void NaveStrMatch (SeqString T, SeqString P) { int i,j,k; int m=P.lenth;//模式串长度 int n=T.length;//目标串长度 for (i=0; i j=0; k=i; while(j k++;j++; } if(j==m) printf(\ }//endfor printf(\ } 关闭 *4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。 解： 这个算法是具有实用性的，但是做起来比较难，简单的算法应是这样的，利用4.9的算法在串T中找到一个P的匹配成功，马上进行串替换，然后从替换后的下一个位置进行匹配，直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。 算法如下： void StrReplaceAll(char *T, char *P, char *S) {//全部替换 int i, j, k ; i=0; while(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+=strlen(S); //将查找位置移到替换后的下一个字符处，避免重复替换 }//endif else i++; }//endwhile }//end 关闭 4.11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 解: 查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下： 链串的结构类型定义: typedef struct node{ char data; struct node *next; }LinkStrNode; //结点类型 typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针 char SearchNoin( 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; } 关闭 第五章 数组与广义表 5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。 解： 按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 第五章 数组与广义表 5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。 解： 按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212 按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：