第C語言楊氏矩陣查找算法實(shí)例講解目錄一、楊氏矩陣介紹二、查找算法1.查找思路2.步驟3.代碼三、楊氏矩陣?yán)}代碼特別注意四、總結(jié)本文以C語言實(shí)現(xiàn)，介紹楊氏矩陣中通用的查找算法。

一、楊氏矩陣介紹

楊氏矩陣種，每一行的數(shù)都從左到右遞增，每一列的數(shù)都從上到下遞增。如下圖是一個(gè)簡(jiǎn)單的楊氏矩陣：

有一個(gè)數(shù)字矩陣，矩陣的每行從左到右是遞增的，矩陣從上到下是遞增的，請(qǐng)編寫程序在這樣的矩陣中查找某個(gè)數(shù)字是否存在。

要求：時(shí)間復(fù)雜度小于O(N)

二、查找算法

1.查找思路

楊氏矩陣是很有特點(diǎn)的，它有規(guī)律遞增的特點(diǎn)決定了針對(duì)表中的任一元素，它的下方和右方的數(shù)一定大于我，左方和上方的數(shù)一定小于我，所以查找的時(shí)候可利用這一特點(diǎn)，從右上角或者左下角來找。

因?yàn)檫@兩個(gè)位置的大于小于有區(qū)分度。例如，若選擇從右上角找，那么沒有上邊和右邊，而下邊一定比我大，左邊一定比我小。那么，如果要查找的數(shù)比遍歷到的元素大，那我就向下查找；如果比遍歷到的元素小，那我就向左查找。

這樣查找的次數(shù)只有x+y-1次，符合題目中要求的O(n)。

2.步驟

3.代碼

intCheck(inta[ROW][COL],introw,intcol,intk){

intx=0;

inty=col-1;

while(x=row-1y=0){

if(ka[x][y]){//比我大就向下

x++;

elseif(ka[x][y]){//比我小就向左

y--;

else{

return1;//相等：找到了

return0;//沒有找到

intmain(){

inta[ROW][COL]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};//示例

intk=0;//要查找的數(shù)

printf("請(qǐng)輸入你要找的數(shù)：\n");

while(~scanf("%d",k)){

if(Check(a,ROW,COL,k)){

printf("找到了！\n");

else{

printf("該數(shù)不存在！\n");

return0;

}

三、楊氏矩陣?yán)}

傳送門

代碼

該題相當(dāng)于是前面楊氏矩陣查找的直接運(yùn)用。注意，當(dāng)題干中出現(xiàn)一個(gè)二維數(shù)組array中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序這樣的描述時(shí)，要立馬反應(yīng)過來它是楊氏矩陣。可能不會(huì)每道題的矩陣都像{{1，2，3，4}，{5，6，7，8}，{9，10，11，12}}這樣規(guī)整，但只要關(guān)注并發(fā)現(xiàn)它的行按一定順序（從左到右或從右到左）遞增，且列也按一定順序（從上到下或從下到上）遞增，那么就可以運(yùn)用楊氏矩陣算法。（有時(shí)候可能題干數(shù)組會(huì)是從右向左遞增，從下向上遞增，剛好和楊氏矩陣反一反，但方法通用。）

boolFind(inttarget,int**array,intarrayRowLen,int*arrayColLen){

intx=0;

inty=*arrayColLen-1;

while(xarrayRowLeny=0){

if(array[x][y]target){

y--;

}elseif(array[x][y]target){

x++;

}else{

returntrue;

returnfalse;

}

特別注意

針對(duì)這串代碼，這里必須附上特別說明。傳二維數(shù)組入函數(shù)，函數(shù)頭寫了形參為int**array，注意這并不是直接傳二維數(shù)組名時(shí)的形參接收方式。

若實(shí)參部分直接傳二維數(shù)組數(shù)組名array，則形參應(yīng)寫為：

//列參數(shù)不可省略

voidfun(intarray[][col]);

或

//一維數(shù)組指針

voidfun(int(*array)[col]);

而用int**array接收，則調(diào)用方應(yīng)該這樣寫：

#includestdio.h

boolFind(inttarget,int**array,intarrayRowLen,int*arrayColLen){

intx=0;

inty=*arrayColLen-1;

while(xarrayRowLeny=0){

if(array[x][y]target){

y--;

}elseif(array[x][y]target){

x++;

}else{

returntrue;

returnfalse;

intmain(){

inta1[]={1,2,8,9};

inta2[]={2,4,9,12};

inta3[]={4,7,10,13};

inta4[]={6,8,11,15};

int*p[]={a1,a2,a3,a4};

intarrayRowLen=4;

intarrayColLen=4;

//傳入指針數(shù)組的數(shù)組名，數(shù)組p內(nèi)的元素是指針類型，存放的是另外四個(gè)一維數(shù)組名

printf("%d",Find(100,p,arrayRowLen,arrayColLen));

retu