爱悠闲 > 算法导论 6-3 Young氏矩阵

算法导论 6-3 Young氏矩阵

分类: 算法导论  |  标签: 算法导论,Young氏矩阵  |  作者: mishifangxiangdefeng 相关  |  发布日期 : 2014-07-22  |  热度 : 653°

一、题目



二、思考

a)不唯一
2	3	4	5
8	9	12	
14	16	
c)
提取Y[1][1],并用ox7FFFFFFF填充。然后向右下调整
YOUNG-EXTRACR-MIN(Y)
1    if  Y[1][1] == 0X7FFFFFFF
2        then error "heap underflow"
3    min <- Y[1][1]
4    A[1][1] <- 0X7FFFFFFF
5    MAX-HEAPIFY(Y, 1, 1)
6    return min
//递归
MIN-YOUNGIFY(Y, i, j)
 1    min <- Y[i][j]
 2    mini <- i
 3    minj <- j
 4    if i < m and Y[i+1][j] < min
 5        mini <- i+1
 6        minj <- j
 7        min <- Y[i+1][j]
 8    if j < n and Y[i+1][j+1] < min
 9        mini <- i
10        minj <- j+1
11        min <- Y[i][j+1]
12    if i != mini or j != minj
13        exchange Y[i][j] <-> Y[mini][minj]
14        MIN-YOUNGIFY(Y, mini, minj)
d)
//若表未满,插入到右下角,然后向左上调整
MIN-YOUNG-INSERT(Y, key)
 1    if Y[m][n] < 0x7fffffff
 2        then error "young overflow"
 3    Y[m][n] <- key
 4    flag <-  true
 5    i <- m
 6    j <- n
 7    max <- key
 8    maxi <- i
 9    maxj <- j
10    while true
11        if i > 1 and max < Y[i-1][j]
12            maxi <- i - 1
13            maxj <- j
14            max <- Y[i-1][j]
15        if j > 1 and max < Y[i][j-1]
16            maxi <- i
17            maxj <- j-1
18            max <- Y[i][j-1]
19        if max == Y[i][j]
20            break
21        exchange Y[maxi][maxj] <-> Y[i][j]
22        i <- maxi
23        j <- maxj
24        max <- Y[i][j]
e)排序过程为:
取下矩阵Y[1][1]元素,O(1)
将Y[1][1]置为0x7FFFFFFF,O(1)
调整矩阵,O(n)
对n^2个结点各执行一次,因此时间为O(n^3)
f)
从左下角开找,若比它小,则向上,则比它大,则向右找
FIND-YOUNG-KEY(Y, key)
 1    i <- m
 2   j <- 0
 3   while i >= 1 and j <= n
 4       if Y[i][j] = key
 5       then return true
 6       else if Y[i][j] < key
 7       then j++
 8       else if Y[i][j] > key
 9       then i--
10   return false


三、代码

(1)Young.h

//头文件
#include <iostream>
#include <stdio.h>
using namespace std;

//宏定义
#define N 100

class Young
{
	public:
	//成员变量
	int Y[N+1][N+1];
	int m, n;
	//构造与析构
	Young(){}
	Young(int a, int b);
	//Heap(int size):length(size),heap_size(size){}
	~Young(){}
	//功能函数
	void Min_Youngify(int i, int j);
	void Build_Min_Young();
	void YoungSort();
	bool Find_Young_key(int key);
	//优先队列函数
	void Young_Decrease_Key(int i, int j, int key);
	void Min_Young_Insert(int key);
	int Young_Minimum();
	int Young_Extract_Min();
	void Young_Delete(int i, int j);
	//辅助函数
	void Print();
};

Young::Young(int a, int b):m(a),n(b)
{
	int i, j;
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
			Y[i][j] = 0x7fffffff;
	}
}

void Young::Build_Min_Young()
{
	int i, j, s;
	for(s = m + n; s >= 2; s--)
	{
		for(i = 1; i <= m; i++)
		{
			j = s - i;
			if(j > n)continue;
			if(j < 1)break;
			Min_Youngify(i, j);
		}
	}
}

int Young::Young_Extract_Min()
{
	int Min = Y[1][1];
	Y[1][1] = 0x7fffffff;
	Min_Youngify(1, 1);
	return Min;
}

void Young::Min_Youngify(int i, int j)
{
	int Min = Y[i][j], mini = i, minj = j;
	if(i < m && Y[i+1][j] < Min)
	{
		mini = i + 1;
		minj = j;
		Min = Y[i+1][j];
	}
	if(j < n && Y[i][j+1] < Min)
	{
		mini = i;
		minj = j + 1;
		Min = Y[i][j+1];
	}
	if(i != mini || j != minj)
	{
		swap(Y[i][j], Y[mini][minj]);
		Min_Youngify(mini, minj);
	}
}

void Young::Min_Young_Insert(int key)
{
	if(Y[m][n] < 0x7fffffff)
	{
		cout<<"error:young overflow"<<endl;
		return ;
	}
	Y[m][n] = key;
	int i = m, j = n, Max = key, maxi = i, maxj = j;
	while(true)
	{
		if(i > 1 && Max < Y[i-1][j])
		{
			maxi = i - 1;
			maxj = j;
			Max = Y[i-1][j];
		}
		if(j > 1 && Max < Y[i][j-1])
		{
			maxi = i;
			maxj = j - 1;
			Max = Y[i][j-1];
		}
		if(Max == Y[i][j])
			break;
		swap(Y[maxi][maxj], Y[i][j]);
		i = maxi;
		j = maxj;
		Max = Y[i][j];
	}
}

bool Young::Find_Young_key(int key)
{
	int i = m, j = 0;
	while(i >= 1 && j <= n)
	{
		if(Y[i][j] == key)
			return true;
		else if(Y[i][j] < key)
			j++;
		else if(Y[i][j] > key)
			i--;
	}
	return false;
}

void Young::Print()
{
	int i, j;
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
			cout<<Y[i][j]<<' ';
		cout<<endl;
	}
}

void Young::Young_Delete(int i, int j)
{
	Y[i][j] = 0x7fffffff;
	Min_Youngify(i, j);
}

void Young::Young_Decrease_Key(int i, int j, int key)
{
	if(key > Y[i][j])
	{
		cout<<"error:new key is larger than current key"<<endl;
		return ;
	}
	Y[i][j] = key;
	int Max = key, maxi, maxj;
	while(true)
	{
		if(i > 1 && Max < Y[i-1][j])
		{
			maxi = i - 1;
			maxj = j;
			Max = Y[i-1][j];
		}
		if(j > 1 && Max < Y[i][j-1])
		{
			maxi = i;
			maxj = j - 1;
			Max = Y[i][j-1];
		}
		if(Max == key)
			break;
		swap(Y[maxi][maxj], Y[i][j]);
		i = maxi;
		j = maxj;
	}
}

int Young::Young_Minimum()
{
	return Y[1][1];
}

void Young::YoungSort()
{
	while(Y[1][1] != 0x7fffffff)
	{
		cout<<Young_Extract_Min()<<' ';
	}
	cout<<endl;
}

(2)main.cpp

#include <iostream>
#include "Young.h"
using namespace std;

int main()
{
	int m, n, x;
	char c;
	cin>>m>>n;
	//输入随机测试数据
	Young *Y = new Young(m, n);
	int i, j;
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
			Y->Y[i][j] = rand() % 100;
	}
	Y->Print();
	//建堆
	Y->Build_Min_Young();
	Y->Print();
	//测试成员函数
	while(cin>>c)
	{
		switch(c)
		{
		case 'E':
			cout<<Y->Young_Extract_Min()<<endl;
			break;
		case 'P':
			Y->Print();
			break;
		case 'I':
			x = rand() % 100;
			cout<<x<<endl;
			Y->Min_Young_Insert(x);
			break;
		case 'F':
			cin>>x;
			cout<<Y->Find_Young_key(x)<<endl;
			break;
		}
	}
	return 0;
}