[关闭]
@songpfei 2016-05-28T07:30:27.000000Z 字数 2324 阅读 628

数据结构


1. 栈的定义

栈(stack):是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

2. 栈的抽象数据类型

  1. ADT 栈(stack)
  2. DATA
  3. 通线性表,元素具有相同的类型,相邻元素具有前驱和后继关系
  4. Operation
  5. InitStack(*s):初始化操作,建立一个空栈;
  6. DestroyStack(*s):若栈存在,则销毁它;
  7. ClearStack(*s):将栈清空;
  8. StackEmpty(*S):若栈为空,则返回true,否则返回false;
  9. GetTop(*s,*e):若栈存在且非空,则用e返回s栈顶元素;
  10. Push(*s,e):若栈s存在,插入新元素e到栈s中并成为栈顶元素
  11. Pop(*s,*e):删除栈s中栈元素,并用e返回其值;
  12. StackLength(*s):返回栈s的元素个数
  13. end ADT

2.1 栈的顺序存储结构及其实现

  1. #ifndef STACK_H
  2. #define STACK_H
  3. typedef int ElemType;
  4. #define MAX_SIZE 20
  5. typedef struct
  6. {
  7. ElemType data[MAX_SIZE];
  8. int top;/*用于栈顶指针*/
  9. }SqStack;
  10. void InitStack(SqStack*s);
  11. bool Push(SqStack*s,ElemType e);
  12. bool Pop(SqStack*s,ElemType &e);
  13. #endif
  1. #include "stack.h"
  2. /*数组存储栈系列操作*/
  3. /* 栈初始化*/
  4. void InitStack(SqStack* s)
  5. {
  6. s->top = -1;
  7. }
  8. /*入栈*/
  9. bool Push(SqStack*s,ElemType e)
  10. {
  11. if (s->top == MAX_SIZE - 1)/*栈满*/
  12. return false;
  13. s->top++;
  14. s->data[s->top] = e;
  15. return true;
  16. }
  17. /*出栈*/
  18. bool Pop(SqStack*s,ElemType &e)
  19. {
  20. if (s->top < 0)/*栈为空*/
  21. return false;
  22. e = s->data[s->top];
  23. s->top--;
  24. return true;
  25. }

2.2 栈的链式存储结构及实现

  1. #ifndef STACK_H
  2. #define STACK_H
  3. typedef int ElemType;
  4. typedef struct StackNode
  5. {
  6. ElemType data;
  7. struct StackNode* next;
  8. }StackNode,*LinkStackPtr;
  9. typedef struct
  10. {
  11. int count;/*元素个数计数*/
  12. LinkStackPtr top;/*用于栈顶指针*/
  13. }LinkStack;
  14. void InitStack(LinkStack *s);
  15. bool Push(LinkStack*s, ElemType e);
  16. bool Pop(LinkStack*s, ElemType &e);
  17. #endif
  1. #include "stack.h"
  2. #include<cstdlib>
  3. /*数组存储栈系列操作*/
  4. /* 栈初始化*/
  5. void InitStack(LinkStack *s)
  6. {
  7. s->top = NULL;
  8. s->count = 0;
  9. }
  10. /*入栈*/
  11. bool Push(LinkStack*s, ElemType e)
  12. {
  13. LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
  14. if (!temp)/*内存申请失败*/
  15. return false;
  16. temp->data = e;
  17. temp->next = s->top;
  18. s->top = temp;
  19. s->count++;
  20. return true;
  21. }
  22. /*出栈*/
  23. bool Pop(LinkStack*s, ElemType &e)
  24. {
  25. if (s->count < 0)/*栈为空*/
  26. return false;
  27. e = s->top->data;
  28. LinkStackPtr p = s->top;/*取出栈顶*/
  29. s->top = p->next;//更新栈顶指针
  30. free(p);
  31. p = NULL;
  32. s->count--;
  33. return true;
  34. }
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include"stack.h"
  4. int main()
  5. {
  6. LinkStack s;
  7. InitStack(&s);
  8. int e;
  9. for (int i = 0; i < 10; i++)
  10. Push(&s, i);
  11. Pop(&s, e);
  12. printf("%d", e);
  13. }

3. 栈的应用---四则运算表达式

3.1 后缀(逆波兰)表达式求值

eg:中缀表达式:9+(3-1)*3+10/2
对应的后缀表达式:9 3 1 - 3 * + 10 2 / +

后缀表达式求值策略:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

3.2 中缀表达式转后缀表达式

标准四则运算表达式:'9+(3-1)*3+10/2' 叫做中缀表达式
转化为对应的后缀表达式:‘9 3 1 - 3 * + 10 2 / +’

规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级不高于栈顶符号(乘除优先加减),则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式。

参考:《大话数据结构》清华大学出版社,程杰著;
http://www.cnblogs.com/cj723/archive/2011/02/06/1949498.html

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注