本文主要是介绍链式队列的结构设计及基本操作的实现(初始化,入队,出队,获取元素个数,判空,清空,销毁),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一.链式队列的设计思想
二.链式队列的结构设计
三.链式队列的实现
四.链式队列的总结
一.链式队列的设计思想
首先一定要理解设计的初衷,就是队头队尾的位置要满足怎么快怎么设计.那么分析如下:
最终我们敲定了入队,出队的时间复杂度都为O(1)的一种设计,也就是第四种设计;当然,头节点的数据域不使用,所以我们设计链式队列的头节点的时候删除数据域即可,链式队列的结构设计如下:
二.链式队列的结构设计
typedef struct LPNode//数据节点{int data;//数据struct LPNode* next;//后继指针
}LPNode;typedef struct HNode //链式队列的头节点{struct LPNode* front;//队头指针,指向第一个数据节点struct LPNode* rear;//队尾指针,指向最后一个数据节点
}HNode ,*PLQueue;
三.链式队列的实现
//初始化
void InitQueue(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return;pq->front = NULL;pq->rear = NULL;}//入队;
bool Push(PLQueue pq, int val)
{assert(pq != NULL);if (pq == NULL)return false;//申请节点LPNode* p = (LPNode*)malloc(sizeof(LPNode));p->data = val;p->next = NULL;//p->next=pq->rear->next;//插入if (IsEmpty(pq))//第一次入队{pq->front = p;pq->rear = p;}else{pq->rear->next = p;//将P插入到队尾pq->rear = p;//更新队尾指针}return true;
}//出队,获取队头的值并且删除
bool Pop(PLQueue pq, int* rtval)
{assert(pq != NULL);if (pq == NULL)return false;if (IsEmpty(pq)){return false;}*rtval = pq->front->data;//删除第一个节点LPNode* p = pq->front;pq->front = p->next;free(p);if (pq->front == NULL)//删除最后一个节点{pq->rear = NULL;}return true;
}//获取队头元素的值但不删除
bool GetTop(PLQueue pq, int* rtval)
{assert(pq != NULL);if (pq == NULL)return false;if (IsEmpty(pq)){return false;}*rtval = pq->front->data;return true;
}//获取长度
int GetLength(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return -1;int count = 0;for (LPNode* p = pq->front; p != NULL; p = p->next){count++;}return count;}//判空
bool IsEmpty(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return false;return pq->front == NULL;
}//销毁
void Destroy(PLQueue pq)
{assert(pq != NULL);if (pq == NULL)return;LPNode* p;while (pq->front != NULL)//总是删除第一个数据节点{p = pq->front;pq->front = p->next;free(p);}pq->rear = NULL;
}
四.链式队列的总结
1.带头节点,队头为第一个数据节点,队尾在最后一个数据节点
2.头节点为一个队头指针,一个队尾指针,增加队尾指针可以让入队的时间复杂度为O(1)
这篇关于链式队列的结构设计及基本操作的实现(初始化,入队,出队,获取元素个数,判空,清空,销毁)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!