在笔试题目中看到一个关于杨氏矩阵（Young Tableau）的问题，说实话，杨氏矩阵我还是第一次听说，就在网上百度谷歌了一番，感觉这个数据结构还蛮有意思的。而且这个数据结构在做增、删、查找的复杂度都比较低。以前只知道学书本上面的问题，现在才知道不能光学课本，还要了解那些能够在实际中有用的东西。

首先介绍一下这个数据结构的定义，杨氏矩阵就是有一个m*n的矩阵，让后有一数组 a[k], 其中 k<=m*n ，然后把a[k]中的数填入 m*n 的矩阵中，填充规则为：

1. 每一行每一列都严格单调递增（有其他的版本是递减，其原理相同）；
2. 如果将a[k]中的数填完后，矩阵中仍有空间，则填入 ∞。

1	2	3	4	5	6
1	3	5	7	8	11	a
2	6	9	14	15	19	b
4	10	21	23	33	57	c
34	37	45	55	56	∞	d
∞	∞	∞	∞	∞	∞	e

 

现在讨论一下插入操作、删除操作和查找操作的详细过程：

插入操作：

本操作的时间复杂度为O( n + m ),其操作类似于堆排序算法。它的堆的结构在这里表现为某个元素Y[x, y] 下面和右面的两个元素 Y[x, y+1] ,Y[x+1, y]均比Y[x, y]要大。于是其插入算法可以描述为，首先把待插入元素以行为主序置于所有有效数字（除了无穷以外的数）最后面，然后执行类似于排序操作，将x与它左边（记为x-l）及上面（记为x-u）的数进行比较，根据比较结果有三种可能的操作：

1. x-u > x 且x-u >= x-l  则将x 与 x-u进行交换；
2. x-l > x 且x-l > x-u  则将x 与 x-l进行交换；
3. x >= x-l 且 x > x-u  则x 不动，此时已经插入成功。

插入操作的过程如下：

1 //Insert 算法要求首先把待插入的数值放在矩阵的右下角 2 //即最后一行数据的最后一个空余位置 3 bool insertElement(int newValue) 4 { 5     if(yangMatrix[ROW-1][COLUMN-1]!=MAX_VALUE)//数组已经满了 6         return false; 7  8     int row=ROW-1 ,column=COLUMN-1; 9     yangMatrix[row][column]=newValue;10 11     int x_upper,x_left;12     while(true)13     {14         if(row>0) 15             x_upper=yangMatrix[row-1][column];16         else17             x_upper=MIN_VALUE;18 19         if(column>0) 20             x_left=yangMatrix[row][column-1];21         else22             x_left=MIN_VALUE;23 24         if(x_upper>newValue&&x_upper>=x_left)//和上面的交换位置25         {26             yangMatrix[row][column]=x_upper;27             yangMatrix[row-1][column]=newValue;28             row--;29         }30         else if(x_left>newValue&&x_upper

 

删除操作：

操作类似于插入操作，其时间复杂度也为O(m+n)。删除算法可以描述为，首先将删除的位置(x, y)的数字删除，然后调整，把杨氏矩阵中的最大值k（可以行为主序进行搜索到最后）填入到被删除位置，然后让此数与其下面的数(k-d)和右面的数进行(k-r)比较,此时比较结果为两种，因为此时元素一定会下移：

1. k-d > k-r 将k-r 和 k进行交换
2. k-d < k-r 将k-d 和 k进行交换  

删除操作如下所示：

1 bool deleteElement(MyPoint p) 2 { 3     if(p.x>=ROW||p.y>=COLUMN) 4     { 5         return false; 6     } 7  8     //杨氏矩阵的最大值 9     int maxElement=0;10     int currentColumn,maxColumn,maxRow;11     for (int i=0;i
      
       x_bottom)42         {43             yangMatrix[p.x+1][p.y]=maxElement;44             yangMatrix[p.x][p.y]=x_bottom;45             p.x++;46         }47         else if(x_right
      

 

查找操作：

查找算法类似于BST二叉排序树，不过需要在其思想上稍微进行修改，才能满足杨氏矩阵的查找操作，同样利用杨氏矩阵的性质，不过此时应该换一个角度思考问题，因为与BST二叉排序树类比，所以应该从左下角开始看起，该元素的上面的元素比本身小和右面的元素比本身大，这样就与BST二叉排序树具有相同的性质。所以在查找时从左下角不断的比较，从而最终确定所查找元素位置。

查找操作如下所示：

1 MyPoint * searchElement(int myValue) 2 { 3     MyPoint * point =(MyPoint*)malloc(sizeof(MyPoint)); 4     int row=ROW-1,column=0,temp1,temp2; 5     while(yangMatrix[row][column]!=myValue){ 6         if (row<=0) 7         { 8             if(yangMatrix[row][column]>myValue){ 9                 if (column
      
       =COLUMN-1)17         {18             if(yangMatrix[row][column]
       
        0) row--;20                 else 21                     break;22             } 23             else 24                 break;25         }26         if(row>0&&column
        
         abs(temp2)){30                 column++;31             }else{32                 row--;33             }34         }35     }36 37     if(yangMatrix[row][column]!=myValue){38         point->x=-1;39         point->y=-1;40     } else {41         point->x=row;42         point->y=column;43     }44     return point;45 }
        
       
      

我自己动手写了一些插入、删除和查找的代码，全部的程序如下所示：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 /************************************************************************/  5 /*   6 杨氏矩阵基本操作。  7 首先介绍一下这个数据结构的定义，Young Tableau有一个m*n的矩阵，让后有一数组 a[k], 其中k<=m*n ，然后把a[k]中的数填入 m*n 的矩阵中，填充规则为：  8 1.  每一行每一列都严格单调递增（有其他的版本是递减，其原理相同）。  9 2.  如果将a[k]中的数填完后，矩阵中仍有空间，则填入 ∞。 10 */ 11 /************************************************************************/ 12 #include 
         
           13 #include 
          
            14 using namespace std; 15 #define ROW 4 16 #define COLUMN 6 17 #define MAX_VALUE 65535 18 #define MIN_VALUE -65535 19  20 int originalArray[]={
    1,    3,5,7,8,11,4,6,9,14,15,19,10,21,23,33,56,57,34,37,45,55}; 21 unsigned int yangMatrix[ROW][COLUMN]={MAX_VALUE}; 22 int nextPosition=0; 23  24 struct MyPoint{ 25     int x; 26     int y; 27 }; 28  29 void printArray() 30 { 31     for (int i=0;i
           
            0) 68 x_upper=yangMatrix[row-1][column]; 69 else 70 x_upper=MIN_VALUE; 71 72 if(column>0) 73 x_left=yangMatrix[row][column-1]; 74 else 75 x_left=MIN_VALUE; 76 77 if(x_upper>newValue&&x_upper>=x_left)//和上面的交换位置 78 { 79 yangMatrix[row][column]=x_upper; 80 yangMatrix[row-1][column]=newValue; 81 row--; 82 } 83 else if(x_left>newValue&&x_upper
            
             =ROW||p.y>=COLUMN)101 {102 return false;103 }104 105 //杨氏矩阵的最大值106 int maxElement=0;107 int currentColumn,maxColumn,maxRow;108 for (int i=0;i
             
              x_bottom)139 {140 yangMatrix[p.x+1][p.y]=maxElement;141 yangMatrix[p.x][p.y]=x_bottom;142 p.x++;143 }144 else if(x_right
              
               myValue){168 if (column
               
                =COLUMN-1)176 {177 if(yangMatrix[row][column]
                
                 0) row--;179 else 180 break;181 } 182 else 183 break;184 }185 if(row>0&&column
                 
                  abs(temp2)){189 column++;190 }else{191 row--;192 }193 }194 }195 196 if(yangMatrix[row][column]!=myValue){197 point->x=-1;198 point->y=-1;199 } else {200 point->x=row;201 point->y=column;202 }203 return point;204 }205 206 int main(){207 initYangMatrix();208 printf("After init:\n");209 printArray();210 211 nextPosition=sizeof(originalArray)/sizeof(int);212 213 int insertValue=2;214 insertElement(insertValue);215 printf("Insert a Value %d:\n",insertValue);216 printArray();217 218 struct MyPoint p={ 0,2};219 deleteElement(p);220 printf("After delete the position(%d,%d):\n",p.x,p.y);221 printArray();222 223 int searchVaule=24;224 MyPoint *point=searchElement(searchVaule);225 if(point->x==-1&&point->y==-1)226 printf("Sorry, but %d is not in his Matrix.\n",searchVaule);227 else 228 printf("The value %d's location is:position(%d,%d).\n",searchVaule,point->x,point->y);229 230 searchVaule=23;231 point=searchElement(searchVaule);232 if(point->x==-1&&point->y==-1)233 printf("Sorry, but %d is not in his Matrix.\n",searchVaule);234 else 235 printf("The value %d's location is:position(%d,%d).\n",searchVaule,point->x,point->y);236 237 return 0;238 }