线性查寻二维数组

线性查找二维数组

1.算法描述

有序（行有序，列有序，且每行从左至右递增，列从上至下递增）二维数组查找，要求复杂度O(n)

?

2.使用到的相关知识：

结构体定义和使用，二维数组传递（http://blog.csdn.net/yzhhmhm/article/details/2045816）

?

3.使用数组名传递

这个的不便之处很明显，一旦确定就是不能设置列值

//使用数组名实现(不便之处很明显：列值确定了，不能灵活)loc* findValue(int a[][5], int row, int value){int col = sizeof(a)/sizeof(int)*row;cout<<"size:"<<col<<endl;//先按列比较(第0列)，找到所在的行int currRow = 0;for(int i=0; i<row; i++){if(a[i][0] > value){if(i != 0) currRow = i - 1;break;}}int index = search(a[currRow], 5, value);//利用结构体指针loc *l;l->row = currRow;l->col = index;return l;}

?

4.使用指针数组传递

//使用指针数组实现loc findValue(int* a[], int row, int col, int value){//先按列比较(第0列)，找到所在的行int currRow = 0;for(int i=0; i<row; i++){if(a[i][0] > value){if(i != 0) currRow = i - 1;break;}}int index = search(a[currRow], col, value);loc l;l.row = currRow;//在给定的行中搜索l.col = index;return l;}

?

5.所有代码

/***有序（行有序，列有序，且每行从左至右递增，列从上至下递增）二维数组查找*要求复杂度O(n)*/#include <iostream>using namespace std;struct loc{ int row; int col;};//如果找到放回下标，否则-1int search(int *a, int length, int value){int i=0,j=length-1;while(i<=j){int center = (i+j)/2;if(a[center]<value) i=center+1;else if(a[center]>value) j=center-1;else return center;}return -1;}//使用数组名实现(不便之处很明显：列值确定了，不能灵活)loc* findValue(int a[][5], int row, int value){int col = sizeof(a)/sizeof(int)*row;cout<<"size:"<<col<<endl;//先按列比较(第0列)，找到所在的行int currRow = 0;for(int i=0; i<row; i++){if(a[i][0] > value){if(i != 0) currRow = i - 1;break;}}int index = search(a[currRow], 5, value);//利用结构体指针loc *l;l->row = currRow;l->col = index;return l;}//使用指针数组实现loc findValue(int* a[], int row, int col, int value){//先按列比较(第0列)，找到所在的行int currRow = 0;for(int i=0; i<row; i++){if(a[i][0] > value){if(i != 0) currRow = i - 1;break;}}int index = search(a[currRow], col, value);loc l;l.row = currRow;//在给定的行中搜索l.col = index;return l;}int main(){int a[5][5],k=0;for(int i=0; i<5;i++){for(int j=0; j<5; j++){a[i][j] = k++;}}int value;cout<<"输入要查找的值：";cin>>value;//---------1---------loc* ll = findValue(a, 5,value);if(ll->col != -1){cout<<"位置在:("<<ll->row<<","<<ll->col<<")"<<endl;}else{cout<<"没有找到！"<<endl;}//---------2---------//使用指针数组，必须先将二维数组转换为下面的形式int *p[] = {*a, *(a+1),*(a+2),*(a+3),*(a+4)};loc l = findValue(p, 5,5,value);if(l.col != -1){cout<<"位置在:("<<l.row<<","<<l.col<<")"<<endl;}else{cout<<"没有找到！"<<endl;}return 0;}