欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C利用語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊(duì)列

 更新時(shí)間:2021年10月08日 09:04:10   作者:柳兮  
隊(duì)列 (Queue):簡稱隊(duì),是另一種限定性的線性表,它只允許在表的一端插入元素,而在另一端刪除元素。q=(a1, a2, a3, … an),其中a1為隊(duì)頭,an為隊(duì)尾,下面文章小編將為大家詳細(xì)介紹,需要的下伙伴可以參考一下

前言:

隊(duì)列在生活中也比較常見,例如購物排隊(duì)——新來的成員總是加入隊(duì)尾,每次離開的成員總是隊(duì)列頭上的。

隊(duì)列按存儲(chǔ)方式可以分為兩種:順序隊(duì)列和鏈隊(duì)列。

一、鏈隊(duì)列

鏈?zhǔn)疥?duì)列中每個(gè)元素定義成一個(gè)結(jié)點(diǎn),含數(shù)據(jù)域與指針域(指向下一結(jié)點(diǎn)),并設(shè)頭尾指針。用圖表示就是。

二、鏈隊(duì)的表示

前面的鏈?zhǔn)浇Y(jié)構(gòu),總是使用一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)來表示鏈表,但是在這里使用新的存儲(chǔ)結(jié)構(gòu)。定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu),和一個(gè)隊(duì)列結(jié)構(gòu)。兩個(gè)結(jié)構(gòu)嵌套。

//定義節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode
{
    QElemType   data;   /*數(shù)據(jù)域*/
    struct QNode   * next;   /*指針域*/
 }QNode, *QueuePtr;
//定義隊(duì)列結(jié)構(gòu)
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }LinkQueue;

三、鏈隊(duì)的基本操作

1. 鏈隊(duì)的初始化

Status initQueue(LinkQueue *Q)
{ 
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

2. 鏈隊(duì)的銷毀

Status destroyQueue(LinkQueue *Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
   return OK;
}

3. 入隊(duì)

Status enQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    //插入數(shù)據(jù)
    p->data = e;
    p->next = NULL;
    //Q.rear一直指向隊(duì)尾
    Q.rear->next = p;
    Q.rear = p;
    return OK;
 }

4. 出隊(duì)

Status deQueue(LinkQueue *Q, QElemType e)
{
    if(Q.front == Q.rear) return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;   //隊(duì)頭元素p出隊(duì)
    if(Q.rear == p)   //如果隊(duì)中只有一個(gè)元素p, 則p出隊(duì)后成為空隊(duì)
    Q.rear = Q.front;     //給隊(duì)尾指針賦值
    free(p);   //釋放存儲(chǔ)空間
    return OK;
}

四、順序隊(duì)列

用一組連續(xù)的存儲(chǔ)單元依次存放隊(duì)列的元素,并設(shè)兩個(gè)指針front、rear分別指示隊(duì)頭和隊(duì)尾元素的位置。
front:指向?qū)嶋H的隊(duì)頭;rear:指向?qū)嶋H隊(duì)尾的下一位置。
初態(tài)front=rear=0;隊(duì)空:front=rear;隊(duì)滿:rear=M;
入隊(duì)q[rear]=x; rear= rear+1; 出隊(duì):x=q[front];front=front+1;

順序隊(duì)列的表示:

#define MAXQSIZE  100
typedef struct
{
    QElemType *base;
    int  front;   //頭指針指示器 
    int  rear;  //尾指針指示器
} SqQueue;

存在的問題:

隨著入隊(duì)、出隊(duì)操作的進(jìn)行,整個(gè)隊(duì)列會(huì)整體向后移動(dòng),這樣就出現(xiàn)了下圖的現(xiàn)象:隊(duì)尾指針雖然已經(jīng)移到了最后,而隊(duì)列卻未真滿的“假溢出”現(xiàn)象,使得隊(duì)列的空間沒有得到有效的利用

那我們?cè)撊绾谓鉀Q假溢出的問題呢?

有以下兩種方法:

  • 將隊(duì)中元素向隊(duì)頭移動(dòng):當(dāng)移動(dòng)數(shù)據(jù)較多時(shí)將會(huì)影響隊(duì)列的操作速度。
  • 采用循環(huán)隊(duì)列:Q[0]接在Q[MAXQSIZE-1]之后,一個(gè)更有效的方法是將隊(duì)列的數(shù)據(jù)區(qū)Q[0 .. MAXQSIZE-1]看成是首尾相連的環(huán),即將表示隊(duì)首的元素Q[0]與表示隊(duì)尾的元素Q[MAXQSIZE–1]連接起來,形成一個(gè)環(huán)形表,這就成了循環(huán)隊(duì)列。當(dāng)Q.rear=MAXQSIZE-1時(shí)再入隊(duì),令Q.rear=0, 則可以利用已被刪除的元素空間。如下圖。

五、循環(huán)隊(duì)列

在循環(huán)隊(duì)列中,不可以根據(jù)等式front == rear可以判別隊(duì)滿和隊(duì)空。因?yàn)榇藭r(shí)條件是相同的,解決這種問題的方法一般有兩種。

少用(損失)一個(gè)空間,以尾指針加1等于頭指針作為隊(duì)滿的標(biāo)志。因此:當(dāng)front==rear,表示循環(huán)隊(duì)列為空;當(dāng)front ==(rear+1)% MAXLEN,表示循環(huán)隊(duì)列為滿。
在定義結(jié)構(gòu)體時(shí),附設(shè)一個(gè)存儲(chǔ)循環(huán)隊(duì)列中元素個(gè)數(shù)的變量n,當(dāng)n==0時(shí)表示隊(duì)空;當(dāng)n==MAXLEN時(shí)為隊(duì)滿。

循環(huán)隊(duì)列的基本操作:

1. 初始化

Status initQueue (SqQueue *Q)
{
    Q.base=(QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

2. 求隊(duì)列長度

int queueLength(SqQueue *Q)
{
    return (Q.rear - Q.front+MAXQSIZE) % MAXQSIZE;
}

3. 入隊(duì)

Status enQueue (SqQueue *Q, QElemType e)
{
    if((Q.rear+1)%MAXQSIZE == Q.front)  return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}

4. 出隊(duì)

Status deQueue (SqQueue *Q, QElemType e)
{
    if(Q.front == Q.rear)
    return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXQSIZE;
    return OK;
}

到此這篇關(guān)于C利用語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu) 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言實(shí)現(xiàn)簡易三子棋

    C語言實(shí)現(xiàn)簡易三子棋

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡易三子棋,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • C++中std::find函數(shù)介紹和使用場景

    C++中std::find函數(shù)介紹和使用場景

    std::find函數(shù)是一個(gè)非常實(shí)用的通用查找算法,適用于各種場景,本文主要介紹了C++中std::find函數(shù)介紹和使用場景,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-02-02
  • 詳解C++中的析構(gòu)函數(shù)

    詳解C++中的析構(gòu)函數(shù)

    這篇文章主要介紹了C++中的析構(gòu)函數(shù)的相關(guān)知識(shí),文中講解非常詳細(xì),代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-06-06
  • 利用Matlab制作抖音同款含褶皺面料圖

    利用Matlab制作抖音同款含褶皺面料圖

    這篇文章主要介紹了如何利用Matlab制作抖音的同款含褶皺面料圖,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)Matlab有一定幫助,需要的可以參考一下
    2022-03-03
  • 基于字符串移位包含的問題詳解

    基于字符串移位包含的問題詳解

    本篇文章是對(duì)字符串移位包含的問題的解決方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C++的最短路徑的弗洛伊德算法案例講解

    C++的最短路徑的弗洛伊德算法案例講解

    這篇文章主要介紹了C++的最短路徑的弗洛伊德算法案例講解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • C++中spdlog的簡單使用示例

    C++中spdlog的簡單使用示例

    spdlog是一個(gè)開源、跨平臺(tái)、無依賴、只有頭文件的C++11日志庫,所以這篇文章主要來和大家介紹一下一個(gè)簡單的spdlog使用示例,感興趣的小伙伴可以了解一下
    2023-08-08
  • C++ 使用CRC32檢測內(nèi)存映像完整性的實(shí)現(xiàn)步驟

    C++ 使用CRC32檢測內(nèi)存映像完整性的實(shí)現(xiàn)步驟

    當(dāng)我們使用動(dòng)態(tài)補(bǔ)丁的時(shí)候,那么內(nèi)存中同樣不存在校驗(yàn)效果,也就無法抵御對(duì)方動(dòng)態(tài)修改機(jī)器碼了,為了防止解密者直接對(duì)內(nèi)存打補(bǔ)丁,我們需要在硬盤校驗(yàn)的基礎(chǔ)上,增加內(nèi)存校驗(yàn),防止動(dòng)態(tài)補(bǔ)丁的運(yùn)用。
    2021-06-06
  • C++ 中const修飾虛函數(shù)實(shí)例詳解

    C++ 中const修飾虛函數(shù)實(shí)例詳解

    這篇文章主要介紹了C++ 中const修飾虛函數(shù)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • 一文搞懂Codec2解碼組件

    一文搞懂Codec2解碼組件

    這篇文章主要介紹了Codec2解碼組件,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09

最新評(píng)論