c.txt

严蔚敏《数据结构》答案

}//LString_Concat 
int Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0
{
  for(i=0;i<CHUNKSIZE&&p->ch[i]!=c;i++);
  if(i==CHUNKSIZE) return 0;
  else return i+1;
}//Find_Char

4.23 
int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0
{
  InitStack(S);
  p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)
  for(k=1;k<=S.curlen;k++)
  {
    if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串
    else if(k>(S.curlen+1)/2)
    {
      Pop(S,c); //将后半段的字符与栈中的元素相匹配
      if(p->ch[i]!=c) return 0; //失配
    }
    if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块
    {
      p=p->next;
      i=0;
    }
  }//for
  return 1; //成功匹配
}//LString_Palindrome
4.24 
void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t
{
  if(t.ch) free(t.ch);
  t.ch=malloc((s1.length+s2.length)*sizeof(char));
  for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];
  for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];
  t.length=s1.length+s2.length;
}//HString_Concat 
4.25 
int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数
{
  for(n=0,i=0;i<=S.length-T.length;i++)
  {
    for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);
    if(k==T.length) //找到了与T匹配的子串:分三种情况处理
    {
      if(T.length==V.length)
        for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换
          S.ch[i+l-1]=V.ch[l-1];
      else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移
      {
        for(l=S.length-1;l>=i+T.length;l--)
          S.ch[l+V.length-T.length]=S.ch[l];
        for(l=0;l<V.length;l++)
          S[i+l]=V[l];
      }
      else //新子串长度小于原子串时:先将后部左移
      {
        for(l=i+V.length;l<S.length+V.length-T.length;l++)
          S.ch[l]=S.ch[l-V.length+T.length];
        for(l=0;l<V.length;l++)
          S[i+l]=V[l];
      }
      S.length+=V.length-T.length;
      i+=V.length;n++;
    }//if
  }//for
  return n;
}//HString_Replace 
4.26 
Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前
{
  if(pos<1) return ERROR;
  if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾
  S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));
  for(i=S.length-1;i>=pos-1;i--)
    S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置
  for(i=0;i<T.length;i++)
    S.ch[pos+i-1]=T.ch[pos]; //插入串T
  S.length+=T.length;
  return OK;
}//HString_Insert 
4.27 
int Index_New(Stringtype s,Stringtype t)//改进的定位算法
{
  i=1;j=1;
  while(i<=s[0]&&j<=t[0])
  {
    if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]]))
    { //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个
      i=i+j-2;
      j=1;
    }
    else
    {
      i++;j++;
    }
  }//while
  if(j>t[0]) return i-t[0];
}//Index_New 
4.28 
void LGet_next(LString &T)//链串上的get_next算法
{
  p=T->succ;p->next=T;q=T;
  while(p->succ)
  {
    if(q==T||p->data==q->data)
    {
      p=p->succ;q=q->succ;
      p->next=q;
    }
    else q=q->next;
  }//while
}//LGet_next 
4.29 
LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针
{
  p=pos;q=T->succ;
  while(p&&q)
  {
    if(q==T||p->chdata==q->chdata)
    {
      p=p->succ;
      q=q->succ;
    }
    else q=q->next;
  }//while
  if(!q)
  {
    for(i=1;i<=Strlen(T);i++)
      p=p->next;
    return p;
  } //发现匹配后,要往回找子串的头
  return NULL;
}//LIndex_KMP 
4.30 
void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度
{
  for(maxlen=0,i=1;i<S[0];i++)//串S2向右移i格
  {
    for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动
    {
      if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数
      else k=0; //失配时k归零
      if(k>maxlen) //发现了比以前发现的更长的重复子串
      {
        lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录
      }
    }//for
  }//for
  if(maxlen)
  {
    printf("Longest Repeating Substring length:%d\n",maxlen);
    printf("Position1:%d  Position 2:%d\n",lrs1,lrs2);
  }
  else printf("No Repeating Substring found!\n");
}//Get_LRepSub
分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2). 
4.31 
void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度
{
  if(S[0]>=T[0])
  {
    StrAssign(A,S);StrAssign(B,T);
  }
  else
  {
    StrAssign(A,T);StrAssign(B,S);
  } //为简化设计,令S和T中较长的那个为A,较短的那个为B
  for(maxlen=0,i=1-B[0];i<A[0];i++)
  {
    if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正
    {
      jmin=1;jmax=i+B[0];
    }//B有一部分在A左端的左边
    else if(i>A[0]-B[0])
    {
      jmin=i;jmax=A[0];
    }//B有一部分在A右端的右边
    else
    {
      jmin=i;jmax=i+B[0];
    }//B在A左右两端之间.
     //以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.
    for(k=0,j=jmin;j<=jmax;j++)
    {
      if(A[j]==B[j-i]) k++;
      else k=0;
      if(k>maxlen)
      {
        lps1=j-k+1;lps2=j-i-k+1;maxlen=k;
      }
    }//for
  }//for
  if(maxlen)
  {
    if(S[0]>=T[0])
    {
      lpsS=lps1;lpsT=lps2;
    }
    else
    {
      lpsS=lps2;lpsT=lps1;
    } //将A,B上的位置映射回S,T上的位置
    printf("Longest Public Substring length:%d\n",maxlen);
    printf("Position in S:%d  Position in T:%d\n",lpsS,lpsT);
  }//if
  else printf("No Repeating Substring found!\n");
}//Get_LPubSub
分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。

 
 
 2004-7-19 02:01 AM             
 
Bamboo
站长



 

积分 33804
发帖 2021
注册 2003-11-19
状态 离线  第 4 楼  第五章 数组和广义表

5.18 
void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间
{
  for(i=1;i<=k;i++)
    if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p
  for(i=0;i<p;i++) 
  {
    j=i;l=(i+n-k)%n;temp=A[i];
    while(l!=i)
    {
      A[j]=A[l];
      j=l;l=(j+n-k)%n;
    }// 循环右移一步
    A[j]=temp;
  }//for
}//RSh
分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].
第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
恰好使所有元素都右移一次.
虽然未经数学证明,但作者相信上述规律应该是正确的. 
5.19 
void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点
{
  for(i=0;i<m;i++)
  {
    for(min=A[i][0],j=0;j<n;j++)
      if(A[i][j]<min) min=A[i][j]; //求一行中的最小值
    for(j=0;j<n;j++)
      if(A[i][j]==min) //判断这个(些)最小值是否鞍点
      {
        for(flag=1,k=0;k<m;k++)
          if(min<A[k][j]) flag=0;
        if(flag)
          printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);
      }
  }//for
}//Get_Saddle 
5.20 
int exps[MAXSIZE]; //exps数组用于存储某一项的各变元的指数
int maxm,n; //maxm指示变元总数,n指示一个变元的最高指数 
void Print_Poly_Descend(int *a,int m)//按降幂顺序输出m元多项式的项，各项的系数已经按照题目要求存储于m维数组中，数组的头指针为a
{
  maxm=m;
  for(i=m*n;i>=0;i--) //按降幂次序,可能出现的最高项次数为mn
    Get_All(a,m,i,0); //确定并输出所有次数为i的项
}//Print_Poly_Descend 
void Get_All(int *a,int m,int i,int seq)//递归求出所有和为i的m个自然数
{
  if(seq==maxm) Print_Nomial(a,exps); //已经求完时,输出该项
  else
  {
    min=i-(m-1)*n; //当前数不能小于min
    if(min<0) min=0;
    max=n<i?n:i; //当前数不能大于max
    for(j=min;j<=max;j++)
    {
      exps[seq]=j; //依次取符合条件的数
      Get_All(a,m-1,i-j,seq+1); //取下一个数
    }
  }//else
  exps[seq]=0; //返回
}//Get_All 
void Print_Nomial(int *a,int exps[ ])//输出一个项,项的各变元的指数已经存储在数组exps中
{
  pos=0;
  for(i=0;i<maxm;i++) //求出该项的系数在m维数组a中低下标优先的存储位置pos
  {
    pos*=n;
    pos+=exps[i];
  }
  coef=*(a+pos); //取得该系数coef
  if(!coef) return; //该项为0时无需输出
  else if(coef>0) printf("+"); //系数为正时打印加号
  else if(coef<0) printf("-"); //系数为负时打印减号
  if(abs(coef)!=1) printf("%d",abs(coef)); //当系数的绝对值不为1时打印系数
  for(i=0;i<maxm;i++)
    if(exps[i]) //打印各变元及其系数
    {
      printf("x");
      printf("%d",i);
      printf("E");
      if(exps[i]>1) printf("%d",exp[i]); //系数为1时无需打印
    }
}//Print_Nomial
分析:本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.

5.21 
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法
{
  C.mu=A.mu;C.nu=A.nu;C.tu=0;
  pa=1;pb=1;pc=1;
  for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
  {
    while(A.data[pa].i<x) pa++;
    while(B.data[pb].i<x) pb++;
    while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
    {
      if(A.data[pa].j==B.data[pb].j)
      {
        ce=A.data[pa].e+B.data[pb].e;
        if(ce) //和不为0
        {
          C.data[pc].i=x;
          C.data[pc].j=A.data[pa].j;
          C.data[pc].e=ce;
          pa++;pb++;pc++;
        }
      }//if
      else if(A.data[pa].j>B.data[pb].j) 
      {
        C.data[pc].i=x;
        C.data[pc].j=B.data[pb].j;
        C.data[pc].e=B.data[pb].e;
        pb++;pc++;
      }
      else
      {
        C.data[pc].i=x;
        C.data[pc].j=A.data[pa].j;
        C.data[pc].e=A.data[pa].e
        pa++;pc++;
      }
    }//while
    while(A.data[pa]==x) //插入A中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=A.data[pa].j;
      C.data[pc].e=A.data[pa].e
      pa++;pc++;
    }
    while(B.data[pb]==x) //插入B中剩余的元素(第x行)
    {
      C.data[pc].i=x;
      C.data[pc].j=B.data[pb].j;
      C.data[pc].e=B.data[pb].e;
      pb++;pc++;
    }
  }//for
  C.tu=pc;
}//TSMatrix_Add 
5.22 
void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上
{
  for(i=1;i<=A.tu;i++)
    A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置
  pa=MAXSIZE-A.tu+1;pb=1;pc=1;
  for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
  {
    while(A.data[pa].i<x) pa++;
    while(B.data[pb].i<x) pb++;
    while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
    {
      if(A.data[pa].j==B.data[pb].j)
      {
        ne=A.data[pa].e+B.data[pb].e;
        if(ne) //和不为0
        {
          A.data[pc].i=x;
          A.data[pc].j=A.data[pa].j;
          A.data[pc].e=ne;
          pa++;pb++;pc++;
        }
      }//if
      else if(A.data[pa].j>B.data[pb].j) 
      {
        A.data[pc].i=x;
        A.data[pc].j=B.data[pb].j;
        A.data[pc].e=B.data[pb].e;
        pb++;pc++;
      }
      else
      {
        A.data[pc].i=x;
        A.data[pc].j=A.data[pa].j;
        A.data[pc].e=A.data[pa].e
        pa++;pc++;
      }
    }//while
    while(A.data[pa]==x) //插入A中剩余的元素(第x行)
    {
      A.data[pc].i=x;
      A.data[pc].j=A.data[pa].j;
      A.data[pc].e=A.data[pa].e
      pa++;pc++;
    }
    while(B.data[pb]==x) //插入B中剩余的元素(第x行)
    {
      A.data[pc].i=x;
      A.data[pc].j=B.data[pb].j;
      A.data[pc].e=B.data[pb].e;
      pb++;pc++;
    }
  }//for
  A.tu=pc;
  for(i=A.tu;i<MAXSIZE;i++) A.data[i]={0,0,0}; //清除原来的A中记录
}//TSMatrix_Addto 
5.23 
typedef struct{
                    int j;
                    int e;
                  } DSElem; 
typedef struct{
                DSElem data[MAXSIZE];
                int cpot[MAXROW];//这个向量存储每一行在二元组中的起始位置
                int mu,nu,tu;
              } DSMatrix; //二元组矩阵类型 
Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元组矩阵的元素A[i][j]的值e
{
  for(s=A.cpot[i];s<A.cpot[i+1]&&A.data[s].j!=j;s++);//注意查找范围
  if(s<A.cpot[i+1]&&A.data[s].j==j) //找到了元素A[i][j]
  {
    e=A.data[s];
    return OK;
  }
  return ERROR;
}//DSMatrix_Locate 
5.24 
typedef struct{
                    int seq; //该元素在以行为主序排列时的序号
                    int e;
                  } SElem; 
typedef struct{