我在電腦上敲了一遍，又在紙上模擬了一遍
下面記錄在電腦上敲的:文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-626518.html
一、用數(shù)組實(shí)現(xiàn)棧
#include <stdio.h> #include <string.h> #define MaxSize 50 typedef struct{ int data[MaxSize]; int top; }stack; void InitStack(stack & S){ S.top = -1; S.data[0] = 5; memset(S.data,0,sizeof(S.data)); // printf("%x\n%x\n\n\n",S.data,&S.data); // 這倆地址指向了同一個(gè)位置a } bool IsEmpty(stack S){ if(S.top == -1) return 1; return 0; } bool IsFull(stack S){ if(S.top == MaxSize-1) return 1; return 0; } bool Push(stack &S,int x){ if(IsFull(S)) return 0; S.data[++S.top] = x; return 1; } bool Pop(stack &S,int &x){ if(IsEmpty(S)) return 0; x = S.data[S.top--]; return 1; } int main(){ stack sk; InitStack(sk); Push(sk,1); Push(sk,2); Push(sk,3); Push(sk,4); Push(sk,5); int ans; for(int i=0;i<=7;i++){ if(Pop(sk,ans)){ printf("%d\n",ans); } else{ puts("Empty Stack!!!"); } } return 0; }
二、用單鏈表實(shí)現(xiàn)棧
#include <stdio.h> #include <malloc.h> #include <typeinfo> typedef struct SNode{ int data; struct SNode *next; } SNode,*Listack; void InitStack(Listack &S){ // 定義頭節(jié)點(diǎn) S = (Listack )malloc(sizeof(SNode)); S->next = NULL; return ; } bool IsStackEmpty(Listack S){ if(S->next == NULL){ return 1; } return 0; } bool StackPush(Listack &S,int x){ SNode * p = (SNode *)malloc(sizeof(SNode)); p->data = x; p->next = S->next; S->next = p; return 1; } bool StackPop(Listack &S,int &x){ if(IsStackEmpty(S)){ return 0; } SNode * p = S->next; x = p->data; S->next = p->next; free(p); return 1; } int main(){ SNode * sn; InitStack(sn); StackPush(sn,1); StackPush(sn,2); StackPush(sn,3); StackPush(sn,4); StackPush(sn,5); int ans; for(int i = 0;i<=7;i++){ if(StackPop(sn,ans)){ printf("%d\n",ans); } else{ printf("EmptyStack!!!\n"); } } return 0; }
三、用雙鏈表實(shí)現(xiàn)棧
#include <stdio.h> #include <malloc.h> typedef struct _DbNode{ int data; struct _DbNode * next; struct _DbNode * last; }DbNode,*PDNode; typedef struct _LiDbNode{ // 定義這個(gè)結(jié)構(gòu)體只是為了管理收尾兩個(gè)節(jié)點(diǎn)，中間的節(jié)點(diǎn)還是全部由DbNode構(gòu)成的 DbNode * head; DbNode * rear; }LiDbNode,*PDbStack; void InitDbNode(PDbStack &S){ DbNode * p = (DbNode *)malloc(sizeof(DbNode)); S = (LiDbNode *)malloc(sizeof(LiDbNode)); p->last = p->next = NULL; S->head = S->rear = p; } bool DbStackPush(PDbStack &S,int x){ DbNode * p = (DbNode *)malloc(sizeof(DbNode)); p->data = x; p->next = NULL; p->last = S->rear; S->rear->next = p; S->rear = p; return 1; } bool IsDbStackEmpty(PDbStack S){ if(S->head == S->rear){ return 1; } return 0; } bool DbStackPop(PDbStack &S,int &x){ if(IsDbStackEmpty(S)){ return 0; } DbNode * p = S->rear; // 注意這里 S->rear指向的就是尾節(jié)點(diǎn)，而在后續(xù)用單鏈表實(shí)現(xiàn)Queue的時(shí)候，S-front指向的是頭節(jié)點(diǎn)，也就是說(shuō)S->front->next才是指向的節(jié)點(diǎn)，這是一個(gè)小坑，注意!! p->last->next = NULL; S->rear = p->last; x = p->data; free(p); return 1; } int main(){ PDbStack sn; InitDbNode(sn); DbStackPush(sn,1); DbStackPush(sn,2); DbStackPush(sn,3); DbStackPush(sn,4); DbStackPush(sn,5); int ans; for(int i = 0;i<=7;i++){ if(DbStackPop(sn,ans)){ printf("%d\n",ans); } else{ printf("EmptyStack!!!\n"); } } return 0; }
四、用數(shù)組實(shí)現(xiàn)隊(duì)列
#include <stdio.h> #include <string.h> #define MaxSize 50 typedef struct{ int data[MaxSize]; int head,rear; }queue; void InitQueue(queue &q){ memset(q.data,0,sizeof(q.data)); q.head = q.rear = 0; } bool IsEmpty(queue q){ if(q.rear == q.head) return 1; return 0; } bool IsFull(queue q){ if((q.rear + 1) % MaxSize == q.head) return 1; return 0; } bool EnPush(queue &q,int x){ if(IsFull(q)) return 0; q.data[q.rear] = x; // 這里為了區(qū)分隊(duì)列是否滿/空，我們犧牲了一個(gè)存儲(chǔ)單元，使rear永遠(yuǎn)指向最后一個(gè)數(shù)據(jù)的下一位置，這也是不用++q.rear的原因,小坑... q.rear = (q.rear+1) % MaxSize; return 1; } bool DePop(queue &q,int &x){ if(IsEmpty(q)) return 0; x = q.data[q.head]; // head 一直指向最開(kāi)始的數(shù)據(jù)單元 q.head = (q.head + 1) % MaxSize; return 1; } int main(){ queue qe; InitQueue(qe); for(int i = 0;i<=70;i++){ if(!EnPush(qe,i)) printf("%d -- ",i); puts("Full Queue!!!"); } int ans; for(int i=0;i<=70;i++){ if(DePop(qe,ans)){ printf("%d\n",ans); } else{ printf("%d -- ",i); puts("Empty Queue!!!"); } } return 0; }
五、用單鏈表實(shí)現(xiàn)隊(duì)列
#include <stdio.h> #include <malloc.h> typedef struct _QNode{ int data; struct _QNode * next; }QNode,*pQNode; typedef struct _LinkQueue{ QNode* rear; QNode* front; }LinkQueue,*pLinkQueue; void InitQueue(pLinkQueue &Q){ // 初始化隊(duì)列，創(chuàng)建頭節(jié)點(diǎn)，使隊(duì)頭指向頭節(jié)點(diǎn)，隊(duì)尾指向頭節(jié)點(diǎn)// Q = (LinkQueue *)malloc(sizeof(LinkQueue)); QNode *q = (QNode *)malloc(sizeof(QNode)); q->next = NULL; Q->rear = Q->front = q; } bool IsEmpty(pLinkQueue Q){ if(Q->front == Q->rear) return 1; return 0; } bool EnPush(pLinkQueue &Q,int x){ QNode *q = (QNode *)malloc(sizeof(QNode)); q->next = NULL; q->data = x; Q->rear->next = q; Q->rear = q; return 1; } bool DePop(pLinkQueue &Q,int &x){ if(IsEmpty(Q)) return 0; QNode *q = Q->front->next; //要注意這里和前面用雙向鏈表實(shí)現(xiàn)棧的時(shí)候不太一樣，當(dāng)時(shí)S->rear指的是最后一個(gè)節(jié)點(diǎn)，而這里的S->front指的是頭節(jié)點(diǎn)，而不是第一個(gè)節(jié)點(diǎn)，我們需要用S->front->next來(lái)獲得第一個(gè)節(jié)點(diǎn)，切記切記!!! x = q->data; Q->front->next = q->next; if(Q->rear == q) //當(dāng)原隊(duì)列中只有一個(gè)節(jié)點(diǎn)時(shí)，刪除后，讓尾指針重新指向頭結(jié)點(diǎn)!!// Q->rear = Q->front; free(q); return 1; } int main(){ pLinkQueue qe; InitQueue(qe); EnPush(qe,1); EnPush(qe,2); EnPush(qe,3); EnPush(qe,4); EnPush(qe,5); int ans; for(int i=0;i<=7;i++){ if(DePop(qe,ans)){ printf("%d\n",ans); } else{ puts("Empty Queue!!!"); } } return 0; }
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-626518.html
?
到了這里，關(guān)于王道408用數(shù)組，鏈表以及雙向鏈表實(shí)現(xiàn)棧、隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
