C语言数据结构（大话数据结构——笔记2）第四章：栈与队列
生活随笔
收集整理的這篇文章主要介紹了
C语言数据结构（大话数据结构——笔记2）第四章：栈与队列
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
- 第四章：棧與隊(duì)列（115）
- 棧頂與棧底，空棧，后進(jìn)先出 Last in first out（LIFO結(jié)構(gòu)）（117）
- 進(jìn)棧、壓棧、入棧：棧的插入操作；出棧、彈棧：棧的刪除操作（118）
- push、pop，壓棧和彈棧（進(jìn)棧和出棧 ）（119）
- 棧的順序存儲(chǔ)結(jié)構(gòu)：順序棧（數(shù)組實(shí)現(xiàn)）（120）
- 兩棧共享空間（122）
- 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈棧）（125）
- 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——進(jìn)棧push操作：（126）
- 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——出棧pop操作：（127）
- 順序棧和鏈棧的優(yōu)缺點(diǎn)：（128）
- 棧的作用：簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題，劃分了不同關(guān)注層次，使得思考范圍縮小，更加聚焦于我們要解決的問(wèn)題核心。（128）
- 棧的應(yīng)用：遞歸（128）
- 斐波那契數(shù)列實(shí)現(xiàn)（129）
- 傳統(tǒng)迭代方法
- 遞歸算法
- 遞歸函數(shù)的定義（131）
- 遞歸與迭代的區(qū)別（132）
- 棧在遞歸操作中的作用（132）
- 棧的應(yīng)用——四則運(yùn)算表達(dá)式求值（132）
- 后綴（逆波蘭）（reverse polish notation, RPN）表示法（133）
- 后綴表達(dá)式（133）
- 中綴表達(dá)式（標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式）轉(zhuǎn)后綴表達(dá)式（136）
- 隊(duì)列的定義（139）
- 隊(duì)列的抽象數(shù)據(jù)類型（140）
- 循環(huán)隊(duì)列（順序存儲(chǔ)結(jié)構(gòu)）（140）
- 隊(duì)列順序存儲(chǔ)的缺點(diǎn)（140）
- front與rear指針（141）
- 假溢出的概念（142）
- 循環(huán)隊(duì)列定義（142）
- 如何判斷循環(huán)隊(duì)列是空還是滿？（143）
- 通用計(jì)算隊(duì)列長(zhǎng)度公式（144）
- 循環(huán)隊(duì)列順序存儲(chǔ)結(jié)構(gòu)代碼（144）
- 順序存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列缺點(diǎn)：可能會(huì)溢出（145）
- 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（其實(shí)就是線性表的單鏈表修改版，只能尾進(jìn)頭出）（鏈隊(duì)列）（145）
- 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——入隊(duì)操作
- 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——出隊(duì)操作
- （順序存儲(chǔ)結(jié)構(gòu)）循環(huán)隊(duì)列與鏈隊(duì)列的對(duì)比（鏈隊(duì)列每次malloc申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一定的時(shí)間開(kāi)銷）（148）
- 棧與隊(duì)列總結(jié)（149）
- 本章配套代碼
- 順序棧
- 兩棧共享空間
- 鏈棧
- 斐波那契函數(shù)
- 順序隊(duì)列
- 鏈隊(duì)列
第四章：棧與隊(duì)列（115）
棧頂與棧底，空棧，后進(jìn)先出 Last in first out（LIFO結(jié)構(gòu)）（117）
進(jìn)棧、壓棧、入棧：棧的插入操作；出棧、彈棧：棧的刪除操作（118）
push、pop，壓棧和彈棧（進(jìn)棧和出棧 ）（119）
棧的順序存儲(chǔ)結(jié)構(gòu)：順序棧（數(shù)組實(shí)現(xiàn)）（120）
兩棧共享空間（122）
最好是相同的數(shù)據(jù)類型共享（124）
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈棧）（125）
鏈棧不需要頭結(jié)點(diǎn)（創(chuàng)建一個(gè)棧鏈結(jié)構(gòu)，結(jié)構(gòu)中包含指向棧頂top的指針和結(jié)點(diǎn)數(shù)量）
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——進(jìn)棧push操作：（126）
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——出棧pop操作：（127）
順序棧和鏈棧的優(yōu)缺點(diǎn)：（128）
棧的作用：簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題，劃分了不同關(guān)注層次，使得思考范圍縮小，更加聚焦于我們要解決的問(wèn)題核心。（128）
棧的應(yīng)用：遞歸（128）
斐波那契數(shù)列實(shí)現(xiàn)（129）
斐波那契數(shù)列：前面兩項(xiàng)之和，構(gòu)成了后一項(xiàng)
傳統(tǒng)迭代方法
遞歸算法
遞歸函數(shù)的定義（131）
一個(gè)直接調(diào)用自己，或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱為遞歸函數(shù)
遞歸與迭代的區(qū)別（132）
棧在遞歸操作中的作用（132）
棧的應(yīng)用——四則運(yùn)算表達(dá)式求值（132）
后綴（逆波蘭）（reverse polish notation, RPN）表示法（133）
后綴表達(dá)式（133）
中綴表達(dá)式（標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式）轉(zhuǎn)后綴表達(dá)式（136）
隊(duì)列的定義（139）
隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表
先進(jìn)先出（first in first out, FIFO），允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭
隊(duì)列的抽象數(shù)據(jù)類型（140）
循環(huán)隊(duì)列（順序存儲(chǔ)結(jié)構(gòu)）（140）
隊(duì)列順序存儲(chǔ)的缺點(diǎn)（140）
出隊(duì)時(shí)間復(fù)雜度高（O(n)）
front與rear指針（141）
假溢出的概念（142）
不循環(huán)所存在的問(wèn)題：后面滿了，但前面空著，不會(huì)把元素加到前面
循環(huán)隊(duì)列定義（142）
頭尾相接的順序存儲(chǔ)結(jié)構(gòu)
如何判斷循環(huán)隊(duì)列是空還是滿？（143）
假設(shè)隊(duì)列的最大尺寸是QueueSize，則隊(duì)列滿的條件是（rear + 1）% QueueSize == front，%為取模符號(hào)
通用計(jì)算隊(duì)列長(zhǎng)度公式（144）
（rear - front + QueueSize）% QueueSize循環(huán)隊(duì)列順序存儲(chǔ)結(jié)構(gòu)代碼（144）
順序存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列缺點(diǎn)：可能會(huì)溢出（145）
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)（其實(shí)就是線性表的單鏈表修改版，只能尾進(jìn)頭出）（鏈隊(duì)列）（145）
隊(duì)頭指針指向隊(duì)列頭結(jié)點(diǎn)，隊(duì)尾指針指向終端結(jié)點(diǎn)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——入隊(duì)操作
入隊(duì)操作：在鏈表尾部插入結(jié)點(diǎn)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——出隊(duì)操作
（順序存儲(chǔ)結(jié)構(gòu)）循環(huán)隊(duì)列與鏈隊(duì)列的對(duì)比（鏈隊(duì)列每次malloc申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一定的時(shí)間開(kāi)銷）（148）
棧與隊(duì)列總結(jié)（149）
本章配套代碼
順序棧
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */typedef int Status; typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int *//* 順序棧結(jié)構(gòu) */ typedef struct {SElemType data[MAXSIZE];int top; /* 用于棧頂指針 */ }SqStack;Status visit(SElemType c) {printf("%d ",c);return OK; }/* 構(gòu)造一個(gè)空棧S */ Status InitStack(SqStack *S) { /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */S->top=-1;return OK; }/* 把S置為空棧 */ Status ClearStack(SqStack *S) { S->top=-1;return OK; }/* 若棧S為空棧，則返回TRUE，否則返回FALSE */ Status StackEmpty(SqStack S) { if (S.top==-1)return TRUE;elsereturn FALSE; }/* 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 */ int StackLength(SqStack S) { return S.top+1; }/* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ Status GetTop(SqStack S,SElemType *e) {if (S.top==-1)return ERROR;else*e=S.data[S.top];return OK; }/* 插入元素e為新的棧頂元素 */ Status Push(SqStack *S,SElemType e) {if(S->top == MAXSIZE -1) /* 棧滿 */{return ERROR;}S->top++; /* 棧頂指針增加一 */S->data[S->top]=e; /* 將新插入元素賦值給棧頂空間 */return OK; }/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ Status Pop(SqStack *S,SElemType *e) { if(S->top==-1)return ERROR;*e=S->data[S->top]; /* 將要?jiǎng)h除的棧頂元素賦值給e */S->top--; /* 棧頂指針減一 */return OK; }/* 從棧底到棧頂依次對(duì)棧中每個(gè)元素顯示 */ Status StackTraverse(SqStack S) {int i;i=0;while(i<=S.top){visit(S.data[i++]);}printf("\n");return OK; }int main() {int j;SqStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("棧中元素依次為：");StackTraverse(s);Pop(&s,&e);printf("彈出的棧頂元素 e=%d\n",e);printf("棧空否：%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("棧頂元素 e=%d 棧的長(zhǎng)度為%d\n",e,StackLength(s));ClearStack(&s);printf("清空棧后，棧空否：%d(1:空 0:否)\n",StackEmpty(s));return 0; }兩棧共享空間
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */typedef int Status; typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int *//* 兩棧共享空間結(jié)構(gòu) */ typedef struct {SElemType data[MAXSIZE];int top1; /* 棧1棧頂指針 */int top2; /* 棧2棧頂指針 */ }SqDoubleStack;Status visit(SElemType c) {printf("%d ",c);return OK; }/* 構(gòu)造一個(gè)空棧S */ Status InitStack(SqDoubleStack *S) { S->top1=-1;S->top2=MAXSIZE;return OK; }/* 把S置為空棧 */ Status ClearStack(SqDoubleStack *S) { S->top1=-1;S->top2=MAXSIZE;return OK; }/* 若棧S為空棧，則返回TRUE，否則返回FALSE */ Status StackEmpty(SqDoubleStack S) { if (S.top1==-1 && S.top2==MAXSIZE)return TRUE;elsereturn FALSE; }/* 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 */ int StackLength(SqDoubleStack S) { return (S.top1+1)+(MAXSIZE-S.top2); }/* 插入元素e為新的棧頂元素 */ Status Push(SqDoubleStack *S,SElemType e,int stackNumber) {if (S->top1+1==S->top2) /* 棧已滿，不能再push新元素了 */return ERROR; if (stackNumber==1) /* 棧1有元素進(jìn)棧 */S->data[++S->top1]=e; /* 若是棧1則先top1+1后給數(shù)組元素賦值。 */else if (stackNumber==2) /* 棧2有元素進(jìn)棧 */S->data[--S->top2]=e; /* 若是棧2則先top2-1后給數(shù)組元素賦值。 */return OK; }/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber) { if (stackNumber==1) {if (S->top1==-1) return ERROR; /* 說(shuō)明棧1已經(jīng)是空棧，溢出 */*e=S->data[S->top1--]; /* 將棧1的棧頂元素出棧 */}else if (stackNumber==2){ if (S->top2==MAXSIZE) return ERROR; /* 說(shuō)明棧2已經(jīng)是空棧，溢出 */*e=S->data[S->top2++]; /* 將棧2的棧頂元素出棧 */}return OK; }Status StackTraverse(SqDoubleStack S) {int i;i=0;while(i<=S.top1){visit(S.data[i++]);}i=S.top2;while(i<MAXSIZE){visit(S.data[i++]);}printf("\n");return OK; }int main() {int j;SqDoubleStack s;int e;if(InitStack(&s)==OK){for(j=1;j<=5;j++)Push(&s,j,1);for(j=MAXSIZE;j>=MAXSIZE-2;j--)Push(&s,j,2);}printf("棧中元素依次為：");StackTraverse(s);printf("當(dāng)前棧中元素有：%d \n",StackLength(s));Pop(&s,&e,2);printf("彈出的棧頂元素 e=%d\n",e);printf("棧空否：%d(1:空 0:否)\n",StackEmpty(s));for(j=6;j<=MAXSIZE-2;j++)Push(&s,j,1);printf("棧中元素依次為：");StackTraverse(s);printf("棧滿否：%d(1:否 0:滿)\n",Push(&s,100,1));ClearStack(&s);printf("清空棧后，棧空否：%d(1:空 0:否)\n",StackEmpty(s));return 0; }鏈棧
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */typedef int Status; typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int *//* 鏈棧結(jié)構(gòu) */ typedef struct StackNode {SElemType data;struct StackNode *next; }StackNode,*LinkStackPtr;typedef struct {LinkStackPtr top;int count; }LinkStack;Status visit(SElemType c) {printf("%d ",c);return OK; }/* 構(gòu)造一個(gè)空棧S */ Status InitStack(LinkStack *S) { S->top = (LinkStackPtr)malloc(sizeof(StackNode));if(!S->top)return ERROR;S->top=NULL;S->count=0;return OK; }/* 把S置為空棧 */ Status ClearStack(LinkStack *S) { LinkStackPtr p,q;p=S->top;while(p){ q=p;p=p->next;free(q);} S->count=0;return OK; }/* 若棧S為空棧，則返回TRUE，否則返回FALSE */ Status StackEmpty(LinkStack S) { if (S.count==0)return TRUE;elsereturn FALSE; }/* 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 */ int StackLength(LinkStack S) { return S.count; }/* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ Status GetTop(LinkStack S,SElemType *e) {if (S.top==NULL)return ERROR;else*e=S.top->data;return OK; }/* 插入元素e為新的棧頂元素 */ Status Push(LinkStack *S,SElemType e) {LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top; /* 把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼，見(jiàn)圖中① */S->top=s; /* 將新的結(jié)點(diǎn)s賦值給棧頂指針，見(jiàn)圖中② */S->count++;return OK; }/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p;if(StackEmpty(*S))return ERROR;*e=S->top->data;p=S->top; /* 將棧頂結(jié)點(diǎn)賦值給p，見(jiàn)圖中③ */S->top=S->top->next; /* 使得棧頂指針下移一位，指向后一結(jié)點(diǎn)，見(jiàn)圖中④ */free(p); /* 釋放結(jié)點(diǎn)p */ S->count--;return OK; }Status StackTraverse(LinkStack S) {LinkStackPtr p;p=S.top;while(p){visit(p->data);p=p->next;}printf("\n");return OK; }int main() {int j;LinkStack s;int e;if(InitStack(&s)==OK)for(j=1;j<=10;j++)Push(&s,j);printf("棧中元素依次為：");StackTraverse(s);Pop(&s,&e);printf("彈出的棧頂元素 e=%d\n",e);printf("棧空否：%d(1:空 0:否)\n",StackEmpty(s));GetTop(s,&e);printf("棧頂元素 e=%d 棧的長(zhǎng)度為%d\n",e,StackLength(s));ClearStack(&s);printf("清空棧后，棧空否：%d(1:空 0:否)\n",StackEmpty(s));return 0; }斐波那契函數(shù)
#include "stdio.h"int Fbi(int i) /* 斐波那契的遞歸函數(shù) */ {if( i < 2 )return i == 0 ? 0 : 1; return Fbi(i - 1) + Fbi(i - 2); /* 這里Fbi就是函數(shù)自己，等于在調(diào)用自己 */ } int main() {int i;int a[40]; printf("迭代顯示斐波那契數(shù)列：\n");a[0]=0;a[1]=1;printf("%d ",a[0]); printf("%d ",a[1]); for(i = 2;i < 40;i++) { a[i] = a[i-1] + a[i-2]; printf("%d ",a[i]); } printf("\n");printf("遞歸顯示斐波那契數(shù)列：\n");for(i = 0;i < 40;i++) printf("%d ", Fbi(i)); return 0; }順序隊(duì)列
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */typedef int Status; typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int *//* 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) */ typedef struct {QElemType data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置 */ }SqQueue;Status visit(QElemType c) {printf("%d ",c);return OK; }/* 初始化一個(gè)空隊(duì)列Q */ Status InitQueue(SqQueue *Q) {Q->front=0;Q->rear=0;return OK; }/* 將Q清為空隊(duì)列 */ Status ClearQueue(SqQueue *Q) {Q->front=Q->rear=0;return OK; }/* 若隊(duì)列Q為空隊(duì)列,則返回TRUE,否則返回FALSE */ Status QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) /* 隊(duì)列空的標(biāo)志 */return TRUE;elsereturn FALSE; }/* 返回Q的元素個(gè)數(shù)，也就是隊(duì)列的當(dāng)前長(zhǎng)度 */ int QueueLength(SqQueue Q) {return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }/* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */ Status GetHead(SqQueue Q,QElemType *e) {if(Q.front==Q.rear) /* 隊(duì)列空 */return ERROR;*e=Q.data[Q.front];return OK; }/* 若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素 */ Status EnQueue(SqQueue *Q,QElemType e) {if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊(duì)列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊(duì)尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置， *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK; }/* 若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值 */ Status DeQueue(SqQueue *Q,QElemType *e) {if (Q->front == Q->rear) /* 隊(duì)列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊(duì)頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置， *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK; }/* 從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素輸出 */ Status QueueTraverse(SqQueue Q) { int i;i=Q.front;while((i+Q.front)!=Q.rear){visit(Q.data[i]);i=(i+1)%MAXSIZE;}printf("\n");return OK; }int main() {Status j;int i=0,l;QElemType d;SqQueue Q;InitQueue(&Q);printf("初始化隊(duì)列后，隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));printf("請(qǐng)輸入整型隊(duì)列元素(不超過(guò)%d個(gè)),-1為提前結(jié)束符: ",MAXSIZE-1);do{/* scanf("%d",&d); */d=i+100;if(d==-1)break;i++;EnQueue(&Q,d);}while(i<MAXSIZE-1);printf("隊(duì)列長(zhǎng)度為: %d\n",QueueLength(Q));printf("現(xiàn)在隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));printf("連續(xù)%d次由隊(duì)頭刪除元素,隊(duì)尾插入元素:\n",MAXSIZE);for(l=1;l<=MAXSIZE;l++){DeQueue(&Q,&d);printf("刪除的元素是%d,插入的元素:%d \n",d,l+1000);/* scanf("%d",&d); */d=l+1000;EnQueue(&Q,d);}l=QueueLength(Q);printf("現(xiàn)在隊(duì)列中的元素為: \n");QueueTraverse(Q);printf("共向隊(duì)尾插入了%d個(gè)元素\n",i+MAXSIZE);if(l-2>0)printf("現(xiàn)在由隊(duì)頭刪除%d個(gè)元素:\n",l-2);while(QueueLength(Q)>2){DeQueue(&Q,&d);printf("刪除的元素值為%d\n",d);}j=GetHead(Q,&d);if(j)printf("現(xiàn)在隊(duì)頭元素為: %d\n",d);ClearQueue(&Q);printf("清空隊(duì)列后, 隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));return 0; }鏈隊(duì)列
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */typedef int Status; typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */typedef struct QNode /* 結(jié)點(diǎn)結(jié)構(gòu) */ {QElemType data;struct QNode *next; }QNode,*QueuePtr;typedef struct /* 隊(duì)列的鏈表結(jié)構(gòu) */ {QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */ }LinkQueue;Status visit(QElemType c) {printf("%d ",c);return OK; }/* 構(gòu)造一個(gè)空隊(duì)列Q */ Status InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!Q->front)exit(OVERFLOW);Q->front->next=NULL;return OK; }/* 銷毀隊(duì)列Q */ Status DestroyQueue(LinkQueue *Q) {while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}return OK; }/* 將Q清為空隊(duì)列 */ Status ClearQueue(LinkQueue *Q) {QueuePtr p,q;Q->rear=Q->front;p=Q->front->next;Q->front->next=NULL;while(p){q=p;p=p->next;free(q);}return OK; }/* 若Q為空隊(duì)列,則返回TRUE,否則返回FALSE */ Status QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear)return TRUE;elsereturn FALSE; }/* 求隊(duì)列的長(zhǎng)度 */ int QueueLength(LinkQueue Q) { int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p){i++;p=p->next;}return i; }/* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */ Status GetHead(LinkQueue Q,QElemType *e) { QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;*e=p->data;return OK; }/* 插入元素e為Q的新的隊(duì)尾元素 */ Status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr s=(QueuePtr)malloc(sizeof(QNode));if(!s) /* 存儲(chǔ)分配失敗 */exit(OVERFLOW);s->data=e;s->next=NULL;Q->rear->next=s; /* 把擁有元素e的新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼，見(jiàn)圖中① */Q->rear=s; /* 把當(dāng)前的s設(shè)置為隊(duì)尾結(jié)點(diǎn)，rear指向s，見(jiàn)圖中② */return OK; }/* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */ Status DeQueue(LinkQueue *Q,QElemType *e) {QueuePtr p;if(Q->front==Q->rear)return ERROR;p=Q->front->next; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p，見(jiàn)圖中① */*e=p->data; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給e */Q->front->next=p->next;/* 將原隊(duì)頭結(jié)點(diǎn)的后繼p->next賦值給頭結(jié)點(diǎn)后繼，見(jiàn)圖中② */if(Q->rear==p) /* 若隊(duì)頭就是隊(duì)尾，則刪除后將rear指向頭結(jié)點(diǎn)，見(jiàn)圖中③ */Q->rear=Q->front;free(p);return OK; }/* 從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素輸出 */ Status QueueTraverse(LinkQueue Q) {QueuePtr p;p=Q.front->next;while(p){visit(p->data);p=p->next;}printf("\n");return OK; }int main() {int i;QElemType d;LinkQueue q;i=InitQueue(&q);if(i)printf("成功地構(gòu)造了一個(gè)空隊(duì)列!\n");printf("是否空隊(duì)列？%d(1:空 0:否) ",QueueEmpty(q));printf("隊(duì)列的長(zhǎng)度為%d\n",QueueLength(q));EnQueue(&q,-5);EnQueue(&q,5);EnQueue(&q,10);printf("插入3個(gè)元素(-5,5,10)后,隊(duì)列的長(zhǎng)度為%d\n",QueueLength(q));printf("是否空隊(duì)列？%d(1:空 0:否) ",QueueEmpty(q));printf("隊(duì)列的元素依次為：");QueueTraverse(q);i=GetHead(q,&d);if(i==OK)printf("隊(duì)頭元素是：%d\n",d);DeQueue(&q,&d);printf("刪除了隊(duì)頭元素%d\n",d);i=GetHead(q,&d);if(i==OK)printf("新的隊(duì)頭元素是：%d\n",d);ClearQueue(&q);printf("清空隊(duì)列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);DestroyQueue(&q);printf("銷毀隊(duì)列后,q.front=%u q.rear=%u\n",q.front, q.rear);return 0; }總結(jié)
以上是生活随笔為你收集整理的C语言数据结构（大话数据结构——笔记2）第四章：栈与队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： C语言malloc动态分配内存分配失败怎
- 下一篇： C语言数据结构（大话数据结构——笔记3）