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

梦里梦外; 2021-09-16 10:44 339阅读 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);
    }