最新发表 推荐阅读 明星博主 原创博文 年度排行 博文排行 博文评论 FPGA/CPLD MCU/ 嵌入式 模拟 电源/新能源 测试测量 通信 智能手机 处理器与DSP PCB 汽车电子 消费电子 智能硬件 物联网 软件与OS 采购与分销 供应链管理 工程师职场 EDA/ IP/ 设计与制造 无人机 机器人/ AI 医疗电子 工业电子 管理
用户1361860
文章：289 阅读：1051882 评论：266 赞：2508
好友 私信 个人主页

原创 数据结构第三章习题参考答案(2)

2008-3-31 21:11 4440 9 9 分类: 软件与OS
这是后面几题,关于queue的,这章就这样了,我没有把每题都做,不过有意思的基本上都在这了

 

// chapt3part2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

//ex 3.28
typedef struct _ClQNode
{
 int data;
 struct _ClQNode *next;
}ClQNode;
typedef struct _ClQueue
{
 ClQNode *head;//指向头结点
 ClQNode *tail;//队尾
}ClQueue;


bool init_clqueue(ClQueue *q)
{
 ClQNode *p;
 if((p=(ClQNode *)malloc(sizeof(ClQNode)))==NULL)
  return false;
 p->next=p;
 q->head=p;
 q->tail=p;
 return true;
}


bool EnClQueue(ClQueue *q,int x)
{
 ClQNode *p=(ClQNode*)malloc(sizeof(ClQNode));
 if(p==NULL)
  return false;
 p->data=x;
 p->next=q->tail->next;
 q->tail->next=p;
 q->tail=p;
 return true;
}

bool DeClQueue(ClQueue *q, int *x)
{
 ClQNode *p;
 if(q->head==q->tail)
  return false;
 *x=q->head->next->data;
 p=q->head->next;
 q->head->next=p->next;
 free(p);
 return true;
}

//ex 3.29
typedef struct _CircleQueue
{
 int data[512];
 int head;
 int tail;
 bool tag;
}CircleQueue;

void init_circlequeue(CircleQueue *q)
{
 q->head=q->tail=0;
 q->tag=false;
}

bool EnCircleQueue(CircleQueue *q,int x)
{
 if(q->tag)
  return false;
 q->data[q->tail++]=x;
 if(q->tail>=512)
  q->tail=0;
 if(q->tail==q->head)
  q->tag=true;
 return true;
}

bool DeCircleQueue(CircleQueue *q,int *x)
{
 if(q->head==q->tail&&(!q->tag))
  return false;
 *x=q->data[q->head++];
 if(q->head>=512)
  q->head=0;
 if(q->head==q->tail)
  q->tag=false;
 return true;
}

//ex3.30
typedef struct _CirQueue
{
 int data[512];
 int length;
 int rear;
}CirQueue;

void init_CirQueue(CirQueue *q)
{
 q->length=q->rear=0;
}

bool EnCirQueue(CirQueue *q,int x)
{
 if(q->length==512)
  return false;//满
 q->data[q->rear++]=x;
 if(q->rear>=512)
  q->rear=0;
 q->length++;
 return true;
}

bool DeCirQueue(CirQueue *q,int *x)
{
 int pos;
 if(q->length==0)
  return false;
 pos=q->rear-q->length;
 if(pos<0)
  pos+=512;
 *x=q->data[pos++];
 q->length--;
 return true;
}

//ex3.31
#define STACK_INIT_SIZE 1024

typedef struct _sqstack
{
 int *bottom;
 int top;
 int size;
}sqstack,*psqstack;

//初始化stack
bool init_stack(sqstack *s)
{
 if((s->bottom=(int *)malloc(sizeof(int)*STACK_INIT_SIZE))==NULL)
  return false;
 s->top=-1;
 s->size=STACK_INIT_SIZE;
 return true;
}

bool push(psqstack s,int x)
{
 if(s->top>=s->size-1)
  return false;
 s->bottom[++s->top]=x;
 return true;
}

bool pop(sqstack *s,int *x)
{
 if(s->top==-1||s->size<=0)
  return false;
 *x=s->bottom[s->top--];
 return true;
}

bool stack_empty(sqstack *s)
{
 if(s->top==-1)
  return true;
 return false;
}

typedef struct _squeue
{
 int data[512];
 int front;
 int rear;
}squeue;

void init_squeue(squeue *q)
{
 q->front=-1;
 q->rear=0;

}

bool EnSqueue(squeue *q,int x)
{
 if(q->rear>=512)
  return false;
 q->data[q->rear++]=x;
 return true;
}

bool DeSqueue(squeue *q,int *x)
{
 if(q->front+1==q->rear)//空
  return false;
 *x=q->data[++q->front];
 return true;
}

bool check_huiwen(sqstack *s,squeue *q)
{
 char c;
 int a,b;
 scanf("%c",&c);
 while(c!='@')
 {
  if(!push(s,(int)c))
  {
   printf("push stack error\n");
   return false;
  }
  if(!EnSqueue(q,(int)c))
  {
   printf("ensqueue error\n");
   return false;
  }
  scanf("%c",&c);
 }
 while(!stack_empty(s))
 {
  pop(s,&a);
  DeSqueue(q,&b);
  if(a!=b)
   return false;
 }
 return true;
}


int main(int argc, char* argv[])
{

 //test ex3.28
 int i,x;
 ClQueue q1;
 ClQNode *node;

 if(!init_clqueue(&q1))
 {
  printf("init clqueue error\n");
  return 1;
 }
 
 for (i=3;i<20;i++)
 {
  EnClQueue(&q1,i);
 }
 printf("now clqueue hold:\n");

 node=q1.head->next;
 printf("#->");
 while(node!=q1.head)
 {
  printf("%d->",node->data);
  node=node->next;
 }
 printf("||\n");
 printf("queue tail is:\n");
 printf("%d\n",q1.tail->data);
 printf("now we dequeue some element\n");
 for(i=0;i<4;i++)
 {
  DeClQueue(&q1,&x);
  printf("%d\t",x);
  printf("then head is:%d\n",q1.head->next->data);
 }

 //test ex3.29
 CircleQueue q2;
 init_circlequeue(&q2);
 for(i=0;i<512;i++)
 {
  if(!EnCircleQueue(&q2,i))
  {
   printf("No %d Enqueue failed\n",i);
   return 1;
  }
 }
 printf("Now circle queue hold:\n");
 for(i=0;i<512;i++)
 {
  printf("%d  ",q2.data);
 }
 printf("\n");
 printf("Now circle queue head and tail is:%d and %d\n",q2.head,q2.tail);
 printf("tag is:%d\n",q2.tag);
 for(i=0;i<512;i++)
 {
  if(!DeCircleQueue(&q2,&x))
  {
   printf("DeCircleQueue error\n");
   return 1;
  }
  printf("No %d times Dequeue:%d---head:%d\n",i,x,q2.head);
 }


 //test ex3.30
 CirQueue q3;
 init_CirQueue(&q3);
 for(i=0;i<512;i++)
 {
  if(!EnCirQueue(&q3,i))
  {
   printf("No %d Enqueue failed\n",i);
   return 1;
  }
 }
 printf("Now cir queue hold:\n");
 for(i=0;i<512;i++)
 {
  printf("%d  ",q3.data);
 }
 printf("\n");
 printf("Now circle queue rear and length is:%d and %d\n",q3.rear,q3.length);
 if(!EnCirQueue(&q3,1000))
  printf("en queue error\n");

 for(i=0;i<512;i++)
 {
  if(!DeCirQueue(&q3,&x))
  {
   printf("DeCirQueue error\n");
   return 1;
  }
  printf("No %d times Dequeue:%d---length:%d\n",i,x,q3.length);
 }


 //test ex3.31
 sqstack s;
 squeue q4;
 if(!init_stack(&s))
 {
  printf("init stack error\n");
  return 1;
 }
 init_squeue(&q4);
 if(!check_huiwen(&s,&q4))
 {
  printf("not huiwen\n");
  return 1;
 }
 printf("yes, it is huiwen\n");


 return 0;
}
写原创有奖励！2024面包板原创奖励正在进行中

文章评论（0条评论）

登录后参与讨论
用户1361860
文章：289 阅读：1051882 评论：266 赞：2508
好友 私信 个人主页
EE直播间
更多
在线研讨会
更多
我要评论
0
9
关闭 站长推荐上一条 /2 下一条
  • 帖子
  • 博文
  • 返回顶部