域外網誌

/*
    作者：    wencan
    Mail:    wencan#live.cn
    Site:    blog.wencan.me
    日期：    2011/11/22
*/

/*蚊香数组
如：
1       2       3       4       5       6
20      21      22      23      24      7
19      32      33      34      25      8
18      31      36      35      26      9
17      30      29      28      27      10
16      15      14      13      12      11
*/

//螺旋遍历解决

//数组宽度
const int Width=6;

struct _Array
{
    int num;//数值
    int x;    //行
    int y;    //列
};

typedef struct _Array Array;

void fun(Array **pArray,int width)
{
    //元素总数
    int total=Width*Width;
   
    //螺旋遍历开始
    //从左上角元素开始
    Array *p=pArray[0];   
    for(int i=0,j=0,w=width,_w=0;i<total; )
    {
        //i统计已遍历的元素的个数
        //j统计遍历过程中折向的次数
        //w为每条直线的宽度
        //_w为当前直线遍历过的元素的个数。
        //故，当_w==w时，当前直线遍历结束，遍历折向
        p->num=++i;
        _w++;
        if(_w==w)
        {
            //遍历折向
            switch(j%4)
            {
                case 0:
                    //移至相邻的下边的元素
                    p=pArray[p->x+1]+p->y;
                    break;
                case 1:
                    //移至相邻的左边的元素
                    p=pArray[p->x]+p->y-1;
                    break;
                case 2:
                    //移至相邻的上边的元素
                    p=pArray[p->x-1]+p->y;
                    break;
                case 3:
                    //移至相邻的右边的元素
                    p=pArray[p->x]+p->y+1;
                    break;
                default:
                    break;
            }
           
            _w=0;
            j++;//折向次数加1

            //直线宽度减1
            if(j%2)
                w–;
        }
        else
        {
            //遍历不折向
            switch(j%4)
            {
                case 0:
                    //移至相邻的右边的元素
                    p=pArray[p->x]+p->y+1;
                    break;
                case 1:
                    //移至相邻的下边的元素
                    p=pArray[p->x+1]+p->y;
                    break;
                case 2:
                    //移至相邻的左边的元素
                    p=pArray[p->x]+p->y-1;
                    break;
                case 3:
                    //移至相邻的上边的元素
                    p=pArray[p->x-1]+p->y;
                    break;
                default:
                    break;
            }
        }
    }
   
}

int main(int argc,char **argv)
{
    //构造动态二维数组
    Array ** pArray=(Array **)malloc(Width*sizeof(Array *));
    for(int i=0;i<Width;i++)
    {
        pArray[i]=(Array *)malloc(Width*sizeof(Array));
        for(int j=0;j<Width;j++)
        {
            pArray[i][j].num=0;
            pArray[i][j].x=i;
            pArray[i][j].y=j;
        }
    }
   
    //计算数组内的数值
    fun(pArray,Width);

    //输出
    for(int i=0;i<Width;i++)
    {
        for(int j=0;j<Width;j++)
            printf("%d\t",pArray[i][j].num);
        printf("\n");
    }       

    //释放
    for(int i=0;i<Width;i++)
        free(pArray[i]);
    free(pArray);

}