2 D配列検索2 Dはいれつけんさく
4727 ワード
1.int a; int*a; int **a; int (*a)[10]; int(*a)(int)の違い.
a)int aは整数を格納するためのメモリ空間を表す.
b)int*aは、整数を格納する空間、すなわちa)に記載された空間を指すポインタを格納するためのメモリ空間を指す.
c)int**aはメモリ空間を表し、この空間はポインタを格納するために使用され、このポインタはポインタを格納する空間を指し、この空間のポインタを指し、整数を指す.b)で述べた空間を指す.
d)int(*a)[10]は、長さ10、タイプintの配列を指すポインタを格納するためのメモリ空間を表し、int**aとの差は主にa++に現れる.
e)int(*a)(int)はメモリ空間を表し、この空間はポインタを格納するために使用され、このポインタは関数を指し、この関数にはint型のパラメータがあり、関数の戻りタイプもintである.
2.配列を宣言するとき、配列の名前もポインタです.32ビットシステムでは,任意のポインタに対してsizeofを求め,得られた結果はいずれも4であった.配列が関数パラメータとして伝達されると,配列は自動的に同型のポインタに劣化する.
3.例題:2 D配列の検索.
2 D配列の各行は、配列に整数が含まれているかどうかを判断するために、左から右へ増加し、上から下へ増加して並べ替えられます.
解決策:一番右の列の最初の数を見つけて、探している数より大きい場合は、その列はもう考えなくてもいいし、探している数より小さい場合は、その行はもう考えなくてもいい.再帰的に解く.
a)int aは整数を格納するためのメモリ空間を表す.
b)int*aは、整数を格納する空間、すなわちa)に記載された空間を指すポインタを格納するためのメモリ空間を指す.
c)int**aはメモリ空間を表し、この空間はポインタを格納するために使用され、このポインタはポインタを格納する空間を指し、この空間のポインタを指し、整数を指す.b)で述べた空間を指す.
d)int(*a)[10]は、長さ10、タイプintの配列を指すポインタを格納するためのメモリ空間を表し、int**aとの差は主にa++に現れる.
e)int(*a)(int)はメモリ空間を表し、この空間はポインタを格納するために使用され、このポインタは関数を指し、この関数にはint型のパラメータがあり、関数の戻りタイプもintである.
2.配列を宣言するとき、配列の名前もポインタです.32ビットシステムでは,任意のポインタに対してsizeofを求め,得られた結果はいずれも4であった.配列が関数パラメータとして伝達されると,配列は自動的に同型のポインタに劣化する.
3.例題:2 D配列の検索.
2 D配列の各行は、配列に整数が含まれているかどうかを判断するために、左から右へ増加し、上から下へ増加して並べ替えられます.
解決策:一番右の列の最初の数を見つけて、探している数より大きい場合は、その列はもう考えなくてもいいし、探している数より小さい場合は、その行はもう考えなくてもいい.再帰的に解く.
#include<iostream>
using namespace std;
int findnumber(const int* array,int number,int &nrows,int &ncols,const int rows,const int cols) //int ** array ,
{
if(nrows==0||ncols==0)
return 0;
else if(*(array+(rows-nrows)*cols+ncols-1)==number)
return 1;
else if(*(array+(rows-nrows)*cols+ncols-1)>number)
{
ncols-=1;
findnumber(array,number,nrows,ncols,rows,cols);
}
else if(*(array+(rows-nrows)*cols+ncols-1)<number)
{
nrows-=1;
findnumber(array,number,nrows,ncols,rows,cols);
}
}
int main() //main() int, bool
{
int array[4][4]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
int rows=4;
int cols=4;
int nrows=rows;
int ncols=cols;
int number=7;
cout<<findnumber(array[0],number,nrows,ncols,rows,cols);
}