鏈?zhǔn)疥?duì)列,簡(jiǎn)稱"鏈隊(duì)列",即使用鏈表實(shí)現(xiàn)的隊(duì)列存儲(chǔ)結(jié)構(gòu)。
鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)思想同順序隊(duì)列類似,只需創(chuàng)建兩個(gè)指針(命名為 top 和 rear)分別指向鏈表中隊(duì)列的隊(duì)頭元素和隊(duì)尾元素夹供,如下圖所示:
所示為鏈?zhǔn)疥?duì)列的初始狀態(tài),此時(shí)隊(duì)列中沒有存儲(chǔ)任何數(shù)據(jù)元素仁堪,因此 top 和 rear 指針都同時(shí)指向頭節(jié)點(diǎn)哮洽。
在創(chuàng)建鏈?zhǔn)疥?duì)列時(shí),強(qiáng)烈建議初學(xué)者創(chuàng)建一個(gè)帶有頭節(jié)點(diǎn)的鏈表弦聂,這樣實(shí)現(xiàn)鏈?zhǔn)疥?duì)列會(huì)更簡(jiǎn)單鸟辅。
由此,我們可以編寫出創(chuàng)建鏈?zhǔn)疥?duì)列的 C 語言實(shí)現(xiàn)代碼為:
//鏈表中的節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥?duì)列的函數(shù)
QNode * initQueue(){
//創(chuàng)建一個(gè)頭節(jié)點(diǎn)
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對(duì)頭節(jié)點(diǎn)進(jìn)行初始化
queue->next=NULL;
return queue;
}
鏈?zhǔn)疥?duì)列數(shù)據(jù)入隊(duì)
鏈隊(duì)隊(duì)列中莺葫,當(dāng)有新的數(shù)據(jù)元素入隊(duì)匪凉,只需進(jìn)行以下 3 步操作:
- 將該數(shù)據(jù)元素用節(jié)點(diǎn)包裹,例如新節(jié)點(diǎn)名稱為 elem捺檬;
- 與 rear 指針指向的節(jié)點(diǎn)建立邏輯關(guān)系再层,即執(zhí)行 rear->next=elem;
- 最后移動(dòng) rear 指針指向該新節(jié)點(diǎn)堡纬,即 rear=elem聂受;
由此,新節(jié)點(diǎn)就入隊(duì)成功了烤镐。
例如蛋济,在上圖的基礎(chǔ)上,我們依次將{1,2,3}
依次入隊(duì)炮叶,各個(gè)數(shù)據(jù)元素入隊(duì)的過程如下圖所示:
數(shù)據(jù)元素入鏈?zhǔn)疥?duì)列的 C 語言實(shí)現(xiàn)代碼為:
QNode* enQueue(QNode * rear,int data){
//1碗旅、用節(jié)點(diǎn)包裹入隊(duì)元素
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//2渡处、新節(jié)點(diǎn)與rear節(jié)點(diǎn)建立邏輯關(guān)系
rear->next=enElem;
//3、rear指向新節(jié)點(diǎn)
rear=enElem;
//返回新的rear祟辟,為后續(xù)新元素入隊(duì)做準(zhǔn)備
return rear;
}
鏈?zhǔn)疥?duì)列數(shù)據(jù)出隊(duì)
當(dāng)鏈?zhǔn)疥?duì)列中医瘫,有數(shù)據(jù)元素需要出隊(duì)時(shí),按照 "先進(jìn)先出" 的原則川尖,只需將存儲(chǔ)該數(shù)據(jù)的節(jié)點(diǎn)以及它之前入隊(duì)的元素節(jié)點(diǎn)按照原則依次出隊(duì)即可登下。這里,我們先學(xué)習(xí)如何將隊(duì)頭元素出隊(duì)叮喳。
鏈?zhǔn)疥?duì)列中隊(duì)頭元素出隊(duì),需要做以下 3 步操作:
- 通過 top 指針直接找到隊(duì)頭節(jié)點(diǎn)缰贝,創(chuàng)建一個(gè)新指針 p 指向此即將出隊(duì)的節(jié)點(diǎn)馍悟;
- 將 p 節(jié)點(diǎn)(即要出隊(duì)的隊(duì)頭節(jié)點(diǎn))從鏈表中摘除;
- 釋放節(jié)點(diǎn) p剩晴,回收其所占的內(nèi)存空間锣咒;
例如,在上圖2b) 的基礎(chǔ)上赞弥,我們將元素 1 和 2 出隊(duì)毅整,則操作過程如下圖所示:
鏈?zhǔn)疥?duì)列中隊(duì)頭元素出隊(duì)的 C 語言實(shí)現(xiàn)代碼為:
void DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("隊(duì)列為空");
return ;
}
// 1、
QNode * p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
注意绽左,將隊(duì)頭元素做出隊(duì)操作時(shí)悼嫉,需提前判斷隊(duì)列中是否還有元素,如果沒有拼窥,要提示用戶無法做出隊(duì)操作戏蔑,保證程序的健壯性。
鏈?zhǔn)疥?duì)列的長(zhǎng)度
鏈?zhǔn)疥?duì)列的長(zhǎng)度鲁纠,只需要設(shè)置一個(gè)移動(dòng)指針总棵,由隊(duì)列頭部移動(dòng)直至到隊(duì)列尾部,來達(dá)到計(jì)數(shù)的效果改含。
//隊(duì)列的長(zhǎng)度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空情龄,長(zhǎng)度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空,移動(dòng)指針計(jì)算長(zhǎng)度
pMove = pMove->next;
length++;
}
return length;
}
鏈?zhǔn)疥?duì)列的打印
鏈?zhǔn)疥?duì)列的打印捍壤,實(shí)際上也就是一個(gè)鏈表的遍歷過程骤视。
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊(duì)列為空!\n");
}
while (pMove!=NULL) {
printf("%d ",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
總結(jié)
通過學(xué)習(xí)鏈?zhǔn)疥?duì)列最基本的數(shù)據(jù)入隊(duì)和出隊(duì)操作白群,我們可以就實(shí)際問題尚胞,對(duì)以上代碼做適當(dāng)?shù)男薷摹?/p>
前面在學(xué)習(xí)順序隊(duì)列時(shí),由于順序表的局限性帜慢,我們?cè)陧樞蜿?duì)列中實(shí)現(xiàn)數(shù)據(jù)入隊(duì)和出隊(duì)的基礎(chǔ)上笼裳,又對(duì)實(shí)現(xiàn)代碼做了改進(jìn)唯卖,令其能夠充分利用數(shù)組中的空間。鏈?zhǔn)疥?duì)列就不需要考慮空間利用的問題躬柬,因?yàn)殒準(zhǔn)疥?duì)列本身就是實(shí)時(shí)申請(qǐng)空間拜轨。因此,這可以算作是鏈?zhǔn)疥?duì)列相比順序隊(duì)列的一個(gè)優(yōu)勢(shì)允青。
這里給出鏈?zhǔn)疥?duì)列入隊(duì)和出隊(duì)的完整 C 語言代碼為:
#include <stdio.h>
#include <stdlib.h>
//鏈表中的節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥?duì)列的函數(shù)
QNode * initQueue(){
//創(chuàng)建一個(gè)頭節(jié)點(diǎn)
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對(duì)頭節(jié)點(diǎn)進(jìn)行初始化
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//使用尾插法向鏈隊(duì)列中添加數(shù)據(jù)元素
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("\n隊(duì)列為空");
return rear;
}
QNode * p=top->next;
printf("出隊(duì)的元素是:%d \n",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
//隊(duì)列的長(zhǎng)度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空橄碾,長(zhǎng)度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空,移動(dòng)指針計(jì)算長(zhǎng)度
pMove = pMove->next;
length++;
}
return length;
}
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊(duì)列為空颠锉!\n");
}
while (pMove!=NULL) {
printf("%d ",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
int main() {
QNode * queue,*top,*rear;
queue=top=rear=initQueue();//創(chuàng)建頭結(jié)點(diǎn)
//向鏈隊(duì)列中添加結(jié)點(diǎn)法牲,使用尾插法添加的同時(shí),隊(duì)尾指針需要指向鏈表的最后一個(gè)元素
for(int i=0;i<10;i++)
{
rear = enQueue(rear, i+1);
}
printQueue(top);
printf("隊(duì)列的長(zhǎng)度為:%d\n",QueueLength(top));
//入隊(duì)完成琼掠,所有數(shù)據(jù)元素開始出隊(duì)列
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
return 0;
}
程序運(yùn)行結(jié)果為:
1 2 3 4 5 6 7 8 9 10
隊(duì)列的長(zhǎng)度為:10
出隊(duì)的元素是:1
出隊(duì)的元素是:2
以上就是本次給大家分享的C語言實(shí)現(xiàn)鏈?zhǔn)疥?duì)列拒垃,如今作為大學(xué)生的我,也開始受網(wǎng)課的折磨了瓷蛙,在家上網(wǎng)課的感覺比在學(xué)校還要累悼瓮。每天都在上課,寫作業(yè)艰猬,所以一直更新文章也比較少横堡。需要了解其他的數(shù)據(jù)結(jié)構(gòu)的知識(shí)的,可以訪問個(gè)人博客,我們一起交流分享肮谔摇命贴!