C語言實(shí)現(xiàn)鏈?zhǔn)疥?duì)列

鏈?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 步操作:

  1. 將該數(shù)據(jù)元素用節(jié)點(diǎn)包裹,例如新節(jié)點(diǎn)名稱為 elem捺檬;
  2. 與 rear 指針指向的節(jié)點(diǎn)建立邏輯關(guān)系再层,即執(zhí)行 rear->next=elem;
  3. 最后移動(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 步操作:

  1. 通過 top 指針直接找到隊(duì)頭節(jié)點(diǎn)缰贝,創(chuàng)建一個(gè)新指針 p 指向此即將出隊(duì)的節(jié)點(diǎn)馍悟;
  2. 將 p 節(jié)點(diǎn)(即要出隊(duì)的隊(duì)頭節(jié)點(diǎn))從鏈表中摘除;
  3. 釋放節(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è)人博客,我們一起交流分享肮谔摇命贴!

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市腊满,隨后出現(xiàn)的幾起案子套么,更是在濱河造成了極大的恐慌,老刑警劉巖碳蛋,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件胚泌,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡肃弟,警方通過查閱死者的電腦和手機(jī)玷室,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來笤受,“玉大人穷缤,你說我怎么就攤上這事÷崾蓿” “怎么了津肛?”我有些...
    開封第一講書人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)汗贫。 經(jīng)常有香客問我身坐,道長(zhǎng)秸脱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任部蛇,我火速辦了婚禮摊唇,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘涯鲁。我一直安慰自己巷查,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開白布抹腿。 她就那樣靜靜地躺著岛请,像睡著了一般。 火紅的嫁衣襯著肌膚如雪幢踏。 梳的紋絲不亂的頭發(fā)上髓需,一...
    開封第一講書人閱讀 52,682評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音房蝉,去河邊找鬼。 笑死微渠,一個(gè)胖子當(dāng)著我的面吹牛搭幻,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播逞盆,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼檀蹋,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了云芦?” 一聲冷哼從身側(cè)響起俯逾,我...
    開封第一講書人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎舅逸,沒想到半個(gè)月后桌肴,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡琉历,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年坠七,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片旗笔。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡彪置,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出蝇恶,到底是詐尸還是另有隱情拳魁,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布撮弧,位于F島的核電站潘懊,受9級(jí)特大地震影響姚糊,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜卦尊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一叛拷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧岂却,春花似錦忿薇、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至扫尺,卻和暖如春筋栋,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背正驻。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工弊攘, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人姑曙。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓襟交,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親伤靠。 傳聞我的和親對(duì)象是個(gè)殘疾皇子捣域,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容