Posted on 2007-07-23 17:51
ZelluX 阅读(409)
评论(0) 编辑 收藏 所属分类:
Algorithm
CLRS上第六章的习题，以前感觉挺难的，现在仔细想了发现其实和堆是一样的。
/* Min-Young tableaus on Page 143 */
#include <iostream>
#include <iomanip>
using namespace std;
template <class Type>
class YTable
{
private:
Type** data;
int m, n;
const static int INFINITY = 9999;
public:
YTable(int m = 10, int n = 10);
~YTable();
int Insert(Type x);
int FloatUp(int x, int y);
int Print();
int Extract(int x, int y, Type value);
};
template <class Type>
YTable<Type>::YTable(int m, int n)
{
this->m = m;
this->n = n;
data = new Type*[m];
for (int i = 0; i < m; i++)
data[i] = new Type[n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
data[i][j] = INFINITY;
}
template <class Type>
YTable<Type>::~YTable()
{
for (int i = 0; i < m; i++)
delete [] data[i];
delete [] data;
}
template <class Type>
int YTable<Type>::Insert(Type x)
{
if (data[m - 1][n - 1] != INFINITY)
return 0;
data[m - 1][n - 1] = x;
FloatUp(m - 1, n - 1);
return 1;
}
template <class Type>
int YTable<Type>::FloatUp(int x, int y)
{
int maxX = x;
int maxY = y;
if (x > 0 && data[x - 1][y] > data[maxX][maxY])
{
maxX = x - 1;
maxY = y;
}
if (y > 0 && data[x][y - 1] > data[maxX][maxY])
{
maxX = x;
maxY = y - 1;
}
if (maxX != x || maxY != y)
{
swap(data[maxX][maxY], data[x][y]);
FloatUp(maxX, maxY);
}
return 1;
}
template <class Type>
int YTable<Type>::Print()
{
cout.setf(ios::fixed);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
if (data[i][j] != INFINITY)
cout << setw(3) << data[i][j];
else
cout << " X ";
cout << endl;
}
return 1;
}
template <class Type>
int YTable<Type>::Extract(int x, int y, Type value)
{
data[x][y] = value;
FloatUp(x, y);
return 1;
}
int main()
{
YTable<int> myTable(4, 4);
int x[] = {9, 16, 3, 2, 4, 8, 1, 5, 14, 12, 7, 11, 10, 15, 13, 6};
for (int i = 0; i < 16; i++)
myTable.Insert(x[i]);
cout << "Initial state:\n";
myTable.Print();
cout << "\nNow change (4,3) to 5:\n";
myTable.Extract(3, 2, 5);
myTable.Print();
return 0;
}