/***********************************************************
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样
的一个二维数组和一个整数，判断数组中是否含有该整数。
************************************************************/
#include <stdio.h>
//在二维数组中寻找给定值
bool findValueInMatrix
(int* matrix, int columns, //不使用二维数组做参数是因为这样做需要先知道数组的列数
int rows, int value)//扩展性小;这里需要注意二维数组与一维数组之间的关系
{
bool found =false;
if(matrix != NULL && columns !=0 && rows != 0)//排除参数无效的情况
{
int row = 0;
int column = columns - 1;
while(row < rows && column >=0 ){
if(value == matrix[row * columns + column]) //从右上角开始寻找
{
found = true;
break; //如果找到数值，不要忘记退出循环
}
else if(value < matrix[row * columns + column])
column--; //如果值小于数组右上角的值，往左寻找
else
row++; //如果值大于数组右上角的值，往下寻找
}
}
return found;
}
//单元测试
void test(int* matrix, int columns,int rows, int value){
if(findValueInMatrix(matrix,columns,rows,value) == true)
{
printf("Found !\n");
}
else
printf("Not found !\n");
}
//一般情况先找到值
void test1()
{
int matrix1[3][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13}};//二维数组表示
test((int*)matrix1,4,3,7); //注意二维数组名和一维指针之间的转换
}
//最大情况下发现该值
void test2()
{
int matrix1[3][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13}};
test((int*)matrix1,3,4,13);
}
//最小情况下发现该值
void test3()
{
int matrix1[3][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13}};
test((int*)matrix1,3,4,1);
}
//没有找到该值
void test4()
{
int matrix1[3][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13}};
test((int*)matrix1,3,4,3);
}
//输入是空的
void test5()
{
//int matrix1[0][0] = NULL;数组不能为空
test(NULL,0,0,7);
}
int main()
{
test1();
test2();
test3();
test4();
test5();
return 0;
}
==参考剑指offer面试题3 |
转播
