算法导论第2版-练习题6.5-8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**********************************************
* 将k个已经完成排序的链表合并为一个排序链表
* 本例从文件test.txt输入所有行,链表用vector来模拟
* 对共有n个数据的k个已排序链表排序,时间为O(n*lgk)
***********************************************/
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <queue>
using namespace std;

struct Item //存储在优先级队列中的项
{
vector<vector<int> >::iterator list;//指向对应链表的迭代器
int value;//值
Item(vector<vector<int> >::iterator l,int v):list(l),value(v){}
bool operator < (const Item& r) const //用于优先级队列内部排序,升序排列
{
return value > r.value;
}
};

int main()
{
//输入已经有序的链表
vector<vector<int> > lists;
ifstream fin("test.txt");
string buf;
while(getline(fin,buf))
{
istringstream sin(buf);
vector<int> list;
int x;
while(sin >> x)
{
list.push_back(x);
}
lists.push_back(list);
}
fin.close();

//取每个链表的头来建立优先级队列
priority_queue<Item> pq;
vector<vector<int> >::iterator list;
int i = 0;
for(list=lists.begin();list!=lists.end();list++)
{
if(list->empty()) continue;
pq.push(Item(list,list->front()));
list->erase(list->begin());
}

vector<int> result;

//取出队列首加入到结果序列中
//将该队列首对应的链表(如果非空)的头加入优先级队列
//当优先队列为空时排序结束
while(!pq.empty())
{
Item item = pq.top();
pq.pop();
result.push_back(item.value);
if(!item.list->empty())
{
pq.push(Item(item.list,item.list->front()));
item.list->erase(item.list->begin());
}
}

//输出结果
vector<int>::iterator it = result.begin();
cout << *it;
for(it++;it!=result.end();it++)
cout << ' ' << *it;
cout << endl;
system("pause");
return 0;
}

给个test.txt的例子:

2 32 54 123 453
4 9 663 2244
1 2 3 78 299
22 44 59 1235
7 68 1790 2790 3678
5 6 7 8 50

执行程序,输出为:

1 2 2 3 4 5 6 7 7 8 9 22 32 44 50 54 59 68 78 123 299 453 663 1235 1790 2244 2790 3678
Press any key to continue . . .