第三章栈和队列 栈和队列的基本操 作是线性表操作的子集 是限定性(操作受限制) 的数据结构。 3.1栈 据>定义:是限定仅在表尾进行插入或删除操作 物的线性表。(后进先出线性表LIFO) 栈底指针(base):是线性表的基址; 栈顶指针(op:指向线性表最后一个元素的后面 当top=base时,为空栈 基本操作 InitStack(&S), Destroy Stack(&S), StackEmpty (s), ClearStack(&s), GetTop(s, &e), StackLength(S) 2Push(&S,e:完成在表尾插入一个元素e Pop(&S,&e):完成在表尾删除一个元素
1 栈和队列的基本操 作是线性表操作的子集， 是限定性（操作受限制） 的数据结构。 第三章 栈和队列 数 据 结 构 之 栈 和 队 列 2 3. 1 栈 ¾ 定义：是限定仅在表尾进行插入或删除操作 的线性表。(后进先出线性表LIFO) ¾ 栈底指针(base) :是线性表的基址； ¾ 栈顶指针(top):指向线性表最后一个元素的后面。 ¾ 当top=base 时，为空栈。 ¾ 基本操作： InitStack(&S), DestroyStack(&S), StackEmpty(S) , ClearStack(&S), GetTop(S ,&e), StackLength(S) , Push(&S, e): 完成在表尾插入一个元素e. Pop(&S,&e): 完成在表尾删除一个元素
栈的表示和实现 据结构 顺序栈:是利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据元素;栈满 之后,可再追加栈空间即为动态栈。 顺序栈的结构类型定义: typedef int SElem Type; 栈 typedef struct SElemType*base;/栈底指针*/ SElemType *top; 栈顶指针 int stacksize;/栈空间大小*/ iSqStack 基本算法描述 建立能存放50个栈元素的空栈 w #define STACK INIT SIZE 50 *#define STACKINCREMENT 10 Status InitStack Sq(stack &S) S base=(SET")malloc(STACK INIT SIZE sizeof(SET)); /为栈分配空间 if(s base=NULL) 栈和队列 exit(oVErFLoW);/存储分配失败* Stop=S base S. stacksize= STACK INIT SIZE; return OK; 3
2 数 据 结 构 之 栈 和 队 列 3 ¾ 栈的表示和实现 ¾ 顺序栈：是利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据元素；栈满 之后，可再追加栈空间即为动态栈。 ¾ 顺序栈的结构类型定义： typedef int SElemType; typedef struct{ SElemType *base; /* 栈底指针 */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 栈空间大小 */ }SqStack ; 数 据 结 构 之 栈 和 队 列 4 ¾ 基本算法描述 ¾建立能存放50个栈元素的空栈 #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 Status InitStack_Sq(Stack &S){ S.base=(SET*)malloc(STACK_INIT_SIZE *sizeof(SET)); /*为栈分配空间*/ if(S.base==NULL) exit(OVERFLOW); /*存储分配失败*/ S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; }
出栈操作算法 *t void pop(Sqstack S, SElemType e) 据结构 if(s top==Sbase return ERROR: top eise 栈和队列 s to top base 出栈操作 return OK 压栈操作算法 void Push(SqStack S, SElemType e) st if(s top-s base>=S. stacksize; )i 据 N S base=(SET*)realloc(S, base, (S stacksize-+STACKINCREMEN 构T) sizeof(sET);/为栈重新分配空间 if(l S base exit(OVERFLOW); Stop=S base+S.stacksize; S. stacksize+=STACKINCREMENT top 栈和队列 S S top++; 3 return OK; ase 压栈操作
3 数 据 结 构 之 栈 和 队 列 5 ¾出栈操作算法 void pop(Sqstack s, SElemType e) { if(s.top= = s.base) return ERROR; else{ s.top--; e= *s.top; } return OK; } 出栈操作 top A B Y top A B base base Y 数 据 结 构 之 栈 和 队 列 6 ¾压栈操作算法 void Push(SqStack s, SElemType e) if(s.top-s.base>= S.stacksize;) { S.base=(SET*)realloc(S,base,(S.stacksize+STACKINCREMEN T) *sizeof(SET)); /*为栈重新分配空间*/ if(！S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top=e; S.top++;} return OK; } top A B 压栈操作 top A B e base base
栈的销毁 void Destroy Stack_Sq(Stack &S) 结 if (S base) free(S base); S base=NULL; S top=NULL S stacks 栈的清除 5 void Clear Stack_ Sq(Stack &s) Stop=S base 判断栈是否为空栈 据 Status Stack Empty Sq(Stack S) 构 if(S. top-==S base) return TRUE else return false 获得栈的实际长度 队 int StackLength Sq(stack S) n(abs(s top-S base)
4 数 据 结 构 之 栈 和 队 列 7 ¾栈的销毁 void DestroyStack_Sq(Stack &S){ if (S.base) free(S.base); S.base=NULL;S.top=NULL; S.stacksize=0; } ¾栈的清除 void ClearStack_Sq(Stack &S){ S.top = S.base ; } 数 据 结 构 之 栈 和 队 列 8 ¾判断栈是否为空栈 Status StackEmpty_Sq(Stack S){ if(S.top==S.base) return TRUE; else return FALSE; } ¾获得栈的实际长度 int StackLength_Sq(Stack S){ return(abs(S.top-S.base)); }
多个栈共享邻接空间 结 地址 中间可用空间 两个栈共享一空间 3.3栈与递归 >递归函数:一个直接调用自己或通 过一系列的调用语句间接地调用自 己的函数 调用函数前,系统需先完成三件事: 将所有的实在参数、返回地址等信息传 递给被调用函数保存; 队 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口
5 数 据 结 构 之 栈 和 队 列 9 ¾ 多个栈共享邻接空间 两个栈共享一空间 : : : : : : top1 top2 1 m 中间可用空间 栈1 栈2 地址 Base1 Base 2 …… 数 据 结 构 之 栈 和 队 列 10 3. 3 栈 与 递归 ¾ 递归函数：一个直接调用自己或通 过一系列的调用语句间接地调用自 己的函数。 ¾ 调用函数前，系统需先完成三件事： ¾将所有的实在参数、返回地址等信息传 递给被调用函数保存； ¾为被调用函数的局部变量分配存储区； ¾将控制转移到被调用函数的入口
据结构 从被调用函数返回调用函数之前,系 统需先完成三件事: 保存被调函数的计算结果; >释放被调函数的数据区; 依照被调函数保存的返回地址将控制转 栈和队列 移到调用函数 嵌套调用时,按照“后调用先返回” 的原则 >栈的应用—递归和非递归 据 构 函数之间的信息传递和控制转移必须通过 “栈”来实现:系统将整个程序运行时所 需的数据空间安排在一个栈中,每当调用 一个函数时,就为它在栈顶分配一个存储 栈和队列 区;每当从一个函数退出时,就释放它的 存储区,则当前正运行的函数的数据区必 在栈顶。(Page56)
6 数 据 结 构 之 栈 和 队 列 11 ¾ 从被调用函数返回调用函数之前，系 统需先完成三件事： ¾保存被调函数的计算结果； ¾释放被调函数的数据区； ¾依照被调函数保存的返回地址将控制转 移到调用函数。 ¾ 嵌套调用时，按照“后调用先返回” 的原则 数 据 结 构 之 栈 和 队 列 12 ¾ 栈的应用——递归和非递归 ¾ 函数之间的信息传递和控制转移必须通过 “栈”来实现：系统将整个程序运行时所 需的数据空间安排在一个栈中，每当调用 一个函数时，就为它在栈顶分配一个存储 区；每当从一个函数退出时，就释放它的 存储区，则当前正运行的函数的数据区必 在栈顶。 ( Page 56 )
据结构 递归函数的运行过程类似于多个函数 的嵌套调用 递归函数的运行的“层次” 栈和队列 13 例1.已知f(m,n)函数(m,n均为自然数)的定义 数据结构 如下 m+n+1 (m*n=0) f(m, n)= f(m-1,f(m,n-1)(m*n≠0) (1)写出计算f(m,n)的递归算法。 和(2)利用堆栈改写出非递归算法。 队 列(3)根据非递归算法,画出计算f(2,1)时 值参、局部变量以及堆栈的变化情况 14
7 数 据 结 构 之 栈 和 队 列 13 ¾ 递归函数的运行过程类似于多个函数 的嵌套调用 ¾ 递归函数的运行的“层次” 数 据 结 构 之 栈 和 队 列 14 例1.已知f(m,n)函数(m,n均为自然数)的定义 如下： m+n+1 (m*n=0) f(m,n)= f(m-1,f(m,n-1)) (m*n≠0) ( 1)写出计算f(m,n)的递归算法。 ( 2)利用堆栈改写出非递归算法。 ( 3)根据非递归算法，画出计算f(2,1)时 值参、局部变量以及堆栈的变化情况
F函数的递归算法 s int f(int m, int n)t if(m*n==0) return(m+n+1) ese return(f(m-1, f(m, n-D))): L2,1 据 构 int f(int m, int n)f 之f(m°n=0) return(m+n+1); else ixI(m,n- 队 y=f(m-1,x); return(y) F函数递归示意图
8 数 据 结 构 之 栈 和 队 列 15 F函数的递归算法 int f(int m,int n){ if(m*n==0) return(m+n+1); else return( f (m-1, f(m,n-1) ) ); } 数 据 结 构 之 栈 和 队 列 16 F函数递归示意图 5 3 5 3 4 2 , 0 1,0 0,2 1 , 2 0 , 4 1, 1 0, 3 1 , 3 2，1 2 3 4 5 int f(int m,int n){ if(m*n==0) return(m+n+1); else {x=f(m,n-1) ; y=f (m-1, x) ; return(y);} }
int F(int m, int nt if(m>=0&&n>=0){ InitStack(S); push(S, m, n); 结 构 while( StackEmpty(S) pop(s, m, n); if (n==-1)n=result if (m*n==0)result= m+n+1 栈和队列 else push(S, m-1, -1);push(S, m, n-1):) return result; 3 3/typedef struct(int m, n; SElem Type; F函数的非递归算法 Result whie( StackEmpty(S))12条语句 第一次循环2 2,0 据pop(S,m,n) 次循环 031,-1 构if(n=1) 第三次循环1 n=result 0,-1 if(m*n==0 第四次循环 result= m+n+l; 0,-1 栈和队列 else 第五次循环1 push(S,m-1,-1); push(S, m, n-1); 第六次循环1020,-1 第七次循环「02|3
9 数 据 结 构 之 栈 和 队 列 17 F函数的非递归算法 int F(int m,int n){ if(m>=0 && n>=0){ InitStack(S); push(S, m , n); while(!StackEmpty(S) ){ pop(S, m , n); if (n==-1) n=result; if (m*n= =0) {result = m+n+1;} else {push(S,m-1,-1);push(S,m,n-1);} } return result; } } //typedef struct{int m,n;}SElemType; 数 据 结 构 之 栈 和 队 列 18 while(!StackEmpty(S) ) { pop(S, m , n); if(n==-1) n=result; if(m*n= =0) result = m+n+1; else { push(S,m-1,-1); push(S,m,n-1); } } 第七次循环 0 2 3 0，-1 0，-1 0，-1 0，-1 第六次循环 1 0 2 1，0 0，-1 0，-1 0，-1 第五次循环 1 1 3 1，1 0，-1 0，-1 第四次循环 1 2 3 1，2 0，-1 第三次循环 1 3 3 第二次循环 2 0 3 1，-1 2，0 1，-1 第一次循环 2 1 1,2条语句 2 1 2,1 标号 M N Result S
例2: Hanoi问题:设有三座塔,依次命名为X、 有n个直径不相同的圆盘,由小到大依 数据结构 次编号为1,2,3,…n,开始时,它们前部按 大小递减的顺序插在塔座X上,现在要求把n个 圆盘按大小递减的顺序放在塔座Z上。其移动规 则如下: 1、每次只能移动一个圆盘; 2、圆盘可以放在任一个塔座上; 栈和队列 任何时刻不能将大圆盘压在小圆盘上 19 int count=0: s void hanoi(int n, char x,char y, char z)t 据 if (n==1) move(x, 1, z); 构 else hanoi(n-1,x,zy);/递归调用* move(x,n,z);/将x上编号为n的盘放到z上* hanoi(n-1,y, x, z); a void move(char x, int n, char z)( printf(%d: move disk %d from %c to %c\n",++count, n, x, Z); return;
10 数 据 结 构 之 栈 和 队 列 19 ¾ 例2：Hanoi问题：设有三座塔，依次命名为X、 Y、Z，有n个直径不相同的圆盘，由小到大依 次编号为1，2，3，….n，开始时，它们前部按 大小递减的顺序插在塔座X上，现在要求把n个 圆盘按大小递减的顺序放在塔座Z上。其移动规 则如下： 1、每次只能移动一个圆盘； 2、圆盘可以放在任一个塔座上； 3、任何时刻不能将大圆盘压在小圆盘上； 1 2 3 1 2 3 X Y Z X Y Z 数 据 结 构 之 栈 和 队 列 20 int count=0; void hanoi(int n,char x,char y, char z) { if（n == 1） move(x,1,z); else{ hanoi(n-1,x,z,y); /*递归调用*/ move(x,n,z); /*将x上编号为n的盘放到z上*/ hanoi(n-1,y,x,z); } } void move(char x, int n, char z) { printf(“%d: move disk %d from %c to %c\n”,++count, n,x,z); return; }