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
