数据结构之栈

一 栈 :是一种线性表

 

规定  :先进后出

 

 

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;

}

 

 

 

 

上一篇:数据结构——栈


下一篇:01:判断数正负