PowerPoint Presentation

Transcription

1 第 章 栈与队列 本章主题 : 栈和队列的应用 教学目的 : 掌握栈和队列的应用方法, 理解栈的重要作用 教学重点 : 利用栈实现行编辑, 利用栈实现表达式求值 教学难点 : 利用栈实现表达式求值

2 .1 ADT 栈 ( 定义和运算 ) 1.. 栈的定义 栈 stack 是一种特殊的 ( 有序表 ) 线性表, 插入 或删除栈元素的运算只能在表的一端进行, 称运算 的一端为栈顶, 另一端称为栈底 - 特点 : 后进先出 栈又称为 后进先出 的线性表, 简称 LIFO 表 例 -1[ 系统栈 ] 处理程序运行时的函数调用 D C B A -1 top top top top top 原栈地址 返回地址 局部变量 原栈地址 返回地址 fp 函数 a1 fp 主函数

3 结构 -11 ADT 栈 Structure Stack object: 零个或多个有穷有序表 Funtion: Stack CreateS(max_size); Boolean IsFull(Stack); Boolean IsEmpty(Stack); Stack Add(stack,item); element Delete(stack); End stack #define MaxSize 100 typedef struct { int key; element; element stack[maxsize MaxSize]; int top=-1; Boolean IsEmpty(Stack)::=top<0 Boolean IsFull(Stack)::=top>= )::=top>=maxsize

4 顺序栈的几种状态 ( 最大长度 MaxSize 为 4) top D 2 2 C 2 top C B 1 B top A 0 A 0 A 0 0 top -1 top -1 (a) (b) (c) (d) (e) (a) 当栈中没有数据元素时, 表示为栈空 栈顶元素所对应的下标值 top=-1 (b) 表示在 (a) 基础上执行 Push(S, A ) 后得到这种状态 (c) 又有三个元素 B C D 先后入栈, 此时栈顶元素的下标值 top= 栈已满 (d) 表示在 (c) 状态下, 执行一次 Pop(S,x) 运算得到 (e) 表示在 (d) 状态下, 执行三次 Pop(S,x) 运算得到 此时栈顶下标值 top=-l 又变成栈空状态

5 程序 -1 栈的基本操作 : 判空 满 插入 删除 element stack_empty(int *top) { if(*top== -1)return 1; element stack_full(int *top) { if(*top= =maxsize-1) return 1; void add(int *top, element item) { if(*top>=maxsize-1) 1){ stack_full(); return; stack[++*top ++*top]=item; element delete(int *top) { if(*top=-1) return stack_empty(); return stack[(*top) (*top)--];

6 * 顺序栈的 C 语言描述如下 : #define MaxSize 数组元素的最大个数 typedef struct { ElemType data[maxsize]; int top; STACK; ElemType 为栈中元素的数据类型 data 域 : 为一个一维数组, 用于存储栈中元素 top 域 : 栈顶指针 取值范围为 0~MaxSize-1 top=-1 表示栈空,top=MaxSize, top=maxsize-1 表示栈满

7 * 栈的基本运算 [ 必须掌握 ] 初始化栈 InitStack(S) 设置一个空栈 S 压栈 Push(S,x) 将元素 x 插入栈 S 中, 使 x 成为栈 S 的栈顶元素 出栈 Pop(S,x) 当栈 S 不空时, 由 x 返回栈顶元素, 并从栈中删除栈顶元素 取栈顶元素 GetTop(S,x) 若栈 S 不空, 则由 x 返回栈顶元素 判栈空 Empty(S) 若栈 S 为空栈, 结果为 1,, 否则结果为

8 .1.2 栈的顺序存储结构及其基本运算的实现 栈有两种存储表示方法 : 顺序存储和链式存储 1. 栈的顺序存储结构 栈的顺序存储结构简称为顺序栈顺序栈 通常由一个一维数组和 一个记录栈顶元素位置的变量组成 2. 基本运算在顺序存储结构的实现 初始化栈 InitStack(S) void InitStack(STACK *S) {s=(stack *)malloc(sizeof(stack)); S->top=-1;

9 压栈 Push(S,x) 教材 :add(s,item) int Push(STACK *S,ElemType x) {if(s->top==maxsize-1){ printf("\n Stack is full!"); return 0; S->data[++S->top]=x; return 1; 出栈 Pop(S,x) 教材 :delete (s) int Pop(STACK *S) { int x; if(empty(s)){printf("stack error"); return 0; x=s->data[s->top--]; return x; stack *s; s=(stack *)malloc(sizeof(stack malloc(sizeof(stack)); s->top= >top=-1;

10 取栈顶元素 GetTop(S,x) int GetTop(STACK *S, ElemType *x) { if(empty(s)){ printf("\n Stack is free!"); retrn 0; *x=s->data[s->top]; return *x; 判栈空 Empty(S) int Empty(STACK *S) { return (S->top==-1?1:0); 判栈满 full(s) int Empty(STACK *S) { return (S->top= =maxsize-1?1:0);

11 例题 : 栈的应用 - 递归 采用递归算法求解正整数 n 的阶乘 n! Fibon 斐波那契数 求 n 的阶乘的递归函数算法如下 : long fact(int n) { long f; 1 n=1 fib(n)= 1 n=2 fib(n-1)+fib(n-2) n>2 if(n==0) f=1; else f=n*fact(n-1); return f;

12 进行 fact(4) 调用的系统栈的变化情况 n r n r n r n r n r n r n r n r n r n r 0 r2 1 r2 1 r2 1 r2 2 r2 2 r2 2 r2 2 r2 2 r2 r2 r2 r2 r2 r2 r2 r2 4 r1 4 r1 4 r1 4 r1 4 r1 4 r1 4 r1 4 r1 4 r1 调用 fact(4) 调用 fact() 调用 fact(2) 调用 fact(1) 调用 fact(0) 返回 fact(0) 返回 fact(1) 返回 fact(2) 返回 fact() 返回 fact(4)

13 函数 fact(4) 的递归调用过程的执行流程 n:4 n: n:2 n:1 n:0 (1) (2) () (4) (5) (6) (7) (8) (9) (10) fact(4) f=4*fact(); f=*fact(2); f=2*fact(1); f=1*fact(0); f=1; (20) (19) (18) (17) (16) (15) (14) (1) (12) (11) return f; return f; return f; return f; return f;

14 .2 2 ADT 队列 1.. 队列的定义 队列也是一种运算受限的线性表 在这种线性表上, 插入限定在表的某一端进行, 删除限定在表的另一端进行 允许插入的一端称为队尾, 允许删除的一端称为队头 特点 : 队列中数据元素的入队和出队过程是按照 先进 先出 的原则进行的 因此, 队列又称为 先进先出 的线 性表, 简称 FIFO 表

15 顺序队列 ( MaxSize=5 ) 的几种状态 rear front rear rear D 4 rear rear front C front front 2 2 B rear 1 0 front A 1 0 front A (a) (b) (c) (d) (e) (f) (a) 表示空队列, rear=front=0 (b) 元素 A 入队后, rear=1,front=0 (c)b,c 依次入队后, rear=,front=0 (d)a,b,c 依此出队后, rear=front= (e)d 入队后,rear=4, front= (f)d 出队后,rear=front=

16 2. ADT 队列 structure Queue object: 零个或多个有穷有序表 Funtions: Queue CreateQ(max_size)::= 创建空队列 Boolean IsFullQ(queue,maxsize)::=if Num(queue)== )==max_size) return Ture else return False Queue AddQ(queue,item ::= if(isfullq(queue)) Queue_full Boolean IsEmptyQ(queue)::= if(queue== ==CreateQ(max_size) ) ) return Ture else return False Element DeleteQ(queue)::= if(isemptyq(queue)) return End Queue else delete e and return item of front

17 队列的顺序存储表示 Queue CreateQ(max_size)::= #define MAX_SIZE 100 typedef struct { int key; element; element queue[max_size] int rear=-1; int front=-1; Boolean IsEmptyQ(queue)::=front==rear 顺序队列的数据类型定义 2 #define MaxSize < 队列的最大容量 > typedef struct{ ElemType data[maxsize]; int front,rear; SQUEUE; Boolean IsFullQ(queue,maxsize)::=rear== MAX_SIZE

18 队列基本操作 程序 - 入队 void addq(int *rear, element item) { /*add an item to queue*/ if(*rear== MAX_SIZE-1){ queue_full(); return; 程序 -4 出队 element deleteq(int *front, int rear) {/*remove/*remove an element at the fornt of~*/ if(*front== rear) return queue_empty(); return queue[++*front]; queue[++*rear]=item;

19 循环队列 - 具有五个存储单元 : A rear 2 B A 1 2 B 1 front C 0 C 0 rear D D 4 front 4 front rear 4 front rear 4 front rear 4 (a) (b) (c) (d) (e) (a) 表示空队列, rear= front=0 (b) 元素 A 入队后, rear=1, front=0 (c)b,c,d 依次入队后, rear=4, front=0 (d)a 出队后, front=1,rear=4 (e)b,c,d 出队后, rear= front=4 Addq 实现 :*rear=(*rear+1)%max_size;

20 程序 -5 循环队列的插入 void addq(int front, int *rear,element item) { /*add an item to the queue */ *rear=(*rear+1)%max_size; if(front==*rear){ queue_full(rear); return; queue[*rear]=item; 程序 -6 循环队列的删除 Element deletq(int *front, int rear) { if(*front==rear){ return queue_empty(); *front=(*front+1)% )%MAX_SIZE; return queue[*front];

21 . 迷宫问题 1. 允许移动方向表的声明 : typedef struct{ short int vert; short int horiz; offsets; Offsets move[8]; 2. 栈的存储问题 : #define MAX_STACK_SIZE 100 typedef struct{ short int row; [row-1] [col-1] X [row] [col[ col] 方向 :p7: short int col; short int dir; element; element stack[max_stack_size];

22 程序 -7 最初的迷宫算法 Initialize a stack to the maze s s entrance coordinates to north; While(stack is not empty) { <row,col,dir>=delete from top of stack; While(there are more moves from current position){ <next_row,next_col>=coordinates of next move; dir=direction of move; if((next_row== ==Exit_row)&&(next_col== ==Exit_col)) success; if(maze[next_row][next_col]==0{ ]==0{ mark[next_row][next_col]=1; ]=1; add<row,col,dir row,col,dir> > to the top of the stack; row=next_row next_row; col=next_col next_col; dir=north;

23 程序 -8 迷宫搜索函数 void path(void) { int i,row,col,next_row,next_col,dir, found=false; element position; mark[1][1]=1;top=0; stack[0].row=1;stack[0].col=1;stack[0].dir=1; while(top>-1&&!found){ position=delete(&top delete(&top); row=position.row position.row; col=position.col position.col; dir=position.dir position.dir; while(dir<8&&!found){ next_row=row+move[dir].vert row+move[dir].vert; next_col=col+move[dir].horiz col+move[dir].horiz; if(next_row== found=true; ==EXIT_ROW&& && next_col== else if(!maze[next_row][next_col]&& ]&& ==EXIT_COL)!mark[next_row][next_col]){]){ mark[].. mark[next_row][next_col]=1 ]=1 position.row=row;position.col row;position.col=col Add(&top,position); row=next_row;col next_row;col=next_col;dir=0; else ++dir; If(found){ printf( The path is:\n ); printf( row row col\n ) for(i=0;i<= =0;i<=top;i++) printf( %2d%5d %2d%5d,stack[i].row,stack[i].col); printf( %2d%5d %2d%5d, row,col); printf( %2d%5d %2d%5d,Exit_row,Exit_col); else printf( The maze does t have a path );

24 .4 表达式求值 例 :x=: x=a/b-c+d*e-a*c; 当 a=4,b=c=2,d=e= 运算的优先级 : 符号运算符优先级结合性 ()[ ] ->. 函数调用 数组元素 结构 17 自左向右 自增 自减 16 自左向右 -- ++! ~ - + & * sizeof 自减 自增 逻辑非 补 一元减或加 求地址 求容量 15 自右向左 (type) 强制类型转换 14 自右向左 * / % 乘 1 自左向右 + - 二元加或减 12 自左向右 << >> 移位 11 自左向右 > >= < <= 关系运算 10 自左向右 ==!= 等于 9 自左向右 & 按位与 8 自左向右 ^ 按位异或 7 自左向右 按位或 6 自左向右 && 逻辑非 5 自左向右 逻辑与 4 自左向右?: 条件 自左向右 = += -= /= *= %= <<= >>= &= ^= = 赋值 2 自右向左, 逗号 1 自左向右

25 中缀算术表达式 ( (7-2) ) 求值的动态过程 *(7-2)# *(7-2)# (7-2)# 7-2)# -2)# 2)# )# )# # # 运算数栈 运算符栈 - - ( ( ( ( ( * * * * * * * # # # # # # # # # # (a) (b) (c) (d) (e) (f) (g) (h) (i) (j)

26 程序 -9 后缀表达式的求值函数 int eval(void) { precedence token; char symbol; int op1,op2; int n=0; int top=-1; token=get_token(&symbol,&n); while(token==operand) add(&top,symbol- 0 ); else { op2=delete(&top); op1=delete(&top); switch(token) { case plus: add(&top,op1+op2); break; case minus:add(&top,op1-op2);break; case times : add(&top,op1*op2); break; case minus:devide(&top,op1/op2);break; token=get_token(&symbol,&n); return delete(&top); /*return result */ 程序 -10 从输入字符串中取出一个 标记符号的函数 Procedence get_token(char*symbol,int *n) *symbol=expr[(*n)++]; switch(*symbol){ case ( :return lparen; case ) : return rparen; case + :return plus; case - :return minus; case / : return devide; case * :return times; case : return eos; default :return operand;

27 程序 -11 中缀表达式转换后缀表达式函数 void postfix(void) { char symbol; precedence token; int n=0; int top=0; stack[0]=eos; for(token=get_token(&symbol,&n); token!=eos; token=get_token(&symbol,&n)){ if(token==operand) printf( %c,symbol); else if(token==rparen){ while(stack[top]!=lparen) print_token(delete(%top)); delete(&top); else { while(isp[stack[top]>=icp[token] print_token(delete(%top)); add(&top); while((token=delete(&top))!=eos) printf_token(token); printf( \n );

28 中缀表达式转换为等价的后缀表达式 中缀表达式 等价后缀表达式 0./(5 (5 2+1) / (4+) (x+y)/(1-x) x) 2 x y x-/ x (25+x) (a (a+b)+b) (a+b)+b) 25 x+a a b+ b+ b

29 .5 多栈和多队列 假定 n 个栈共用一个数组, 可将可用空间, 分成 n 段. 相关声明 : #define MEMORY_SIZE 100 #define MAX_STACKS 10 Element memory[memory_size]; Int top[maz_stacks] Int boundary[max_stacks]; Int n; 数组分割代码 : Top[0]=boundary[0]=-1; For(i=1;i<n;i++) top[i]=boundary[i]=(memory_size/n)*i; Bondary[n]=MEMORY_SIZE-1;

30 .5 多栈和多队列 程序 -12 向栈 stack_no 中插入 item void add(int i, element item) { if (top[i]==boundary[i+1]) stack_full(i); memory[++top[i]]=item; 程序 -1 从栈 stack_no 中删除元素 void delete(int i) { if (top[i]==boundary[i]) return stack_empty(i); return memory[top[i]--];

31 P67 P75 5 迷宫项目程序 ( 选做 ) P81 1,7 习题