博文视点有奖答题第一题：二维数组中的查找

博文视点有奖答题第一题：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#define ROWNUM    	4
#define COLNUM    	4
#define BUFFSIZE  	4096
#define BUFFSPACE	4
#define FOUND     	1
#define NOTFOUND	-1


int *matrix_total, row_num_total, col_num_total;
typedef struct{
	int row;
	int col;
}Position; //This variable is to be used in future, the way to calculate it should be adjusted.


void oops(char *s1, char *s2);
int get_matrix();
void get_row_col(int*, int*);
void print_matrix();
int check_input();
int search_matrix(int, int*, int, int, Position*);


int main(int ac, char* av[]){
	Position pos = {0, 0};


	get_row_col(&row_num_total, &col_num_total);
        matrix_total = (int*)malloc( row_num_total*col_num_total*sizeof(int) );
	if( get_matrix(matrix_total, row_num_total, col_num_total) == -1)
		oops("error in get the matrix", "undefined");	
	
	int target;  
	printf("Please input the number to find\n");
	scanf("%d", &target);
	
	if( search_matrix(target, matrix_total, row_num_total, col_num_total, &pos) == FOUND )
//		printf("%d is in the matrix, row: %d col: %d\n", target, pos.row+1, pos.col+1);
		printf("%d is in the matrix\n", target);
	else
		printf("%d is not in the matrix\n", target);	
	
	return 0;
}


void oops(char * s1, char * s2){
	fprintf(stderr, "Error: %s ", s1);
	perror(s2);
	exit(1);
}


int get_matrix(){
        char *buff, *char_input;


        buff = (char*)malloc( row_num_total*col_num_total*BUFFSPACE*sizeof(char) );


        printf("please input your matrix\n");
        char c;
        while ( (c = getchar()) != '\n' && c != EOF )
                ; 
        if( fgets(buff, BUFFSIZE, stdin) == NULL )
                printf("An error occurs when reading user input\n");


        int num_input = 0, i = 0;
        char_input = strtok(buff, " ");
        while( char_input != NULL ){    
                num_input = atoi(char_input);
                matrix_total[i++] = num_input; 
                char_input = strtok(NULL, " ");
        }
        


        if( i != (row_num_total*col_num_total) ){
                printf("your input did not conform to your declared matrix, please run this program again\n");
                exit(1);
        }


        print_matrix(matrix_total, row_num_total, col_num_total);
        if( check_input(matrix_total, row_num_total, col_num_total) == -1){
		printf("The matrix is not legal\n");
		exit(1);
	}


        free(buff);
        return 0;
}


void get_row_col(int *row_num, int *col_num){
        printf("Please input the number of rows\n");
        scanf("%d", row_num);
        printf("Please input the number of cols\n");
        scanf("%d", col_num);
}
 
void print_matrix(){
        int i, j;
        int k = 0;
        
        printf("Your %d * %d matrix is: \n", row_num_total, col_num_total);
        for(i=0; i<row_num_total; i++){
                for(j=0; j<col_num_total;j++){
                        printf( "%d\t", *(matrix_total+k) );
                        k++;
                }
                printf("\n");
        }
}


int check_input(){
        int count = 0;
        int i, j;
        int *matrix;
		
		matrix = matrix_total; 
        for(i=0; i<row_num_total; i++)
                for(j=0; j<col_num_total; j++){
                        if(i == 0 && j == 0)
                                ;
                        if(i == 0 && j > 0)
                                if(*matrix < *(matrix - 1)){
                                        printf("row %d, col %d: %d is illegal, please run this program again\n", i+1, j+1, *matrix);
                                        return -1;
                                }
                        if(i > 0 && j == 0)
                                if(*matrix < *(matrix - col_num_total*i)){
                                        printf("row %d, col %d: %d is illegal, please run this program again\n", i+1, j+1, *matrix);
                                        return -1;
                                }       
                        if(i > 0 && j > 0)
                                if( *matrix < *(matrix - col_num_total*i) || *matrix < *(matrix - 1) ){
                                        printf("row %d, col %d: %d is illegal, please run this program again\n", i+1, j+1, *matrix);
                                        return -1;
                        }


                        matrix++;
                        count++;
        }
        if(count != row_num_total*col_num_total){
                printf("Your matrix contains %d elements which not equals to %d * %d\n", count, row_num_total, col_num_total);
                return -1;
        }
                
        return 0;
}


int search_matrix(int target, int *matrix, int row_num, int col_num, Position *pos){
	int diag, i, j;


	diag = row_num<col_num? row_num : col_num;
	if(row_num < 3 || col_num < 3){
		for(i=0; i<row_num; i++)
			for(j=0; j<col_num; j++)
				if( target == *(matrix + i*col_num_total + j) ){
					pos->row += i;
					pos->col += j;
					return FOUND;
				}
		return NOTFOUND;
	}else{
		if(target < *matrix)
			return NOTFOUND;


		i = 0, j = diag;
		while(i < diag){
			if( target == *(matrix+i+i*col_num_total) ){
				pos->row += i;
				pos->col += i;
				return FOUND;
			}
			if( target < *(matrix+i+i*col_num_total) ){
				pos->row += i;
				pos->col += i;
				if( search_matrix(target, (matrix + i*col_num_total), row_num-i, i, pos) == FOUND )
					return FOUND;
				if( search_matrix(target, (matrix + i), i, col_num-i, pos) == FOUND )
					return FOUND;
				return NOTFOUND;
			}
			if( target > *(matrix+i+i*col_num_total) ){
				i++;
			}
		}
		return NOTFOUND;
	}
}