先介绍一下这个数据结构的定义,Young Tableau有一个m*n的矩阵,然后有一数组 a[k], 其中 k<=m*n ,然后把a[k]中的数填入 m*n 的矩阵中,填充规则为:
1. 每一行每一列都严格单调递增(有其他的版本是递减,其原理相同)。
2. 如果将a[k]中的数填完后,矩阵中仍有空间,则填入 ∞。
举例:
这里主要给出杨氏矩阵的定义和查找
方法:理由每一列,没一行都是递增的,我们从左上角开始查找,不断的缩小矩阵的大小,最后只剩一1*1的矩阵。
C++代码:
#pragma once
//YoungTableau.h
#include <iostream>
class YoungTableau
{
public:
YoungTableau(int rows, int columns,int**newTable)
{
x = rows; //行数
y = columns; //列数 if (newTable!=NULL)
{
table = (int **)((new int[rows*columns]));
for (int i = ; i < rows*columns; i++) {
((int*)table)[i] = ((int*)newTable)[i];
std::cout << ((int*)table)[i] << std::endl;
} } };
~YoungTableau();
private:int x;
private:int y;
private: int **table; public:
void print_matrix(void)
{
std::cout <<x<<y << std::endl;
if (table != NULL)
{
for (int i = ; i < x; i++)
for (int j = ; j < y; j++)
std::cout << ((int*)table)[i*y+j]<<std:: endl;
}
}
public:int get_element(int rows, int columns,int*res)
{
if (res != NULL)
{
if (rows>=this->x || columns >= this->y)
{
*res = ;
return -;
}
else
{
*res = ((int*)table)[rows*y + columns];
return ;
}
}
else
{
*res = ;
return -;
}
}
private:bool IsEqualAtLeftTop(int data, int rownum, int columnnum)
{
if (this->table != NULL)
{
if (rownum >= x || columnnum >= y || (rownum == x - && columnnum == && data != ((int*)this->table)[rownum*y + columnnum]))
{
std::cout << "illgal column" << std::endl;
return false;
}
else if (data == ((int*)this->table)[rownum*y + columnnum])
{
return true;
}
else if (data < ((int*)this->table)[rownum*y + columnnum])
{
std::cout << "next column"<< std::endl;
if (columnnum == )
return false;
else
return IsEqualAtLeftTop(data, rownum, columnnum - );
}
else
{
std::cout << "next row" << std::endl;
if (rownum == x-)
return false;
else
return IsEqualAtLeftTop(data, rownum+, columnnum);
} }
else
{
return false;
}
}
public:bool IsExistence(int data)
{
if (this->table != NULL)
{
/*for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++)
{
if (data == ((int*)table)[i*y + j])
return true;
}
return false;*/
return IsEqualAtLeftTop(data, , y - );
}
return false;
} };
// Young_Tableau.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include "YoungTableau.h" int _tmain(int argc, _TCHAR* argv[])
{
int tmp_table[][] =
{
{, , },
{, , },
{, , }
};
YoungTableau matrix(,,(int**)tmp_table);
matrix.print_matrix();
int tmp = ;
matrix.get_element(,,&tmp);
std::cout << tmp << std::endl; if (matrix.IsExistence()==true)
std::cout <<"true"<< std::endl;
else std::cout << "false" << std::endl;
while ();
return ;
}
#include "stdafx.h"
#include "YoungTableau.h"
// YoungTableau.cpp : 类的实现
// YoungTableau::~YoungTableau()
{ }