本文主要是介绍第二十三章：杨氏矩阵查找、排序、添加、删除，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Young氏矩阵
在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
算法思想：
//杨氏矩阵
#include <iostream>
using namespace std; #define ROW 4
#define COL 4//杨氏矩阵调整,右下调整
void Young_down_heapify(int arr[][COL],int i,int j){int min_i,min_j;if (j+1<COL && arr[i][j]>arr[i][j+1]){min_i=i,min_j=j+1;}else {min_i=i,min_j=j;}if (i+1<ROW && arr[min_i][min_j] > arr[i+1][j]){min_i=i+1,min_j=j;} if (min_i!=i || min_j!=j ){swap( arr[i][j],arr[min_i][min_j]);Young_down_heapify(arr,min_i,min_j);}
}
//杨氏矩阵调整，左上调整
void Young_up_heapify(int arr[][COL],int i,int j){int max_i,max_j;if(j>0&&arr[i][j]<arr[i][j-1]){max_i=i,max_j=j-1;}else{max_i=i,max_j=j;}if(i>0&&arr[max_i][max_j]<arr[i-1][j]){max_i=i-1,max_j=j;}if(max_i!=i||max_j!=j){swap(arr[i][j],arr[max_i][max_j]);Young_up_heapify(arr,max_i,max_j);}
}
//pop出最小元素
int Young_pop(int arr[][COL]){int minV=arr[0][0];arr[0][0]=arr[ROW-1][COL-1];arr[ROW-1][COL-1]=INT_MAX;Young_down_heapify(arr,0,0);return minV;
}//删除元素
void Young_delete(int arr[][COL],int i,int j){arr[i][j]=arr[ROW-1][COL-1];arr[ROW-1][COL-1]=INT_MAX;Young_down_heapify(arr,i,j);
}void Young_insert(int arr[][COL], int key){if(arr[ROW-1][COL-1]<INT_MAX){cout<<"杨氏矩阵元素已满"<<endl;return;}arr[ROW-1][COL-1]=key;Young_up_heapify(arr,ROW-1,COL-1);
}
//杨氏矩阵查找迭代法
//从右上角到左下角搜索
bool Young_search(int arr[][COL],int target){int i=0,j=COL-1;int var=arr[i][j];while(true){if(var==target)return true;else if(var<target&&i<ROW-1)var = arr[++i][j];else if(var>target&&j>0)var = arr[i][--j];else return false;}
}
//杨氏矩阵查找递归版
bool Young_search(int arr[][COL],int i,int j,int key){if(i>=ROW||j<0)return false;if(arr[i][j]==key)return true;if(arr[i][j]<key)return Young_search(arr,i+1,j,key);else return Young_search(arr,i,j-1,key);
}
void Young_make(int arr[][COL],int key[]){for(int i=0;i<ROW*COL;i++){Young_insert(arr,key[i]);}
}
//排序
//设元素个数为n^2个，则时间复杂度为O(n^3)
void Young_sort(int arr[][COL]){cout<<"杨氏矩阵排序："<<endl;for(int i=0;i<ROW*COL;++i){cout<<Young_pop(arr)<<" ";}cout<<endl;
}
//print
void print(int arr[][COL]){for(int i=0;i<ROW;++i){for(int j=0;j<COL;++j)printf("%d\t",arr[i][j]);printf("\n");}
}
int main()
{ //int arr[ROW][COL]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};//int target=13;//if(Young_search(arr,target))cout<<"存在"<<endl;//if(Young_search(arr,0,COL-1,target))cout<<"存在"<<endl;int key[]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};int arr[ROW][COL];for(int i=0;i<ROW;i++)for(int j=0;j<COL;j++)arr[i][j]=INT_MAX;////Young_make(arr,key);print(arr);//生成的杨氏矩阵为：//1 2 4 6//2 4 7 8//8 9 10 11//9 12 13 15Young_sort(arr);
}
这篇关于第二十三章：杨氏矩阵查找、排序、添加、删除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
