欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列的链式存储结构及其实现

程序员文章站 2024-03-01 11:58:58
...

队列也是一种特殊的线性表,只允许在一端进行插入操作,在另一端进行删除操作。允许插入的一段为对尾,允许删除的一端为队头。本次记录的是队列的链式存储结构以及实现。该存储结构有两个指针,一个指向头节点,称为头指针(front);一个指向队尾,称为尾指针(rear)。当front==rear时,表示空队列。当需要在队列中插入元素时,需要将队尾结点指向新插入的结点,然后将尾指针指向新插入的结点。当要在队列中进行删除操作时,只需让头指针指向队头结点的下一个结点即可。实现代码如下:

#include <iostream>
#include<stdlib.h>
using namespace std;


typedef struct QNode   //定义一个连队列的结点
{
    int data;
    struct QNode *next;
}QNode;
typedef struct         //定义链队列的数据结构
{
    QNode *front;
    QNode *rear;
}LinkQueue;

// 构造一个空队列q
LinkQueue *InitQueue(LinkQueue *q)
{
	QNode *tmp = (QNode*)malloc(sizeof(QNode));
    q->front = tmp;
	q->rear = tmp;
    q->front->next = NULL;
    return q;
}
// 元素入队
LinkQueue *EnQueue(LinkQueue *q, int e)
{
    QNode *p = (QNode*)malloc(sizeof(QNode));//为插入节点分配空间
    if(!p)
    {//分配空间失败
        cout<<"插入节点内存分配失败!"<<endl;
    }
    else
    {   //建节点
        p->data = e; //为插入节点数据域赋值
        p->next = NULL;//为插入节点指针域赋值
        //实现插入
        q->rear->next = p;//插入到队尾
        q->rear = p;//队尾指针重新指向新任队尾
    }
    return q;
}
//元素出队
LinkQueue *DeQueue(LinkQueue *q)
{
    QNode *p;
    if(q->front == q->rear)
    {
        cout<<"链队列已空,不可再执行删除操作!"<<endl;
    }
    else
    {
        p = q->front->next;//将欲删除的队头结点暂存给p
        int e = p->data;//把队头数据赋给e
        cout <<"delete: " << e <<endl;
        q->front->next = p->next;//删除,将原队头结点的后继p->next赋值给头结点后继
        if(q->rear == p)    //此时链队列只存在一个元素结点
        {
			//若队头就是队尾,则删除后将rear指向头结点
            cout<<"链队列数据全部删除完毕!"<<endl;
            q->rear = q->front;
        }
        free(p);
    }
    return q;
}
//返回队头元素
void GetQHead(LinkQueue *q)
{
    QNode *p;
    if(q->front == q->rear)
    {
        cout<<"链队列为空,无法返回队头数据"<<endl;
    }
    else
    {
        p = q->front->next;//队头
        cout<< "队头元素:" << p->data <<endl;
    }
}
//求队列长度
void QueueLength(LinkQueue *q)
{
    int length = 0;
    QNode *p;
    p = q->front->next;//队头
    while(p)
    {
        length++;
        p = p->next;
    }
    cout<<"队列长度:"<< length << endl;
}
//打印。带头结点,真正存储元素的位置从头结点下一位置(队头)开始!!!
void PrintQueue(LinkQueue *q)
{
    QNode *p;//队头
    p = q->front->next;//头结点的下一节点,即为队头!!!
    while(p)
    {//从队头开始,依次往后遍历
        cout<< p->data <<" ";
        p = p->next;
    }
    cout << endl;
}
int main()
{
    LinkQueue q ;
	InitQueue(&q);

    EnQueue(&q, 1);
    PrintQueue(&q);
    EnQueue(&q, 2);
    PrintQueue(&q);
    EnQueue(&q, 3);
    PrintQueue(&q);
    EnQueue(&q, 4);
    PrintQueue(&q);

    GetQHead(&q);

    QueueLength(&q);
    cout<<"***************"<<endl;
    DeQueue(&q);
    PrintQueue(&q);
    GetQHead(&q);

    DeQueue(&q);
    PrintQueue(&q);
    GetQHead(&q);

    DeQueue(&q);
    PrintQueue(&q);

    DeQueue(&q);
    PrintQueue(&q);

    QueueLength(&q);

    cout<<"***************"<<endl;
    DeQueue(&q);
    cout<<"***************"<<endl;

    return 0;
}

运行结果截图:

队列的链式存储结构及其实现

队列的链式存储结构及其实现

上一篇: WIN32 基础控件的使用

下一篇: