chapter3栈.ppt

1、第三章：栈,3.1 基本概念 3.2 栈的存储结构和操作 3.3 栈的应用,3.1 基本概念,栈（Stack） 是一种特殊的线性表，是操作受限的线性表。 栈的应用： 程序设计、调试和运行等。 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表。 表尾栈顶。 表头栈底。 不含元素的空表称空栈。 特点： 先进后出（FILO）或后进先出（LIFO）。,3.2 栈的存储结构和操作,3.2.1 顺序栈 3.2.2 链栈,3.2.1 顺序栈,1.顺序栈的实现 用一维数组实现 #define Stack_INTSIZE 50 DataType s Stack_INTSIZE; int top;/定

2、义栈顶指针,思考： 栈顶指针top与前面所讲的指针有什么区别？,用结构体实现 #define Stack_INTSIZE 50 /设定栈的最大存储空间 typedef struct DataType sStack_INTSIZE; int top; SeqStack; SeqStack *st；,栈顶指针top,初值为-1。,进栈,A,出栈,栈满,B,C,D,E,F,设数组元素个数为M top= = -1,栈空，此时出栈，则下溢（underflow) top= =M-1,栈满，此时入栈，则上溢（overflow),栈空,2. 顺序栈的操作示意图,判断栈是否为空 int IsEmpty(SeqS

3、tack* st ) return ( st-top= = -1 ) ? 1: 0; / 栈为空返回1，否则返回0 ,3.顺序栈的基本操作,进栈 void Push(SeqStack* st, DataType x) if (st-top= = Stack_INTSIZE-1) printf(n栈满，不能入栈!); else st-top+; /先修改指针，后赋值 st-sst-top=x; ,A,B,出栈 void Pop(SeqStack* st) /*出栈函数，没有返回栈顶元素值，必要时须补上*/ if ( IsEmpty (st) ) printf(n栈空，不能出栈!n); else

4、st-top-; ,读栈顶元素 DataType ReadTop(SeqStack* st)/*读栈顶元素的值*/ DataType x; if ( IsEmpty (st) )/判断是否为空栈 printf(n栈中无元素); return (0); else /取栈顶元素的值 x=st-sst-top; return x ; ,1. 结点定义 struct node DataType data; struct node *next; ; LinkStack *top; /栈顶指针,typedef,LinkStack,3.2.2 链栈,2.链栈操作示意图,p-next=top; top=p;,

5、q= top; top = top-next; free(q);,进栈算法,出栈算法,3.链栈操作算法,进 栈 void Push(DataType x) LinkStack *p; p=(LinkStack *) malloc ( sizeof (LinkStack) ); /分配一个节点空间 p-data=x; p-next=top; top=p; ,出 栈 DataType Pop(LinkStack * top)/出栈，并返回栈顶元素的值 DataType x; if (top)/栈不为空 q= top; x=q-data; top = top-next; free(q); retur

6、n(x); ,3.3 栈的应用,3.3.1 数制转换 3.3.2 表达式求值 3.3.3 过程的嵌套调用 3.3.4 递归,3.3.1 数制转换,中缀表达式 后缀表达式（逆波兰式) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈,例 计算 # 2+4-3*6#（#为表达式开始和结束标记）,3.3.2 表达式求值,中缀表达式 后缀表达式（逆波兰式) a+(b*c+d)/e abc*d+e/+,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,3.3.3 过程的嵌套调用,例 递归的执行情况分析,递归：函数直接或间接调用自身叫递归。 实现：建立递归工作栈。,void write (int n) 1 int i; 2 if ( n!=0) 3 write (n-1); /调用函数本身 4 for(i=1;i=n;+i) 5 printf(“%d,”,n); 6 printf(“n”); 7