二項隊列實現文件c語言,c語言實現一個隊列

本文目錄一覽：

• 1、【數據結構】堆（優先隊列）：二叉堆、d堆、左式堆、斜堆與二項隊列
• 2、c語言實現隊列和棧的方法
• 3、C語言中怎麼實現雙端隊列這個數據結構
• 4、C語言的隊列如何實現和表示

【數據結構】堆（優先隊列）：二叉堆、d堆、左式堆、斜堆與二項隊列

這是數據結構類重新複習筆記的第 五 篇，同專題的其他文章可以移步：

堆 （Heap）又稱為 優先隊列 （priority queue），在隊列的基礎上，堆允許所有隊列中的元素不一定按照 先進先出 （FIFO）的規則進行，而是使得每個元素有一定的優先級，優先級高的先出隊列。

優先隊列至少存在兩個重要的操作：

有幾種簡單而明顯的方法實現優先隊列。

二叉堆 （binary heap）是一種對於優先隊列的實現，可以簡稱為堆

堆是一棵 完全二叉樹 （complete binary tree），即所有節點都必須有左右兩個子節點，除了最後一排元素從左向右填入，直到沒有元素為止。

很顯然，一棵高為h的完全二叉樹有 2^h 到 2^(h+1)-1 個節點，即其高度為 logN 向下取整。

完全二叉樹的好處在於其規律性，可以使用一個數組而不需要鏈表來表示

對於數組中任一位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子後的單元 (2i+1) 上，它的父親則在位置 i/2 向下取整上。

因此，不僅不需要鏈，而且遍歷該樹所需要的操作也極簡單，在大部分計算機上都可能運行得非常快。唯一問題是最大的堆的大小需要事先估計。

使操作可以快速執行的性質是 堆序性質 （heap-order property）：對於每一個節點X，X的父節點中的鍵小於等於X中的鍵，除沒有父節點根節點外。

將待插入的元素首先放置在最後一個位置上，以保證他是一個完全二叉樹，然後將該元素與其父節點（i/2向下取整）比較，如果比其父節點小，就將兩者互換，互換後再和新的父節點比較，這種方式稱為 上濾 （percolate up），得到一個小頂堆（min heap），如果比較的時候是較大的值向上走，就會得到一個大頂堆（max heap）

比如向一個小頂堆中插入元素14的操作：

找出、返回並刪除最小元非常簡單，最小元就是根節點處的元素，將其返回並刪除。接下來是處理這個B。首先拿下最後一個元素X，如果元素X比B的兩個子節點都小，可以直接將X插入到B的位置，如果X比B的兩個子節點中的任意一個大，就不能插入，此時找到兩個子節點中較小的那個放到B處，B轉而移至這個子結點處。重複如上的步驟直到X可以插入B處為止。這個操作成為 下濾 （percolate down）

比如從一個小頂堆中刪除根節點

decreaseKey(p, A) 操作減小在位置p處的元素的值，減少量為A，可以理解為調高了某個元素的優先級。操作破壞了堆的性質，從而需要上濾操作進行堆的調整。

increaseKey(p, A) 操作增加在位置p處的元素的值，增加量為A，可以理解為降低了某個元素的優先級。操作破壞了堆的性質，從而需要下濾操作進行堆的調整。

remove(p) 操作刪除在堆中位置p處的節點，這種操作可以通過連續執行 decreaseKey(p, ∞) 和 deleteMin() 完成，可以理解馬上刪除某個一般優先級的元素

即將一個原始集合構建成二叉堆，這個構造過程即進行N次連續的 insert 操作完成

定理 ：包含 2^(h+1)-1 個節點且高度為h的理想二叉樹（perfect binary tree）的節點的高度和為 2^(h+1)-1-(h+1)

d堆 （d-Heaps）是二叉堆的簡單推廣，它與二叉堆很像，但是每個節點都有d個子節點，所以二叉堆是d為2的d堆。d堆是完全d叉樹。比如下邊的一個3堆。

d堆比二叉堆淺很多，其insert的運行時間改進到 O(logdN) 。但是deleteMin操作比較費時，因為要在d個子節點中找到最小的一個，需要進行d-1次比較。d堆無法進行find操作，而且將兩個堆合二為一是很困難的事情，這個附加操作為merge合併。

注意！ 在尋找節點的父節點、子節點的時候，乘法和除法都有因子d。如果d是一個2的冪，則可以通過使用二進制的 移位 操作計算，這在計算機中是非常省時間的。但是如果d不是一個2的冪，則使用一般的乘除法計算，時間開銷會急劇增加。有證據顯示，實踐中，堆可以勝過二叉堆

這些高級的數據結構很難使用一個數據結構來實現，所以一般都要用到鏈式數據結構，這種結構可能會使得其操作變慢。

零路徑長 （null path length）npl(X)：定義為從一個X節點到其不具有兩個子節點的子節點的最短路徑長，即具有0個或者1個子節點的節點npl=0，npl(null)=-1，任意節點的零路徑長都比其各個子節點中零路徑長最小值多1。

左式堆 （leftist heap）是指對於任意一個節點X，其左子節點的零路徑長都大於等於其右子節點的零路徑長。很顯然，左式堆趨向於加深左路徑。比如下邊的兩個堆，只有左邊的是左式堆，堆的節點標示的是該節點的零路徑長。

左式堆的實現中，需要有四個值：數據、左指針、右指針和零路徑長。

定理 ：在右路徑上有r個節點的左式堆必然至少有 2^r-1 個節點

merge 是左式堆的基本操作， insert 插入可以看成是一個單節點的堆與一個大堆的 merge ， deleteMin 刪除最小值操作可以看成是首先返回、刪除根節點，然後將根節點的左右子樹進行 merge 。所以 merge 是左式堆的基本操作。

假設現在有兩個非空的左式堆H1和H2，merge操作遞歸地進行如下的步驟：

例如如下的兩個堆：

將H2與H1的右子樹（8–17–26）進行merge操作，此時（8–17–26）和H2的merge操作中又需要（8–17–26）和H2的右子堆（7–37–18）進行merge操作……如此遞歸得到如下的堆：

然後根據遞歸的最外層（回到H1和H2的merge的第二步），將上邊合併的堆成為H1的右子堆

此時根節點（3）處出現了左右子堆不符合左式堆的情況，互換左右子堆並更新零路徑長的值

斜堆 （skew heap）是左式堆的自調節形式，實現起來極其簡單。斜堆和左式堆的關係類似於伸展樹和AVL樹之間的關係。斜堆是具有堆序的二叉樹，但是不存在對樹的結構的現限制。不同於左式堆，關於任意結點的零路徑長的任何信息都不保留。斜堆的右路徑在任何時刻都可以任意長，因此，所有操作的最壞情形運行時間均為O(N)。然而，正如伸展樹一樣，可以證明對任意M次連續操作，總的最壞情形運行時間是 O(MlogN)。因此，斜堆每次操作的 攤還開銷 （amortized cost）為O(logN)

斜堆的基本操作也是merge合併，和左式堆的合併相同，但是不需要對不滿足左右子堆的左式堆條件的節點進行左右子堆的交換。斜堆的交換是無條件的，除右路徑上所有節點的最大者不交換它的左右兒子外，都要進行這種交換。

比如將上述的H1和H2進行merge合併操作

首先進行第一步，除了交換左右子樹的操作與左式堆不同，其他的操作都相同

將合併的堆作為H1的右子堆並交換左右子堆，得到合併後的斜堆

二項隊列 （binomial queue）支持merge、insert和deleteMin三種操作，並且每次操作的最壞情形運行時間為O(logN)，插入操作平均花費常數時間。

二項隊列不是一棵堆序的樹，而是堆序的樹的集合，成為 森林 （forest）。堆序樹中的每一棵都是有約束的 二項樹 （binomial tree）。二項樹是每一個高度上至多存在一棵二項樹。高度為0的二項樹是一棵單節點樹，高度為k的二項樹Bk通過將一棵二項樹Bk-1附接到另一棵二項樹Bk-1的根上而構成的。如下圖的二項樹B0、B1、B2、B3和B4。

可以看到二項樹Bk由一個帶有兒子B0，B1，……，Bk-1的根組成。高度為k的二項樹恰好有2^k個節點，而在深度d處的節點數為二項係數Cdk。

我們可以使用二項樹的集合唯一地表示任意大小的優先隊列。以大小為13的隊列為例，13的二進制表示為1101，從而我們可以使用二項樹森林B3、B2、B0表示，即二進制表示的數中，第k位為1表示Bk樹出現，第k位為0表示Bk樹不出現。比如上述的堆H1和堆H2可以表示為如下的兩個二項隊列：

二項隊列額merge合併操作非常簡單，以上邊的二項隊列H1、H2為例。需要將其合併成一個大小為13的隊列，即B3、B2、B0。

首先H2中有一個B0，H1中沒有，所以H2中的B0可以直接作為新的隊列的B0的樹

其次H1和H2中兩個B1的樹可以合併成一個新的B2的樹，只需要將其中根節點較小的堆掛到根節點較大的堆的根節點上。這樣就得到了三棵B2堆，將其中根節點最大的堆直接放到新隊列中成為它的B2堆。

最後將兩個B2堆合併成一個新隊列中的B3堆。

二項隊列的deleteMin很簡單，只需要比較隊列中所有二項堆的根節點，返回和刪除最小的值即可，時間複雜度為O(logN)，然後進行一次merge操作，也可以使用一個單獨的空間每次記錄最小值，這樣就可以以O(1)的時間返回。

森林中樹的實現採用“左子右兄弟”的表示方法，然後二項隊列可以使用一個數組來記錄森林中每個樹的根節點。

例如上邊的合成的二項隊列可以表示成如下的樣子：

STL中，二叉堆是通過 priority_queue 模板類實現的，在頭文件 queue 中，STL實現一個大頂堆而不是小頂堆，其關鍵的成員函數如下：

c語言實現隊列和棧的方法

#define OVERFLOW -1

#define OK 1

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#define N 20

typedef char SElemType;

typedef int Status;typedef struct {

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;#includestdio.h

#includestdlib.hStatus CreatStack(SqStack S){

//創建棧

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}//CreatStackStatus Push(SqStack S,SElemType e){

//插入e為新的棧頂元素

if(S.top-S.base=S.stacksize){//棧滿，追加存儲空間

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit (OVERFLOW);//存儲空間分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}//PushStatus Pop(SqStack S ,SElemType e){

//若棧不空，刪除棧頂元素，並用e返回其值

if(S.top==S.base) return ERROR;

e=*–S.top;

return OK;

}//Pop typedef char QElemType;

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QNodePtr;typedef struct{

QNodePtr front;

QNodePtr rear;

}LinkQueue;Status CreatQueue(LinkQueue Q){

//建立一個空的鏈式棧

Q.front=Q.rear=(QNodePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

Q.front-next=NULL;

return OK;

}Status EnQueue(LinkQueue Q,QElemType e){ QNodePtr p;

p=(QNodePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);

p-data=e;p-next=NULL;

Q.rear-next=p;

Q.rear=p;

return OK;

}Status DeQueue(LinkQueue Q,QElemType e){QNodePtr p;brif(Q.front==Q.rear) return ERROR;brp=Q.front-next; e=p-data;brQ.front-next=p-next;brif(Q.rear==p) Q.rear=Q.front;brfree(p);brreturn OK;br}int stackPalindrom_Test()//判別輸入的字符串是否迴文序列,是則返回1,否則返回0

{

printf(“棧練習，請輸入要判斷的字符串以#作為結束符，不要超過二十個字符\n”);

SqStack S;

CreatStack(S);

char c;

SElemType a;

SElemType b[N];

int count = 0;

fgets( b, N, stdin );

while((b[count])!=’#’)

{

Push(S,b[count]); //進棧

count++;

}

int i = 0;

while(i count)

{

Pop(S,a);

if(a!=b[i])

return ERROR;

i++;

}

return OK;}//stackPalindrom_Test int queuePalindrom_Test()//判別輸入的字符串是否迴文序列,是則返回1,否則返回0

{

printf(“隊列練習，請輸入要判斷的字符串以#作為結束符，不要超過二十個字符\n”);

LinkQueue Q;

CreatQueue(Q); char c;

SElemType a;

SElemType b[N];

int count = 0;

fgets( b, N, stdin );

while((b[count])!=’#’)

{

EnQueue(Q,b[count]);; //入列

count++;

} while(count– 0)

{

DeQueue(Q,a);

if(a!=b[count])

return ERROR;

}

return OK;

}//queuePalindrom_Test Status main(){ if(stackPalindrom_Test()==1)

printf(“是迴文\n”);

else printf(“不是迴文\n”); if(queuePalindrom_Test()==1)

printf(“是迴文\n”);

else printf(“不是迴文\n”);

return OK;

}

C語言中怎麼實現雙端隊列這個數據結構

雙端隊列數據類型

typedef

struct

qnode

{

DataType

data;

struct

qnode

*next;

}LQNode;

typedef

struct

{

LQNode

*front;

LQNode

*rear;

}LQueue;

尾出隊：首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊尾結點

賦給臨時結點。將隊尾結點的前驅指針賦給隊列的隊尾指針，再將隊尾結

點的後繼指針置空。最後返回臨時結點或所需要的數據。

C語言的隊列如何實現和表示

我能想到的有兩種方法（假設隊列元素都是int）

一，用鏈表的方法

struct A

{

int n;

struct A *a;

} *p,*head,*rear;

head=rear=NULL；/*頭指針，尾指針*/

添加元素：p=(struct A*)malloc(sizeof(struct A));……給新元素賦值…..;rear-a=p;rear=p;

當然添加第一個元素的時候要給head賦值。

刪除元素：p=head;head=head-a;free(p);

用的是單向鏈表，當然也可以用雙向鏈表，不過刪除，添加元素的過程要麻煩點。

二，利用數組，當然也可以開闢動態儲存空間

int a[N]，*head,*rear; N就是個常數

head=rear=a;

添加元素：scanf(“%d”,rear-a==N?rear=a:++rear);

刪除元素：head-a==N?head=a:head++;

當然要檢查隊列是否溢出，可以設變量n=0;

每次添加元素n++

每次刪除元素n–

當n0後nN數據溢出