第四章 串 （答案版）

第四章 串 1、 简述下列每个术语的区别： 空串和空格串； 串变量和串常量； 主串和子串； 串名和串值； 答：空串和空格串：空串是长度为0的串，它不包含任何字符，空格串是由空格字符组成的串，长度大于0。 串变量和串常量：编程中经常使用串变量和串常量，其中，串变量可以依需要进行多次数值变换，但必须是字符串型，而串常量一经赋值，即不能改变。 主串和子串：一个字符串中任意个连续的字符组成的子序列称为该串的子串。该串相应地称为主串。 串名和串值：一个串在程序中被定义成一个变量或常量的名称，称为该串的串名，串名实际保存的串值，称为串值，因为一般编程中，采用字符来表达变量或常量名称，所以，要注意不要搞混。 2、 用串的其他基本运算构造串的子串定位运算index。 int index(s,t){ l1=length(s); l2=length(t); for(i=1;i<=l1-l2){ x=sunstr(s,l1,l2); if x==t return I; } return 0 } 3、设有A=””，B=”mule”，C=”old”，D=”my”，请计算下面运算的结果： （1）strcat(A,B) （2）substr(B,3,2) （3）strlen(A) （4）index(B,D) （5）insert(B,1,A) （6）replace(C,2,2,”k”) 答：（1）strcat(A,B)=”mule” (2) substr(B,3,2)=”le” (3) strlen(A)=0 (4) index(B,D)=0 (5) insert(B,1,A)= “mule” (6) replace(C,2,2,”k”)=”ok” 4、 已知：S=”(xyz)”，T=”(x+z)*y”，利用联接、求子串和置换等基本运算，将S转换为T。 答：T1=sunstr(s,2,1) T2=substr(s,3,1) T3=substr(s,4,1) T=strcat(“(”,t1) T=strcat(T,”+”) T=strcat(T,t3) T=strcat(T,”)”) T=strcat(T,”*”) T=strcat(T,T2) 5、 若X和Y是用结点大小为1的单链表表示的串，试设计一个算法找出X中第一个不在Y中出现的字符。 linklist* temp = y; while (x != NULL) { while (temp != NULL && x->data != temp->data) temp = temp->next; if (temp == NULL) return x->data; else { x = x->next; temp = y; } } 6、 试设计一个算法，在顺序串上实现串的比较运算strcmp(S,T)。 while(*s == *t) {          if(*s == '\0') return0;          s++;          t++; }     return *s - *t; 7、 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法将S中首次与串T匹配的子串逆置。 linklist *s = CREATLIST(); linklist *t = CREATLIST(); linklist *head_t = t; linklist *temps = s; linklist *tempt = t; linklist *p, *m, *n; for (;;) { while (temps != NULL && temps->data == tempt->data) { temps = temps->next; tempt = tempt->next; } if (temps == NULL) break; else { t = t->next; temps = s; tempt = t; } } p = head_t; while (p->next != t) p = p->next; m = t->next; n = m->next; t->next = tempt; while (n != tempt) { m->next = t; t = m; m = n; n = n->next; } m->next = t; p->next = m; 8、设有两个字符串，目标 S=“abcabeacadaadadasfsf”,模式