算法导论练习6—3 Young氏矩阵

算法导论习题6—3 Young氏矩阵Young氏矩阵具有从左到右元素顺次排列，从上到下元素顺次排列。该代码实现了从

算法导论习题6—3 Young氏矩阵

Young氏矩阵具有从左到右元素顺次排列，从上到下元素顺次排列。该代码实现了从矩阵中抽取最小元素，并重新调整young氏矩阵，插入元素并重新调整矩阵，查找元素。这三个函数的时间复杂度都是lg（m+n），其中m是矩阵行数，n是矩阵列数。

//Young氏矩阵，性质从左到右顺序排列，从上到下顺序排列#include<iostream>using namespace std;#define M 100#define N 100//该函数为对Young氏矩阵的调整，目的是维持Young氏矩阵的性质void MaxYoung(int (*a)[4],int m,int n,int i,int j){int r=i,t=j;int temp;if(a[r+1][t]<a[r][t]&&(r+1)<m){r=r+1;}if(r>i){if(a[r][t]>a[r-1][t+1]&&(t+1)<n){r=r-1;t=t+1;}}else{if(a[r][t]>a[r][t+1]&&(t+1)<n){t=t+1;}}if(r!=i||t!=j){temp=a[i][j];a[i][j]=a[r][t];a[r][t]=temp;MaxYoung(a,m,n,r,t);}}//extreat the min element and adjust the array!int ExtractMin(int (*a)[4],int m,int n ){if(a[0][0]==0x7fffffff){cout<<"the Young is empty!"<<endl;return 0x7fffffff;}int max;max=a[0][0];a[0][0]=0x7fffffff;MaxYoung(a,m,n,0,0);return max;}//Insert num into A,and A is Young array.//the time complexity is lg(m+n)//the way is insert the num into the A at the last position//and adjust the Young

bool Insert(int (*a)[4],int m,int n,int num){int i,temp;if(a[m-1][n-1]<0x7fffffff){cout<<"the Young is full !"<<endl;return 0;}else{a[m-1][n-1]=num;for(i=n-2;i>=0;i--){if(a[m-1][i]>a[m-1][i+1]){temp=a[m-1][i];a[m-1][i]=a[m-1][i+1];a[m-1][i+1]=temp;}else break;}if(i==-1){for(i=m-2;i>=0;i--){if(a[i][0]>a[i+1][0]){temp=a[i][0];a[i][0]=a[i+1][0];a[i+1][0]=temp;}else break;}}}return 1;}//find the  num in a[][].the time complexity is lg(m+n)//the way is compare the num with the upright element,if equal return.//else if less than the element,delete the most right rank,//else if big than the element,delete the most up row//row and rank is the location of the element we need!//if we can'f find the element ,row and rank are all -1bool FindElement(int (*a)[4],int m,int n,int num,int &row,int &rank){row=rank=-1;int i=0,j=n-1;int target;while(i<=m-1&&j>=0){if(a[i][j]==num){row=i+1;rank=j+1;return 1;}else if(a[i][j]>num){j--;}else{i++;}}return 0;}int main(){int a[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};int min;min=ExtractMin(a,4,4);cout<<min<<endl;if(Insert(a,4,4,1))cout<<a[0][0]<<endl;int row,rank;if(FindElement(a,4,4,12,row,rank)){cout<<"the "<<12<<"is exit in a and the row num is :"<<row<<" the rank num is :"<<rank<<endl;}else {cout<<"there is no "<<12<<"in a!"<<endl;}return 0;}

改代码中的缺陷是二维数组传参依然没有得到解决，预期今天解决。

1楼mishifangxiangdefeng昨天 14:13: 不错，越写越好了，继续坚持！