01.棧
main.c
#include "stack.h"
int main()
{ stack_p S=(stack_p)create_stack(); //1.入棧 printf("入棧數據1:\n"); push_stack(S,1); show_stack(S); printf("入棧數據2:\n"); push_stack(S,2); show_stack(S); printf("入棧數據3:\n"); push_stack(S,3); show_stack(S); printf("入棧數據4:\n"); push_stack(S,4); show_stack(S); printf("入棧數據5:\n"); push_stack(S,5); show_stack(S); //2.出棧 printf("出棧數據1:%d\n",pop_stack(S)); show_stack(S); printf("出棧數據2:%d\n",pop_stack(S)); show_stack(S); //3.銷毀棧 printf("銷毀后數據:\n"); destory(&S); printf("%p\n",S); return 0;
}
stack.c
#include "stack.h"
//1、創建順序棧
stack_p create_stack()
{stack_p S = (stack_p)malloc(sizeof(stack));if(S==NULL){return NULL;}bzero(S,sizeof(stack)); //把申請的所有空間都初始為0S->top = -1; //-1是棧頂位置top的初始值return S;
}
//2、判空
int empty_stack(stack_p S)
{if(S==NULL){return -1;}return S->top==-1;
}
//3、判滿
int full_stack(stack_p S)
{if(S==NULL){return -1;}return S->top==MAX-1;
}
//4、入棧
void push_stack(stack_p S,int value)
{if(S==NULL){return;}if(full_stack(S)){return;}//先加棧頂位置，再將元素壓入棧//先加再壓//S->data[++(S->top)] = value;S->top++;S->data[S->top] = value;
}
//5、出棧
int pop_stack(stack_p S)
{if(S==NULL){return -1;}if(empty_stack(S)){return -2;}return S->data[S->top--];
}
//6、輸出棧中元素
void show_stack(stack_p S)
{if(S==NULL){return;}if(empty_stack(S)){return;}int i;for(i=S->top;i>=0;i--){printf("%d\n",S->data[i]);}
}
//7、銷毀棧
/*void destory(stack_p S)
{if(S==NULL){return;}free(S);
}*/
void destory(stack_p *S)
{if(S==NULL||*S==NULL){return;}free(*S);*S = NULL;
}
//7、銷毀棧
void destory(stack_p *S)
{ if(S==NULL||*S==NULL) { printf("空棧無需銷毀.\n"); return; } while(empty_stack(*S)==0){ pop_stack(*S); } free(*S); *S=NULL;
} stack.h
#ifndef __STACK_H__
#define __STACK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 7
typedef struct
{int data[MAX];int top; //記錄棧頂元素的下標
}stack,*stack_p;
//1、創建順序棧
stack_p create_stack();
//2、判空
int empty_stack(stack_p S);
//3、判滿
int full_stack(stack_p S);
//4、入棧
void push_stack(stack_p S,int value);
//5、出棧
int pop_stack(stack_p S);
//6、輸出棧中元素
void show_stack(stack_p S);
//7、銷毀棧
void destory(stack_p *S);#endif
02.鏈棧
main.c
#include "link.h"
int main()
{node_p S=NULL;printf("入棧第一數:\n");push_stack(&S,1);show_stack(&S);printf("入棧第二數:\n");push_stack(&S,2);show_stack(&S);printf("入棧第三數:\n");push_stack(&S,3);show_stack(&S);printf("入棧第四數:\n");push_stack(&S,4);show_stack(&S);printf("出棧第一數:\n");printf("%d\n",pop_stack(&S));printf("出棧第一數:\n");printf("%d\n",pop_stack(&S));printf("入棧第五數:\n");push_stack(&S,100);show_stack(&S);return 0;
}
links.c
#include "link.h"
node_p create_node(int value)
{node_p new=(node_p)malloc(sizeof(node));if(new==NULL){printf("創建結點失敗.\n");return NULL;}new->next=NULL;new->data=value;return new;
}
int empty_stack(node_p S)
{return S==NULL;
}//入棧操作需要修改主函數中棧頂指針的指向
void push_stack(node_p *S,int value)
{//S是一個二級指針，保存主函數內棧頂指針的地址if(S==NULL){return;}//不用判斷*S,因為如果*S==NULL說明棧中沒有元素node_p new = create_node(value);new->next = *S; //新結點指向原來的棧頂元素*S = new; //讓主函數中的棧頂指針S指向新的棧頂結點
}
//出棧
int pop_stack(node_p *S)
{if(*S==NULL){return -1;}if(empty_stack(*S)){return -2;}int ret=(*S)->data;node_p del = *S; //先保存棧頂結點*S = (*S)->next; //讓棧頂指針向后指一個結點free(del); //釋放棧頂元素return ret;}
//輸出
void show_stack(node_p *S)
{if(S==NULL){printf("入參指針為空,無法操作.\n");return;}node_p p=*S;if(empty_stack(p)){printf("棧為空，沒有值可以輸出.\n");return;}printf("棧元素(從棧頂到棧底):\n");while(p!=NULL){printf("%d->",p->data);p=p->next;}printf("bottom\n");
}links.h
#ifndef __LINK_H__
#define __LINK_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{int data;struct node *next;
}node,*node_p;node_p create_node(int value);
int empty_stack(node_p S);
void push_stack(node_p *S,int value);
int pop_stack(node_p *S);
void show_stack(node_p *S);
#endif
03.循環隊列
main.c
#include "queue.h"
int main()
{queue_p Q=(queue_p)create_que();printf("入隊第一個數字:\n");push_que(Q,1);show(Q);printf("入隊第二個數字:\n");push_que(Q,2);show(Q);printf("入隊第三個數字:\n");push_que(Q,3);show(Q);printf("入隊第四個數字:\n");push_que(Q,4);show(Q);printf("入隊第五個數字:\n");push_que(Q,5);show(Q);printf("出隊第1個數字:\n");pop_que(Q);show(Q);printf("出隊第2個數字:\n");pop_que(Q);show(Q);printf("隊列中元素個數:%d\n",cont_que(Q));printf("銷毀前:");printf("%p\n",Q);destory(&Q);printf("銷毀后:");printf("%p\n",Q);}
queue.c
#include "queue.h"//1.創建循環隊列
queue_p create_que()
{queue_p Q=(queue_p)malloc(sizeof(queue));if(Q==NULL){printf("申請節點失敗.\n");return NULL;}bzero(Q,sizeof(queue));Q->front=4;Q->front=Q->rear;return Q;
}
//2.判空
int empty_queue(queue_p Q)
{if(Q==NULL){printf("入參為空.\n");return -1;}return Q->front==Q->rear?1:0;
}
//3.判滿
int full_queue(queue_p Q)
{if(Q==NULL){printf("入參為空.\n");return -1;}return (Q->rear+1)%MAX==Q->front?1:0;
}
//4.入隊
void push_que(queue_p Q,int value)
{if(Q==NULL){printf("入參為空.\n");return;}if(full_queue(Q)){printf("隊列已滿,無法入隊.\n");return;}Q->data[Q->rear]=value;Q->rear=(Q->rear+1)%MAX;
}
//5.出隊
int pop_que(queue_p Q)
{if(Q==NULL){printf("入參為空.\n");return -1;}if(empty_queue(Q)){printf("隊列為空,無法入隊.\n");return -2;}int ret=Q->data[Q->front];Q->front=(Q->front+1)%MAX;return ret;
}
//6.從對頭開始輸出
void show(queue_p Q)
{if(Q==NULL){printf("入參為空.\n");return;}if(empty_queue(Q)){printf("隊列為空,無法輸出.\n");return;}int i=Q->front;while(i!=Q->rear){printf("%-3d",Q->data[i]);i=(i+1)%MAX;}putchar(10);
}
//7.返回隊列中元素的個數
int cont_que(queue_p Q)
{if(Q==NULL){printf("入參為空.\n");return -1;}return (Q->rear-Q->front+MAX)%MAX;}//8.銷毀隊列
void destory(queue_p *Q)
{if(Q==NULL||*Q==NULL){printf("隊列為空.\n");return;}free(*Q);*Q=NULL;}queue.h
#ifndef __QUEUE_H__
#define __QUEUE_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 8
typedef struct {int data[MAX];int front;int rear;
}queue,*queue_p;queue_p create_que();
int empty_queue(queue_p Q);
int full_queue(queue_p Q);
void push_que(queue_p Q,int value);
int pop_que(queue_p Q);
void destory(queue_p *Q);
void show(queue_p Q);
int cont_que(queue_p Q);#endif
