第四章 串 (参考答案)
在以下习题解答中，假定使用如下类型定义：
#define MAXSIZE 1024
typedef struct
{ char data[MAXSIZE];
int
curlen; // curlen表示终端结点在向量中的位置
}seqstring;
typedef struct node
{char data;
struct
node *next ；
}linkstring;
4.2 int index(string s,t)
//s,t是字符串，本算法求子串t在主串s中的第一次出现，若s串中包含t串，返回其
//第一个字符在s中的位置，否则返回0
{m=length(s); n=length(t);
i=1;
while(i<=m-n+1)
if(strcmp(substr(s,i,n),t)==0) break;
else i++;
if(i<=m-n+1) return(i);//模式匹配成功
else return(0);//s串中无子串t
}//算法index结束
4.3 设A=” ”, B=”mule”, C=”old”, D=”my” 则：
（a） strcat（A,B）=”mule”
（b） strcat(B,A)=”mule”
（c） strcat(strcat(D,C),B)=”myoldmule”
（d） substr(B,3,2)=”le”
（e） substr(C,1,0)=” ”
（f） strlen(A)=0
（g） strlen(D)=2
（h） index(B,D)=0
（i） index(C,”d”)=3
（j） insert(D,2,C)=”moldy”
（k） insert(B,1,A)=”mule”
（l） delete(B,2,2)=”me”
（m） delete(B,2,0)=”mule”
（n） replace(C,2,2,”k”)=”ok”
4.4 将S=“（xyz）*”转为T=“（x+z）*y”
S=concat(S, substr(S,3,1)) // ”(xyz)*y”
S=replace(S,3,1,”+”) // ”(x+z)*y”
4.5
char search(linkstring *X,
linkstring *Y)
// X和Y是用带头结点的结点大小为1的单链表表示的串，本算法查找X中 第一个不在Y中出现的字符。算法思想是先从X中取出一个字符，到Y中去查找，如找到，则在X中取下一字符，重复以上过程；若没找到，则该字符为所求
{ linkstring *p, *q,*pre; // p,q为工作指针，pre控制循环
p=X->next; q=Y->next;
pre=p;
while (p && q)
{ ch=p->data;
// 取X中的字符
while (q
&& q->data!=ch) q=q->next; // 和Y中字符比较
if (!q) return(ch);
// 找到Y中没有的字符
else { pre=p->next;
// 上一字符在Y中存在，
p=pre;
// 取X中下一字符。
q=Y->next;
// 再从Y的第一个字符开始比较
}
}
return(null); //
X中字符在Y中均存在
}// 算法结束
4.6
int strcmp(seqstring *S,
seqstring *T)
// S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1
{int i=0;
while (s->ch[i]!=’\0’
&& t->ch[i]!=’\0’)
if
(s->ch[i]>t->ch[i]) return(1);
else if (s->ch[i]<t->ch[i])
return(-1);
else i++; // 比较下一字符
if (s->ch[i]!=’\0’&&
t->ch[i]==0) return(1);
else if (s->ch[i]==’\0’&& t->ch[i]!=0)
return(-1);
else
return(0);
}// 算法结束
4.7
linkstring *invert(linkstring
*S, linkstring *T)
// S和T是用带头结点的结点大小为1的单链表表示的串，S是主串，T是
// 模式串。本算法是先模式匹配，查找T在S中的第一次出现。如模式匹
// 配成功，则将S中的子串（T串）逆置。
{linkstring *pre,*sp, *tp;
pre=S; // pre是前驱指针，指向S中与T匹配时，T
中的前驱
sp=S->next; tp=T->next;//sp 和tp分别是S和T串上的工作指针
while (sp && tp)
if (sp->data==tp->data)
// 相等时后移指针
{sp=sp->next; tp=tp->next;}
else // 失配时主串回溯到下一个字符，子串再以第一个字符开始
{pre=pre->next;
sp=pre->next; tp=T->next;}
if (tp!=null) return (null); // 匹配失败，没有逆置
else // 以下是T串逆置
{tp=pre->next; // tp是逆置的工作指针，现在指向待逆置的第一个字符
pre->next=sp; // 将S中与T串匹配时的前驱指向匹配后的后继
while (tp!=sp)
{ r=tp->next;
tp->next=pre->next;
pre->next=tp;
tp=r
}
}
}// 算法结束