队列的链表存储结构及实现.cpp

队列的链表存储结构及实现

#include"stdio.h"
#include"stdlib.h"
#define ElemType int
typedef  struct NodeType                 /*数据元素结点的结构*/
          {  ElemType  data;
             struct NodeType *next;
          }NodeType;
typedef struct                          /*队列头、尾指针被封装在一起*/
          {NodeType *front,*rear;
          }LinkQueue;                   /*队列头尾指针结构体*/
NodeType *p,*s,*h;
void outlin(LinkQueue qq);              /*参数要与下面的函数说明一致*/
void creat(LinkQueue *qe);
void insert(LinkQueue *qe,ElemType x);
ElemType Delete(LinkQueue *qe);
void main()
{LinkQueue que;ElemType y,x;
  int cord;
  do{printf("\n            主菜单        \n");
     printf("     1    建立链表队列      \n");
     printf("     2    入队一个元素X     \n");
     printf("     3    出队一个元素      \n");
     printf("     4    结束程序运行      \n");
     printf("----------------------------\n");
     printf(" 请输入您的选择(1, 2, 3, 4)");scanf("%d",&cord);
     switch(cord)
     { case 1:{  /*重要 ，这是头尾指针结点*/
              creat(&que);
              outlin(que);
              }break;
       case 2:{ printf("\n x=?"); scanf("%d",&x);
               insert(&que,x);  outlin(que);
              }break;
       case 3:{y=Delete(&que); printf("\n   x=%d",y);
             outlin(que);
              }break;
       case 4:exit(0);
     }
  }while(cord<=4);
}/*main  end*/
void outlin(LinkQueue qq)
{ p=qq.front->next;
  while(p!=NULL){printf("  data=%4d\n",p->data);
     p=p->next;
    }
   printf("\n outend \n\n");
}
void insert(LinkQueue *qe,int x)
{  /*值为x的结点入队*/
   s=(NodeType *)malloc(sizeof(NodeType));  
   s->data=x;  s->next=NULL;
   qe->rear->next=s;  qe->rear=s;
}
ElemType Delete(LinkQueue *qe)
{  ElemType x;
   if(qe->front==qe->rear){printf("队列为空。\n");x=0;}
    else{p=qe->front->next;
         qe->front->next=p->next;
         if(p->next==NULL)qe->rear=qe->front;  /*防止尾指针丢失*/
         x=p->data;  free(p);
        }
  return(x);
}
void creat(LinkQueue *qe)
{int i,n,x;
 h=(NodeType *)malloc(sizeof(NodeType));
 h->next=NULL;
 qe->front=h;qe->rear=h;
 printf("n=");  scanf("%d",&n);
 for(i=1;i<=n;i++)
  {printf("\n data=");  scanf("%d",&x);
   insert(qe,x);
  }
}