2013年09月16日

打印螺旋矩阵


题目很简单,打印螺旋数组。

例如:

1  2  3 
8  9  4
7  6  5

1 2 3
4 5 6

分析

此题复杂的地方在于如何准确的控制下标,除了此之外,还需要考虑此矩阵不是N*N类型的,对于M*N的矩形也需要仔细考虑。

我们可以直接根据螺旋的过程来实现打印,从第一个元素开始,向右走N步,然后转向下,需要走的步数则为N-1,然后转向右,需要走的步数依然为N-1,最后往上走,需要走N-2步。这样就螺旋的打印完了最外围一圈,接着是往里的一圈,又重复这样的过程。需要注意的是,每次每个方向走的步数。对于下面的这种情况,只需要走一圈,然后将中间空缺的数据填上。

1  2  3 
12 13 4 
11 14 5
10 15 6
9  8  7

代码

设置变量,控制向左和向下需要打印的数字个数。

#include<iostream>
#include<iomanip>

using namespace std;

void print(int **matrix, int row, int col){
    if(matrix == NULL)
        return;
    int i = 0, j = 0;
    for(i; i < row; i++){
        for(j = 0; j < col; j++){
            cout << setw(4) << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

void print(int **matrix, int dimension){
    if(matrix == NULL || dimension <= 0){
        return;
    }
    int i = 0, j = 0;     
    for(i;i < dimension; i++){
        for(j = 0; j < dimension; j++){
            cout << setw(4) << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

void printMatrix(int **matrix, int dimension){
    if(matrix == NULL || dimension <= 0)
        return;
    int i = 0, j = 0, steps = dimension;
    int circle = steps >> 1;
    int num = 1, k = 0;
    while(k < circle){
        i = j = k;
        while(j < steps){ // fisrt print steps-j elements
            matrix[i][j++] = num++;
        }
        --j;

        while(i < steps - 1){ // 0,1,2,3
            matrix[++i][j] = num++;
        }

        while(j > k){
            matrix[i][--j] = num++;
        }

        while(i > k+1){
            matrix[--i][j] = num++;
        }
        ++k;
        --steps;
    }
    if(dimension & 0x1 == 1)
        matrix[circle][circle] = num;
}

void printMatrix(int **matrix,int row, int col){
    if(matrix == NULL || row <= 0 || col <= 0)
        return;
    int i = 0, j = 0,k = 0;
    int left = col >> 1, down = row >> 1;
    int num = 1;
    while(k < left && k < down){
        i = j = k;
        while(j < col){
            matrix[i][j++] = num++;
        }
        --j;
        ++i;
        while(i < row){
            matrix[i++][j] = num++;
        } 
        --i;
        --j;
        while(j >= k){
            matrix[i][j--] = num++;
        }
        ++j;
        --i;
        while(i >= k+1){
            matrix[i--][j] = num++;
        }
        --row;
        --col;
        ++k;
    }
    if(k == left && k == down){
        if(k != row && k != col)
            matrix[k][k] = num;
    }else if(k == left && k < down){
        if(k != col){
            i = j = k;
            while(i > row){
                matrix[i++][j] = num++;
            }
        }
    }else if(k < left && k == down){
        if(k != row){
            i = j = k;
            while(j < col){
                matrix[i][j++] = num++;
            }
        }
    }
}


void test_printv1(){
    int row;
    int col;
    cout << "row:";
    cin >> row;
    cout << "col:";
    cin >> col;
    int** matrix = new int*[row];
    int i = 0;
    for(i = 0; i < row; i++){
        matrix[i] = new int[col];
    }

    printMatrix(matrix,row);
    print(matrix,row);

    for(i = 0; i < row; i++){
        delete [] matrix[i];
    }
    delete [] matrix;

}

void test_printv2(){
    int row;
    int col;
    cout << "row:";
    cin >> row;
    cout << "col:";
    cin >> col;
    int** matrix = new int*[row];
    int i = 0;
    for(i = 0; i < row; i++){
        matrix[i] = new int[col];
    }

    printMatrix(matrix,row,col);
    print(matrix,row,col);

    for(i = 0; i < row; i++){
        delete [] matrix[i];
    }
    delete [] matrix;
}

int main(){
    test_printv2();
    return 0;
}
前一篇: 最长回文子串 后一篇: Openstack Network学习(五)