【数据结构】链式队列的实现-蒲公英云

【数据结构】链式队列的实现

梦里梦外; 2021-09-16 10:44 469阅读 0赞

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct{ 
 int stuNo;
 char name[10];
}QElemType;// 定义了一个新类型，类型名为 QElemType
typedef struct QNode{ 
 QElemType data;
 struct QNode* next; // 指向QNode类型的指针
}QNode,*QueuePtr; // QueuePtr的类型为 QNode* ，即指向自己的一个指针
typedef struct{ 
 QueuePtr front; //队头指针
 QueuePtr rear;  // 队尾指针
}LinkQueue;
Status InitQuque(LinkQueue &Q){  // 初始化队列
   Q.front=Q.rear = (QueuePtr)malloc(sizeof(QNode));
   if(!Q.front) return OVERFLOW;//存储分配失败
   Q.front->next=NULL;
    return OK;
}
Status DestroyQueue(LinkQueue &Q){  //销毁队列
    while(Q.front){  //当 头指针不空的时候回
        Q.rear=Q.front->next;
        free(Q.front);
        Q.front =Q.rear;
    }
  return OK;
}
Status getHead(LinkQueue Q,QElemType &e){ 
  if(Q.front==Q.rear) return ERROR;
  e= Q.front->next->data;
  return OK;
}
Status QueueEmpty(LinkQueue Q){ 
    if(Q.front==Q.rear) return TURE;
    else return FALSE;
}
int QueueLength(LinkQueue Q){ 
     int n=0;
     while(Q.front!=Q.rear){ 
        Q.front= Q.front->next;
        n++;
     }
     return n;
}
Status EnQueue(LinkQueue &Q,QElemType e){ //插入元素e为队列Q的新的队尾元素
 QueuePtr p =(QueuePtr)malloc(sizeof(QNode));
 if(!p) return OVERFLOW; //存储分配失败
 p->data=e; p->next=NULL;
 Q.rear->next=p;
 Q.rear=p;
 return OK;
}
Status DeQueue(LinkQueue &Q, QElemType &e){ 
    if(Q.front==Q.rear) return ERROR;// 头指针和尾指针指向同一位置时，队列为空
    QueuePtr p = Q.front->next; //p指针指向队头元素
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear==p) Q.rear=Q.front;//如果队头元素已经是队列的最后一个元素，让尾指针指向和头指针指向的位置
    free(p);
    return OK;
}
void QueueTravel(LinkQueue Q){ 
    QueuePtr p=Q.front;
     while(p!=Q.rear){ 
        p = p->next;
        printf("\n%d %s",p->data.stuNo,p->data.name);
     }
}
int main()
{ 
    LinkQueue Q;
    InitQuque(Q);
    QElemType e;
    for(int i=0;i<3;i++){ 
        scanf("%d%s",&e.stuNo,e.name);
        EnQueue(Q,e);
    }
    QueueTravel(Q);
    printf("\nDEQueue:");
    DeQueue(Q,e);
    QueueTravel(Q);
}