陈海明 副教授 信息学院 计算机系 http://EEE.chenhaiming.cn 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系 http://EEE.chenhaiming.cn

数据结构 线性表 栈 队列 顺序表 任意位置 插入和删除 链 表 线性结构 顺序表 顶部插入 顶部删除 入栈 出栈 链 表

栈 出栈 入栈 栈顶（Top）：进行插入、删除操作的一端。动态变化。 栈底（Bottom) 3 2 1

栈 栈的操作特点：先进后出（FILO) 4 3 若进栈顺序为1234，能否得到3142的出栈顺序？ 2 1

栈 栈初始化 基本操作 销毁栈 判栈空 入栈 出栈 取栈顶元素

顺序栈 s->top++; y=s->data[s->top]; s->top--; s->data[++s->top]=x; y=s->data[s->top--]; s->data[s->top]=x; top C top B top A A top top=-1 top=0 top=2

顺序栈 #define MAX 100 //顺序栈的最大容量 typedef struct { int data[MAX]; //栈的存储空间 int top; //栈顶 }SeqStack; SeqStack *Init_SeqStack() //栈初始化 { SeqStack *s; //定义一个指向顺序栈的指针 s=(SeqStack*)malloc(sizeof(SeqStack)); s->top=-1; return s; }

顺序栈 int Empty_SeqStack(SeqStack *s) //判栈空 { if(s->top==-1) return 1; else return 0; } int Push_SeqStack(SeqStack *s,int x) //入栈 { if(s->top==MAX-1) return 1; else{ s->top++; s->data[s->top]=x; return 0; }

顺序栈 int Pop_SeqStack(SeqStack *s, int *y) //出栈 { if(Empty_SeqStack(s)) return 1; else{ *y=s->data[s->top]; s->top--; return 0; }

栈 数制转换问题 栈的应用 表达式求值 递归问题 迷宫问题的求解

顺序栈 N N/8 N%8 45 7 45 5 5 5 0 5 【例题】数制转换问题。将十进制转换成r进制。 算法： 45 7 45 5 5 5 0 5 算法： 步骤1、当N！=0时，将N%r压入栈，接着执行步骤2；若N=0，则将栈的内容依次出栈，算法结束； 步骤2：用N/r代替N。

顺序栈 int main() { int N,r; scanf("%d%d",&N,&r); conversion(N,r); 例题 顺序栈 void conversion(int N,int r) { int s[MAX],top; int x; top=-1; //初始化栈 Ehile(N) { s[++top]=N%r; //入栈 N=N/r; } Ehile(top!=-1) { x=s[top--]; printf("%d", x); void conversion(int N,int r) { SeqStack *s; int x; s=Init_SeqStack(); Ehile(N) { Push_SeqStack(s, N%r); N=N/r; } Ehile(!Empty_SeqStack(s)) { Pop_SeqStack(s,&x); printf("%d", x); int main() { int N,r; scanf("%d%d",&N,&r); conversion(N,r); printf("\n"); return 0; }

链栈 ^ typedef struct node { char data; struct node *next; }LinkStack; top ^ 链栈示意图 头结点 栈底结点 typedef struct node { char data; struct node *next; }LinkStack; 栈顶结点 void Init(LinkStack *s) //栈初始化 { s=(LinkStack*)malloc(sizeof(LinkStack)); s->next=NULL; }

链栈 int Empty_LinkStack(LinkStack *s) //判栈空 { if(s->next==NULL) return 1; else return 0; } void Push(LinkStack *s,char x) //入栈 { LinkStack *p; p=(LinkStack*)malloc(sizeof(LinkStack)); p->data=x; p->next=s->next; s->next=p; }

链栈 int Pop(LinkStack *s,char *x) //出栈 { LinkStack *p; if(s->next==NULL) return 1; else{ p=s->next; *x=p->data; s->next=p->next; free(p); return 0; }

栈链 int GetTop(LinkStack *s,char x) //取栈顶元素 { if(s->next==NULL) return 1; x=s->next->data; return 0; }

链栈 判断输入的表达式中括号是否配对（假设只含有左右圆括号）。 int match(char exp[],int n) { 初始化链栈 { 初始化链栈 Ehile(i<n) { if(exp[i]==‘(’) 入栈; else if(exp[i]==')') { 若栈顶有元素可取 { 若取出的元素不是左括号，则配对失败; 否则，左括号出栈，完成一组括号配对; } 否则 return 1; //取栈顶元素下溢时返回1 i++; if(栈空) return 0; //栈空时返回0 else return 2;

int match(char exp[],int n) { int i=0; char x; LinkStack *st=NULL; Init(st); Ehile(i<n) { if(exp[i]=='(') Push(st, exp[i]); else if(exp[i]==')') { if(GetTop(st,x)==1) if(x!='(') return 0; else Pop(st,&x); } else return 1; //取栈顶元素下溢时返回1 i++; if(Empty_LinkStack(st)==1) return 0; //栈空时返回0 else return 2;

栈 数制转换问题 栈的应用 表达式求值 递归问题 迷宫问题的求解

栈的应用 表达式求值 包含四则运算和括号 10-2*3 (10-2)*3 - # * 结果 * 3 - 2 6 # 4 10

运算优先级   + - * / ( ) # > < =  E E 

运算优先级   + - * / ( ) [ ] { } # > < = E M  M  >