C语言数据结构——队列

骑猪看日落 2022-06-16 06:18 248阅读 0赞

1、队列是一种先进先出的线性表，它只允许在一端进行插入，在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫对头。  
2、队列的基本操作：

InitQueue(&Q)  //构造一个空队列
    DestroyQueue(&Q)  //销毁队列
    ClearQueue(&Q)   //清除队列
    QueueEmpty(&Q)  //判断是否为空队列
    QueueLength(&Q)  //求队列的长度
    GetHead(Q,&e)  //用e返回对头元素
    EnQueue(&Q,e)  //插入元素e为新的对头元素
    DeQueue(&Q,&e)   //删除对头元素，并用e返回其值
    QueueTraverse(Q,visit())  
    //从对头到对尾，依次对Q的每个元素调用函数visit()，调用失败则操作失败

3、

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define OK 1
    #define FALSE 0
    #define ERROR 0
    #define TRUE 1
    #define OVERLOW -2
    
    typedef int Status;
    
    //结点结构 
    typedef struct QNode
    {
        int data;
        struct QNode *next;
    }QNode,*QueuePtr;
    
    //队列链表结构
    typedef struct 
    {
        QueuePtr front;  //对头指针
        QueuePtr reat;  //对尾指针  
    }LinkQueue;
    
    //构造一个空队列
    Status InitQueue(LinkQueue &Q)
    {
        Q.front = Q.reat =(QueuePtr)malloc(sizeof(QNode));
        if(!Q.front)
            exit(OVERLOW);  
        Q.front->next = NULL;
        return OK;
    }
    
    //销毁队列
    Status DestroyQueue(LinkQueue &Q)
    {
        wile(Q.front)
        {
            Q.reat = Q.front->next;
            free(Q.front);
            Q.front = Q.reat;   
        }   
        return OK;
    } 
    
    //插入元素为e的新对尾元素，并返回其值
    Status EnQueue(LinkQueue &Q,int e)
    {
        QueuePtr p;
        p = (QueuePtr)malloc(sizeof(QNode));
        if(!p)  //分配失败 
            exit(OVERLOW);  
        p->data = e;  //插入到最后一个后，数据域为e,指针域为空 
        p->next = NULL;
        Q.reat->next = p;   //把拥有元素e的p赋值给原对位指针的直接后继 
        Q.reat = p;   //把当前的p设置为队尾结点，rear指向p 
        return OK;
    } 
    
    //若队列不为空，删除对头元素，用e返回其值，并返回ok
    Status DeQueue(LinkQueue &Q,int &e)
    {
        QueuePtr p;
        if(Q.front == Q.reat)  //分配失败 
            return  ERROR;
        p = Q.front->next;   //将要删除的对头节点暂存给p 
        *e = p->next;   //将要删除的对头结点的值赋值给e 
        Q.front->next = p->next;  //将原对头结点的后继赋值给头结点的后继 
        if(Q.reat == p)
            Q.reat = Q.front;   //若对头是队尾，则删除后将rear指向头结点 
        free(p);   //释放p 
        return OK;
    }