当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

线性查找二维数组

发表于: 2012-06-05   作者:hao3100590   来源:转载   浏览:
摘要: 1.算法描述 有序(行有序,列有序,且每行从左至右递增,列从上至下递增)二维数组查找,要求复杂度O(n)   2.使用到的相关知识: 结构体定义和使用,二维数组传递(http://blog.csdn.net/yzhhmhm/article/details/2045816)   3.使用数组名传递 这个的不便之处很明显,一旦确定就是不能设置列值 //使

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;
};

//如果找到放回下标,否则-1
int 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;
}
 

线性查找二维数组

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺
1 bool Find(int *matrix,int rows,int clumns,int number) 2 { 3 bool found=false; 4 if(matrix!=
二维数组中的查找 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完
二维数组由行和列组成。由arr[$i][$j]表示,先后表示行和列,类似于坐标点。 打印二维数组-----通过
源代码 #ifndef SEARCHDATA_TWODIMENSION_H #define SEARCHDATA_TWODIMENSION_H #include<iostre
我们门来看一下题目:在一个数组中,每一行都按照从左往右递增的顺序排序。每一列都按照从上到下递
问题:在一个二维数组中,每行的元素从左到右是递增的,每列元素从上到下是递增的。写一个函数,查
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号