题目要求：
应用输者树结构模拟实现外排序。
基本要求：
1.
设计并实现
最小输者树
结构
ADT
，
ADT
中应包括初始化、返回赢者，重构等基本操作。
2.
应用最小输者树设计实现外排序，外部排序中的生成最初归并串以及
K
路归并都应用最小输者树结构实现；
3.
验证你所实现的外排序的正确性。
（
1
）随机创建一个较长的文件作为外排序的初始数据，设置最小输者树中选手的个数，验证生成最初归并串的正确性。获得最初归并串的个数及最初归并串文件，每一最初归并串使用一个文件。
（2）使用以上生成的归并串，设置归并路数，验证
K
路归并的正确性。获得 K
路归并中各趟的结果，每一趟的结果使用一个文件。
*4.
获得外排序的访问磁盘次数，并分析其影响因素。
代码实现：
最小输者树：
losetree.h:
#ifndef _LOSETREE_H
#define _LOSETREE_H
#include<bits/stdc++.h>
using namespace std;
const int MAX_INT = 2147483647; //设置int的最大值
const int MIN_INT = -2147483648; //设置int的最小值
struct Node //设置Node节点，用来进行初始归并段的生成
{
int id; //优先级
int number;
bool operator<(const Node& a)const
{
if (id != a.id) //如果优先级不同那么就先比较优先级，如果优先级相同，则比较数值
return id < a.id;
else
return number < a.number;
}
};
template<class T>
class losetree
{
public:
losetree(T* a,int num);
T winner();
T player1();
void reinit(T element);
private:
int number;
T* loser; //输者树
int* winer; //记录每次的赢者下标
T* player; //赢者树
};
#endif losetree.cpp:
#include"losetree.h"
template<class T>
losetree<T>::losetree(T* a,int num) //复杂度为O（n）
{
number = num;
player = new T[2 * num]();
winer = new int[num * 2]();
loser = new T[num]();
for (int i = number; i < 2 * number; i++)
{
player[i] = a[i - number];
winer[i] = i;
}
for (int i = number - 1; i > 0; i--)
{
if (player[2 * i] < player[2 * i + 1])
{
player[i] = player[2 * i];
loser[i] = player[2 * i + 1];
winer[i] = winer[2 * i];
}
else
{
player[i] = player[2 * i + 1];
loser[i] = player[2 * i];
winer[i] = winer[2 * i + 1];
}
}
loser[0] = player[winer[1]]; //记录最小值
}
template<class T>
T losetree<T>::winner()
{
return loser[0]; //loser[0]中存储的是最小值
}
template<class T>
T losetree<T>::player1()
{
return winer[1]; //最小值的下标
}
template<class T>
void losetree<T>::reinit(T element) //复杂度为O（logn）
{
player[winer[1]] = element;
for (int i = winer[1] / 2; i > 0; i = i / 2) //重构时需要将最小值的元素与其父节点相比较，直到根节点为止
{
if (player[2 * i] < player[2 * i + 1])
{
player[i] = player[2 * i];
loser[i] = player[2 * i + 1];
winer[i] = winer[2 * i];
}
else
{
player[i] = player[2 * i + 1];
loser[i] = player[2 * i];
winer[i] = winer[2 * i + 1];
}
}
loser[0] = player[winer[1]]; //记录最小值
}
外排序：
Merge.h:
#ifndef _MERGE_H
#define _MERGE_H
#include"losetree.cpp"
template<class T>
class Merge
{
public:
Merge(int _Size, int _NumberOfCombine);
void outputname(string s1); //设置归并段的名称
void devide(string name); //初始归并段的生成
void combine(); //归并段的合并
int NumberOfTimes(); //磁盘的读取次数
private:
int Size; //输者树的大小
int NumberOfCombine; //记录归并路数
int NumberOfFile; //记录每次产生的归并段个数
string s, s1; //产生归并段的名称
string answer; //最终输出的文件的名称
int times; //记录磁盘的读取次数
};
#endif Merge.cpp:
#include"Merge.h"
template<class T>
Merge<T>::Merge(int _Size, int _NumberOfCombine)
{
Size = _Size;
NumberOfCombine = _NumberOfCombine;
NumberOfFile = 0;
s1 = ".txt";
answer = "output.txt";
times = 0;
}
template<class T>
void Merge<T>::outputname(string s) //设置归并段的名称
{
this->s = s;
}
template<class T>
void Merge<T>::devide(string name) //初始归并段的生成
{
ifstream victory(name, ios::in); //打开名为name的文件
int number;
victory >> number; //从文件中读取数据的个数
times++;
Node* well = new Node[Size]; //建立一个大小为输者树大小的数组
for (int i = 0; i < Size; i++)
{
victory >> well[i].number;
well[i].id = 1; //初始优先级均为1
}
losetree<Node> defeat(well, Size);
int num = 0;
while (1)
{
victory >> num;
if (victory.eof()) //判断文件末位，文件到末尾则退出循环
break;
Node p1 = defeat.winner();
Node p;
p.number = num;
if (num > p1.number) //如果num比最小输者树的最小值大，则优先级相同，反之则优先级+1
{
p.id = p1.id;
}
else
{
p.id = p1.id + 1;
NumberOfFile = max(NumberOfFile, p.id); //得到产生的初始归并段的个数
}
defeat.reinit(p); //重构
string s3 = s + "0-" + to_string(p1.id) + s1;
ofstream fff(s3, ios::app); //ios::app在文件末位接着输出，ios::out重新在文件中输出
fff << p1.number << ' ';
fff.close();
times++; //由于打开了s3文件因此，寻盘次数加一
}
while (1) //将输者树中剩余的数输出
{
if (defeat.winner().number == MAX_INT)
break;
Node p1 = defeat.winner();
Node p; //p的优先级得是最低，并且值是最大
p.id = MAX_INT;
p.number = MAX_INT;
defeat.reinit(p);
string s3 = s + "0-" + to_string(p1.id) + s1;
ofstream fff(s3, ios::app);
fff << p1.number << ' ';
fff.close();
times++;
}
}
template<class T>
void Merge<T>::combine() //归并段的合并
{
for (int h = 0; NumberOfFile != 1; h++)
{
int* he = new int[NumberOfCombine];
ifstream* infile = new ifstream[NumberOfFile + 1]; //将所有的归并段都放入缓冲区
for (int i = 1; i <= NumberOfFile; i++)
{
infile[i].open(s + to_string(h) + "-" + to_string(i) + s1, ios::in);
times++;
}
int j = 0;
for (; j < ceil((double)NumberOfFile / (double)NumberOfCombine); j++) //将所有的文件进行k路归并
{
string out;
if (NumberOfFile <= NumberOfCombine) //判断产生的文件是否是最终的归并结果，对输出的文件名进行定义
{
out = answer;
}
else
{
out = s + to_string(h + 1) + "-" + to_string(j + 1) + s1;
}
ofstream outfile(out, ios::out);
times++;
for (int i = 1; i <= NumberOfCombine; i++)
{
if (j * NumberOfCombine + i >= NumberOfFile + 1) //判断剩余的文件个数是否小于归并路数，如果小于则要将这个数组中的差值用最大值进行补充
{
he[i - 1] = MAX_INT;
}
else
infile[j * NumberOfCombine + i] >> he[i - 1];
}
losetree<int> L(he, NumberOfCombine);
while (L.winner() != MAX_INT)
{
outfile << L.winner() << ' ';
for (int f = 0; f < NumberOfCombine; f++)
{
if (L.player1() == f + NumberOfCombine && j * NumberOfCombine + 1 + f < NumberOfFile + 1) //得到最小输者树的最小值下标是具体的那个文件，此时还要注意有可能存在剩余的文件个数小于归并路数的情况
{
int u = 0;
infile[j * NumberOfCombine + 1 + f] >> u;
if (infile[j * NumberOfCombine + 1 + f].eof()) //如果到文件末位则将最大值输入到输者树中，然后进行重排即可
u = MAX_INT;
L.reinit(u);
break;
}
}
}
outfile.close();
}
for (int i = 1; i <= NumberOfFile; i++)
infile[i].close();
NumberOfFile = j;
}
}
template<class T> //磁盘的读取次数
int Merge<T>::NumberOfTimes()
{
return times;
}
//文件末位如果有空格，则需要先将数据读入，因为将数据放入缓冲区后，eof函数在将最后一个数据放入缓冲区后，并没有到达文件的末尾，还需要再读入一位最后的空格，此时会将缓冲区的数读入，也就是最后一个数据再读一遍
//文件末位没有空格，那就先判断是否到文件末位，再读入数据就可以了主函数：文章来源：https://www.toymoban.com/news/detail-859214.html
main.cpp:文章来源地址https://www.toymoban.com/news/detail-859214.html
#include"Merge.cpp"
bool judge(string s) //判断文件是否可以打开
{
ifstream Try(s, ios::in);
if (!Try.is_open())
{
return false;
}
Try.close();
return true;
}
int main()
{
cout << "请输入输者树的大小:" << endl;
int Size;
cin >> Size;
cout << "请输入要实现几路归并:" << endl;
int Several;
cin >> Several;
Merge<int> M(Size, Several);
cout << "请输入要生成的文件名称:" << endl;
string s;
cin >> s;
M.outputname(s);
cout << "请输入要外排序的文件名称:" << endl;
string name;
cin >> name;
while (!judge(name)) {
cout << "请重新输入要外排序的文件名称:" << endl;
cin >> name;
}
M.devide(name);
M.combine();
cout << "磁盘访问次数为:" << endl;
cout << M.NumberOfTimes() << endl;
}到了这里，关于山东大学数据结构课设第一部分实验二——外排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
