快捷導(dǎo)航

C語言楊氏矩陣實例教你編寫

更新時間：2023年02月01日 14:52:24 作者：莫陌尛.

楊氏矩陣是一個數(shù)字矩陣，矩陣的每一行從左到右一次遞增，矩陣從上到下遞增，在這樣的矩陣中查找一個數(shù)字是否存在。時間復(fù)雜度小于O(N)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪

一、楊氏矩陣是什么

一個數(shù)字矩陣，矩陣的每一行從左到右一次遞增，矩陣從上到下遞增，在這樣的矩陣中查找一個數(shù)字是否存在。時間復(fù)雜度小于O(N)。

二、編寫步驟

1.首先給出一個三乘三的矩陣，我們想找到數(shù)字7是否在這個數(shù)組之中，如圖所示。

2. 我們給出的方法是一種從右上角開始，另一種是從左下角開始。比如從右上角開始，編寫一個函數(shù)。

3. 函數(shù)的編寫。從右上角開始，將右上角數(shù)字與數(shù)字7比較，如果數(shù)字7大于右上角的數(shù)字（3）(因為第一行最大的數(shù)字是右上角的數(shù)字（3），可以確定所判斷的數(shù)字不在第一行)，那么排除第一行，且行數(shù)加一繼續(xù)判斷右上角數(shù)字與數(shù)字7的大??；如果數(shù)字7小于右上角的數(shù)字(3),那么排除第一列，且列數(shù)減一繼續(xù)判斷。至到判斷到數(shù)字與7相等，返回1；否則判斷到左下角數(shù)字，未能與數(shù)字7相等，返回0。

4. 函數(shù)的返回類型是int，返回1或者0，判斷如果為1，證明數(shù)組矩陣存在數(shù)字7，反之沒有。

1.代碼的編寫

int FindNum(int arr[3][3],int k,int row,int col)
{
	int x = 0;
	int y = col-1;
	while(x<=row&&y>=0)
	{
		if(arr[x][y]<k)
		{
			x++;
		}
		else if(arr[x][y]>k)
		{
			y--;
		}
		else
		//找到了；
		return 1;
	}
	//找不到
	return 0;
}
int main()
{
	int arr[3][3]={{1,2,3},{4,5,6},{7,8,9}};
	int k = 7;
	int ret = FindNum(arr,k,3,3);
	if(ret ==1)
	{
		printf("找到了\n");
	}
	else
	printf("找不到\n");
	return 0;
}

2.運行結(jié)果

三、程序的改進(jìn)

在數(shù)組矩陣中，如果能找到相應(yīng)的數(shù)字如7，那么在基礎(chǔ)之上輸出數(shù)字的下標(biāo)。

1.代碼的編寫

int FindNum(int arr[3][3],int k,int* px,int* py)
{
	int x = 0;
	int y = *py-1;
	while(x<=*py&&y>=0)
	{
		if(arr[x][y]<k)
		{
			x++;
		}
		else if(arr[x][y]>k)
		{
			y--;
		}
		else
		{//找到了；
			*px = x;
			*py = y;
			return 1;
		}
	}
	//找不到
	return 0;
}
int main()
{
	int arr[3][3]={{1,2,3},{4,5,6},{7,8,9}};
	int k = 7;
	int x = 3;
	int y = 3;
	//返回型參數(shù)
	int ret = FindNum(arr,k,&x,&y);
	if(ret ==1)
	{
		printf("找到了\n");
		printf("下標(biāo)是:%d,%d\n",x,y);
	}
	else
	printf("找不到\n");
	return 0;
}``

2.運行結(jié)果