数据结构之栈和队列.ppt

《数据结构之栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构之栈和队列.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 栈和队列栈和队列栈和队列是两种特殊的线性表，是栈和队列是两种特殊的线性表，是操作受限操作受限的线性表，的线性表，称限定性称限定性DS3.1 栈（栈（stack）栈的定义和特点栈的定义和特点v定义：限定仅在定义：限定仅在表尾表尾进行插入或删除操作的线性表，表进行插入或删除操作的线性表，表尾尾栈顶栈顶，表头，表头栈底栈底，不含元素的空表称空栈，不含元素的空表称空栈v特点：先进后出（特点：先进后出（FILO）或后进先出（或后进先出（LIFO）ana1a2.栈底栈底栈顶栈顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)#define STACK_INIT_SIZE 100;#define

2、 STACKINCREAMENT 10;typedef struct SELemType*base;SElemType *top;int stacksize;SqStack;栈的存储结构栈的存储结构v顺序栈顺序栈l实现：动态实现：动态栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为top=basetop进栈进栈Atop出栈出栈栈满栈满BCDEFtop=base,栈空，栈空，此时出栈，则此时出栈，则下溢下溢（underflow)top-base=stacksize,栈满，此时入栈，栈满，此时入栈，需重新分配需重新分配空间，如空间分配失败空间，如空间分配失败则则

3、上溢上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空栈空base=0123450栈空栈空top=0123450base123450ABCDEFbase算法算法v构造空栈构造空栈s sv返回栈顶元素返回栈顶元素 if(S.top=S.base)return ERROR;e=*(S.top-1);v进栈进栈 if(S.top S.base=S.StackSize)S.base=(ElemType*)realloc(S.base,S.stacksize+STACKINCREAMENT)*sizeof(ElemType);if(!S.base)exit(O

4、VERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;*S.top+=e;v出栈出栈if(S.top=S.base)retuen ERROR;e=*-S.top;l入栈算法入栈算法l出栈算法出栈算法v链栈链栈栈顶栈顶栈顶栈顶 .topdata link栈底栈底l结点定义结点定义l入栈算法入栈算法l出栈算法出栈算法typedef struct node int data;struct node *next;JD;.栈底栈底toptopxptop .栈底栈底topqv数制转换：数制转换：(159)10=(237)8159819

5、82802 3 7 余余 7余余 3余余 2toptop7top73top732栈的应用栈的应用例例 把十进制数把十进制数159转换成八进制数转换成八进制数v括号匹配的检验括号匹配的检验 检检验验括括号号是是否否匹匹配配的的方方法法可可用用 期期待待的的急急迫迫程程度度 这这个个概概念念来描述。来描述。toptoptop(top(top(toptop例如考虑下列括号序列：例如考虑下列括号序列：(（）)1 2 3 4 5 6 1 2 3 4 5 6v回文游戏：顺读与逆读字符串一样（不含空格）回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串读入字符串2.去掉空格（原串）去掉空格

6、（原串）3.压入栈压入栈4.原串字符与出栈字符依次比较原串字符与出栈字符依次比较 若不等，非回文若不等，非回文 若直到栈空都相等，回文若直到栈空都相等，回文字符串：字符串：“madam im adam”v行编辑程序行编辑程序一一个个简简单单的的行行编编辑辑程程序序的的功功能能是是：接接受受用用户户从从终终端端输输入入的的程程序序或或数数据据，并并存入用户的数据区。存入用户的数据区。例例如如，可可用用一一个个退退格格符符“#”表表示示前前一一个个字字符符无无效效；可可用用一一个个退退行行符符“”，表示当前行中的字符均无效。，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：例如，假设

7、从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);v迷宫问题迷宫问题(a)(a)迷宫的图形表示迷宫的图形表示(b)(b)迷宫的二维数组表示迷宫的二维数组表示 求解迷宫中一条路径的方法求解迷宫中一条路径的方法：从入口出发，沿某一方向进行探索，若能走通，从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方探索，直到所有可能的通路都探索到为

8、止。这类方法统称法统称回溯法回溯法。用一个栈记录走过的位置，栈中每个元素包括用一个栈记录走过的位置，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即位置上所选的方向（即directondirecton数组的下标值）数组的下标值）v表达式求值表达式求值 优先关系表优先关系表 3*（7+3*6/2-5）*(+/=3*（7+18/2-5）*(+-=3*（7+9-5）*(-=3*（16-5）*()=3*11输入：输入：3*（7+3*6/2-5#)运算对象栈运算对象栈运算符栈运算符栈3*(7+3*618/2916-51133

9、v表达式求值表达式求值l后缀表达式：后缀表达式：31 5 22-*70+l中缀表达式：中缀表达式：31*(5-22)+70l中缀表达式到后缀表达式的转换中缀表达式到后缀表达式的转换基本思想：顺序扫描中缀表达式，当读入一个运算分量基本思想：顺序扫描中缀表达式，当读入一个运算分量时就立即输出，而在读入一个运算符时，则判断其与栈顶时就立即输出，而在读入一个运算符时，则判断其与栈顶运算符的优先级，是右括号或优先级低于栈顶（乘除优于运算符的优先级，是右括号或优先级低于栈顶（乘除优于加法）则栈顶首先把它压入一个运算符栈中，一直等到它加法）则栈顶首先把它压入一个运算符栈中，一直等到它的两个运算分量都读到后，

10、才能把它输出，当扫描遇到一的两个运算分量都读到后，才能把它输出，当扫描遇到一个左括号时立即把它推入栈中，继续扫描直到右括号出现，个左括号时立即把它推入栈中，继续扫描直到右括号出现，括号内的表达式也按如上规则进行压栈和输出。括号内的表达式也按如上规则进行压栈和输出。注意：注意：括号不必输出括号不必输出。l后缀表达式求值：后缀表达式求值：使用一个存放运算分量的栈，求值过程顺序扫描后缀表达使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量就把它推如栈中式，每次遇到运算分量就把它推如栈中，遇到运算符，就从，遇到运算符，就从栈中弹出两个运算分量进行运算，再打运算结果推入栈中。栈中弹出

11、两个运算分量进行运算，再打运算结果推入栈中。扫描结束，留在栈定的即为表达式的值扫描结束，留在栈定的即为表达式的值v函数的嵌套调用函数的嵌套调用r主主程程序序srrrs函函数数1rst函函数数2rst函函数数3栈与递归栈与递归v 递归的定义递归的定义l递归：函数直接或间接的调用自身叫递归：函数直接或间接的调用自身叫例：例：阶乘函数阶乘函数 n!1 n=0 n*F(n-1)n0F(n)=例例 递归的执行情况分析递归的执行情况分析 v递归函数实现递归函数实现l实现：建立递归工作栈实现：建立递归工作栈void print(int w)int i;if(w!=0)print(w-1);for(i=1;i

12、1时，先把上面时，先把上面n-1个圆盘从个圆盘从A移到移到B,然后将然后将n号盘从号盘从A移到移到C,再将再将n-1个盘从个盘从B移到移到C。即把求即把求解解n个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解n-1个圆盘的个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆问题，依次类推，直至转化成只有一个圆盘的盘的Hanoi问题问题l算法：算法：l执行情况：u递归工作栈保存内容：形参n,x,y,z和返回地址u返回地址用行编号表示n x y z 返回地址返回地址 void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x

13、,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)main()int m;printf(Input number of disks”);scanf(%d,&m);printf(”Steps:%3d disks”,m);hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z

14、);(8)(9)ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main()int m;printf(Input the number of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x

15、,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main()int m;printf(Input the number of disks scanf(%d,&m);printf(The steps to moving%3d hanoi(m,A,B,C);(0)void hanoi(int n,char x,char y,char z)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1

16、,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9)ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0栈空栈空3 A B C 02 B A C 8作业：作业：1.1.编写顺序栈的进栈和出栈操作的算法编写顺序栈的进栈和出栈操作的算法2.2.编写链栈的进栈和出栈操作的算法编写链栈的进栈和出栈操作的算法3.3.利用栈实现括号匹配利用栈实现括号匹配4.4.上机实现并且把算法写在作业本上上交上机实现并且把算法写在作业本上上交3.2 队列队列队列的定义及特点队列的定义及特点v定义：队列是限定

17、只能在表的一端进行插入，在表的定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表另一端进行删除的线性表l队尾队尾(rear)允许插入的一端允许插入的一端l队头队头(front)允许删除的一端允许删除的一端v队列特点：先进先出队列特点：先进先出(FIFO)a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an)v双端队列双端队列a1 a2 a3.an 端端1端端2入队入队出队出队入队入队出队出队链队列链队列v结点定义结点定义typedef struct QNode QElemType data;struct QNode *next;Qnode,

18、*QueuePtr;头结点头结点 .front队头队头队尾队尾rear设队首、队尾指针设队首、队尾指针front和和rear,front指向头结点，指向头结点，rear指向队尾指向队尾typedef structQueuePtr front;QueuePtr rear;LinkQueue;v链表定义链表定义frontrearx入入队队xfrontreary入入队队xyfrontrearx出出队队xyfront rear空队空队front reary出出队队v入队算法入队算法v出队算法出队算法v构造空队列算法构造空队列算法v销毁队列算法销毁队列算法队列的顺序存储结构队列的顺序存储结构v实现：实现

19、：front=0rear=0123450队空队空123450frontJ1,J1,J3入队入队J1J2J3rearJ4J5J6rear123450J4,J5,J6入队入队front设两个指针设两个指针front,rear,约定：约定：rear指示队尾元素指示队尾元素的后一个位置的后一个位置；front指示队头元素指示队头元素初值初值front=rear=0空队列条件：空队列条件：front=rear入队列：入队列：Q.base rear+=x;出队列：出队列：x=Q.basefront+;rearrearrearJ1J2123450J1,J2,J3出队出队J3frontfrontfrontfr

20、ontv存在问题存在问题设数组维数为设数组维数为M，则：则：l当当front=0,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出l当当front 0,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出假溢出假溢出v解决方案解决方案l队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪费时间浪费时间l循环队列循环队列u基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让Q0接在接在QM-1之后，若之后，若rear+1=M,则令则令rear=0;0M-11frontrear.u实现：利用实现：利用“模模”运算运算u入队：入队：r

21、ear=(rear+1)%M;Q.baserear=x;u出队：出队：front=(front+1)%M;x=Q.basefront;u队满、队空判定条件队满、队空判定条件J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间：队空：队空：front=rear 队满：队满：(rear+1)%M=frontJ4J5J6012345rearfront初始状态初始状态Q.frontQ.rear012345rearfrontQ.frontQ.rearJ4J5J6012345rearfrontJ9J8J7Q.FrontQ.rearu入队算法：u出队算法：