数据结构：链对

链队列.c

//
// Created by 方朋 on 16/12/20.
//


#include <stdio.h>
#include <stdlib.h>
#include "global.h"

/*
 * ADT 队列(Queue)
 * Data
 *  同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
 * Operation
 *  InitQueue(*Q)       // 初始化, 建立一个空队列
 *  DestroyQueue(*Q)    // 若Q存在则销毁队列
 *  ClearQueue(*Q)      // 将队列Q清空
 *  QueueEmpty(Q)       // 是否为空
 *  GetHead(Q, *e)      // 若队列存在且非空,用e返回队列Q的队头元素
 *  EnQueue(*Q, e)      // 若队列Q存在,插入新元素e到队列Q中并成为队尾元素
 *  DeQueue(*Q, *e)     // 删除队列Q中队头元素,并用e返回其值
 *  QueueLength(Q)      // 返回队列Q的元素个数
 * endADT
 */

typedef int QElemType;

// 结点结构
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

// 队列的链表结构
typedef struct
{
    QueuePtr front, rear;   // 队头,队尾指针
}LinkQueue;

// 构造一个空队列Q
Status InitQueue(LinkQueue *Q)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->next = NULL;
    Q->front = p;
    Q->rear = p;
    return OK;
}

// 是否为空
int QueueEmpty(LinkQueue Q)
{
    return Q.rear == Q.front;
}

// 入队
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;      /* 把拥有元素e的新结点p赋值给原队尾结点的后继 */
    Q->rear = p;            /* 把当前的p设置为队尾结点, rear指向p */
    return OK;
}

// 出队
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    if (QueueEmpty(*Q)) return ERROR;
    QueuePtr p = Q->front->next; // 出队操作时,就是头结点的后继结点出队
    *e = p->data;
    Q->front->next = p->next;
    // 如果链表除了头结点外只剩下一个元素, 则将rear指向头结点.
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    free(p);
    return OK;
}

int QueueLength(LinkQueue Q)
{
    int len = 0;
    while (Q.front != Q.rear)
    {
        len++;
        Q.front = Q.front->next;
    }
    return len;
}

Status QueueTraverse(LinkQueue Q)
{
    while (Q.front != Q.rear)
    {
        printf("%d ", Q.front->next->data);
        Q.front = Q.front->next;
    }
    printf("\n");
    return OK;
}
Status GetHead(LinkQueue Q, QElemType *d)
{
    *d = Q.front->next->data;
    return OK;
}

/* 将Q清为空队列 */
// 我写的与《大话数据结构》有出入
Status ClearQueue(LinkQueue *Q)
{
    QueuePtr p = Q->front;
    while (p != Q->rear)
    {
        free(p);
        p = p->next;
    }
    Q->front = Q->rear;
    return OK;
}

/* 销毁队列Q */
Status DestroyQueue(LinkQueue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

int main()
{
    QElemType d;
    LinkQueue Q;

    InitQueue(&Q);
    printf(QueueEmpty(Q) ? "空" : "非空");
    printf("队列的长度为%d\n",QueueLength(Q));

    EnQueue(&Q, -5);
    EnQueue(&Q, 5);
    EnQueue(&Q, 10);
    printf("插入3个元素(-5, 5, 10)后,队列的长度为%d\n", QueueLength(Q));
    printf("是否空队列？%d(1:空 0:否)  \n",QueueEmpty(Q));
    printf("队列的元素依次为：");
    QueueTraverse(Q);

    GetHead(Q, &d);
    printf("队头元素是：%d\n",d);

    DeQueue(&Q, &d);
    printf("删除了队头元素%d\n",d);
    int i=GetHead(Q, &d);
    if(i==OK)
        printf("新的队头元素是：%d\n",d);
    QueueTraverse(Q);

    ClearQueue(&Q);
    printf("清空队列后,Q.front=%p Q.rear=%p Q.front->next=%p\n",Q.front, Q.rear, Q.front->next);
    DestroyQueue(&Q);
    printf("销毁队列后,Q.front=%p Q.rear=%p\n", Q.front, Q.rear);
}