唐国民版栈和队列案例分析.ppt

分析第 i 行元素与第 i+1行元素的关系如图所示 ： 在i=2时,队列的头指针指向0，尾指针指向1的下一位，我们看如何 由第二行得到第三行的。①第三行的0入队②队头元素0出队并送入s中③取队头元素1并送入t中④s+t的值1入队。这时队列的队头指针指向1，队尾指针指向第三行的第一个3的位置。重复②③④三步就得到第三行；类推，我们由第三行又得到第四行；…… front rear 杨辉三角形元素入队顺序 0 0 0 0 0 0 假设n=4，i=3，则输出第3行元素并求解第4行元素值的循环执行过程中队列的变化状态如图所示 ： void YangHui( int n )/*打印杨辉三角形的前n行*/ { SeqQueue *q; int i, j,s,t; for(i=1;i=n;i++) printf( ); printf(1\n); /*在中心位置输出杨辉三角最顶端的1*/ q=InitQueue(); /*设置容量为n+2的空队列*/ EnQueue(q,0); /*添加行分隔符，即0入队*/ EnQueue(q,1);EnQueue(q,1); /*第一行的值入队*/ １、出队并保存出队元素　　　２、取出front所指元素并保存 ３、计算前两步得到的元素值之和并入队 重复这三步。（当由第i行求得第i+1行时，０先入队……） 上图的操作过程是： for(j=1;jn;j++) /*利用循环队列输出前n-1行的值*/ {for(i=1;in-j;i++) /*在输出第j行的首元素之间输出n-j个空格*/ printf( ); EnQueue(q,0); /*行分隔符0入队*/ do /*输出第j行并计算第j+1行*/ {s=DeQueue(q); /*删除队头元素并赋给s*/ t=GetHead(q); /*取队头元素给t*/ if(t) printf(%5 d,t); /*若不到行分隔符0，则输出t，再输出一个空格*/ else printf(\n); /*否则输出一个换行符*/ EnQueue(q,s+t); /*将第j+1行的对应元素s+t入队*/ }while(t!=0); } DeQueue(q); /* 删除行分隔符 */ printf(%3d,DeQueue(q)); /* 输出第n行的第一个元素 */ while(!QueueEmpty(q)) /* 输出第n行的其余元素 */ {t=DeQueue(q); printf(“%5 d,t); } } 输出杨辉三角形的最后一行（）第n行 2、迷宫问题： 寻找一条从迷宫入口到出口的最短路径 迷宫问题是实验心理学的一个经典问题，心理学家把一只老鼠从一个无顶盖的迷宫入口处赶进迷宫，在迷宫的出口处设置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到学习走通迷宫的路线。 算法分析 如果用计算机来处理：求出一条从入口到出口的通路，或者得出没有通路的结论。通常采用一种称为回溯法的方法，即不断试探且及时纠正错误的有哪些信誉好的足球投注网站方法，这需要借助“栈”来实现。此法在许多书中都有介绍，在此不再赘述。 如果在一般走迷宫的方法上，更进一步要求不论试探方位为何，找出一条最短路径，那该如何解决呢？其算法的基本思想是：从迷宫的入口[1][1]出发，向四周有哪些信誉好的足球投注网站，记下所有一步能到达的坐标点；然后依次从每一点出发，向四周有哪些信誉好的足球投注网站，记下所有从入口点出发，经过两步可以到达的坐标点……依次进行下去，一直到达迷宫的出口处[m][n]。然后从出口处沿有哪些信誉好的足球投注网站路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 入口 出口 迷宫 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1