c.txt

严蔚敏《数据结构》答案

                    SElem data[MAXSIZE];
                    int mu,nu,tu;
                  } SMatrix; //单下标二元组矩阵类型 
Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e
{
  s=i*A.nu+j+1;p=1;
  while(A.data[p].seq<s) p++; //利用各元素seq值逐渐递增的特点
  if(A.data[p].seq==s) //找到了元素A[i][j]
  {
    e=A.data[p].e;
    return OK;
  }
  return ERROR;
}//SMatrix_Locate 
5.25 
typedef enum{0,1} bool; 
typedef struct{
                    int mu,nu;
                    int elem[MAXSIZE];
                    bool map[mu][nu];
                  } BMMatrix; //用位图表示的矩阵类型 
void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法
{
  C.mu=A.mu;C.nu=A.nu;
  pa=1;pb=1;pc=1;
  for(i=0;i<A.mu;i++) //每一行的相加
    for(j=0;j<A.nu;j++) //每一个元素的相加
    {
      if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0
      {
        C.elem[pc]=A.elem[pa]+B.elem[pb];
        C.map[i][j]=1;
        pa++;pb++;pc++;
      }
      else if(A.map[i][j]&&!B.map[i][j])
      {
        C.elem[pc]=A.elem[pa];
        C.map[i][j]=1;
        pa++;pc++;
      }
      else if(!A.map[i][j]&&B.map[i][j])
      {
        C.elem[pc]=B.elem[pb];
        C.map[i][j]=1;
        pb++;pc++;
      }
    }
}//BMMatrix_Add 
5.26 
void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵
{
  for(i=0;i<A.mu;i++)
  {
    if(A.rhead[i])
      for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表
        printf("%d %d %d\n",i,p->j,p->e;
  }
}//Print_OLMatrix 
5.27 
void OLMatrix_Add(OLMatrix &A,OLMatrix B)//把十字链表表示的矩阵B加到A上
{
  for(j=1;j<=A.nu;j++) cp[j]=A.chead[j]; //向量cp存储每一列当前最后一个元素的指针
  for(i=1;i<=A.mu;i++)
  {
    pa=A.rhead[i];pb=B.rhead[i];pre=NULL;
    while(pb)
    {
      if(pa==NULL||pa->j>pb->j) //新插入一个结点
      {
        p=(OLNode*)malloc(sizeof(OLNode));
        if(!pre) A.rhead[i]=p;
        else pre->right=p;
        p->right=pa;pre=p;
        p->i=i;p->j=pb->j;p->e=pb->e; //插入行链表中
        if(!A.chead[p->j])
        {
          A.chead[p->j]=p;
          p->down=NULL;
        }
        else
        {
          while(cp[p->j]->down) cp[p->j]=cp[p->j]->down;
          p->down=cp[p->j]->down;
          cp[p->j]->down=p;
        }
        cp[p->j]=p; //插入列链表中
      }//if
      else if(pa->j<pb->j)
      {
        pre=pa;
        pa=pa->right;
      } //pa右移一步
      else if(pa->e+pb->e)
      {
        pa->e+=pb->e;
        pre=pa;pa=pa->right;
        pb=pb->right;
      } //直接相加
      else
      {
        if(!pre) A.rhead[i]=pa->right;
        else pre->right=pa->right;
        p=pa;pa=pa->right; //从行链表中删除
        if(A.chead[p->j]==p)
          A.chead[p->j]=cp[p->j]=p->down;
        else cp[p->j]->down=p->down; //从列链表中删除
        free (p);
      }//else
    }//while
  }//for
}//OLMatrix_Add
分析:本题的具体思想在课本中有详细的解释说明. 
5.28 
void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导
{
  for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp)
  {
    if(p->tag) Mul(p->hp,p->exp);
    else p->coef*=p->exp; //把指数乘在本结点或其下属结点上
    p->exp--;
  }
  pre->tp=NULL;
  if(p) free (p); //删除可能存在的常数项
}//MPList_PianDao 
void Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x
{
  for(p=L;p;p=p->tp)
  {
    if(!p->tag) p->coef*=x;
    else Mul(p->hp,x);
  }
}//Mul
    
5.29 
void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法
{
  C=(MPLNode*)malloc(sizeof(MPLNode));
  if(!A->tag&&!B->tag) //原子项,可直接相加
  {
    C->coef=A->coef+B->coef;
    if(!C->coef)
    {
      free(C);
      C=NULL;
    }
  }//if
  else if(A->tag&&B->tag) //两个多项式相加
  {
    p=A;q=B;pre=NULL;
    while(p&&q)
    {
      if(p->exp==q->exp)
      {
        C=(MPLNode*)malloc(sizeof(MPLNode));
        C->exp=p->exp;
        MPList_Add(A->hp,B->hp,C->hp);
        pre->tp=C;pre=C;
        p=p->tp;q=q->tp;
      }
      else if(p->exp>q->exp)
      {
        C=(MPLNode*)malloc(sizeof(MPLNode));
        C->exp=p->exp;
        C->hp=A->hp;
        pre->tp=C;pre=C;
        p=p->tp;
      }
      else
      {
        C=(MPLNode*)malloc(sizeof(MPLNode));
        C->exp=q->exp;
        C->hp=B->hp;
        pre->tp=C;pre=C;
        q=q->tp;
      }
    }//while
    while(p)
    {
      C=(MPLNode*)malloc(sizeof(MPLNode));
      C->exp=p->exp;
      C->hp=p->hp;
      pre->tp=C;pre=C;
      p=p->tp;
    }
    while(q)
    {
      C=(MPLNode*)malloc(sizeof(MPLNode));
      C->exp=q->exp;
      C->hp=q->hp;
      pre->tp=C;pre=C;
      q=q->tp;
    } //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题
  }//else if
  else if(A->tag&&!B->tag) //多项式和常数项相加
  {
    x=B->coef;
    for(p=A;p->tp->tp;p=p->tp);
    if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项
    if(!p->tp->coef)
    {
      free(p->tp);
      p->tp=NULL;
    }
    else
    {
      q=(MPLNode*)malloc(sizeof(MPLNode));
      q->coef=x;q->exp=0;
      q->tag=0;q->tp=NULL;
      p->tp=q;
    } //否则新建常数项,下同
  }//else if
  else
  {
    x=A->coef;
    for(p=B;p->tp->tp;p=p->tp);
    if(p->tp->exp==0) p->tp->coef+=x;
    if(!p->tp->coef)
    {
      free(p->tp);
      p->tp=NULL;
    }
    else
    {
      q=(MPLNode*)malloc(sizeof(MPLNode));
      q->coef=x;q->exp=0;
      q->tag=0;q->tp=NULL;
      p->tp=q;
    }
  }//else
}//MPList_Add 
5.30 
int GList_Getdeph(GList L)//求广义表深度的递归算法
{
  if(!L->tag) return 0; //原子深度为0
  else if(!L) return 1; //空表深度为1
  m=GList_Getdeph(L->ptr.hp)+1;
  n=GList_Getdeph(L->ptr.tp);
  return m>n?m:n;
}//GList_Getdeph 
5.31 
void GList_Copy(GList A,GList &B)//复制广义表的递归算法
{
  if(!A->tag) //当结点为原子时,直接复制
  {
    B->tag=0;
    B->atom=A->atom;
  }
  else //当结点为子表时
  {
    B->tag=1;
    if(A->ptr.hp)
    {
      B->ptr.hp=malloc(sizeof(GLNode));
      GList_Copy(A->ptr.hp,B->ptr.hp);
    } //复制表头
    if(A->ptr.tp)
    {
      B->ptr.tp=malloc(sizeof(GLNode));
      GList_Copy(A->ptr.tp,B->ptr.tp);
    } //复制表尾
  }//else
}//GList_Copy 
5.32 
int GList_Equal(GList A,GList B)//判断广义表A和B是否相等,是则返回1,否则返回0
{ //广义表相等可分三种情况:
  if(!A&&!B) return 1; //空表是相等的
  if(!A->tag&&!B->tag&&A->atom==B->atom) return 1;//原子的值相等
  if(A->tag&&B->tag)
    if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp))
      return 1; //表头表尾都相等
  return 0;
}//GList_Equal 
5.33 
void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次
{
  if(!A) return;
  if(!A->tag) printf("%d %d\n",A->atom,layer);
  else
  {
    GList_PrintElem(A->ptr.hp,layer+1);
    GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次
  }
}//GList_PrintElem 
5.34 
void GList_Reverse(GList A)//递归逆转广义表A
{
  GLNode *ptr[MAX_SIZE];
  if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转
  {
    for(i=0,p=A;p;p=p->ptr.tp,i++)
    {
      if(p->ptr.hp) GList_Reverse(p->ptr.hp);        //逆转各子表
      ptr[i]=p->ptr.hp; 
    }
    for(p=A;p;p=p->ptr.tp)        //重新按逆序排列各子表的顺序
      p->ptr.hp=ptr[--i];
  }
}//GList_Reverse 
5.35 
Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针
{
  scanf("%c",&ch);
  if(ch==' ')
  {
    L=NULL;
    scanf("%c",&ch);
    if(ch!=')') return ERROR;
    return OK;
  }
  L=(GList)malloc(sizeof(GLNode));
  L->tag=1;
  if(isalphabet(ch)) //输入是字母
  {
    p=(GList)malloc(sizeof(GLNode)); //建原子型表头
    p->tag=0;p->atom=ch;
    L->ptr.hp=p;
  }
  else if(ch=='(') Create_GList(L->ptr.hp); //建子表型表头
  else return ERROR;
  scanf ("%c",&ch);
  if(ch==')') L->ptr.tp=NULL;
  else if(ch==',') Create_GList(L->ptr.tp); //建表尾 
  else return ERROR;
  return OK;
}//Create_GList
分析:本题思路见书后解答. 
5.36 
void GList_PrintList(GList A)//按标准形式输出广义表
{
  if(!A) printf("()"); //空表
  else if(!A->tag) printf("%d",A->atom);//原子
  else
  {
    printf("(");
    for(p=A;p;p=p->ptr.tp) 
    {
      GList_PrintList(p->ptr.hp);
       if(p->ptr.tp) printf(",");        //只有当表尾非空时才需要打印逗号
    } 
    printf(")");
  }//else
}//GList_PrintList 
5.37 
void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子
{
  if(A&&A->ptr.hp) 
  {
    if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x);
    else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x)
    {
      q=A;
      A=A->ptr.tp;    //删去元素值为x的表头
      free(q);
      GList_DelElem(A,x);
    }
  }
  if(A&&A->ptr.tp) GList_DelElem(A->ptr.tp,x);
}//GList_DelElem 
5.39 
void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素
{
  InitQueue(Q);
  for(p=L;p;p=p->ptr.tp) EnQueue(Q,p);
  while(!QueueEmpty(Q))
  {
    DeQueue(Q,r);
    if(!r->tag) printf("%d",r->atom);
    else
      for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); 
  }//while
}//GList_PrintElem_LOrder 
分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.

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



 

积分 33804
发帖 2021
注册 2003-11-19
状态 离线  第 5 楼  第六章 树和二叉树

6.33 
int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  if(u==v) return 1;
  else
  {
    if(L[v])
      if (Is_Descendant(u,L[v])) return 1;
    if(R[v])
      if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
  }
  return 0;
}//Is_Descendant_C 
6.34 
int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  for(p=u;p!=v&&p;p=T[p]);
  if(p==v) return 1;
  else return 0;
}//Is_Descendant_P 
6.35 
这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 
6.36 
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
  if(!B1&&!B2) return 1;
  else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
    return 1;
  else return 0;
}//Bitree_Sim 
6.37 
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } //向左走到尽头
    pop(S,p);
    if(!StackEmpty(S))
    {
     pop(S,p);
     push(S,p->rchild); //向右一步
    }
  }//while
}//PreOrder_Nonrecursive 
6.38 
typedef struct {
                     BTNode* ptr;
                     enum {0,1,2} mark;
                   } PMType; //有mark域的结点指针类型 
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
  PMType a;
  InitStack(S); //S的元素为PMType类型
  Push (S,{T,0}); //根结点