二、矩阵遍历

　　矩阵遍历是一个数据结构方面的问题。假设有一个矩阵Matrix，它共有RowCount行，每行有ColCount列，当利用y表示行数，x表示列数，那么利用Matrix[y,x]就可以访问矩阵中的任意元素。假设有一个10×10大小的矩阵，它的遍历方法有以下三种：


此主题相关图片如下：
（图1）
 

在上图中矩阵中的数字表示遍历到元素的先后次序，箭头表示遍历的方向。第一种的一般遍历法在很多编程书上都有介绍，而且经常作为循环代码的示范程序使用。这种遍历方法稍加修改就可以做到从右上角开始、从左下角开始、从右下角开始。这种遍历方法很简单，这里就不多说了。与一般遍历相反，螺旋遍历在所有的编程书和数据结构书上都没有讲到。现在详细的说明一下螺旋遍历。
 

　　螺旋遍历可以做到以一个基点为中心向四周遍历，这个基点可以不是矩阵的中心点，实际上基点可以是矩阵上的任意一点，甚至可以是矩阵外的点。注意：这里所说的“点”是指可以用（y，x）访问的元素，当（y，x）坐标超出矩阵范围，例如（-1，-1），这就是矩阵外的点。可以看出螺旋遍历对于找图找色非常有用。螺旋遍历实现起来并不难，仔细观察图1中的螺旋遍历就会发现遍历可以由遍历方向和遍历步数组成。从（3，2）点开始向上遍历一步，再向右遍历一步，再向下遍历二步，再向左遍历二步，这时完成一轮，遍历方向又开始向上、向右、向下、向左一轮又一轮，同时遍历步数逐步加大。当向上遍历时y总是减1；当向右遍历时x总是加1；当向下遍历时y总是加1；当向左遍历时x总是减1，这样可以根据遍历方向计算出坐标的变化。另外螺旋遍历有可能会访问到矩阵外的点，在访问时要进行判断。正是由于螺旋遍历会访问矩阵外的点，遍历循环将无法停止从而出现死循环。这时要设定一个访问计数VisitCount，当遍历循环访问了矩阵中的所有点后退出循环。综上所述，螺旋遍历的示范代码如下：

type
    //遍历方向
    TAspect = (asLeft, asRight, asUp, asDown);

const
    //移动坐标差
    MoveVal : array [asLeft..asDown] of TPoint = (
        (X : -1; Y :  0), //asLeft
        (X :  1; Y :  0), //asRight
        (X :  0; Y : -1), //asUp
        (X :  0; Y :  1)  //asDown
    );

    //矩阵大小
    RowCount = 10;
    ColCount = 10;

var
    //矩阵
    Matrix : array [0..RowCount-1,0..ColCount-1] of Integer;

//螺旋遍历（不支持步长）
procedure MatrixOrder1_(y,x : Integer);
var
    Aspect : TAspect;
    VisitCount,Count,i : Integer;
begin
    VisitCount:=0;
    Aspect:=asUp;
    Count:=1;
    while VisitCount<(RowCount*ColCount) do
    begin
        for i:=0 to Count-1 do
        begin
            if (x>=0) and (x<ColCount) and
               (y>=0) and (y<RowCount) then
            begin

                //访问矩阵元素
                Matrix[y,x]:=VisitCount;

                VisitCount:=VisitCount+1;
            end;
            x:=x+MoveVal[Aspect].X;
            y:=y+MoveVal[Aspect].Y;
        end;
        case Aspect of
            asLeft  : begin Aspect:=asUp;   Count:=Count+1; end;
            asRight : begin Aspect:=asDown; Count:=Count+1; end;
            asUp    : begin Aspect:=asRight; end;
            asDown  : begin Aspect:=asLeft;  end;
        end;
    end;
end;

　　这里还有一个步长的问题，所谓步长就是指在遍历的时候跳过一些点，只平均访问矩阵中的某些点。例如以下数据就是步长为2以（3，2）为基点的螺旋遍历后的矩阵，其中“-”表示遍历时没有访问到的点。

输出矩阵：
   +  0  1  2  3  4  5  6  7  8  9
 0 :  -  -  -  -  -  -  -  -  -  -
 1 :  8  -  1  -  2  -  9  - 16  -
 2 :  -  -  -  -  -  -  -  -  -  -
 3 :  7  -  0  -  3  - 10  - 17  -
 4 :  -  -  -  -  -  -  -  -  -  -
 5 :  6  -  5  -  4  - 11  - 18  -
 6 :  -  -  -  -  -  -  -  -  -  -
 7 : 15  - 14  - 13  - 12  - 19  -
 8 :  -  -  -  -  -  -  -  -  -  -
 9 : 24  - 23  - 22  - 21  - 20  -

　　使用步长可以实现矩阵的抽样查找，但上面给出的螺旋遍历算法却不支持步长。因为它要利用访问计数退出循环，使用步长时会使矩阵中访问到的点的数目不确定，使的上述算法出现死循环。对上述算法的一个改进是使用一个逻辑变量记录遍历一轮是否有访问到点。如果没有，说明这一轮访问已经以位于矩阵之外可以退出循环。当步长为1时这种改进的算法要比前面的算法更慢，因为它要“空转”一轮。而且这种算法也不支持矩阵外的点作为基点，它会使循环提前退出。支持步长的螺旋遍历算法的示范代码如下：注意这时的VisitCount仅作为测试使用，不作为退出循环的条件。

type
    //遍历方向
    TAspect = (asLeft, asRight, asUp, asDown);

const
    //遍历步长
    Interval = 2;

    //移动坐标差
    MoveVal : array [asLeft..asDown] of TPoint = (
        (X : -Interval; Y : 0), //asLeft
        (X :  Interval; Y : 0), //asRight
        (X : 0; Y : -Interval), //asUp
        (X : 0; Y :  Interval)  //asDown
    );

    //矩阵大小
    RowCount = 10;
    ColCount = 10;

var
    //矩阵
    Matrix : array [0..RowCount-1,0..ColCount-1] of Integer;

//螺旋遍历2（支持步长）
procedure MatrixOrder2(y,x : Integer);
var
    Aspect : TAspect;
    VisitCount : Integer; //访问计数，测试用
    Count,i : Integer;
    Visit : Boolean;
begin
    VisitCount:=0; //访问计数，测试用
    Visit:=false;
    Aspect:=asUp;
    Count:=1;
    while true do
    begin
        for i:=0 to Count-1 do
        begin
            if (x>=0) and (x<ColCount) and
               (y>=0) and (y<RowCount) then
            begin

                //访问矩阵元素
                Matrix[y,x]:=VisitCount;
                VisitCount:=VisitCount+1; //访问计数，测试用

                Visit:=true;
            end;
            x:=x+MoveVal[Aspect].X;
            y:=y+MoveVal[Aspect].Y;
        end;
        case Aspect of
            asLeft : begin
                if not Visit then break;
                Visit:=false;
                Aspect:=asUp;
                Count:=Count+1;
            end;
            asRight : begin Aspect:=asDown; Count:=Count+1; end;
            asUp    : begin Aspect:=asRight; end;
            asDown  : begin Aspect:=asLeft;  end;
        end;
    end;
end;
 
　　对于回形遍历与螺旋遍历大同小异，这里就不多说了。在下面的压缩包中是矩阵遍历的示范程序，里面有一般遍历、螺旋遍历和回形遍历的示范代码，可以用于参考。