首页 > 代码库 > 杨氏矩阵定义及其查找的实现C++
杨氏矩阵定义及其查找的实现C++
先介绍一下这个数据结构的定义，Young Tableau有一个m*n的矩阵，然后有一数组 a[k], 其中 k<=m*n ，然后把a[k]中的数填入 m*n 的矩阵中，填充规则为：
1. 每一行每一列都严格单调递增（有其他的版本是递减，其原理相同）。
2. 如果将a[k]中的数填完后，矩阵中仍有空间，则填入 ∞。
举例：
这里主要给出杨氏矩阵的定义和查找
方法：理由每一列，没一行都是递增的，我们从左上角开始查找，不断的缩小矩阵的大小，最后只剩一1*1的矩阵。
C++代码：
1 #pragma once 2 //YoungTableau.h 3 #include <iostream> 4 class YoungTableau 5 { 6 public: 7 YoungTableau(int rows, int columns,int**newTable) 8 { 9 x = rows; //行数 10 y = columns; //列数 11 12 if (newTable!=NULL) 13 { 14 table = (int **)((new int[rows*columns])); 15 for (int i = 0; i < rows*columns; i++) 16 17 { 18 ((int*)table)[i] = ((int*)newTable)[i]; 19 std::cout << ((int*)table)[i] << std::endl; 20 } 21 22 } 23 24 }; 25 ~YoungTableau(); 26 private:int x; 27 private:int y; 28 private: int **table; 29 30 public: 31 void print_matrix(void) 32 { 33 std::cout <<x<<y << std::endl; 34 if (table != NULL) 35 { 36 for (int i = 0; i < x; i++) 37 for (int j = 0; j < y; j++) 38 std::cout << ((int*)table)[i*y+j]<<std:: endl; 39 } 40 } 41 public:int get_element(int rows, int columns,int*res) 42 { 43 if (res != NULL) 44 { 45 if (rows>=this->x || columns >= this->y) 46 { 47 *res = 0; 48 return -1; 49 } 50 else 51 { 52 *res = ((int*)table)[rows*y + columns]; 53 return 0; 54 } 55 } 56 else 57 { 58 *res = 0; 59 return -2; 60 } 61 } 62 private:bool IsEqualAtLeftTop(int data, int rownum, int columnnum) 63 { 64 if (this->table != NULL) 65 { 66 if (rownum >= x || columnnum >= y || (rownum == x - 1 && columnnum == 0 && data != ((int*)this->table)[rownum*y + columnnum])) 67 { 68 std::cout << "illgal column" << std::endl; 69 return false; 70 } 71 else if (data =http://www.mamicode.com/= ((int*)this->table)[rownum*y + columnnum]) 72 { 73 return true; 74 } 75 else if (data < ((int*)this->table)[rownum*y + columnnum]) 76 { 77 std::cout << "next column"<< std::endl; 78 if (columnnum == 0) 79 return false; 80 else 81 return IsEqualAtLeftTop(data, rownum, columnnum - 1); 82 } 83 else 84 { 85 std::cout << "next row" << std::endl; 86 if (rownum == x-1) 87 return false; 88 else 89 return IsEqualAtLeftTop(data, rownum+1, columnnum); 90 } 91 92 } 93 else 94 { 95 return false; 96 } 97 } 98 public:bool IsExistence(int data) 99 {100 if (this->table != NULL)101 {102 /*for (int i = 0; i < x; i++)103 for (int j = 0; j < y; j++)104 {105 if (data =http://www.mamicode.com/= ((int*)table)[i*y + j])>106 return true;107 }108 return false;*/109 return IsEqualAtLeftTop(data, 0, y - 1);110 }111 return false;112 }113 114 };
1 // Young_Tableau.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include "YoungTableau.h" 6 7 int _tmain(int argc, _TCHAR* argv[]) 8 { 9 int tmp_table[3][3] = 10 {11 {1, 3, 4 },12 {2, 3, 6},13 {5, 8, 10}14 };15 YoungTableau matrix(3,3,(int**)tmp_table);16 matrix.print_matrix();17 int tmp = 0;18 matrix.get_element(2,2,&tmp);19 std::cout << tmp << std::endl;20 21 if (matrix.IsExistence(5)==true)22 std::cout <<"true"<< std::endl;23 else std::cout << "false" << std::endl;24 while (1);25 return 0;26 }
1 #include "stdafx.h" 2 #include "YoungTableau.h" 3 // YoungTableau.cpp : 类的实现 4 // 5 6 7 YoungTableau::~YoungTableau() 8 { 9 10 }
杨氏矩阵定义及其查找的实现C++
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。