杨氏矩阵的增删改查

本文主要是介绍杨氏矩阵的增删改查，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

杨氏矩阵一左上角斜着往下看可以使小顶堆的树

#include<iostream>
#define INFINITY 100000
using namespace std;
class CYoungTableau
{
private:
int m_nRow;
int m_nCol;
int **m_pData;

public:

CYoungTableau(int row, int col);
~CYoungTableau();
void Init(int row, int col);
void Destory();
bool Insert(int x);
bool Insert2(int x);
void Delete(int row, int col);
bool Find(int x, int&row, int&col) const;
void Print() const;
};

CYoungTableau::CYoungTableau(int row, int col)
{
Init(row, col);
}

CYoungTableau::~CYoungTableau()
{
Destroy();
}

/*****************插入方法1,一行插完再插另一行*********************/
bool CYoungTableau::Insert(int x)
{
int row=m_nRow-1;
int col=m_nCol-1;
if(m_pData[row][col]<INFINITY)//杨氏矩阵已满，因为右下角不是无穷而是数
return false;
m_pData[row][col]=x;
int r=row;
int c=col; //从右下角往左上角找
while((row>=0)|| (col>=0))
{
if((row>=1)&&(m_pData[row-1][col]>m_pData[r][c]))
{
r=row-1;
c=col;
}
if((col>=1)&&(m_pData[row][col-1]>m_pData[r][c]))//不能用else。这里先和上边比，比完后再拿上边和左边比，左边大于上边和左边换，避免（17，19;20,'INFINITY ';）插入20;
{
r=row; //上左都大于该数，则选择与较大的换，若换较小的可能出错。
c=col-1;
}
if((r==row)&&(c==col))
break;
swap(m_pData[row][col],m_pData[r][c]);
row=r;
col=c;
}
return true;
}

/*****************插入方法2，优先插入逆对角线左上部插入*********************/
bool IsBig(int a, int b)
{
if( rand()%2==0) //有%50的概率为>=,有%50的概率为>。
return a>=b;
return a>b;
}

bool CYoungTableau::Insert2(int x)
{
int row=m_nRow-1;
int col=m_nCol-1;
if(m_pData[row][col]<INFINITY)
return false;
m_pData[row][col]=x;
int r=row;
int c=col;
while((row>=0)||(col>=0))
{
if((row>=1)&&m_pData[row-1][col]>m_pData[r][c])
{
r=row-1;
c=col;
}
if((col>=1) && IsBig(m_pData[row][col-1],m_pData[r][c]))
{
r=row;
c=col-1;
}
if((r==row)&&(c==col))
break;
swap(m_pData[row][col],m_pData[r][c]);
row=r;
col=c;
}
return true;
}

bool CYoungTableau::Find(int x, int& row, int &col) const
{
row=0;
col=m_nCol-1;
while((row<m_nRow) && (col>=0))
{
if(m_pData[row][col]==x)
return true;
if(x>m_pData[row][col])
row++;
else
col--;
}
return false;
}

void CYoungTableau::Delete(int row, int col)
{
int r=row;
int c=col;
while((row<m_nRow)&&(col<m_nCol))
{
if(m_pData[row][col]==INFINITY)
break;
if(row+1<m_nRow)
{
r=row+1;
c=col;
}
if((col+1<m_nCol) && (m_pData[row][col+1]<m_pData[r][c]))//删除数的下边和右边相比谁小，用谁替换
{
r=row;
c=col+1;
}
if((row==r)&&(col==c))
break;
m_pData[row][col]=m_pData[r][c];
row=r;
col=c;
}
m_pData[m_nRow-1][m_nCol-1]=INFINITY;
}