北邮算法与数据结构习题参考答案

作业参考答案
一、（带头结点）多项式乘法 C = A×B：
void  PolyAdd ( list  &C,  list  R)    // R 为单个结点
{
  p=C;
  while  ((！p->next) && (p->next->exp>R->exp))  p=p->next;
  if  ((p->next) || (p->next->exp<R->exp))
{  R->next=p->next;  p->next=R;  }  else
{  p->next->inf += R->inf;  delete  R;
  if  ( !  p->next->inf )
    {  R=p->next;  p->next=R->next;  delete  R; }
}
}
void  PolyMul ( list  A,  list  B,  list  &C )
{
  C=new  struct  node;  C->next=NULL;  q=B->next;
  While  ( q )
  {
p=A->next;
while  ( p )
{
  r = new  struct  node;  r->exp = p->exp + q->exp;
  r->inf = p-> inf * q->inf;  PolyAdd(C, r);
  p=p->next;
}
q=q->next;
  }
}
二、梵塔的移动次数：
已知移动次数迭代公式为： M ( n ) = 2M ( n-1 ) + 1
初值为：                M ( 0 ) = 0
则：                    M ( n ) = 2 ( 2M ( n-2 ) + 1 ) + 1
                              = 4M ( n-2 ) + 3
                              = 8M ( n-3 ) + 7
                              = 2iM ( n-i ) + 2i – 1
若n=i , 则M ( n-n ) = 0, 故：M ( n ) = 2nM ( n-n ) + 2n – 1
                              = 2n – 1
所以，梵塔的移动次数为2n – 1次。
三、简化的背包问题：
void  Pack ( int  m,  int  i,  int  t )  // 初始值为: 1 1 t
{
  for  ( k=i;  k<=n;  k++ )
  {
solution[m] = weight[k];
if  ( t == weight[k] )
{
  for  ( j=1;  j<=m;  j++ )  cout<<solution[j];  cout<<endl;
}  else  if  ( t > weight[k] )  Pack ( m+1, k+1, t - weight[k] );
  }
}
四、判断括号是否配对：
int  Correct ( string  s )
数据结构与算法第二版课后题答案
{
  Inistack(Q);
  for  ( i=0;  s[i] == ‘=’;  i++ )  // 表达式以‘=’结束
  {
switch  ( s[i] )
{
case  ‘(’:
case  ‘[’:
case  ‘{’:
  Push ( Q, s[ i ] );  break;
case  ‘)’:
case  ‘]’:
case  ‘}’:
        if  ( Empty(Q))  return  0;  t=Pop(Q);
        if  ( !  Matching( t, s[i] ))  return  0;
}
  }
  if  ( !  Empty(Q) )  return  0;
return  1;
}
五、堆栈可能的输出：
12341243  1324  1342  1423  1432
21342143  2314  2341  2413  2431
3124  3142  3214  3241  3412 3421
41234132  4213  4231  4312  4321
六、用两个堆栈实现一个队列：
int  FullQ ( )
{
  if  (Full (S1) && ! Empty (S2))  return  1;  return  0;
}
int  EmptyQ ( )
{
  if  ( Empty (S1) && Empty (S2))  return  1;  return  0;
}
void  Enqueue ( elemtype  x)
{
  if (Full(S1)) if (Empty(S2)) while (! Empty (S1)) Push(S2, Pop(S1));
  if  (! Full(S1))  Push(S1, x);
}
elemtype  Dequeue ( )
{
  if (Empty(S2)) while (! Empty(S1)) Push(S2, Pop(S1));
  if  (! Empty(S2))  return  Pop(S2);
}
七、生成新串及字符第一次出现位置：
int  Index ( string  S,  string  T )
{
  for  ( i=1;  i + Len(T)-1<=Len(S);  i++ )
    if  Equal ( Sub ( S, I, Len (T)), T )  return  i;
  return  0;
}
void  CreatNewStr ( string  S,  string  T,  string  R,  arrant  P)
{
  R=“”;  j=0;
  for  ( i=1;  i<=Len(S);  i++ )

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。