C語言楊氏矩陣查找算法實例講解
本文以C語言實現(xiàn)，介紹楊氏矩陣中通用的查找算法。
一、楊氏矩陣介紹
楊氏矩陣種，每一行的數(shù)都從左到右遞增，每一列的數(shù)都從上到下遞增。如下圖是一個簡單的楊氏矩陣：
有一個數(shù)字矩陣，矩陣的每行從左到右是遞增的，矩陣從上到下是遞增的，請編寫程序在這樣的矩陣中查找某個數(shù)字是否存在。
要求：時間復(fù)雜度小于O(N)
二、查找算法
1.查找思路
楊氏矩陣是很有特點的，它有規(guī)律遞增的特點決定了針對表中的任一元素，它的下方和右方的數(shù)一定大于我，左方和上方的數(shù)一定小于我，所以查找的時候可利用這一特點，從右上角或者左下角來找。
因為這兩個位置的大于小于有區(qū)分度。例如，若選擇從右上角找，那么沒有上邊和右邊，而下邊一定比我大，左邊一定比我小。那么，如果要查找的數(shù)比遍歷到的元素大，那我就向下查找；如果比遍歷到的元素小，那我就向左查找。
這樣查找的次數(shù)只有x+y-1次，符合題目中要求的O(n)。
2.步驟
3.代碼
int Check(int a[ROW][COL],int row,int col,int k) {
int x = 0;
int y = col - 1;
while(x <= row-1 && y >= 0){
if (k > a[x][y]) { //比我大就向下
x++;
}
else if (k < a[x][y]) { //比我小就向左
y--;
}
else {
return 1; //相等：找到了
}
}
return 0; //沒有找到
}
int main() {
int a[ROW][COL] = { {1,2,3,4},{5,6,7,8},{9,10,11,12}};//示例
int k = 0; //要查找的數(shù)
printf("請輸入你要找的數(shù)：\n");
while(~scanf("%d", &k)){
if (Check(a, ROW, COL, k)) {
printf("找到了！\n");
}
else {
printf("該數(shù)不存在！\n");
}
}
return 0;
}三、楊氏矩陣例題
代碼
該題相當于是前面楊氏矩陣查找的直接運用。注意，當題干中出現(xiàn) “一個二維數(shù)組array中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序” 這樣的描述時，要立馬反應(yīng)過來它是楊氏矩陣。可能不會每道題的矩陣都像{{1，2，3，4}，{5，6，7，8}，{9，10，11，12}}這樣規(guī)整，但只要關(guān)注并發(fā)現(xiàn)它的行按一定順序（從左到右或從右到左）遞增，且列也按一定順序（從上到下或從下到上）遞增，那么就可以運用楊氏矩陣算法。（有時候可能題干數(shù)組會是從右向左遞增，從下向上遞增，剛好和楊氏矩陣反一反，但方法通用。）
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
int x = 0;
int y = *arrayColLen - 1;
while(x < arrayRowLen && y >= 0){
if(array[x][y] > target) {
y--;
}else if(array[x][y] < target) {
x++;
}else{
return true;
}
}
return false;
}特別注意
針對這串代碼，這里必須附上特別說明。傳二維數(shù)組入函數(shù)，函數(shù)頭寫了形參為int** array，注意這并不是直接傳二維數(shù)組名時的形參接收方式。
若實參部分直接傳二維數(shù)組數(shù)組名array，則形參應(yīng)寫為：
//列參數(shù)不可省略 void fun(int array[][col]);
或
//一維數(shù)組指針 void fun(int (*array)[col]);
而用int** array接收，則調(diào)用方應(yīng)該這樣寫：
#include<stdio.h>
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
int x = 0;
int y = *arrayColLen - 1;
while(x < arrayRowLen && y >= 0){
if(array[x][y] > target) {
y--;
}else if(array[x][y] < target) {
x++;
}else{
return true;
}
}
return false;
}
int main(){
int a1[]={1,2,8,9};
int a2[]={2,4,9,12};
int a3[]={4,7,10,13};
int a4[]={6,8,11,15};
int* p[] = {a1,a2,a3,a4};
int arrayRowLen = 4;
int arrayColLen = 4;
//傳入指針數(shù)組的數(shù)組名，數(shù)組p內(nèi)的元素是指針類型，存放的是另外四個一維數(shù)組名
printf("%d",Find(100, p,arrayRowLen ,&arrayColLen));
return 0;
}四、總結(jié)
概括來說，楊氏矩陣查找的算法是根據(jù)楊氏矩陣中數(shù)遞增規(guī)律特點設(shè)計的，而這種設(shè)計算法的思路可以遷移。若題干變換為其它類型的、其中數(shù)具有變化規(guī)律的矩陣，要能想起楊氏矩陣的查找算法，并嘗試將這種設(shè)計的思路遷移到變式中去。
到此這篇關(guān)于C語言楊氏矩陣查找算法實例講解的文章就介紹到這了,更多相關(guān)C語言楊氏矩陣內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++排序算法之冒泡排序解析,從左到右,相鄰兩數(shù)兩兩比較,若下標小的數(shù)大于下標大的數(shù)則交換,將最大的數(shù)放在數(shù)組的最后一位,,再次遍歷數(shù)組,將第二大的數(shù),放在數(shù)組倒數(shù)第二的位置,以此類推,直到數(shù)組有序需要的朋友可以參考下2023-10-10
這篇文章主要介紹了C語言二叉樹的非遞歸遍歷,包括了先序遍歷、中序遍歷與后序遍歷,需要的朋友可以參考下2014-09-09
大家好，本篇文章主要講的是C++實現(xiàn)水仙花數(shù)判斷實例，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
逆波蘭式指的是操作符在其所控制的操作數(shù)后面的表達式。本文主要介紹了C++棧實現(xiàn)逆波蘭式的應(yīng)用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細介紹了C++實現(xiàn)Huffman的編解碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C++中的友元函數(shù)與友元類詳情，對類的封裝是C++三大特性中的一個重要特性,封裝好的數(shù)據(jù)在類的外部是訪問不到的但是一旦出了問題,想要操作被封裝的數(shù)據(jù)怎么辦呢？由此友元函數(shù)友元類誕生了，下文我們來詳細來接一下具體的有緣類吧2022-02-02
本篇文章主要介紹了C++讀入XML文件，讀取和設(shè)置xml配置文件是最常用的操作,TinyXML是一個開源的解析XML的C++解析庫，感興趣的小伙伴們可以參考一下。2016-12-12
QT出現(xiàn)沒有MySQL驅(qū)動手動編譯詳細步驟
這篇文章主要給大家介紹了關(guān)于QT出現(xiàn)沒有MySQL驅(qū)動手動編譯詳細步驟的相關(guān)資料,文中通過圖文介紹的非常詳細,對大家學(xué)習或者使用QT具有一定的參考學(xué)習價值,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了C++中指針和引用的區(qū)別詳解的相關(guān)資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了C語言中組成不重復(fù)的三位數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11