数据结构课后习题及解析第四章.doc

第四章习题
1、 设s=’I AM A STUDENT’,  t=’GOOD’,  q=’WORKER’。给出下列操作得结果:
StrLength(s);  SubString(sub1,s,1,7);  SubString(sub2,s,7,1);
StrIndex(s,’A’,4);  StrReplace(s,’STUDENT’,q); 
StrCat(StrCat(sub1,t), StrCat(sub2,q));
2、 编写算法,实现串得基本操作StrReplace(S,T,V)。
3、 假设以块链结构表示串,块得大小为1,且附设头结点。
试编写算法,实现串得下列基本操作:
StrAsign(S,chars); StrCopy(S,T); Strpare(S,T); StrLength(S);
StrCat(S,T); SubString(Sub,S,pos,len)。 
4.  叙述以下每对术语得区别:空串与空格串;串变量与串常量;主串与子串;串变量得名字与串变量得值。
5.    已知:S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串与置换等操作,将S转换为T、
6.  S与T就是用结点大小为1得单链表存储得两个串,设计一个算法将串S中首次与T匹配得子串逆置。
7.  S就是用结点大小为4得单链表存储得串,分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。
以下算法用定长顺序串:
8.    编写下列算法:
(1)将顺序串r中所有值为ch1得字符换成ch2得字符。
(2)将顺序串r中所有字符按照相反得次序仍存放在r中。
(3)从顺序串r中删除其值等于ch得所有字符。
(4)从顺序串r1中第index 个字符起求出首次与串r2相同得子串得起始位置。
(5)从顺序串r中删除所有与串r1相同得子串。
9.  写一个函数将顺序串s1中得第i个字符到第j个字符之间得字符用s2串替换。
10.              写算法,实现顺序串得基本操作Strpare(s,t)。
11.              写算法,实现顺序串得基本操作StrReplace(&s,t,v)。

实习题
1.    已知串S与T,试以以下两种方式编写算法,求得所有包含在S中而不包含在T中得字符构成得新串R,以及新串R中每个字符在串S中第一次出现得位置。
(1)       利用CONCAT、LEN、SUB与EQUAL四种基本运算来实现。
(2)       以顺序串作为存储结构来实现。
2.    编写一个行编辑程序EDLINE,完成以下功能:
(1)       显示若干行:list [[n1]-[n2]]:显示第n1行到第n2行,n1缺省时,从第一行开始,n2缺省时,到最后一行,
(2)       删除若干行。del [[n1]-[n2]]: n1、n2说明同(1)。
(3)       编辑第n行。edit n:显示第n行得内容,另输入一行替换该行。
(4)       插入一行。ins n:在第n行之前插入一行。
(5)       字符替换。replace str1,str2, [[n1]-[n2]]:在n1到n2行之间用str2替换str1。
3.设计一个文学研究辅助程序,统计小说中特定单词出现得频率与位置。

第四章答案

4、1 设s=’I AM A STUDENT’,t=’GOOD’, q=’WORKER’。给出下列操作得结果
【解答】StrLength(s)=14;
SubString(sub1,s,1,7)                  sub1=’I AM A ’;
SubString(sub2,s,7,1)                  sub2=’ ’;
StrIndex(s,4,’A’)=6;
StrReplace(s,’STUDENT’,q);            s=’I AM A WORKER’;
StrCat(StrCat(sub1,t),StrCat(sub2,q))      sub1=’I AM A GOOD WORKER’。

4、2编写算法,实现串得基本操作StrReplace(S,T,V)。
 【解答】算法如下:
int  strReplace(SString S,SString T, SString V)
{/*用串V替换S中得所有子串T */
  int  pos,i;               
  pos=strIndex(S,1,T);                /*求S中子串T第一次出现得位置*/
  if(pos = = 0)     return(0);
  while(pos!=0)                     /*用串V替换S中得所有子串T */
  {
    switch(T、len-V、len)
    {
      case  0:                                 /*串T得长度等于串V得长度*/
              for(i=0;i<=V、len;i++)                 /*用V替换T*/
                 S->ch[pos+i]=V、ch[i];
      case  >0:                                /*串T得长度大于串V得长度*/
             for(i=pos+t、ien;ilen;i--)           /*将S中子串T后得所有字符
                 S->ch[i-t、len+v、len]=S->ch[i];           前移T、len-V、len个位置*/
             for(i=0;i<=V、len;i++)                     /*用V替换T*/
                 S->ch[pos+i]=V、ch[i];
             S->len=S->len-T、len+V、len;
      case  <0:                                 /*串T得长度小于串V得长度*/
            if(S->len-T、len+V、len)<= MAXLEN       /*插入后串长小于MAXLEN*/
              { /*将S中子串T后得所有字符后移V、len-T、len个位置*/
                 for(i=S->len-T、len+V、len;i>=pos+T、len;i--)
                    S->ch[i]=S->ch[i-T、len+V、len];   
                 for(i=0;i<=V、len;i++)                   /*用V替换T*/
                    S->ch[pos+i]=V、ch[i];
                 S->len=S->len-T、len+V、len; }
           else
              {                  /*替换后串长>MAXLEN,但串V可以全部替换*/     
                if(pos+V、len<=MAXLEN)
                 {   for(i=MAXLEN-1;i>=pos+T、len; i--)
                        S->ch[i]=s->ch[i-T、len+V、len]
                     for(i=0;i<=V、len;i++)                 /*用V替换T*/
                       S->ch[pos+i]=V、ch[i];
                     S->len=MAXLEN;}
                else                             /*串V得部分字符要舍弃*/
                {  for(i=0;ii++)
                      S->ch[i+pos]=V、ch[i];
                  S->len=MAXLEN;}
   }/*switch()*/
pos=StrIndex(S,pos+V、len,T);                    /*求S中下一个子串T得位置*/
}/*while()*/        
return(1);
}/*StrReplace()*/

附加题:用链式结构实现定位函数。
【解答】
typedef  struct  Node
{  char  data;
   struct  Node  *next;
}Node,*Lstring;

int  strIndex(Lstring  S, int pos,  Lstring  T) 
/*从串S得pos序号起,串T第一次出现得位置 */
{
Node  *p, *q, *Ppos; 
int i=0,,j=0;
if(T->next= =NULL  ||  S->next = =NULL)   return(0); 
p=S->next;
q=T->next;
  while(p!=NULL  &&  j/
    {p=p->next;  j++;}
  if(j!=pos)     return(0);    
 while(p!=NULL  &&  q!=NULL)
  {
     Ppos=p;                   /*Ppos指向当前匹配得起始字符*/
     if(p->data = = q->data) 
{p=p->next; q=q->next;}
     else                       /*从Ppos指向字符得下一个字符起从新匹配*/
 {p=Ppos->next;
  q=T->head->next;
  i++;}
  }
if(q= =NULL)   return(pos+i);   /*匹配成功*/
else  return(0);                 /*失败*/
  }
第4章                     串
习题
1、 设s=’I AM A STUDENT’,  t=’GOOD’,  q=’WORKER’。给出下列操作得结果:
StrLength(s);  SubString(sub1,s,1,7);  SubString(sub2,s,7,1);
StrIndex(s,’A’,4);  StrReplace(s,’STUDENT’,q); 
StrCat(StrCat(sub1,t), StrCat(sub2,q));
[参考答案]
StrLength(s)=14;  sub1= ’I AM A_’;  sub2= ’_’;  StrIndex(s,’A’,4)=6; 
StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’; 
StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’;

2、 编写算法,实现串得基本操作StrReplace(S,T,V)。
3、 假设以块链结构表示串,块得大小为1,且附设头结点。
试编写算法,实现串得下列基本操作:
StrAsign(S,chars); StrCopy(S,T); Strpare(S,T); StrLength(S); StrCat(S,T); SubString(Sub,S,pos,len)。
[说明]:用单链表实现。
4.             叙述以下每对术语得区别:空串与空格串;串变量与串常量;主串与子串;串变量得名字与串变量得值。
5.             已知:S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串与置换等操作,将S转换为T、
6.             S与T就是用结点大小为1得单链表存储得两个串,设计一个算法将串S中首次与T匹配得子串逆置。
7.             S就是用结点大小为4得单链表存储得串,分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。
以下算法用定长顺序串:
8.             写下列算法:
(1)      将顺序串r中所有值为ch1得字符换成ch2得字符。
(2)      将顺序串r中所有字符按照相反得次序仍存放在r中。
(3)      从顺序串r中删除其值等于ch得所有字符。
(4)      从顺序串r1中第index 个字符起求出首次与串r2相同得子串得起始位置。
(5)      从顺序串r中删除所有与串r1相同得子串。
9.             写一个函数将顺序串s1中得第i个字符到第j个字符之间得字符用s2串替换。
[提示]:(1)用静态顺序串   (2)先移位,后复制
10.       写算法,实现顺序串得基本操作Strpare(s,t)。
11.       写算法,实现顺序串得基本操作StrReplace(&s,t,v)。
[提示]:
(1)           被替换子串定位(相当于第9题中i)
(2)           被替换子串后面得字符左移或右移(为替换子串准备房间)
(3)           替换子串入住(复制)

(4)           重复上述,直到……