一 栈 :是一种线性表
规定 :先进后出
1.顺序栈
typedef struct
{
//栈空间
DATAYPTE data[MAX];
int top;//记录栈顶元素位置
}SeqStack;
2.创建一个空栈
SeqStack *create_empty_stack()
{
....
s->top = 0;
}
3.判栈是否满
int is_full_stack(SeqStack *s)
{
return s->top == MAX ? 1 : 0;
}
4.判断是否空
int is_empty_stack(SeqStack *s)
{
return s->top == 0 ? 1 : 0;
}
5.进栈
int push_stack(SeqStack *s,DATAYPTE data)
{
判断是否满
s->data[s->top] = data;
s->top ++;
}
6.出栈
DATAYPTE pop_stack(SeqStack *s);
测试代码:
int main()
{
int i = 1;
SeqStack *s = create_empty_stack();
while(!is_full_stack(s))
{
push_stack(s,i ++);
}
while(!is_empty_stack(s))
{
printf("%d ",pop_stack(s));
}
printf("\n");
return 0;
}
二 链式栈
1.数据结构
<1>栈中节点的类型
typedef struct node
{
DATAYPTE data;
struct node *next;
}LinkNode;
<2>栈头节点的类型
typedef struct
{
//记录栈顶元素位置
LinkNode *top;
//栈中元素的个数
int n;
}LinkStack;
2.操作
<1>创建一个空栈
LinkStack *create_empty_stack()
{
//分配栈头节点
//初始化top和n的值
//返回栈头节点的地址
}
<2>栈空
int is_empty_stack(LinkStack *s)
{
return s->top == NULL ? 1 : 0;
}
<3>获得栈顶元素值 (返回其值)
DATAYPTE get_top_data(LinkStack *s);
<4>进栈
int push_linkstack(LinkStack *s,DATAYPTE data);
<5>出栈
DATAYPTE pop_linkstack(LinkStack *s);
顺序栈
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef int DATATYPE;
typedef struct
{
DATATYPE data[MAX];//栈空间
int top;//记录栈顶元素的位置
}SeqStack;
SeqStack *create_empty_stack()
{
SeqStack *s;
s = (SeqStack *)malloc(sizeof(SeqStack));
s->top = 0;
return s;
}
int is_empty_stack(SeqStack *s)
{
return s->top == 0 ? 1 : 0;
}
int is_full_stack(SeqStack *s)
{
return s->top == MAX ? 1 : 0;
}
int push_stack(SeqStack *s,DATATYPE data)
{
if(is_full_stack(s))
{
printf("The stack is full!\n");
return -1;
}
s->data[s->top] = data;
s->top ++;
return 0;
}
DATATYPE pop_stack(SeqStack *s)
{
if(is_empty_stack(s))
{
printf("The stack is empty!\n");
return -1;
}
s->top --;
return s->data[s->top];
}
int main(int argc, const char *argv[])
{
int i = 0;
SeqStack *s = create_empty_stack();
while(!is_full_stack(s))
{
push_stack(s,++i);
}
while(!is_empty_stack(s))
{
printf("%d ",pop_stack(s));
}
printf("\n");
return 0;
}
链栈
#ifndef _HEAD_H_
#define _HEAD_H_
typedef int DATATYPE;
//链表节点的类型
typedef struct node
{
DATATYPE data;
struct node *next;
}LinkNode;
//栈头的类型
typedef struct
{
LinkNode *top;//记录栈顶元素的位置
int n;//栈中元素的个数
}LinkStack;
extern LinkStack *create_empty_linkstack();
extern int is_empty_linkstack(LinkStack *s);
extern DATATYPE get_top_linkstack(LinkStack *s);
extern int push_linkstack(LinkStack *s,DATATYPE data);
extern DATATYPE pop_linkstack(LinkStack *s);
#endif
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
int main(int argc, const char *argv[])
{
int i = 0;
LinkStack *s = create_empty_linkstack();
for(i = 1;i <= 10;i ++)
{
push_linkstack(s,i);
}
printf("stack top data : %d\n",get_top_linkstack(s));
while(!is_empty_linkstack(s))
{
printf("%d ",pop_linkstack(s));
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
LinkStack *create_empty_linkstack()
{
LinkStack *s;
s = (LinkStack *)malloc(sizeof(LinkStack));
s->top = NULL;
s->n = 0;
return s;
}
int is_empty_linkstack(LinkStack *s)
{
return s->top == NULL ? 1 : 0;
}
DATATYPE get_top_linkstack(LinkStack *s)
{
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
return s->top->data;
}
int push_linkstack(LinkStack *s,DATATYPE data)
{
LinkNode *temp;
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = data;
temp->next = s->top;
s->top = temp;
s->n ++;
return 0;
}
DATATYPE pop_linkstack(LinkStack *s)
{
DATATYPE data;
LinkNode *temp;
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
temp = s->top;
s->top = temp->next;
data = temp->data;
free(temp);
return data;
}
计算器
二 表达式计算
//1+3*5-4
char buf[1024] = "1+3*4-5";
第一步:
创建两个栈 operand_stack,operator_stack
第二 :
扫描表达式
操作数入栈的规则:直接入栈
push_stack(operator_stack,*p - '0');
运算符入栈的规则:
1.栈为空
2.当前运算符level > 栈顶运算符 level
提示:
int get_level(char operator)
{
switch(operator)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
defalut:
printf("Invalid operator : %c.\n",operator);
return -1;
}
}
注意:
1.如果不满足运算符入栈的条件,就计算，一直到满足入栈条件为止
//计算的函数
int compute(LinkStack *opd_s,LinkStack *opt_s)
{
int data,data1,data2;
switch(pop_stack(opts))
{
case '+':
data2 = pop_stack(opd_s);
data1 = pop_stack(opd_s);
data = data1 + data2;
push_stack(data,opd_s);
break;
.....
}
}
2.扫描结束的时候，需要判断运算符的栈是否为空
不为空则计算
最后的结果放在操作数的栈
#ifndef _HEAD_H_
#define _HEAD_H_
typedef int DATATYPE;
//链表节点的类型
typedef struct node
{
DATATYPE data;
struct node *next;
}LinkNode;
//栈头的类型
typedef struct
{
LinkNode *top;//记录栈顶元素的位置
int n;//栈中元素的个数
}LinkStack;
extern LinkStack *create_empty_linkstack();
extern int is_empty_linkstack(LinkStack *s);
extern DATATYPE get_top_linkstack(LinkStack *s);
extern int push_linkstack(LinkStack *s,DATATYPE data);
extern DATATYPE pop_linkstack(LinkStack *s);
#endif
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
int get_operator_level(int operator)
{
switch(operator)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
printf("Invaild operator : %c\n",operator);
return -1;
}
}
int calc(LinkStack *opd_stack,LinkStack *opt_stack)
{
int value;
int data1,data2;
switch(pop_linkstack(opt_stack))
{
case '+':
data2 = pop_linkstack(opd_stack);
data1 = pop_linkstack(opd_stack);
value = data1 + data2;
push_linkstack(opd_stack,value);
break;
case '-':
data2 = pop_linkstack(opd_stack);
data1 = pop_linkstack(opd_stack);
value = data1 - data2;
push_linkstack(opd_stack,value);
break;
case '*':
data2 = pop_linkstack(opd_stack);
data1 = pop_linkstack(opd_stack);
value = data1 * data2;
push_linkstack(opd_stack,value);
break;
case '/':
data2 = pop_linkstack(opd_stack);
data1 = pop_linkstack(opd_stack);
value = data1 / data2;
push_linkstack(opd_stack,value);
break;
}
return 0;
}
int deal_with_operator(LinkStack *opd_stack,LinkStack *opt_stack,int operator)
{
int current_level = get_operator_level(operator);
//运算符入栈条件:
//栈为空或当前运算符优先级 > 栈顶运算符的优先级
//处理不能入栈的情况
while(!is_empty_linkstack(opt_stack) && current_level <=\
get_operator_level( get_top_linkstack(opt_stack) ) )
{
calc(opd_stack,opt_stack);
}
//运算符可以进栈
push_linkstack(opt_stack,operator);
return 0;
}
int calc_express(char *string)
{
char *p;
LinkStack *opd_stack = create_empty_linkstack();
LinkStack *opt_stack = create_empty_linkstack();
//1+3*4-5
for(p = string; *p != '\0';p ++)
{
if(*p >= '0' && *p <= '9')
{
push_linkstack(opd_stack,*p - '0');
}else{
deal_with_operator(opd_stack,opt_stack,*p);
}
}
while(!is_empty_linkstack(opt_stack))
{
calc(opd_stack,opt_stack);
}
return pop_linkstack(opd_stack);
}
int main(int argc, const char *argv[])
{
int value;
char buf[1024];
printf("Input express : ");
//1+3*4-5
scanf("%s",buf);
value = calc_express(buf);
printf("%s = %d\n",buf,value);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
LinkStack *create_empty_linkstack()
{
LinkStack *s;
s = (LinkStack *)malloc(sizeof(LinkStack));
s->top = NULL;
s->n = 0;
return s;
}
int is_empty_linkstack(LinkStack *s)
{
return s->top == NULL ? 1 : 0;
}
DATATYPE get_top_linkstack(LinkStack *s)
{
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
return s->top->data;
}
int push_linkstack(LinkStack *s,DATATYPE data)
{
LinkNode *temp;
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = data;
temp->next = s->top;
s->top = temp;
s->n ++;
return 0;
}
DATATYPE pop_linkstack(LinkStack *s)
{
DATATYPE data;
LinkNode *temp;
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
temp = s->top;
s->top = temp->next;
data = temp->data;
free(temp);
s->n --;
return data;
}
球钟问题
#ifndef _HEAD_H_
#define _HEAD_H_
typedef int DATATYPE;
//链表节点的类型
typedef struct node
{
DATATYPE data;
struct node *next;
}LinkNode;
//栈头的类型
typedef struct
{
LinkNode *top;//记录栈顶元素的位置
int n;//栈中元素的个数
}LinkStack;
extern LinkStack *create_empty_linkstack();
extern int is_empty_linkstack(LinkStack *s);
extern DATATYPE get_top_linkstack(LinkStack *s);
extern int push_linkstack(LinkStack *s,DATATYPE data);
extern DATATYPE pop_linkstack(LinkStack *s);
///////////////////////////////////////////////////////////////////
typedef struct
{
LinkNode *front;
LinkNode *rear;
}LinkQueue;
extern LinkQueue *create_linkqueue();
extern int is_empty_linkqueue(LinkQueue *q);
extern int enter_linkqueue(LinkQueue *q,DATATYPE data);
extern DATATYPE delete_linkqueue(LinkQueue *q);
#endif
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
#define MN 4
#define FN 11
#define HN 11
int is_true_ballqueue(LinkQueue *q)
{
int i = 1;
LinkNode *p = q->front->next;
for(i = 1;i <= 27;i ++)
{
if(p->data != i )
return 0;
p = p->next;
}
return 1;
}
int answer_balltime(LinkQueue *q,LinkStack *ms,LinkStack *fs,LinkStack *hs)
{
int ball;
int count = 0;
while(1)
{
ball = delete_linkqueue(q);
if(ms->n != MN)
{
push_linkstack(ms,ball);
continue;
}
//清空分钟指示器
while(!is_empty_linkstack(ms))
{
enter_linkqueue(q,pop_linkstack(ms));
}
if(fs->n != FN)
{
push_linkstack(fs,ball);
continue;
}
//清空五分钟指示器
while(!is_empty_linkstack(fs))
{
enter_linkqueue(q,pop_linkstack(fs));
}
if(hs->n != FN)
{
push_linkstack(hs,ball);
continue;
}
//清空小时指示器
while(!is_empty_linkstack(hs))
{
enter_linkqueue(q,pop_linkstack(hs));
}
enter_linkqueue(q,ball);
count ++;
if(is_true_ballqueue(q))
break;
}
return count / 2;
}
int main(int argc, const char *argv[])
{
int ball;
int day;
LinkQueue *q = create_linkqueue();
LinkStack *mstack = create_empty_linkstack();
LinkStack *fstack = create_empty_linkstack();
LinkStack *hstack = create_empty_linkstack();
for(ball = 1;ball <= 27;ball++)
{
enter_linkqueue(q,ball);
}
day = answer_balltime(q,mstack,fstack,hstack);
printf("ball time day:%d\n",day);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
LinkQueue *create_linkqueue()
{
LinkNode *head;
LinkQueue *q;
head = (LinkNode *)malloc(sizeof(LinkNode));
head->next = NULL;
q = (LinkQueue *)malloc(sizeof(LinkQueue));
q->front = q->rear = head;
return q;
}
int is_empty_linkqueue(LinkQueue *q)
{
return q->front == q->rear ? 1 : 0;
}
int enter_linkqueue(LinkQueue *q,DATATYPE data)
{
LinkNode *temp;
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = data;
temp->next = NULL;
//让链表链接
q->rear->next = temp;
//更新rear到新的尾部节点
q->rear = temp;
return 0;
}
DATATYPE delete_linkqueue(LinkQueue *q)
{
LinkNode *temp;
if(is_empty_linkqueue(q))
{
printf("The LinkQueue is empty!\n");
return -1;
}
temp = q->front;
q->front = temp->next;
free(temp);
return q->front->data;
}
#include <stdio.h>
#include <stdlib.h>
#include "head.h"
LinkStack *create_empty_linkstack()
{
LinkStack *s;
s = (LinkStack *)malloc(sizeof(LinkStack));
s->top = NULL;
s->n = 0;
return s;
}
int is_empty_linkstack(LinkStack *s)
{
return s->top == NULL ? 1 : 0;
}
DATATYPE get_top_linkstack(LinkStack *s)
{
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
return s->top->data;
}
int push_linkstack(LinkStack *s,DATATYPE data)
{
LinkNode *temp;
temp = (LinkNode *)malloc(sizeof(LinkNode));
temp->data = data;
temp->next = s->top;
s->top = temp;
s->n ++;
return 0;
}
DATATYPE pop_linkstack(LinkStack *s)
{
DATATYPE data;
LinkNode *temp;
if(is_empty_linkstack(s))
{
printf("The LinkStack is empty!\n");
return -1;
}
temp = s->top;
s->top = temp->next;
data = temp->data;
free(temp);
s->n --;
return data;
}