第3章_栈和队列(1) (1)

1、第三章 栈和队列(1)(1)郭大庆郭大庆 电子科技大学生命科学与技术学院电子科技大学生命科学与技术学院神经信神经信息教育部重点实验室息教育部重点实验室约瑟夫问题15个教徒和个教徒和15 个非教徒在深海上遇险，必须个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：难，于是想了一个办法：30个人围成一圆圈个人围成一圆圈，从第一个人开始依次报数，每数到第九个，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入个人为止。问怎样排

2、法，才能使每次投入大海的都是非教徒。大海的都是非教徒。第三章 栈和队列 本章学习两种特殊的线性数据结构，它们特殊在定本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端义的操作不同，即插入和删除操作只能在线性表的两端进行。进行。 只能在一端进行的只能在一端进行的- 栈栈 分别在两端进行的分别在两端进行的- 队列队列 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in内容提要：3.4

3、队列的定义及逻辑结构队列的定义及逻辑结构3.5 循环队列存储结构及操作实现循环队列存储结构及操作实现3.6 队列的链式存储结构及操作实现队列的链式存储结构及操作实现3.1 3.1 栈的定义及逻辑结构：定义和逻辑特性n特殊的线性表：操作受限n限定仅在表尾进行插入或删除操作的线性表,允许插入或删除的一端称为栈顶(top),另一端称为栈底(bottom)n老派观点认为栈是“下推表” n新派观点认为栈底不动 - n元素插入栈称为“入栈”或“压栈”（push）n删除元素称为“出栈”或“弹出”（pop）进栈进栈 出栈出栈an.a1栈顶栈顶栈底栈底一个有关入栈、出栈的习题例题：假设有例题：假设有A ， B

4、, C , D 四个元素；它们入栈的次序为四个元素；它们入栈的次序为A B C D，出，出栈次序任意，请问不可能得到下面哪些出栈序列？栈次序任意，请问不可能得到下面哪些出栈序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D( 5 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D 答案：答案：( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D( 5 ) A C B D ( 6 ) D B A C ( 7 ) A D C

5、 B ( 8 ) C A B D 栈的ADTADT描述ADT Stack 数据对象：数据对象：D = ai | ai属于属于Elemset, (i=1,2,n, n0) 数据关系：数据关系：R1 = ai-1,ai|ai-1,ai属于属于D,(i=2,3,n) 约定约定an 为栈顶为栈顶, a1为栈底。为栈底。 基本操作基本操作 (9个个)： InitStack(&S); DestroyStack(&S); ClearStack(&S); StackEmpty(S); StackLength(S) ; GetTop(S,&e); Push(&S,e);

6、Pop(&S,&e); StackTraverse(S,visit () ADT Stack栈的四个重要基本操作 初始条件：栈初始条件：栈s不存在。不存在。 操作结果：构造了一个空栈。操作结果：构造了一个空栈。 初始条件：栈初始条件：栈s已存在已存在 。 操作结果：在栈操作结果：在栈s的顶部插入一个新元素的顶部插入一个新元素e， e成为新的栈顶成为新的栈顶 元素。栈发生变化。元素。栈发生变化。 初始条件：栈初始条件：栈s存在且非空。存在且非空。 操作结果：将栈操作结果：将栈s的栈顶元素从栈中删除，并用的栈顶元素从栈中删除，并用e返回其值。栈发返回其值。栈发 生变化。生变化。 初

7、始条件：栈初始条件：栈s存在且非空。存在且非空。 操作结果：读栈顶元素并用操作结果：读栈顶元素并用e返回其值。栈不变化。返回其值。栈不变化。栈是一种特殊的线性表，因此栈也可采用两种存储结构：栈是一种特殊的线性表，因此栈也可采用两种存储结构：顺序存储结构顺序存储结构链式存储结构链式存储结构顺序栈p 顺序栈的存储结构顺序栈的存储结构顺序栈是指顺序栈是指，即利用一组，即利用一组的数据元素，同时附设指针的数据元素，同时附设指针，指示指示在顺序栈中的在顺序栈中的。栈顶栈顶(top) 栈底栈底(base)栈中元素数目：栈中元素数目：n = top - base顺序栈p 类型定义（类型定义（） 注意注意to

8、p的含义的含义约定约定 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct ElemType *base; ElemType*top; int stacksize; SqStack;顺序栈的基本操作：构建一个空栈S SStatus InitStack(SqStack *s) s.base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s.base) return(OVERFLOW); s.top = s.base; s.stack

9、size = STACK_INIT_SIZE; return OK; /* InitStack */顺序栈的基本操作：进栈操作Status Push(SqStack *s, SElemType e) if (s.top s.base = s.stacksize) l_temp=(SElemType*)realloc (s.base,(s.stacksize+STACKINCREMENT) *sizeof(SElemType); if (!l_temp) return(OVERFLOW); s.base = l_temp; s.top = s.base + s.stacksize; s.stac

10、ksize += STACKINCREMENT; *(s.top+) = e; return OK; / /* Push */顺序栈的基本操作：出栈操作 Status Pop(SqStack *s, SElemType *e) if (s.top = s.base) return ERROR; *e = *(-s.top); return OK; /* Pop */顺序栈的基本操作：取( (栈顶) )元素 Status GetTop(SqStack *s, SElemType *e) if (s.top = s.base) return ERROR; *e = *(s.top-1); retu

11、rn OK; /* Pop */链栈：栈的链式存储结构（概略）n链栈链栈: :同一般线性表的单链式存储结构基本相同。但是应同一般线性表的单链式存储结构基本相同。但是应该确定链表的哪端对应于栈顶，如果链表尾作为栈顶，则该确定链表的哪端对应于栈顶，如果链表尾作为栈顶，则入、出栈操作的时间复杂性为入、出栈操作的时间复杂性为O( n ) . n无栈满问题(除非分配不出内存), 空间可扩充n栈顶-链表的表头n可以不必引入头结点n入栈相当于在单链表的第一个结点之前进行插入操作n出栈相当于在单链表中删除第一个结点/* 链栈结点链栈结点*/typedef struct StackNode SElemType

12、data; struct StackNode *next; StackNode,*LinkStackPtr;链栈：栈的链式存储结构/* 构造一个空栈构造一个空栈S */Status InitStack(LinkStack *S) S-top=NULL; /将栈顶指向空，表示为空栈将栈顶指向空，表示为空栈 S-count=0; return OK;/* 链栈头指针链栈头指针*/typedef struct LinkStackPtr top; int count; LinkStack;链栈结构链栈结构 Status Push(LinkStack *S,SElemType e) LinkStackP

13、tr s=(LinkStackPtr)malloc(sizeof(StackNode); s-data=e; s-next=S-top; S-top=s S-count+; return OK;自己考虑出栈自己考虑出栈的操作怎样实现的操作怎样实现顺序栈和链栈的比较，以及为什么要用栈？n顺序栈和链栈的比较：顺序栈和链栈的比较：n顺序栈和链栈的进栈push和出栈pop操作；n顺序栈需要事先确定一个固定的长度，可能会存在内存；n链栈要求，这也会，但栈的了； 栈的使用过程中，栈的使用过程中，。n为什么要用栈：为什么要用栈：n栈的引入，。n此外，许多高级语言，比如Java、C#等都有对栈结构的封装，可以

14、直接使用栈的push和pop方法，非常方便。在n非负十进制数转换成其它进制的数的一种简单方法：n转换原理：N=(N div d)*d + N mod d div整除，mod求余q例，十进制转换成八进制：(66)10=(102)8 结果为余数的逆序结果为余数的逆序( (出栈顺序出栈顺序) )：n先求得的余数在写出结果时最后写出，最后求出的余数最先写出，先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换。符合栈的先入后出性质，故可用栈来实现数制转换。n同理，一个非负十进制整数同理，一个非负十进制整数N N转换为另一个等价的基为转换为另一个等价的基

15、为B B的的B B进制数，进制数，可以采用可以采用 来解决来解决 20166/8=8 66/8=8 余余 2 28/8=1 8/8=1 余余 0 01/8=0 1/8=0 余余 1 1void conversion() InitStack(&s); /初始化一个空栈初始化一个空栈 scanf(“%d”,&N); while(N) Push(&s, N%8); /将余数依次压入栈将余数依次压入栈 N = N/8; /做整除得到下一次求余操作的整数做整除得到下一次求余操作的整数 while(!StackEmpty(s) /判断是否为空栈判断是否为空栈 Pop(&s,

16、&e); /若不为空，将栈顶元素出栈若不为空，将栈顶元素出栈 printf(“%d”,e); /* conversion */数制转换算法：数制转换算法：n中缀表达式：中缀表达式：n运算符在中间n需要括号改变优先级n 9+(3-1)3+10/2n后缀表达式（逆波兰法）后缀表达式（逆波兰法）n运算符在后面n完全不需要括号n9 3 1- 3 * + 10 2 / + 运算规则：依次顺序读入表达式的符号序列（假设以作为输入序运算规则：依次顺序读入表达式的符号序列（假设以作为输入序列的结束），并根据读入的元素符号逐一分析：列的结束），并根据读入的元素符号逐一分析： 当遇到的是一个操作数，则压入

17、栈顶； 当遇到的是一个运算符, 就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶。 如此继续，直到结束如此继续，直到结束, 这时栈顶的值就是输入表达式的值这时栈顶的值就是输入表达式的值 后缀表达式后缀表达式: 9 3 1- 3 * + 10 2 / +3-1=22*3=69+6=1510/2=515+5=20空栈空栈一个关键问题：如何将一个关键问题：如何将？答案：可以通过答案：可以通过来完成转换。来完成转换。 转换规则：从左到右遍历中缀表达式的每个数字和符号，并做以下转换规则：从左到右遍历中缀表达式的每个数字和符号，并做以下操作：操作：1.若是若是，即成为后缀表达

18、式的一部分；，即成为后缀表达式的一部分；2.若是若是，则，则。 如此继续，一直到最终输出后缀表达式为止。如此继续，一直到最终输出后缀表达式为止。99 3 19 3 1 -9 3 1 3 *+9 3 1 3 *+109 3 1 3 *+10 29 3空栈空栈9 3 1 - 3# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # $(x, y)=(0, 0)01234567890 1 2 3 4 5 6 7 8 9 求迷宫中一条从

19、入口到出口的路径的算法可简单描述如下求迷宫中一条从入口到出口的路径的算法可简单描述如下:设定当前位置的初值为入口位置设定当前位置的初值为入口位置:do 若当前位置可通若当前位置可通,则则 将当前位置插入堆栈顶将当前位置插入堆栈顶; 若该位置是出口位置若该位置是出口位置,则结束则结束; 否则切换当前位置的东邻块为新的当前位置否则切换当前位置的东邻块为新的当前位置; 否则否则 若堆栈不空且栈顶位置尚有其他方向未经探索若堆栈不空且栈顶位置尚有其他方向未经探索; 则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相 邻块邻块; 若栈不空但栈顶位置

20、的四周均不可通若栈不空但栈顶位置的四周均不可通, 则则 删去栈顶位置删去栈顶位置; 若栈不空若栈不空,则重新测试新的栈顶位置则重新测试新的栈顶位置, 直至找到一个可通的相邻或出栈至栈空直至找到一个可通的相邻或出栈至栈空; (栈不空栈不空)递归：在高级语言中，调用自己和其他函数并没有本质的不同。我递归：在高级语言中，调用自己和其他函数并没有本质的不同。我们把们把。递归。递归。 求阶乘时时当当时时当当 1 ,)!1( 0 , 1!nnnnn求解阶乘函数的递归算法求解阶乘函数的递归算法: 1. long fact ( long n ) 2. if ( n = 0 ) return 1; / 3. e

21、lse return n * fact (n- -1); 4. main( ): fact(4)参参数数传传递递结结果果返返回回 fact(4): fact(3): fact(2): fact(1): fact(0): 1直接定值为直接定值为1 1计算计算 4*fact(3)计算计算 3*fact(2)计算计算 2*fact(1)计算计算 1*fact(0)12624以主程序中调用以主程序中调用FACT(4)(4)为例：为例：n: 4控制链返回地址控制链返回地址第第1次调用次调用fact时的活动记录时的活动记录x: 4主程序主程序main的的活动记录活动记录栈生长方向栈生长方向栈生长方向栈生长

22、方向n: 4控制链返回地址控制链返回地址第第1次调用次调用fact时的活动记录时的活动记录x: 4主程序主程序main的的活动记录活动记录n: 3控制链返回地址控制链返回地址第第2次调用次调用fact时的活动记录时的活动记录栈生长方向栈生长方向n: 4控制链返回地址控制链返回地址第第1次调用次调用fact 时的活动记录时的活动记录x: 4主程序主程序main 的活动记录的活动记录n: 3控制链返回地址控制链返回地址第第2次调用次调用fact 时的活动记录时的活动记录n: 2控制链返回地址控制链返回地址n: 1控制链返回地址控制链返回地址第第3次调用次调用fact 时的活动记录时的活动记录第第4次调用次调用fact 时的活动记录时的活动记录自由空间自由空间1! = 12! = 2*1! =