c.txt

严蔚敏《数据结构》答案

{
  p=L.left;pre=NULL;
  while(p)
  {
    printf("%d",p->data);
    q=XorP(p->LRPtr,pre);
    pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针
  }
}//Print_XorLinkedList 
2.35 
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
{
  p=L.left;pre=NULL;
  r=(XorNode*)malloc(sizeof(XorNode));
  r->data=x;
  if(i==1) //当插入点在最左边的情况
  {
    p->LRPtr=XorP(p.LRPtr,r);
    r->LRPtr=p;
    L.left=r;
    return OK;
  }
  j=1;q=p->LRPtr; //当插入点在中间的情况
  while(++j<i&&q)
  {
    q=XorP(p->LRPtr,pre);
    pre=p;p=q;
  }//while //在p,q两结点之间插入
  if(!q) return INFEASIBLE; //i不可以超过表长
  p->LRPtr=XorP(XorP(p->LRPtr,q),r);
  q->LRPtr=XorP(XorP(q->LRPtr,p),r);
  r->LRPtr=XorP(p,q); //修改指针
  return OK;
}//Insert_XorLinkedList 
2.36 
Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素
{
  p=L.left;pre=NULL;
  if(i==1) //删除最左结点的情况
  {
    q=p->LRPtr;
    q->LRPtr=XorP(q->LRPtr,p);
    L.left=q;free(p);
    return OK;
  }
  j=1;q=p->LRPtr;
  while(++j<i&&q)
  {
    q=XorP(p->LRPtr,pre);
    pre=p;p=q;
  }//while //找到待删结点q
  if(!q) return INFEASIBLE; //i不可以超过表长
  if(L.right==q) //q为最右结点的情况
  {
    p->LRPtr=XorP(p->LRPtr,q);
    L.right=p;free(q);
    return OK;
  }
  r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点
  p->LRPtr=XorP(XorP(p->LRPtr,q),r);
  r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针
  free(q);
  return OK;
}//Delete_XorLinkedList 
2.37 
void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点
{
  p=L.next;
  while(p->next!=L&&p->next->next!=L)
  {
    p->next=p->next->next;
    p=p->next;
  } //此时p指向最后一个奇数结点
  if(p->next==L) p->next=L->pre->pre;
  else p->next=l->pre;
  p=p->next; //此时p指向最后一个偶数结点
  while(p->pre->pre!=L)
  {
    p->next=p->pre->pre;
    p=p->next;
  }
  p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状
  for(p=L;p->next!=L;p=p->next) p->next->pre=p;
  L->pre=p; //调整pre链的结构,同2.32方法
}//OEReform
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 
2.38 
DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找
{
  p=L.next;
  while(p.data!=x&&p!=L) p=p->next;
  if(p==L) return NULL; //没找到
  p->freq++;q=p->pre;
  while(q->freq<=p->freq&&p!=L) q=q->pre; //查找插入位置
  if(q!=p->pre)
  {
    p->pre->next=p->next;p->next->pre=p->pre;
    q->next->pre=p;p->next=q->next;
    q->next=p;p->pre=q; //调整位置
  }
  return p;
}//Locate_DuList 
2.39 
float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
{
  PolyTerm *q;
  xp=1;q=P.data;
  sum=0;ex=0;
  while(q->coef)
  {
    while(ex<q->exp) xp*=x0;
    sum+=q->coef*xp;
    q++;
  }
  return sum;
}//GetValue_SqPoly 
2.40 
void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3
{
  PolyTerm *p,*q,*r;
  Create_SqPoly(P3); //建立空多项式P3
  p=P1.data;q=P2.data;r=P3.data;
  while(p->coef&&q->coef)
  {
    if(p->exp<q->exp)
    {
      r->coef=p->coef;
      r->exp=p->exp;
      p++;r++;
    }
    else if(p->exp<q->exp)
    {
      r->coef=-q->coef;
      r->exp=q->exp;
      q++;r++;
    }
    else
    {
      if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中
      {
        r->coef=p->coef-q->coef;
        r->exp=p->exp;r++;
      }//if
      p++;q++;
    }//else
  }//while
  while(p->coef) //处理P1或P2的剩余项
  {
    r->coef=p->coef;
    r->exp=p->exp;
    p++;r++;
  }
  while(q->coef)
  {
    r->coef=-q->coef;
    r->exp=q->exp;
    q++;r++;
  }
}//Subtract_SqPoly 
2.41 
void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导
{
  p=L->next;
  if(!p->data.exp)
  {
    L->next=p->next;p=p->next; //跳过常数项
  }
  while(p!=L)
  {
    p->data.coef*=p->data.exp--;//对每一项求导
    p=p->next;
  }
}//QiuDao_LinkedPoly 
2.42 
void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
{
  p=L->next;
  A=(PolyNode*)malloc(sizeof(PolyNode));
  B=(PolyNode*)malloc(sizeof(PolyNode));
  pa=A;pb=B;
  while(p!=L)
  {
    if(p->data.exp!=2*(p->data.exp/2))
    {
      pa->next=p;pa=p;
    }
    else
    {
      pb->next=p;pb=p;
    }
    p=p->next;
  }//while
  pa->next=A;pb->next=B; 
}//Divide_LinkedPoly

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



 

积分 33804
发帖 2021
注册 2003-11-19
状态 离线  第 2 楼  第三章 栈与队列

3.15 
typedef struct{
                    Elemtype *base[2];
                    Elemtype *top[2];
                  }BDStacktype; //双向栈类型 
Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws
{
  tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));
  tws.base[1]=tws.base[0]+m;
  tws.top[0]=tws.base[0];
  tws.top[1]=tws.base[1];
  return OK;
}//Init_Stack 
Status push(BDStacktype &tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈
{
  if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件
  if(i==0) *tws.top[0]++=x;
  else if(i==1) *tws.top[1]--=x;
  else return ERROR;
  return OK;
}//push 
Status pop(BDStacktype &tws,int i,Elemtype &x)//x出栈,i=0表示低端栈,i=1表示高端栈
{
  if(i==0)
  {
    if(tws.top[0]==tws.base[0]) return OVERFLOW;
    x=*--tws.top[0];
  }
  else if(i==1)
  {
    if(tws.top[1]==tws.base[1]) return OVERFLOW;
    x=*++tws.top[1];
  }
  else return ERROR;
  return OK;
}//pop 
3.16 
void Train_arrange(char *train)//这里用字符串train表示火车,'H'表示硬席,'S'表示软席
{
  p=train;q=train;
  InitStack(s);
  while(*p)
  {
    if(*p=='H') push(s,*p); //把'H'存入栈中
    else *(q++)=*p; //把'S'调到前部
    p++;
  }
  while(!StackEmpty(s))
  {
    pop(s,c);
    *(q++)=c; //把'H'接在后部
  }
}//Train_arrange 
3.17 
int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
  InitStack(s);
  while((e=getchar())!='&')
  {
    if(e==’@’) return 0;//不允许在’&’之前出现’@’
    push(s,e); 
  }
  while( (e=getchar())!='@')
  {
    if(StackEmpty(s)) return 0;
    pop(s,c);
    if(e!=c) return 0;
  }
  if(!StackEmpty(s)) return 0;
  return 1;
}//IsReverse 
3.18 
Status Bracket_Test(char *str)//判别表达式中小括号是否匹配
{
  count=0;
  for(p=str;*p;p++)
  {
    if(*p=='(') count++;
    else if(*p==')') count--;
    if (count<0) return ERROR;
  }
  if(count) return ERROR; //注意括号不匹配的两种情况
  return OK;
}//Bracket_Test 
3.19 
Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配
{
  InitStack(s);
  for(p=str;*p;p++)
  {
    if(*p=='('||*p=='['||*p=='{') push(s,*p);
    else if(*p==')'||*p==']'||*p=='}')
    {
      if(StackEmpty(s)) return ERROR;
      pop(s,c);
      if(*p==')'&&c!='(') return ERROR;
      if(*p==']'&&c!='[') return ERROR;
      if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配
    }
  }//for
  if(!StackEmpty(s)) return ERROR;
  return OK;
}//AllBrackets_Test 
3.20 
typedef struct {
.             int x; 
              int y; 
            } coordinate;


void Repaint_Color(int g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为color
{
  old=g[i][j];
  InitQueue(Q);
  EnQueue(Q,{I,j});
  while(!QueueEmpty(Q))
  {
    DeQueue(Q,a);
  x=a.x;y=a.y;
    if(x>1)
      if(g[x-1][y]==old)
      {
        g[x-1][y]=color;
        EnQueue(Q,{x-1,y}); //修改左邻点的颜色
      }
    if(y>1)
      if(g[x][y-1]==old)
      {
        g[x][y-1]=color;
        EnQueue(Q,{x,y-1}); //修改上邻点的颜色
      }
    if(x<m)
      if(g[x+1][y]==old)
      {
        g[x+1][y]=color;
        EnQueue(Q,{x+1,y}); //修改右邻点的颜色
      }
    if(y<n)
      if(g[x][y+1]==old)
      {
        g[x][y+1]=color;
        EnQueue(Q,{x,y+1}); //修改下邻点的颜色
      }
  }//while
}//Repaint_Color
分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢? 
3.21 
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
  p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号
  InitStack(s); //s为运算符栈
  while(*p)
  {
    if(*p是字母)) *q++=*p; //直接输出
    else
    {
      c=gettop(s);
      if(*p优先级比c高) push(s,*p);
      else
      {
        while(gettop(s)优先级不比*p低)
        {
          pop(s,c);*(q++)=c;
        }//while
        push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
      }//else
    }//else
    p++;
  }//while
}//NiBoLan //参见编译原理教材 
3.22 
int GetValue_NiBoLan(char *str)//对逆波兰式求值
{
  p=str;InitStack(s); //s为操作数栈
  while(*p)
  {
    if(*p是数) push(s,*p);
    else
    {
      pop(s,a);pop(s,b);
      r=compute(b,*p,a); //假设compute为执行双目运算的过程
      push(s,r);
    }//else
    p++;
  }//while
  pop(s,r);return r;
}//GetValue_NiBoLan 
3.23 
Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new
{
  p=str;Initstack(s); //s的元素为stringtype类型
  while(*p)
  {
    if(*p为字母) push(s,*p);
    else
    {
      if(StackEmpty(s)) return ERROR;
      pop(s,a);
      if(StackEmpty(s)) return ERROR;
      pop(s,b);
      c=link(link(*p,b),a);
      push(s,c);
    }//else
    p++;
  }//while
  pop(s,new);
  if(!StackEmpty(s)) return ERROR;
  return OK;
}//NiBoLan_to_BoLan
分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b). 
3.24 
Status g(int m,int n,int &s)//求递归函数g的值s
{
  if(m==0&&n>=0) s=0;
  else if(m>0&&n>=0) s=n+g(m-1,2*n);
  else return ERROR;
  return OK;
}//g 
3.25 
Status F_recursive(int n,int &s)//递归算法
{
  if(n<0) return ERROR;
  if(n==0) s=n+1;
  else
  {
    F_recurve(n/2,r);
    s=n*r;
  }
  return OK;
}//F_recursive 
Status F_nonrecursive(int n,int s)//非递归算法
{
  if(n<0) return ERROR;
  if(n==0) s=n+1;
  else
  {
    InitStack(s); //s的元素类型为struct {int a;int b;}
    while(n!=0)
    {
      a=n;b=n/2;
      push(s,{a,b});