数据结构基础(五).队

#include <stdio.h>
#include <malloc.h>


typedef struct qnode //定义一个队列节点结构体
{
  int score;
  struct qnode *next;
}QN,*NP;   //重命名结构体为QN,指针为NP

typedef struct queue //定义一个队列头结构体
{
  int count; //用来存储所有成员的个数
  struct qnode *front; //指向队头节点
  struct qnode *rear; //指向队尾节点
}QU,*QP; //重命名结构体为QU,指针为QP


QP INIT() //初始化队列
{
  QP head=NULL; 
  head=(QP)malloc(sizeof(QU)); //动态申请内存，创建头节点
  if(NULL == head) //进行判断，申请内存失败则提醒并且返回
  {
    printf("xxx error:no enough memory!\n");
    return NULL;
  }
  head->count=0; //初始化元素个数为0
  head->front=NULL; 
  head->rear=NULL; //初始化队头队尾为空
  return head; //将头节点位置返回
}

int IFEMPTY(const QP head) //判断队列是否为空，为空则返回0
{
  if (0 == head->count) return 0;
  else return -1;
}

int ENQUEUE(const QP head,const int score) //入队操作
{
  NP np=NULL;
  np=(NP)malloc(sizeof(QN)); //动态申请内存，创建节点
  if(NULL == np)  //进行判断，申请内存失败则提醒并且返回
  {
    printf("error:no enough memory!\n");
    return -1;
  }
  np->score=score; //给节点赋值
  np->next=NULL; //插入队尾，后继置空
  if(NULL != head->rear) head->rear->next=np; //避开第一交的插入操作，对第一次插入的节点要进行特殊对待
  head->rear=np; //更新队尾指针
  if(NULL == head->front) head->front=np; //对第一次插入操作进行特殊处理，如果是第一次插入，就将队头也指向这个结节
  head->count++; //及时更新元素个数
  return 0;
}


int DEQUEUE(const QP head) //出队操作
{
  NP np=NULL;
  int res=-1;
  if(0 == IFEMPTY(head)) //操作前进行一下检查，判断此队是否为空
  {
    printf("DEQUEUE error:this is a empty queue!\n");
    return -1;
  }
  np=head->front;  //将地址进行缓存
  head->front=head->front->next; 
  if(NULL == head->front )head->rear=NULL; //对于只有一个节点的出队操作进行特殊处理，将队尾置空
  res=np->score; //取出分数
  free(np); //释放节点空间
  head->count--; //及时更新元素个数
  return res; //将数值返回
}

int FRONT(const QP head) //取出队头数据，但不进行出队操作
{
  if(0 == IFEMPTY(head)) //操作前进行一下检查，判断此队是否为空
  {
    printf("DEQUEUE error:this is a empty queue!\n");
    return -1;
  }
  return head->front->score; //返回队头值
}


int COUNT(const QP head) //计算元素个数
{
  return head->count; //取出元素个数，进行返回
}

int SHOW(const QP head) //打印所有元素
{
  NP np=NULL;
  if(0 == IFEMPTY(head)) //操作前进行一下检查，判断此队是否为空
  {
    printf("DEQUEUE error:this is a empty queue!\n");
    return -1;
  }
  for(np=head->front;np;np=np->next)printf("(%d)",np->score); //遍历元素进行打印
  printf("\n");
  return 0;
}

int SETNULL(const QP head) //清空队列
{
  while(head->count)DEQUEUE(head); //循环出队
  return 0;
}


int main()
{
  ////INIT
  QP que=NULL; 
  que=INIT(); //初始化测试
  ////SHOW
  SHOW(que); //打印测试
  ////ENQUEUE
  printf("add five nodes to this queue 50,80,70,90,100\n"); 
  ENQUEUE(que,50);
  ENQUEUE(que,80);
  ENQUEUE(que,70);
  ENQUEUE(que,90);
  ENQUEUE(que,100); //入队测试
  SHOW(que); 
  ////COUNT
  printf("the total number of nodes in queue is:%d\n",COUNT(que)); //计数测试
  ////DEQUEUE
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que));
  SHOW(que);
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que));
  SHOW(que);
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que)); //出队测试
  SHOW(que);
  printf("the total number of nodes in queue is:%d\n",COUNT(que));  
  SHOW(que);
  ////FRONT
  printf("the front node in queue is:%d\n",FRONT(que));
  SHOW(que);
  printf("the total number of nodes in queue is:%d\n",COUNT(que));
  printf("the front node in queue is:%d\n",FRONT(que)); 
  SHOW(que);
  printf("the total number of nodes in queue is:%d\n",COUNT(que));
  printf("the front node in queue is:%d\n",FRONT(que));  //打印队头测试
  SHOW(que);
  printf("the total number of nodes in queue is:%d\n",COUNT(que));
  ////SETNULL
  printf("ready to clear this queue\n");
  SETNULL(que); //清队测试
  SHOW(que);
  ////ENQUEUE
  printf("add two more nodes into this queue 50,80\n");
  ENQUEUE(que,50);
  ENQUEUE(que,80);  //进一步的入队出队测试
  SHOW(que);
  ////DEQUEUE
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que));
  SHOW(que);
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que));
  SHOW(que);
  printf("the DEQUEUE ops result is:%d\n",DEQUEUE(que));
  SHOW(que);
  printf("the total number of nodes in queue is:%d\n",COUNT(que));
  SHOW(que);
  return 0;
}

emacs@ubuntu:~/c$ alias gtc
alias gtc='gcc -Wall -g -o'
emacs@ubuntu:~/c$ gtc queue.x queue.c
emacs@ubuntu:~/c$ ./queue.x 
DEQUEUE error:this is a empty queue!
add five nodes to this queue 50,80,70,90,100
(50)(80)(70)(90)(100)
the total number of nodes in queue is:5
the DEQUEUE ops result is:50
(80)(70)(90)(100)
the DEQUEUE ops result is:80
(70)(90)(100)
the DEQUEUE ops result is:70
(90)(100)
the total number of nodes in queue is:2
(90)(100)
the front node in queue is:90
(90)(100)
the total number of nodes in queue is:2
the front node in queue is:90
(90)(100)
the total number of nodes in queue is:2
the front node in queue is:90
(90)(100)
the total number of nodes in queue is:2
ready to clear this queue
DEQUEUE error:this is a empty queue!
add two more nodes into this queue 50,80
(50)(80)
the DEQUEUE ops result is:50
(80)
the DEQUEUE ops result is:80
DEQUEUE error:this is a empty queue!
DEQUEUE error:this is a empty queue!
the DEQUEUE ops result is:-1
DEQUEUE error:this is a empty queue!
the total number of nodes in queue is:0
DEQUEUE error:this is a empty queue!
emacs@ubuntu:~/c$