习题四及上机答案.doc

习题四

⒋１简述下列每对术语的区别：
空串和空格串；串变量和串常量；主串和子串；串名和串值
答：
空格串：由一个或多个空格组成的串称为空格串。
空串：不含任何字符的串，它的长度为0。

⒋２对于字符串的每个基本运算，讨论是否可用其它基本运算构

4.3 设串s1='ABCDEFG',s2='PQRST',函数con(x,y)返回x和y串的连接串，subs(s,I,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2)))的结果串是什么
  答：BCDEFEF
4.4 设s='I AM A STUDENT'， t='GOOD'， q='WORKER'。
求：Len(s)，Len(t)，SubStr(s,8,7)，SubStr(t,2,1)，Index(s,'A')，Index(s,t)，Replace(s,'STUDENT',q)和Concat(substr(s,6,2),Concat(t,substr(s,7,8)))。
 答:len(s)=14;len(t)=4;substr(s,8,7)=‘STUDENT’;
Substr(t,2,1)=‘o’;index(s,’A’)=3;
index(s,t)=-1;
Replace(s,'STUDENT',q)=‘I AM A WORKER’;
Concat(substr(s,6,2),Concat(t,substr(s,7,8)))=
‘A GOOD STUDENT’
4.5试问执行以下过程会产生怎样的输出结果？
Demonstrate()
{
Assign(s,'THIS IS A BOOK');
Replace(s,SubStr(s,3,7),'ESE ARE');
Assign(t,Concat(s,'S'));
Assign(u,'XYXYXYXYXYXY');
Assign(v,SubStr(u,6,3));
Assign(w,'W');
printf('t=%s v=%s u=%s %s',t,v,u,replace(u,v,w));
}/*demonstrate*/
t=‘THESE ARE A BOOKS’
V=‘YXY’
U=‘XYXYXYXYXYXY’
XWXWXW
4.6已知：s='(XYZ)+*'，t='(X+Z)*Y'。试利用联接、求子串和置换等运算，将s转化为t。
Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new
{
  Initstack(s); //s的元素为Stringtype类型
  for(i=1;i<=Strlen(str);i++)
  {
    r=SubString(str,i,1);
    if(r为字母) push(s,r);
    else
    {
      if(StackEmpty(s)) return ERROR;
      pop(s,a);
      if(StackEmpty(s)) return ERROR;
      pop(s,b);
      StrAssign(t,Concat(r,b));
      StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c
      push(s,c);
    }
  }//for
  pop(s,new);
  if(!StackEmpty(s)) return ERROR;
  return OK;
}//NiBoLan_to_BoLan

4.7设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时，请给出所有的有效位移。
 4.8写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。
suan(slstrtype *x,slstrtype *y)
{
char *p,*q;
char m;
p=x;
q=y;
while(p!=NULL)
{
m=p->ch;
while(q!=NULL)
{
if(m!=q->ch) return m;
q=q->next;
}
p=p->next;
}
return -1; /*S中的字符在Y中都有*/
}

⒋9在串的顺序存储结构上实现串的比较运算StrCmp(S,T)。
 int strcmp(a，b)
orderstring *a，*b;
{
int i，minlen;
if (a->len<b->len) minlen=a->len; /*计算:minlen=min(m，n)*/
else minlen=b->len;
i=0;
while (i<=minlen)
{
if (a->vec[i]<b->vec[i]) return(-1); /*s<t*/
else if (a->vec[i]>b->vec[i]) return(1); /*s>t*/
else i++;
} /*以下是公共长度部分均相同的情况*/
if (a->len==b->len) return(0); /*s=t*/
else if (a->len<b->len) return(-1); /*s<t*/
else return(1); /*s>t*/
}

4.10_若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符
char findfirst(x，y)
linkstring *x，*y;
{
linkstring *p;
char c;
p=x;
if (x==NULL) printf("x 为空\n");
else
{
while (found(p->info，y)) p=p->link;
c=p->info;
}
return(c);
}
/*函数 found()的功能是:若 head 的链表中包含有 data 域为 x 的*/
/*结点则返回 1；否则返回 0*/
int found(d，head)
linkstring *head;
char d;
{
while (head!=NULL && head->info!=d)
head=head->link;
if (head==NULL) return(0);
else return(1);
}

第四章上机内容
1，  设计一个算法将串中所有的字符倒过来重新排列。
dao(slstrtype *p)
{
slstrtype *m,*n;
char a[50]; /*最大字符数*/
int top=0;
m=p;n=p;
while(m!=NULL)
{
a[top++]=m->ch;
m=m->next;
}
while(top>=0)
{
n->ch=a[--top];
n=n->next;
}
return p;
}
2、采用顺序结构存储串，编写一个函数index(s1,s2),用于判断s2是否是s1的子串。若是，返回其在主串中的位置；否则返回-1。
提示：设s1=“a1a2…am” ； s2=“b1b2…bn” 从s1中找出与b1匹配的字符ai,若ai=b1,则判断是否ai+1=b2,…,ai+n-1=bn,若都相等，s2为s1的子串，否则继续比较ai之后的字符。
#define N 20
int substring (s1，s2)
orderstring *s1，*s2;
{
int i，j，k，yes=0;
i=0;
while (i<s1->len && !yes)
{
j=0;
if (s1->vec[i]==s2->vec[j])
{
k=i+1;
j++;
while (s1->vec[k]==s2->vec[j])
{
k++;
j++;
}
if (j==s2->len) yes=1;
else i++;
}
else i++;
}
return(yes);
}

3、利用串的基本运算，编写一个算法删除串s1中所有s2子串。
提示：本题利用2题的index()函数和删除子串函数循环实现。

#define N 20
#include<string.h>
int index(char *s1,char *s2)
{
int x,i,j;
x=-1;
for(i=0;*(s1+i)!='\0';i++)
{
if(*(s1+i)==*s2)
{
for(j=1;*(s2+j)!='\0';j++)
if(*(s1+i+j)!=*(s2+j)) break;
if(*(s2+j)=='\0') x=i+1;
}
}
return(x);
}
void del(char *s1,char *s2)
{
int i,j;
while(index(s1,s2)!=-1)
{
i=index(s1,s2);
for(j=0;j<=strlen(s2);j++)
{
s1[i-1]=s1[i+strlen(s2)-1];
i++;
}
}
}
main()
{
char s1[N],s2[N];
printf("input the string s1:\n");
scanf("%s",s1);
printf("input the string s2:\n");
scanf("%s",s2);
while(index(s1,s2)!=-1)
{
printf("the positon of s2 is %d.\n",index(s1,s2));
del(s1,s2);
}
printf("the result is:\n%s",s1);
getch();
}