数据结构栈和队列算法应用.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 汉塔问题的栈递归模拟过程 hanoi(3, A, B, C) ; 第一次循环 2,A,C,B 1,A,B,C 2,B,A,C 3,A,B,C 汉诺塔问题 汉塔问题的栈递归模拟过程 hanoi(3, A, B, C) ; 第二次循环 2,B,A,C 1,A,B,C 1,A,C,B 1,C,A,B 1,A,B,C 2,B,A,C 汉诺塔问题 汉塔问题的栈递归模拟过程 hanoi(3, A, B, C) ; 第三次循环 1,B,C,A 1,B,A,C 1,A,B,C 汉诺塔问题 【例4】 设计算法输出二项式系数表（杨辉三角）的第n行序列。 1　　 　　 　 1 1　　　　　 1　2　1　　　　　1　3　3　1　　　　1　4　6　4　1　　　 …………………… 4、杨辉三角形问题 解题分析 （1）问题的数学解法 这是一个初等数学中讨论的问题。系数表中的第 k行有 k+1个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。　　 杨辉三角形问题 （2）选取数据结构 一种最直接的想法是利用两个数组，其中一个存放已经计算得到的第 k 行的值，然后输出第 k 行的值同时计算第 k+1行的值，并且这两个数组在计算过程中需相互交换。 若引入“循环队列”，则可以省略一个数组的辅助空间，而且可以利用队列的操作，使程序结构变得清晰，问题简化。 杨辉三角形问题 （3）算法描述 每行添加一个数字0，即作为行标记，又参与计算。 [1] 初始化队列，第1行（0，1，1）入队，计数器k赋初值 1； [2]当k n时，下一行0标记入队，否则，转[6]； 杨辉三角形问题 [3] 删除队头元素，并将其值与当前队头元素的值相加的和插入队列； [4] 判断是否换行，若否，转[3]； [5] k值加1，转[2]； [6] 删除队头元素0； [7] 输出第n行，结束。 杨辉三角形问题 输出二项式系数表的第n行 void yanghui ( int n ) {　 // 输出杨辉三角形的第 n( n1 )行 InitQueue(Q,n+2); 　　 　　　 // 设置最大容量为 n+2 的空队列 　　EnQueue(Q,0 );　　 　　　 // 添加行界值 　　EnQueue( Q,1); 　　EnQueue( Q,1 ); 　 　　　// 第一行的值入队列 　　k = 1; 　　 杨辉三角形问题 while ( k n ) {　　　　　 　　　// 通过循环队列求前 n-1 行的值 　　　EnQueue ( Q,0 ); 　　　 　　// 下一行界值“0”入队列 　　　 do { 　　　　　 　　　 // 输出第 k 行，计算第 k+1 行 杨辉三角形问题 Dequeue( Q,s ); 　　　　GetHead( Q,e ); 　　　　EnQueue(Q,s+e); //插入　　} while (e!=0); //非换行 　k++; //准备计算下一行 　} // while DeQueue ( Q,e ); // 行界值0出队列  杨辉三角形问题 　　while (!QueueEmpty (Q) ) { 　　　　　　　　　　　 　 // 单独处理第 n 行的值的输出 　　　 DeQueue ( Q,e ); 　　 printf(e)； 　 } // while} // yanghui? 容易看出此算法的时间复杂度为O (n2)。 杨辉三角形问题 假设只计算四行，则队列的最大容量为 5。 1 1 0 0 q.front q.rear 1 1 0 0 1 q.front q.rear 1 1 0 2 1 q.front q.rear 1 1 0 2 1 q.front q.rear 1 0 0 2 1 q.front q.rear 1 0 1 2 1 q.front q.rear 杨辉三角形问题 1 0 1 2 1 q.front q.rear 1 0 1 2 3 q.front