数据结构 邓欣-ch3.pptVIP

* 【例】CPU分时系统在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。 * 【例】打印杨辉三角形 习题 1、链栈中为何不设置头结点？ 2、循环队列的优点是什么？ 如何判别它的空和满？ 3、回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 4、设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空。 * 需要找 几个例子的程序。 * * * * * * * * * * * * * * * * * * * * * * Program for Hanoi const int disks = 64; // Make this constant much smaller to run program. void move(int count, int start, int finish, int temp); main( ) { move(disks, 1, 3, 2); } * Move 递归函数 void move(int count, int start, int finish, int temp) { if (count 0) { move(count - 1, start, temp, finish); printf(“Move disk %d from %d to %d /n”,count, start, finish); move(count - 1, temp, finish, start); } } * 改进 递归函数 void move(int count, int start, int finish, int temp) { if (count ==1) printf(“Move disk %d from %d to %d /n”,1, start, finish); else { move(count - 1, start, temp, finish); printf(“Move disk %d from %d to %d /n”,count, start, finish); move(count - 1, temp, finish, start); } } * Ackerman 函数定义如下：请写出递归算法。 　　　　　　　　 n+1　　　 当m=0时 AKM ( m , n ) = AKM( m-1 ,1) 当m≠0 ，n=0时 　　　　　　　　 AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时 * 解：算法如下 int AKM( int m, int n){ if ( m== 0) return n+1; if ( m0 n==0 ) return AKM( m-1, 1); if ( m0 n0 ) return AKM( m-1, AKM( m, n-1));} * 3.4 　队列 　队列是一种先进先出(FIFO) 的线性表. 它只允许在表的一端进行插入,而在另一端删除元素 a1 a2 a3 an ... 入队列 队头 队尾 * a1 a2 a3 an ... 队头 队尾 出队列 * a1 a2 a3 an ... 队头 队尾 出队列 * a1 a2 a3 an ... 队头 队尾 出队列 * 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。 （A）2 （B