论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

03)第3章 栈与队列题解

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:47:09

                   第三章 栈与队列
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())!='&')
    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});
file://修改上邻点的颜色
      }
    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);
file://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});
      n=b;
    }//while
    s=1;
    while(!StackEmpty(s))
    {
      pop(s,t);
      s*=t.a;
    }//while
  }
  return OK;
}//F_nonrecursive
3.26
float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法
{
  if(abs(p^2-A)<=e) return p;
  else return sqrt_recurve(A,(p+A/p)/2,e);
}//Sqrt_recurve
float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非递归算法
{
  while(abs(p^2-A)>=e)
    p=(p+A/p)/2;
  return p;
}//Sqrt_nonrecursive
3.27
这一题的所有算法以及栈 的变化过程请参见《数据结构(pascal版)》,作者不再具体写出.
3.28
void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q
{
  Q=(CiLNode*)malloc(sizeof(CiLNode));
  Q->next=Q;
}//InitCiQueue
void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素
{
  p=(CiLNode*)malloc(sizeof(CiLNode));
  p->data=x;
  p->next=Q->next;
//直接把p加在Q的后面
  Q->next=p;
  Q=p; 
//修改尾指针
}
Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x
{
  if(Q==Q->next) return INFEASIBLE;
file://队列已空
  p=Q->next->next;
  x=p->data;
  Q->next->next=p->next;
  free(p);
  return OK;
}//DeCiQueue
3.29
Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法
{
  if(Q.front==Q.rear&&Q.tag==1)
//tag域的值为0表示"空",1表示"满"
    return OVERFLOW;
  Q.base[Q.rear]=x;
  Q.rear=(Q.rear+1)%MAXSIZE;
  if(Q.front==Q.rear) Q.tag=1;
//队列满
}//EnCyQueue
Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法
{
  if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;
  Q.front=(Q.front+1)%MAXSIZE;
  x=Q.base[Q.front];
  if(Q.front==Q.rear) Q.tag=1;
//队列空
  return OK;
}//DeCyQueue
分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.
3.30
Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法
{
  if(Q.length==MAXSIZE) return OVERFLOW;
  Q.rear=(Q.rear+1)%MAXSIZE;
  Q.base[Q.rear]=x;
  Q.length++;
  return OK;
}//EnCyQueue
Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法
{
  if(Q.length==0) return INFEASIBLE;
  head=(Q.rear-Q.length+1)%MAXSIZE;
//详见书后注释
  x=Q.base[head];
  Q.length--;
}//DeCyQueue
3.31
int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0
{
  InitStack(S);InitQueue(Q);
  while((c=getchar()!='@')
  {
    Push(S,c);EnQueue(Q,c);
//同时使用栈和队列两种结构
  }
  while(!StackEmpty(S))
  {
    Pop(S,a);DeQueue(Q,b));
    if(a!=b) return ERROR;
  }
  return OK;
}//Palindrome_Test
3.32
void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项
{
  InitCyQueue(Q);
//其MAXSIZE设置为k
  for(i=0;i<k-1;i++) Q.base[i]=0;
  Q.base[k-1]=1;
//给前k项赋初值
  for(i=0;i<k;i++) printf("%d",Q.base[i]);
  for(i=k;i<=n;i++)
  {
    m=i%k;sum=0;
    for(j=0;j<k;j++) sum+=Q.base[(m+j)%k];
    Q.base[m]=sum;
//求第i项的值存入队列中并取代已无用的第一项
    printf("%d",sum);
  }
}//GetFib_CyQueue
3.33
Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作
{
  if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW;
//队列满
  avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2;
  if(x>=avr)
//根据x的值决定插入在队头还是队尾
  {
    Q.base[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXSIZE;
  }
//插入在队尾
  else
  {
    Q.front=(Q.front-1)%MAXSIZE;
    Q.base[Q.front]=x;
  }
//插入在队头
  return OK;
}//EnDQueue
Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作
{
  if(Q.front==Q.rear) return INFEASIBLE;
//队列空
  x=Q.base[Q.front];
  Q.front=(Q.front+1)%MAXSIZE;
  return OK;
}//DeDQueue
3.34
void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列
{
  r=train;
  InitDQueue(Q);
  while(*r)
  {
    if(*r=='P')
    {
      printf("E");
      printf("D");
//实际上等于不入队列,直接输出P车厢
    }
    else if(*r=='S')
    {
      printf("E");
      EnDQueue(Q,*r,0);
//0表示把S车厢从头端入队列
    }
    else
    {
      printf("A");
      EnDQueue(Q,*r,1);
//1表示把H车厢从尾端入队列
    }
  }//while
  while(!DQueueEmpty(Q))
  {
    printf("D");
    DeDQueue(Q);
  }//while
//从头端出队列的车厢必然是先S后H的顺序
}//Train_Rearrange

视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058