算法导论 6-3 Young氏矩阵

柔情只为你懂 2022-05-15 11:43 149阅读 0赞

# 一、题目 #

![1347537936_2367.gif][]

# 二、思考 #

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a）不唯一  
2.  2   3   4   5  
3.  8   9   12    
4.  14  16    
5.  c）  
6.  提取Y\[1\]\[1\]，并用ox7FFFFFFF填充。然后向右下调整  
7.  YOUNG-EXTRACR-MIN(Y)  
8.  1    if  Y\[1\]\[1\] == 0X7FFFFFFF  
9.  2        then error "heap underflow"  
10. 3    min <- Y\[1\]\[1\]  
11. 4    A\[1\]\[1\] <- 0X7FFFFFFF  
12. 5    MAX-HEAPIFY(Y, 1, 1)  
13. 6    return min  
14. //递归  
15. MIN-YOUNGIFY(Y, i, j)  
16.  1    min <- Y\[i\]\[j\]  
17.  2    mini <- i  
18.  3    minj <- j  
19.  4    if i < m and Y\[i+1\]\[j\] < min  
20.  5        mini <- i+1  
21.  6        minj <- j  
22.  7        min <- Y\[i+1\]\[j\]  
23.  8    if j < n and Y\[i+1\]\[j+1\] < min  
24.  9        mini <- i  
25. 10        minj <- j+1  
26. 11        min <- Y\[i\]\[j+1\]  
27. 12    if i != mini or j != minj  
28. 13        exchange Y\[i\]\[j\] <-> Y\[mini\]\[minj\]  
29. 14        MIN-YOUNGIFY(Y, mini, minj)  
30. d）  
31. //若表未满，插入到右下角，然后向左上调整  
32. MIN-YOUNG-INSERT(Y, key)  
33.  1    if Y\[m\]\[n\] < 0x7fffffff  
34.  2        then error "young overflow"  
35.  3    Y\[m\]\[n\] <- key  
36.  4    flag <-  true  
37.  5    i <- m  
38.  6    j <- n  
39.  7    max <- key  
40.  8    maxi <- i  
41.  9    maxj <- j  
42. 10    while true  
43. 11        if i > 1 and max < Y\[i-1\]\[j\]  
44. 12            maxi <- i - 1  
45. 13            maxj <- j  
46. 14            max <- Y\[i-1\]\[j\]  
47. 15        if j > 1 and max < Y\[i\]\[j-1\]  
48. 16            maxi <- i  
49. 17            maxj <- j-1  
50. 18            max <- Y\[i\]\[j-1\]  
51. 19        if max == Y\[i\]\[j\]  
52. 20            break  
53. 21        exchange Y\[maxi\]\[maxj\] <-> Y\[i\]\[j\]  
54. 22        i <- maxi  
55. 23        j <- maxj  
56. 24        max <- Y\[i\]\[j\]  
57. f）  
58. 从左下角开找，若比它小，则向上，则比它大，则向右找  
59. FIND-YOUNG-KEY(Y, key)  
60.  1    i <- m  
61.  2   j <- 0  
62.  3   while i >= 1 and j <= n  
63.  4       if Y\[i\]\[j\] = key  
64.  5       then return true  
65.  6       else if Y\[i\]\[j\] < key  
66.  7       then j++  
67.  8       else if Y\[i\]\[j\] > key  
68.  9       then i--  
69. 10   return false

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]
    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 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  //头文件   
2.  \#include <iostream>   
3.  \#include <stdio.h>    
4.  using namespace std;  
5.    
6.  //宏定义   
7.  \#define N 100   
8.    
9.  class Young  
10. \{  
11.     public:  
12.     //成员变量   
13.     int Y\[N+1\]\[N+1\];  
14.     int m, n;  
15.     //构造与析构   
16.     Young()\{\}  
17.     Young(int a, int b);  
18.     //Heap(int size):length(size),heap\_size(size)\{\}   
19.     ~Young()\{\}  
20.     //功能函数   
21.     void Min\_Youngify(int i, int j);  
22.     void Build\_Min\_Young();  
23.     void YoungSort();  
24.     bool Find\_Young\_key(int key);  
25.     //优先队列函数   
26.     void Young\_Decrease\_Key(int i, int j, int key);  
27.     void Min\_Young\_Insert(int key);  
28.     int Young\_Minimum();  
29.     int Young\_Extract\_Min();  
30.     void Young\_Delete(int i, int j);  
31.     //辅助函数   
32.     void Print();  
33. \};  
34.   
35. Young::Young(int a, int b):m(a),n(b)  
36. \{  
37.     int i, j;  
38.     for(i = 1; i <= m; i++)  
39.     \{  
40.         for(j = 1; j <= n; j++)  
41.             Y\[i\]\[j\] = 0x7fffffff;  
42.     \}  
43. \}  
44.   
45. void Young::Build\_Min\_Young()  
46. \{  
47.     int i, j, s;  
48.     for(s = m + n; s >= 2; s--)  
49.     \{  
50.         for(i = 1; i <= m; i++)  
51.         \{  
52.             j = s - i;  
53.             if(j > n)continue;  
54.             if(j < 1)break;  
55.             Min\_Youngify(i, j);  
56.         \}  
57.     \}  
58. \}  
59.   
60. int Young::Young\_Extract\_Min()  
61. \{  
62.     int Min = Y\[1\]\[1\];  
63.     Y\[1\]\[1\] = 0x7fffffff;  
64.     Min\_Youngify(1, 1);  
65.     return Min;  
66. \}  
67.   
68. void Young::Min\_Youngify(int i, int j)  
69. \{  
70.     int Min = Y\[i\]\[j\], mini = i, minj = j;  
71.     if(i < m && Y\[i+1\]\[j\] < Min)  
72.     \{  
73.         mini = i + 1;  
74.         minj = j;  
75.         Min = Y\[i+1\]\[j\];  
76.     \}  
77.     if(j < n && Y\[i\]\[j+1\] < Min)  
78.     \{  
79.         mini = i;  
80.         minj = j + 1;  
81.         Min = Y\[i\]\[j+1\];  
82.     \}  
83.     if(i != mini || j != minj)  
84.     \{  
85.         swap(Y\[i\]\[j\], Y\[mini\]\[minj\]);  
86.         Min\_Youngify(mini, minj);  
87.     \}  
88. \}  
89.   
90. void Young::Min\_Young\_Insert(int key)  
91. \{  
92.     if(Y\[m\]\[n\] < 0x7fffffff)  
93.     \{  
94.         cout<<"error:young overflow"<<endl;  
95.         return ;  
96.     \}  
97.     Y\[m\]\[n\] = key;  
98.     int i = m, j = n, Max = key, maxi = i, maxj = j;  
99.     while(true)  
100.     \{  
101.         if(i > 1 && Max < Y\[i-1\]\[j\])  
102.         \{  
103.             maxi = i - 1;  
104.             maxj = j;  
105.             Max = Y\[i-1\]\[j\];  
106.         \}  
107.         if(j > 1 && Max < Y\[i\]\[j-1\])  
108.         \{  
109.             maxi = i;  
110.             maxj = j - 1;  
111.             Max = Y\[i\]\[j-1\];  
112.         \}  
113.         if(Max == Y\[i\]\[j\])  
114.             break;  
115.         swap(Y\[maxi\]\[maxj\], Y\[i\]\[j\]);  
116.         i = maxi;  
117.         j = maxj;  
118.         Max = Y\[i\]\[j\];  
119.     \}  
120. \}  
121.   
122. bool Young::Find\_Young\_key(int key)  
123. \{  
124.     int i = m, j = 0;  
125.     while(i >= 1 && j <= n)  
126.     \{  
127.         if(Y\[i\]\[j\] == key)  
128.             return true;  
129.         else if(Y\[i\]\[j\] < key)  
130.             j++;  
131.         else if(Y\[i\]\[j\] > key)  
132.             i--;  
133.     \}  
134.     return false;  
135. \}  
136.   
137. void Young::Print()  
138. \{  
139.     int i, j;  
140.     for(i = 1; i <= m; i++)  
141.     \{  
142.         for(j = 1; j <= n; j++)  
143.             cout<<Y\[i\]\[j\]<<' ';  
144.         cout<<endl;  
145.     \}  
146. \}  
147.   
148. void Young::Young\_Delete(int i, int j)  
149. \{  
150.     Y\[i\]\[j\] = 0x7fffffff;  
151.     Min\_Youngify(i, j);  
152. \}  
153.   
154. void Young::Young\_Decrease\_Key(int i, int j, int key)  
155. \{  
156.     if(key > Y\[i\]\[j\])  
157.     \{  
158.         cout<<"error:new key is larger than current key"<<endl;  
159.         return ;  
160.     \}  
161.     Y\[i\]\[j\] = key;  
162.     int Max = key, maxi, maxj;  
163.     while(true)  
164.     \{  
165.         if(i > 1 && Max < Y\[i-1\]\[j\])  
166.         \{  
167.             maxi = i - 1;  
168.             maxj = j;  
169.             Max = Y\[i-1\]\[j\];  
170.         \}  
171.         if(j > 1 && Max < Y\[i\]\[j-1\])  
172.         \{  
173.             maxi = i;  
174.             maxj = j - 1;  
175.             Max = Y\[i\]\[j-1\];  
176.         \}  
177.         if(Max == key)  
178.             break;  
179.         swap(Y\[maxi\]\[maxj\], Y\[i\]\[j\]);  
180.         i = maxi;  
181.         j = maxj;  
182.     \}  
183. \}  
184.   
185. int Young::Young\_Minimum()  
186. \{  
187.     return Y\[1\]\[1\];  
188. \}  
189.   
190. void Young::YoungSort()  
191. \{  
192.     while(Y\[1\]\[1\] != 0x7fffffff)  
193.     \{  
194.         cout<<Young\_Extract\_Min()<<' ';  
195.     \}  
196.     cout<<endl;  
197. \}

//头文件
    #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 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  \#include <iostream>   
2.  \#include "Young.h"   
3.  using namespace std;  
4.    
5.  int main()  
6.  \{  
7.      int m, n, x;  
8.      char c;  
9.      cin>>m>>n;  
10.     //输入随机测试数据   
11.     Young \*Y = new Young(m, n);  
12.     int i, j;  
13.     for(i = 1; i <= m; i++)  
14.     \{  
15.         for(j = 1; j <= n; j++)  
16.             Y->Y\[i\]\[j\] = rand() % 100;  
17.     \}  
18.     Y->Print();  
19.     //建堆   
20.     Y->Build\_Min\_Young();  
21.     Y->Print();  
22.     //测试成员函数   
23.     while(cin>>c)  
24.     \{  
25.         switch(c)  
26.         \{  
27.         case 'E':  
28.             cout<<Y->Young\_Extract\_Min()<<endl;  
29.             break;  
30.         case 'P':  
31.             Y->Print();  
32.             break;  
33.         case 'I':  
34.             x = rand() % 100;  
35.             cout<<x<<endl;  
36.             Y->Min\_Young\_Insert(x);  
37.             break;  
38.         case 'F':  
39.             cin>>x;  
40.             cout<<Y->Find\_Young\_key(x)<<endl;  
41.             break;  
42.         \}  
43.     \}  
44.     return 0;  
45. \}

#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;
    }

转载自：[http://blog.csdn.net/mishifangxiangdefeng/article/details/7976452][http_blog.csdn.net_mishifangxiangdefeng_article_details_7976452]

[1347537936_2367.gif]: https://img-my.csdn.net/uploads/201209/13/1347537936_2367.gif
[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7976452#
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7976452]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7976452