• 队列的链式表示和实现
  • 发布于 1个月前
  • 53 热度
    0 评论
链队:队列的链式表示和实现
相应函数定义
InitQueue(&Q);                  构造空队列
DestroyQueue(&Q);               销毁队列
ClearQueue(&S);                 清空队列
QueueEmpty(S);                  判空.空-TRUE
QueueLength(Q);                 取队列长度
GetHead(Q, &e);                 取队头元素
EnQueue(&Q, e);                 入队列
DeQueue(&Q, &e);                出队列
QueueTraverse(Q, visit());      遍历
头文件、宏定义
#include<stdlib.h>      // 使用exit(0)时需要引用头文件
#define MAXSIZE 100
#define ElemType int
// 以下为使用Status的配套操作
#define Status int
#define OK 1
#define Error 1
定义结构体
#define ElemType int 
typedef struct QNode        // 当定义链式结构(需要定义指针时),记得需要再struct后面加类名
{
    ElemType data;
    struct QNode* next;     // 这个记得要写对,就算定义链式结构中next指针时记得加struct
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
链队初始化
step 1 : 生成新节点作为头结点,队头和队尾指针都指向此结点。
step 2 : 头结点的指针域取为NULL
Status InitQueue(LinkQueue& Q)
{
    // 生成新节点作为头结点,对头和队尾指针指向该结点
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;   //头结点的指针与置空
    return OK;
}
判断链队是否为空
bool EmptyQueue(LinkQueue Q)
{
    return Q.front == Q.rear;
}
求链队的队头元素
记得判断队列是否非空
Status GetHeadQueue(LinkQueue Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;  // 判断队列是否非空
    e = Q.front->data;
    return OK;
}
链队入队
step 1:为入队元素分配结点空间,用指针p指向
step 2:将新结点数据域置为e,指针域置为空
step 3:将新结点插入到队尾
step 4:修改队尾指针为p
Status EnQueue(LinkQueue& Q, ElemType e)
{
    // 链队不需要判断是否队满
    QNode* p = new QNode;   // 为入队元素分配结点空间,用指针p指向
    p->data = e;            // 将新结点数据域置为e
    p->next = NULL;
    Q.rear->next = p;       // 将新结点插入到队尾
    Q.rear = p;             // 修改队尾指针
    return OK;
}
思考:链队**需要头结点**,因为当没有头结点时,我们需要判断是否为第一个结点,如果为第一个结点,那么就将`front`以及`rear`指针指向第一个结点,
链队出队
step 1:判断队列是否为空,若空着返回Error
step 2:临时保存队头元素的空间,已备释放
step 3:修改头结点的指针域,使其指向下一个结点
step 4:判断出队元素是否为最后一个元素,若是,则将队尾指针重新赋值,指向头结点。
step 5:释放原始队头元素的空间
Status DeQueue(LinkQueue& Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;
    QNode* p = new QNode;
    p = Q.front->next;                  // p 指向首元结点
    e = Q.front->data;                  // e保存队头结点的数据域
    Q.front = Q.front->next;            // 修改头结点的指针域
    if (Q.rear == p) Q.rear = Q.front;  // 若删的是最后一个元素,则修改队尾指针指向头结点
    delete p;                           // 释放原队头元素的空间
    return OK;
}
思考:链队**需要头结点**,因为当没有头结点时,如果链队出完后为空,那么我需要将`front`和`rear`指针置空,又会多一步判断。
销毁链表
将rear指针当做第三方指针,用于记录front->next指针,然后删除前一个指针,直到front指针为空,那么就删除完了。
Status DestroyQueue(LinkQueue& Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}


用户评论