程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言使用非循環雙向鏈表實現隊列

C語言使用非循環雙向鏈表實現隊列

編輯:關於C語言

C語言使用非循環雙向鏈表實現隊列


在前面兩篇博客中,我分別使用了靜態數組和動態數組來模擬循環隊列。但是線性表中和隊列最神似的莫過於鏈表了。我在前面也使用了大量的篇幅來講述了鏈表的各種操作。今天我們使用一種比較特殊的鏈表——非循環雙向鏈表來實現隊列。首先這裡的說明的是構建的是普通的隊列,而不是循環隊列。當我們使用數組的時候創建循環隊列是為了節省存儲空間,而來到鏈表中時,每一個節點都是動態申請和釋放的,不會造成空間的浪費,所以就不需要采用循環隊列了。第二,大家在很多書上看到的是使用單鏈表實現隊列,我這裡將會使用帶頭結點尾結點的非循環雙鏈表實現,雖然多維護了兩個節點和指針域,但是在鏈表頭尾進行插入刪除的時候不需要遍歷鏈表了,隊列操作變得非常的方便。真正實現了只在頭尾操作。

核心代碼如下:

(1)初始化隊列

//初始化帶頭結點和尾結點的非循環雙向鏈表
void InitialQueue(Queue **pHead,Queue **pTail){

    *pHead = (Queue *)malloc(sizeof(Queue));
    *pTail = (Queue *)malloc(sizeof(Queue));

    if (*pHead == NULL || *pTail == NULL) {
        printf("%s函數執行,內存分配失敗,初始化雙鏈表失敗\n",__FUNCTION__);
    }else{
        //這個裡面是關鍵,也是判空的重要條件
        (*pHead)->next = NULL;
        (*pTail)->prior = NULL;

        //鏈表為空的時候把頭結點和尾結點連起來
        (*pHead)->prior = *pTail;
        (*pTail)->next = *pHead;

        printf("%s函數執行,帶頭結點和尾節點的雙向非循環鏈表初始化成功\n",__FUNCTION__);
    }
}

(2)入隊,在尾結點插入元素
//入隊,也就是在鏈表的尾部插入節點
void EnQueue(Queue *head,Queue *tail,int x){

    Queue *pInsert;
    pInsert = (Queue *)malloc(sizeof(Queue));
    memset(pInsert, 0, sizeof(Queue));
    pInsert->next = NULL;
    pInsert->prior = NULL;
    pInsert->element = x;

    tail->next->prior = pInsert;
    pInsert->next = tail->next;
    tail->next = pInsert;
    pInsert->prior = tail;
}

(3)出隊,在頭結點處刪除節點
//出隊,在隊列頭部刪除元素
void DeQueue(Queue *head,Queue *tail){

    if (IsEmpty(head,tail)) {
        printf("隊列為空,出隊列失敗\n");
    }else{

        Queue *pFreeNode;
        pFreeNode = head->prior;
        head->prior->prior->next = head;
        head->prior = head->prior->prior;

        free(pFreeNode);
        pFreeNode = NULL;
    }
}
(4)打印所有節點
//打印出從隊列頭部到尾部的所有元素
void PrintQueue(Queue *head,Queue *tail){

    Queue *pMove;
    pMove = head->prior;
    printf("當前隊列中的元素為(從頭部開始):");
    while (pMove != tail) {
        printf("%d ",pMove->element);
        pMove = pMove->prior;
    }
    printf("\n");
}

(5)判斷隊列是否為空
//判斷隊列是否為空,為空返回1,否則返回0
int IsEmpty(Queue *head,Queue *tail){

    if (head->prior == tail) {
        return 1;
    }

    return 0;
}

(6)測試代碼
int main(int argc, const char * argv[]) {

    Queue *pHead;//頭結點
    Queue *pTail;//尾結點

    InitialQueue(&pHead, &pTail);

    EnQueue(pHead, pTail, 2);EnQueue(pHead, pTail, 1);
    EnQueue(pHead, pTail, 9);EnQueue(pHead, pTail, 3);EnQueue(pHead, pTail, 4);
    PrintQueue(pHead, pTail);

    DeQueue(pHead,pTail);DeQueue(pHead,pTail);DeQueue(pHead,pTail);
    PrintQueue(pHead, pTail);

    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved