題目要求：
應(yīng)用輸者樹結(jié)構(gòu)模擬實(shí)現(xiàn)外排序。
基本要求：
1.
設(shè)計(jì)并實(shí)現(xiàn)
最小輸者樹
結(jié)構(gòu)
ADT
，
ADT
中應(yīng)包括初始化、返回贏者，重構(gòu)等基本操作。
2.
應(yīng)用最小輸者樹設(shè)計(jì)實(shí)現(xiàn)外排序，外部排序中的生成最初歸并串以及
K
路歸并都應(yīng)用最小輸者樹結(jié)構(gòu)實(shí)現(xiàn)；
3.
驗(yàn)證你所實(shí)現(xiàn)的外排序的正確性。
（
1
）隨機(jī)創(chuàng)建一個(gè)較長的文件作為外排序的初始數(shù)據(jù)，設(shè)置最小輸者樹中選手的個(gè)數(shù)，驗(yàn)證生成最初歸并串的正確性。獲得最初歸并串的個(gè)數(shù)及最初歸并串文件，每一最初歸并串使用一個(gè)文件。
（2）使用以上生成的歸并串，設(shè)置歸并路數(shù)，驗(yàn)證
K
路歸并的正確性。獲得 K
路歸并中各趟的結(jié)果，每一趟的結(jié)果使用一個(gè)文件。
*4.
獲得外排序的訪問磁盤次數(shù)，并分析其影響因素。
代碼實(shí)現(xiàn)：
最小輸者樹：
losetree.h:
#ifndef _LOSETREE_H
#define _LOSETREE_H
#include<bits/stdc++.h>
using namespace std;
const int MAX_INT = 2147483647; //設(shè)置int的最大值
const int MIN_INT = -2147483648; //設(shè)置int的最小值
struct Node //設(shè)置Node節(jié)點(diǎn)，用來進(jìn)行初始?xì)w并段的生成
{
int id; //優(yōu)先級(jí)
int number;
bool operator<(const Node& a)const
{
if (id != a.id) //如果優(yōu)先級(jí)不同那么就先比較優(yōu)先級(jí)，如果優(yōu)先級(jí)相同，則比較數(shù)值
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; //記錄每次的贏者下標(biāo)
T* player; //贏者樹
};
#endif losetree.cpp:
#include"losetree.h"
template<class T>
losetree<T>::losetree(T* a,int num) //復(fù)雜度為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]中存儲(chǔ)的是最小值
}
template<class T>
T losetree<T>::player1()
{
return winer[1]; //最小值的下標(biāo)
}
template<class T>
void losetree<T>::reinit(T element) //復(fù)雜度為O（logn）
{
player[winer[1]] = element;
for (int i = winer[1] / 2; i > 0; i = i / 2) //重構(gòu)時(shí)需要將最小值的元素與其父節(jié)點(diǎn)相比較，直到根節(jié)點(diǎn)為止
{
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); //設(shè)置歸并段的名稱
void devide(string name); //初始?xì)w并段的生成
void combine(); //歸并段的合并
int NumberOfTimes(); //磁盤的讀取次數(shù)
private:
int Size; //輸者樹的大小
int NumberOfCombine; //記錄歸并路數(shù)
int NumberOfFile; //記錄每次產(chǎn)生的歸并段個(gè)數(shù)
string s, s1; //產(chǎn)生歸并段的名稱
string answer; //最終輸出的文件的名稱
int times; //記錄磁盤的讀取次數(shù)
};
#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) //設(shè)置歸并段的名稱
{
this->s = s;
}
template<class T>
void Merge<T>::devide(string name) //初始?xì)w并段的生成
{
ifstream victory(name, ios::in); //打開名為name的文件
int number;
victory >> number; //從文件中讀取數(shù)據(jù)的個(gè)數(shù)
times++;
Node* well = new Node[Size]; //建立一個(gè)大小為輸者樹大小的數(shù)組
for (int i = 0; i < Size; i++)
{
victory >> well[i].number;
well[i].id = 1; //初始優(yōu)先級(jí)均為1
}
losetree<Node> defeat(well, Size);
int num = 0;
while (1)
{
victory >> num;
if (victory.eof()) //判斷文件末位，文件到末尾則退出循環(huán)
break;
Node p1 = defeat.winner();
Node p;
p.number = num;
if (num > p1.number) //如果num比最小輸者樹的最小值大，則優(yōu)先級(jí)相同，反之則優(yōu)先級(jí)+1
{
p.id = p1.id;
}
else
{
p.id = p1.id + 1;
NumberOfFile = max(NumberOfFile, p.id); //得到產(chǎn)生的初始?xì)w并段的個(gè)數(shù)
}
defeat.reinit(p); //重構(gòu)
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文件因此，尋盤次數(shù)加一
}
while (1) //將輸者樹中剩余的數(shù)輸出
{
if (defeat.winner().number == MAX_INT)
break;
Node p1 = defeat.winner();
Node p; //p的優(yōu)先級(jí)得是最低，并且值是最大
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]; //將所有的歸并段都放入緩沖區(qū)
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++) //將所有的文件進(jìn)行k路歸并
{
string out;
if (NumberOfFile <= NumberOfCombine) //判斷產(chǎn)生的文件是否是最終的歸并結(jié)果，對(duì)輸出的文件名進(jìn)行定義
{
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) //判斷剩余的文件個(gè)數(shù)是否小于歸并路數(shù)，如果小于則要將這個(gè)數(shù)組中的差值用最大值進(jìn)行補(bǔ)充
{
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) //得到最小輸者樹的最小值下標(biāo)是具體的那個(gè)文件，此時(shí)還要注意有可能存在剩余的文件個(gè)數(shù)小于歸并路數(shù)的情況
{
int u = 0;
infile[j * NumberOfCombine + 1 + f] >> u;
if (infile[j * NumberOfCombine + 1 + f].eof()) //如果到文件末位則將最大值輸入到輸者樹中，然后進(jìn)行重排即可
u = MAX_INT;
L.reinit(u);
break;
}
}
}
outfile.close();
}
for (int i = 1; i <= NumberOfFile; i++)
infile[i].close();
NumberOfFile = j;
}
}
template<class T> //磁盤的讀取次數(shù)
int Merge<T>::NumberOfTimes()
{
return times;
}
//文件末位如果有空格，則需要先將數(shù)據(jù)讀入，因?yàn)閷?shù)據(jù)放入緩沖區(qū)后，eof函數(shù)在將最后一個(gè)數(shù)據(jù)放入緩沖區(qū)后，并沒有到達(dá)文件的末尾，還需要再讀入一位最后的空格，此時(shí)會(huì)將緩沖區(qū)的數(shù)讀入，也就是最后一個(gè)數(shù)據(jù)再讀一遍
//文件末位沒有空格，那就先判斷是否到文件末位，再讀入數(shù)據(jù)就可以了主函數(shù)：文章來源：http://www.zghlxwxcb.cn/news/detail-859214.html
main.cpp:文章來源地址http://www.zghlxwxcb.cn/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 << "請(qǐng)輸入輸者樹的大小:" << endl;
int Size;
cin >> Size;
cout << "請(qǐng)輸入要實(shí)現(xiàn)幾路歸并:" << endl;
int Several;
cin >> Several;
Merge<int> M(Size, Several);
cout << "請(qǐng)輸入要生成的文件名稱:" << endl;
string s;
cin >> s;
M.outputname(s);
cout << "請(qǐng)輸入要外排序的文件名稱:" << endl;
string name;
cin >> name;
while (!judge(name)) {
cout << "請(qǐng)重新輸入要外排序的文件名稱:" << endl;
cin >> name;
}
M.devide(name);
M.combine();
cout << "磁盤訪問次數(shù)為:" << endl;
cout << M.NumberOfTimes() << endl;
}到了這里，關(guān)于山東大學(xué)數(shù)據(jù)結(jié)構(gòu)課設(shè)第一部分實(shí)驗(yàn)二——外排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
