当前位置：首页 > news >正文

队列的链式存储结构及其基本运算实现

news 来源：原创 2024/4/26 20:25:21

前面我们介绍了顺序队列的存储 ,是利用数组存储数据 , 然后删除节点数据和添加节点数据都是在数组完成的 , 有一个弊端就是 ,当我们操作的数量很大时 , 如果数组存储结构就很难队列操作了 ,那就需要利用链式存储结构了

●链队组成:
(1) 存储队列元素的单链表
(2) 指向队头和队尾的链队头结点

●存储结构的定义
• 数据节点的定义
typedef struct qnode
{
    ElemType data;
    struct qnode*next;
}QNode;
数据节点就是我们的链队节点,包含数据区和后继指针区

•链队节点
typedef struct
{
    QNode *front;
    QNode *rear;
}LiQueue;
链队节点就是管理队列的指针 , front 指向单链表的头结点 , rear 指向单链表的尾结点

链队 4 要素

(1)队空条件: front = rear = NULL

初始链队内无元素 , 所以指向 NULL

(2)队满条件 : 不考虑

因为存储数据的是链表 , 所以存储容量是灵活的

(3) 进队操作 : 将包含新元素 e 的节点插入到单链表表尾

我们需要构造一个新节点 ,数据区包含新元素e 的数据 (进队不考虑队满,我们链表优势)

然后队尾节点的后继指针要指向新节点 ,然后我们的队尾指针rear 也要指向新节点

(4) 出队操作: 删除单链表中首个数据节点 , 并将要出队的节点数据保存传出 .

考虑队空因素 , 链队内无元素 ,则无法出队操作

要删除队首指针front所指向的节点 ,首先最好把其位置存储一下,方便后续释放其空间

然后把 front 指向删除节点的后一个节点即可(我们在覆盖或删除指针前 ,特别注意我们以后还会不会用到这个指针 ,如果用到 ,我们最后存储或存储之后,再将其删除或覆盖)

初始化队列InitQueue(q)

●构造一个空队列 ,即只创建一个包含队首指针和队尾指针的头结点 ,front和 rear都置为空,
因为是空队列,所以没有元素,不创建元素节点
//传入要创建的链队的指针地址
void InitQueue(LiQueue *&q)
{
    //链队头结点申请空间
    q = (LiQueue *)malloc(sizeof(LiQueue));
    //队首尾指针置空
    q->front = q->rear =NULL;
}

 

销毁队列DestroyQueue(q)

● 释放队列占用的存储空间 , 包括链队头结点和所有数据节点的存储空间

我们释放链表,当然不会像释放顺序队一样 ,直接把一个数组释放就可以了,因为我们链队的每一个节点都是一个独立的节点 , 他们通过指针指引链接 ,我们需要逐个释放数据节点

注意: 当我们释放第一个节点 a1 的时候 ,因为 a1的后继指针存储着后续节点的位置信息 ,所以我们不能直接释放 ,我们需要再定义一个数据节点 r 来存储删除的节点的后继指针 ,从而保证我们能够顺利的找到下一个要删除释放的节点
//传入要释放删除的链队
void DestroyQueue(LiQueue *&q)
{
	//定义指向要删除的节点的变量和 保存后续节点指针的变量
	//初始要删除的节点是链队第一个元素 ,就是链队头节点q的后一个节点
	//为什么第一个不删除 链队头结点呢?因为头结点q 和数据节点的类型不一样,我们后续单独删除释放即可
	QNode *p = q->front;
	QNode *r;
	//先判断链队是否为空,为空无需删除数据节点 ,直接释链队头结点q即可
	if(p!=NULL)
	{
		//初始要删除第一个节点,然后r保存第二个节点的位置, 位置信息存储在p->next;
		r=p->next;
		while(r!=NULL)
		{
			//当我们要删除的节点后无节点
			free(p);
			//释放完p 之后,我们接着释放后一个节点,r赋值给p
			p = r;
			// r向后移动,存储 p 后面的节点
			r = p->next;
		}
	}
	free(p);
	free(q);
}
当我们释放完倒数第二个数据节点 p 时 , p指向最后一个节点 , r指向空,则跳出了循环, 我们链表最后一个节点未释放 ,我们此时再在循环外释放最后一个链表节点 ,链队头结点q

● 判断队列是否为空 QueueEmpty(q)

•若链队节点的rear域值为NULL , 表示队列为空,返回true;否则返回flase.
//传入要判断为空的队列
bool QueueEmpty(LiQueue *q)
{
    return(q->rear==NULL);
}

●入队enQueue(q,e)

操作:
   •创建data域为e的数据节点 *p
   •若原队列为空,则将链队节点的两个域均为指向*p节点,否则将*p链到单链表的末尾,
   并让链队节点的rear域指向它

//传入要入队的队列,和入队的新元素
void enQueue(LiQueue *&q,ElemType e)
{
    //为新元素创建链表节点
    QNode *p;
    p = (QNode *)malloc(sizeof(QNode));
    p->data = e;
    //因为新节点作为尾结点,所以后继指针置空
    p->next = NULL;
    //插入前,先判断队列是否为空,如果为空,则新元素作为唯一一个节点,
    //队首指针和队尾指针都指向这个节点
    if(q->rear == NULL)
    {
        q->front = q->rear = p;
    }
    else
    {
        //如果原队列不为空,则只用把新节点插入到链表最后一个元素后面,然后把rear指向p
        q->rear->next = p;
        q->rear = p;
    }

}

●出队deQueue(q,e)

操作:
•若原队列不为空则将第一个数据节点的data域值赋给e,并删除之.
•若出队前队列中只有一个节点,则需要将链队节点的两个域均置空为NULL,表示队列已空

我们既然要出队元素,就需要考虑指针 front 和 rear ,我们只是出队一个元素,为什么要注意两个指针呢?因为有的情况,两个指针指向同一个元素,然后我们删除并出队那个元素,我们就需要改变两个指针

①首先,要出队,首先判断队列是否为空, 为空谈何出队

②当我们出队一个元素时候,两个指针都变的时候,那就是出队前,队列里只有一个数据元素,

front和rear都指向那个元素,出完队 , 我们需要将队首和队尾指针置空

③ 就是我们队列里面不止一个元素,然后我们出队只需要动 front 即可出完队 ,把front 指向队列下一个元素即可
bool deQueue(LiQueue*&q,ElemType &e)
{
     QNode *t;
     if ((q->rear==NULL)
       return false;
     t=q->front;
     if (q->front==q->rear)
          q->front=q->rear=NULL;
     else
          q->front=q->front->next;
     e=t->data;
     free(t);
     return true;

}