4．2流程觀察分析法

　　流程觀察分析法，是通過觀察分析程序執(zhí)行流程，了解程序執(zhí)行信息、并分析這些信息，從而找出錯(cuò)誤原因及位置。如果，程序的輸出信息不足以提供程序執(zhí)行流程，那么，需要在程序的控制結(jié)構(gòu)中插入信息輸出（即程序插裝）語句，使得程序試運(yùn)行時(shí)能輸出相關(guān)信息以獲取程序執(zhí)行流程信息，使調(diào)試者能根據(jù)這些信息進(jìn)行分析，獲知程序運(yùn)行流程與錯(cuò)誤結(jié)果間的關(guān)系，進(jìn)而判斷出錯(cuò)原因。對(duì)于一些新手遇到的“不見程序運(yùn)行結(jié)果”的情形，通過在程序流程的適當(dāng)位置插入輸出語句后，能夠了解程序運(yùn)行的大致情況，從而進(jìn)入下一步調(diào)試。

　　例4.1 需求描述：設(shè)計(jì)程序，將一維數(shù)組（元素為int型）中指定位置pos處的1個(gè)元素刪除。

　　程序：

　　/*ch4_ex1.c*/

　　#include stdio.h

　　#define MAX 10

　　main()

　　int a[MAX],i,pos,num;

　　num=MAX;

　　printf("Input array a(%d integer numbers):",MAX);

　　for(i=0;iMAX;i++)/*輸入數(shù)組元素*/

　　scanf("%d",a[i]);

　　printf("Specify the position:");

　　scanf("%d",pos);/*輸入刪除位置，首元從1開始*/

　　if(pos1||posMAX)/*刪除位置合法性檢查*/

　　printf("Eroor! Enter a key to continue...\n");

　　getchar();

　　return;

　　while(posMAX) /*將pos及其后的元素復(fù)制到前一單元*/

　　a[pos-1]=a[pos];

　　pos++;

　　num--;

　　printf("Now,array a:\n");

　　for(i=0;inum;i++)/*輸出刪除后的數(shù)組元素*/

　　printf("%8d",a[i]);

　　程序運(yùn)行情況：

　　程序運(yùn)行后，根據(jù)提示信息Input array a (10 integer numbers):輸入數(shù)據(jù)

　　1 2 3 4 5 6 7 8 9 10

　　再根據(jù)提示信息Specify the position:輸入 5，程序沒有反應(yīng)，強(qiáng)行退出程序執(zhí)行。分析程序出錯(cuò)誤情況，從交互信息看，程序已經(jīng)執(zhí)行到while循環(huán)，可能無法退出循環(huán)而表現(xiàn)為沒有反應(yīng)。那么，看看循環(huán)體的語句吧。從while語句到程序結(jié)束的語句

　　while(posMAX) /*將pos及其后的元素復(fù)制到前一單元*/

　　a[pos-1]=a[pos];

　　pos++;

　　num--;

　　printf("Now,array a:\n");

　　for(i=0;inum;i++)/*輸出刪除后的數(shù)組元素*/

　　printf("%8d",a[i]);

　　中，按算法意圖可以看出，while循環(huán)是將pos及其后的元素復(fù)制到前一單元，在重復(fù)復(fù)制過程中，pos++應(yīng)該與復(fù)制操作（a[pos-1]=a[pos];）同步進(jìn)行，但原程序中卻沒有用花括號(hào)將這兩條語句括起來構(gòu)成循環(huán)體，先將發(fā)現(xiàn)的這個(gè)問題改正了

　　while(posMAX) /*將pos及其后的元素覆蓋前一單元*/

　　a[pos-1]=a[pos];

　　pos++;

　　num--;

　　printf("Now,array a:\n");

　　for(i=0;inum;i++)/*輸出刪除后的數(shù)組元素*/

　　printf("%8d",a[i]);

　　運(yùn)行改正后的程序，結(jié)果正常。這樣，程序的錯(cuò)誤就算排除了。

　　更多的時(shí)候，情形并非如此，可能不能直接從程序試運(yùn)行所得結(jié)果中了解程序執(zhí)行流程信息。有些程序在運(yùn)行時(shí)看不到運(yùn)行結(jié)果，或者程序的輸出結(jié)果看不出程序的執(zhí)行流程。確實(shí)遇到過這樣的情形，程序運(yùn)行后沒有任何輸出，也就不知道程序運(yùn)行后做了些什么，是否結(jié)束運(yùn)行還是停在什么位置，這與程序設(shè)計(jì)風(fēng)格有關(guān)，有些程序甚至在數(shù)據(jù)鍵盤輸入的語句之前，也沒有相應(yīng)的提示信息輸出，應(yīng)該避免這樣的做法。

　　例4.3 需求描述：老鼠走迷宮（參見例2.8）

　　算法描述：（參見文獻(xiàn)[6]）以二維數(shù)組maze表示迷宮，其中元素為0表示走得通、元素為1表示走不通（受阻），路徑只考慮水平和垂直兩個(gè)方向（上下左右）。假設(shè)老鼠從maze[1][1]進(jìn)入迷宮，而迷宮的唯一出口在maze[m][n]（右下角），任一時(shí)刻老鼠在迷宮中的位置為maze[i][j]，它有四個(gè)方向可以試探，設(shè)下一個(gè)位置為maze[g][h]，顯然，若向右走一步，則g=i,h=j+1；向上走一步，則g=i-1,h=j。但當(dāng)老鼠走到迷宮邊緣時(shí)，不可能再有四個(gè)方向可以試探，因此可以將迷宮數(shù)組擴(kuò)大為maze[m+2][n+2]，并令第0、m+1行和第0、n+1列元素均為1（受阻）。那么，老鼠走迷宮的步驟如下：

　　1) 老鼠走進(jìn)迷宮入口；

　　2) 在當(dāng)前位置上從右方開始，然后依下、左、上的順序探測(cè)前進(jìn)方向；

　　3) 向可以進(jìn)入的位置前進(jìn)，即該位置的maze和mark（標(biāo)志數(shù)組）的對(duì)應(yīng)元素均為0。前進(jìn)一步后，將原來位置改為當(dāng)前位置，將標(biāo)志數(shù)組mark的相應(yīng)元素標(biāo)志為1（已走過），并將前一位置坐標(biāo)及進(jìn)入當(dāng)前位置的方向入棧；

　　4) 重復(fù)步驟2和3；

　　5) 若找不到前進(jìn)通路，從原路后退一步（退棧），改變探測(cè)方向，再重復(fù)步驟2和3，以尋找另一條新的通路。

　　6) 重復(fù)步驟2-5，直到走出迷宮或宣布無通路為止。

　　程序：例2.8改正了語法錯(cuò)誤后的函數(shù)mazepath()如下

　　/*ch2_ex8.c*/

　　void mazepath(int move[2][4],int m,int n)

　　int i,j,d,g,h;/*d記錄方向, i,j 為移動(dòng)前坐標(biāo)，g,h為新坐標(biāo)*/

　　mark[1][1]=1;

　　top=0;

　　i=1;

　　j=1;

　　d=0;

　　do

　　g=i+move[0][d];

　　h=j+move[1][d]; /*try*/

　　if((maze[g][h]==0)(mark[g][h]==0))

　　mark[g][h]=1; /*Enter new pos*/

　　top++;

　　stack[top].i=i; /*old pos push*/

　　stack[top].j=j;

　　stack[top].d=d;

　　i=g;

　　j=h;

　　d=0;

　　else

　　if(d3) d=d+1;

　　else

　　if(top0)

　　{ i=stack[top].i;

　　j=stack[top].j;

　　d=stack[top].d;

　　top--;

　　} /*try again*/

　　else

　　printf("No path has been found\n");

　　} while((g==m)(h==n));/*do-while*/

　　printf("Out maze:g=%d,h=%d\n",g,h);

　　在例2.8中省略的函數(shù)init_array()和disp_path()如下：

　　void init_array(int a[MAX_SIZE][MAX_SIZE],int m,int n,int fac)

　　{ /*將數(shù)組元素賦初值fac*/

　　int i,j;

　　for(i=0;i=m+1;i++)

　　for(j=0;j=n+1;j++)

　　a[i][j]=fac;

　　void disp_path()

　　{ /*輸出走出迷宮的路徑*/

　　int k;

　　for(k=0;k=top;k++)

　　printf("row=%d,col=%d\n",stack[k].i,stack[k].j);

　　程序運(yùn)行情況：

　　用如圖4.2所示的迷宮布局?jǐn)?shù)據(jù)，運(yùn)行該程序。

　　運(yùn)行程序并輸入圖4.2b)的迷宮矩陣，結(jié)果輸出：

　　Out maze

　　row=0,col=0

　　row=1,col=1

　　該結(jié)果顯然有問題，因?yàn)?，既然老鼠走出迷宮了，應(yīng)該顯示出完整的路徑，但這里僅顯示老鼠到達(dá)位置（1，1），路徑是不完整的。

　　調(diào)試：

　　首先用數(shù)據(jù)透視法查看數(shù)組mark和maze中的數(shù)據(jù)是否正確，即在main函數(shù)調(diào)用新增的如下函數(shù)：

　　Void disp_array(int a[MAX_SIZE][MAX_SIZE],int m,int n)

　　int i,j;

　　printf("The array:\n");

　　for(i=0;i=row+1;i++)

　　for(j=0;j=col+1;j++)

　　printf("%3d",mark[i][j]);

　　printf("\n");

　　將數(shù)組maze和mark的元素輸出顯示后，發(fā)現(xiàn)數(shù)組中的數(shù)據(jù)是正確的。這樣，把調(diào)試重點(diǎn)放到函數(shù)mazepath中。該函數(shù)主要部分是do循環(huán)，也是老鼠走迷宮算法的主體。不妨用流程觀察分析法來調(diào)試該函數(shù)。為此，在mazepath函數(shù)的do循環(huán)中增加語句

　　printf("i=%d\n",i);

　　且作為do循環(huán)體的第一句。再運(yùn)行該程序，顯示結(jié)果為：

　　i=1

　　Out maze

　　row=0,col=0

　　row=1,col=1

　　從顯示結(jié)果可以看出，do循環(huán)僅僅執(zhí)行了1（i=1）次。分析該循環(huán)控制條件，根據(jù)算法描述，只有當(dāng)老鼠到達(dá)最右下角 (m,n)時(shí)，才能走出迷宮，也就是說，當(dāng)(g==m)(h==m)時(shí)應(yīng)結(jié)束循環(huán)，而繼續(xù)循環(huán)的條件應(yīng)是上述退出循環(huán)條件的非，即(gm)||(hn)，但程序中循環(huán)體末的}后的循環(huán)條件是：

　　while((g==m)(h==n));/*do-while*/

　　當(dāng)程序初始進(jìn)入循環(huán)后g、h的取值只可能是0、1、2，所以執(zhí)行1次就退出循環(huán)了。顯然，這個(gè)條件的表述搞反了。其次，分析if結(jié)構(gòu)，發(fā)現(xiàn)

　　if(top0)

　　{ i=stack[top].i;

　　j=stack[top].j;

　　d=stack[top].d;

　　top--;

　　else

　　printf("No path has been found\n");

　　的else分支在輸出了"No path has been found"信息、報(bào)告沒有通路后，沒有及時(shí)退出該函數(shù)，這將在迷宮無通路時(shí)導(dǎo)致死循環(huán)。因此，將其改正如下

　　if(top0)

　　{ i=stack[top].i;

　　j=stack[top].j;

　　d=stack[top].d;

　　top--;

　　} /*try again*/

　　else

　　printf("No path has been found\n");

　　return;

　　} while((gm)||(hn));/*do-while*/

　　去掉剛剛插入do循環(huán)體的語句Printf("i=%d\n",i)，再試運(yùn)行程序。顯示如下

　　Out maze

　　row=0,col=0

　　row=1,col=1

　　row=1,col=2

　　row=2,col=2

　　row=2,col=3

　　row=3,col=3

　　這個(gè)結(jié)果又出現(xiàn)了新的問題，按算法描述，數(shù)組maze的四周為受阻（不可走），怎么會(huì)輸出0行0列坐標(biāo)，又出口應(yīng)該是（3，4）而堆棧中保存的路徑卻沒有該坐標(biāo)呢？為了找出原因，在if((maze[g][h]==0)(mark[g][h]==0))分支復(fù)合語句中，增加如下輸出語句：

　　if((g==m)||(h==n)) printf("(%d,%d)\n",g,h);

　　作為該復(fù)合語句中的第一條語句，以查看老鼠是否曾到達(dá)坐標(biāo)（3，4）。運(yùn)行結(jié)果顯示，老鼠到達(dá)了出口位置（3，4）。那么，為什么堆棧中沒有記錄呢？分析函數(shù)mazepath代碼，其4行將top賦初值0，do循環(huán)的if分支中第一個(gè)坐標(biāo)入棧前已將top++。這樣，使得stack棧底（0）元素不是老鼠曾經(jīng)所在的位置；同時(shí)，老鼠走出迷宮時(shí)的最后坐標(biāo)(3,4)也不在棧所保存的路徑中，因?yàn)閺某绦蛄鞒贪l(fā)現(xiàn)，其總是將老鼠的上一次所在位置入棧，而當(dāng)老鼠到達(dá)出口時(shí)的位置卻沒有入棧。正確的做法應(yīng)該是，首先將入口位置壓入棧底，而后每前進(jìn)一步就將當(dāng)前位置入棧。依據(jù)上述分析，應(yīng)將mazepath函數(shù)修改為：

　　void mazepath(int move[2][4],int m,int n)

　　int i,j,d,g,h;

　　mark[1][1]=1;

　　top=0;

　　i=1;

　　j=1;

　　d=0;

　　stack[top].i=i; /*迷宮入口位置入棧*/

　　stack[top].j=j;

　　stack[top].d=d;

　　do

　　g=i+move[0][d];

　　h=j+move[1][d];

　　if((maze[g][h]==0)(mark[g][h]==0))

　　mark[g][h]=1; /*Enter new pos*/

　　top++;

　　stack[top].i=g; /*old pos push*/

　　stack[top].j=h;

　　stack[top].d=d;

　　i=g;

　　j=h;

　　d=0;

　　else {

　　if(d3) d=d+1;

　　else

　　if(top0)

　　{ i=stack[top].i;

　　j=stack[top].j;

　　d=stack[top].d;

　　top--;

　　} /*try again*/

　　else

　　printf("No path has been found\n");

　　return;

　　}while((gm)||(hn));/*do-while*/

　　printf("Out maze\n");

　　再運(yùn)行程序，顯示結(jié)果正確。費(fèi)了這么多工夫，終于把它調(diào)試正確了，聽聽音樂輕松一下吧。

　　好了，輕松之后，我們來討論一下迷宮布局的一般情形，如果迷宮的入口不是本例算法描述所指定的（1，1）、以及出口也不是位置（m,n），那么只需要簡(jiǎn)單地修改mazepath函數(shù)中的i、j初始化語句，以及do循環(huán)末尾的while()條件表達(dá)式，即可使程序具有通用性。

　　通常情況下，流程觀察分析法可以幫助我們了解程序執(zhí)行的流程，通過分析程序的執(zhí)行流程，可以發(fā)現(xiàn)程序在實(shí)現(xiàn)算法時(shí)存在的一些差錯(cuò)，從而加以改正。對(duì)于算法流程復(fù)雜、規(guī)模較大的程序調(diào)試，該法是有效的方法。