日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言數據結構之隊列的定義與實現_C 語言

作者：MT_125 ? 更新時間： 2022-08-26 編程語言

一、隊列的性質

上次我們學習棧，了解到棧儲存釋放數據的方式是：先進后出

而隊列與其相反，隊列是：先進先出，后進后出。

二、隊列的結構

多個鏈表節點 + 頭尾指針 ? （鏈表式隊列）

鏈表節點負責存儲數據；頭節點 負責定位先進的起始數據，方便先出；

尾節點負責記錄尾部數據，方便確定隊列當前狀態。

三、代碼實現

頭文件

這里方便統一調用，將頭尾指針定義成一個結構體 。?

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int Quetype;          //定義隊列的數據類型
 
typedef struct QueNode        //定義數據節點
{
    struct QueNode* Next;
    Quetype data;
}QueNode;
 
typedef struct Quetail        
{                         
    struct QueNode* head;     //定義頭尾指針
    struct QueNode* tail;
}Quetail;
 
void Que_Init(Quetail* pq);                //隊列的初始化
void Que_Destory(Quetail* pq);             //隊列的銷毀
void Que_push(Quetail* pq ,Quetype data);  //插入數據
void Que_pop(Quetail* pq);                 //刪除數據
bool Que_Empty(Quetail* pq);               //判斷隊列是否為空
int Que_size(Quetail* pq);                 //統計隊列長度
int Que_front(Quetail* pq);                //查找隊列的頭部數據

功能函數

1.隊列的初始化：

將頭尾指針置為NULL 方便后續使用。

void Que_Init(Quetail* pq)           //隊列的初始化
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

2.插入數據：

創建鏈表節點 >> 導入數據 >> 頭部指針指向頭節點 >> 尾部指針指向尾節點?

//插入數據
void Que_push(Quetail* pq,Quetype data)
{ 
    assert(pq);
    QueNode* NewNode = (QueNode*)malloc(sizeof(QueNode));//創建節點
    if (NewNode == NULL)
    {
        printf("Que_push->malloc");
        exit(-1);
    }
    NewNode->Next = NULL;          
    NewNode->data = data;
    if (pq->head == NULL)         //判斷是否創建為頭節點
    {
        pq->head = NewNode;       //更新頭指針
    }
    else
    {
        pq->tail->Next = NewNode; //不為頭節點，就正常鏈接在尾節點后
    }
    pq->tail = NewNode;           //更新尾指針
}

3.刪除數據：

記錄頭節點的下一個位置 >> 判斷是否為最后的數據 >> 更新頭指針

細節點：如果隊列中還剩多個節點時，刪除頭節點后，尾指針始終指向尾節點，不需要改動；

但是如果只剩一個數據節點的話，刪除后需要將尾指針置空。

//刪除數據
void Que_pop(Quetail* pq)
{
    assert(pq);                       
    assert(!Que_Empty(pq));         //判斷隊列是否為空
    QueNode* Next = pq->head->Next; //記錄刪除數據的
 
    if (pq->head == pq->tail)       //判斷是否是最后的數據
    {
        free(pq->head);
        pq->tail = NULL;            //更新尾指針
    }
    else
    {
        free(pq->head);             
    }
    pq->head = Next;                //更新頭指針
}

4.判斷列表是否為空：

用bool 作為返回類型

//判斷隊列是否為空
bool Que_Empty(Quetail* pq)
{
    assert(pq);
    return pq->head == NULL;
}

5.查找隊列的頭部數據：

判斷隊列是否為空 >> 返回頭部數據

//查找隊列的頭部數據
Quetype Que_front(Quetail* pq)
{
    assert(pq);
    assert(!Que_Empty(pq));    //判斷隊列是否為空
    return pq->head->data;     //返回頭部數據
}

6. 統計隊列的長度：

就是統計有多少個鏈表節點

int Que_size(Quetail* pq)
{
    assert(pq);
    int size;
    QueNode* pphead = pq->head;
    for (size = 0; pphead; pphead = pphead->Next, size++);
    return size;
}

7.隊列的銷毀：

依次刪除數據 >> 將申請空間釋放

細節點：這里可以進行復用：判斷隊列是否為空 、 刪除數據

void Que_Destory(Quetail* pq)
{
    for (; !Que_Empty(pq); )  //判斷隊列是否為空
    {
        Que_pop(pq);          //刪除數據
    }
}

原文鏈接：https://blog.csdn.net/MT_125/article/details/125592627

欄目分類
最近更新