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)); //把申请的所有空间都初始为0
S->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