应用竞赛树结构模拟实现外排序。
(1) 设计实现最小输者树结构ADT,ADT中应包括初始化、返回赢者,重构等基本操作。
(2) 设计实现外排序,外部排序中的生成最初归并串以及K路归并都应用最小输者树结构实现;
(3) 随机创建一个较长的文件;设计归并路数以及缓冲区的大小;获得外排序的访问磁盘的次数并进行分析。可采用小文件来模拟磁盘块。
对于输者树的构建过程,数据结构课本上并没有多说,仅仅讲解了赢者树,如下图所示,赢者上升进入下一次比赛。
哦,原来这就是赢者树,那么这个最小赢者树是不是就是最大输者树了呢?
想多了,课本上有一个最小输者树的图如下图所示:
说实话,第一次见到这个图我是一脸懵逼的(可能我当时上课讲的忘了),中间结点加上上面的输者结点,包含 a ∼ f a\sim f a∼f的所有结点,根本就不是我开始想象的输者树就是每个结点记录当前的输者。
后来在网上看了一些博客才懂什么意思,我们下面看一下课本上这个图是怎么建立起来的:
这棵树上,边的值才是比赛晋级的选手,而不是赢者树中结点的才是晋级。
我们按照先从右孩子开始的顺序来构建这棵最小输者树。
所以说,每个结点都保存了当前的输者没有错,只是图上没有表现出来晋级的选手而已。每次比赛的选手都是晋级的选手(我就说嘛,什么比赛最后要输的一方)。
这个外排序的思路是先利用内排序构造顺串,然后这些顺串在进行k路归并,合并成最终结果。
我们在这里使用最小输者树来构造顺串,这样可以减少初始顺串的个数。
在利用最小输者树构造顺串的时候,每个选手都对应着输入集合中的一个元素。另外,每一个选手还有一个顺串号。
赢者的规则是:
那这些元素的顺串号又怎么确定呢?伪代码如下:
建立前p个选手的最小赢者树(p是内存的大小)
while(还有元素没有输出到对应的顺串中)
{
将最终赢者w移入它的顺串号所对应的顺串中;
if(输入集合中又下一个元素)
n=下一个元素;
else {
n=INT_MIN;
n的顺串号=INT_MAX;//这样就不会输入顺串中
}
if(n的元素值>=w的值) n的顺串号=w的顺串号;
else n的顺串号=w的顺串号+1;
n代替w的位置,重构赢者树;
}
建立了这些顺串后,再利用一次最小输者树就可以将他们归并,并且存到对应的磁盘文件中。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
#include <fstream>
#include <ctime>
#include <random>
using namespace std;
struct Variable//变量结构体
{
Variable(){
visitDiskTime=0;
n=0; m=0;
numberOfDisk=0;
}
string path;//磁盘的位置,可以根据自己的电脑修改
string fileName="Disk.txt";//磁盘文件名称
string file;//最终完整路径
int visitDiskTime,n,m,numberOfDisk;
char ch1,ch;
};
struct SequentialStringPlayer//用于构建顺串
{
int id,key;
bool operator<=(SequentialStringPlayer &p){
return (id!=p.id) ? (id<p.id) : (key<p.key);
}
};
template <class T>
class loserTree
{
public:
virtual ~loserTree(){
}
virtual void initialize(T* thePlayer,int number)=0;
virtual int getTheWinner() const =0;
virtual void rePlay(int thePLayer,T newvalue)=0;
};
template <class T>
class MinimumLoserTree : public loserTree<T>
{
public:
MinimumLoserTree(T* thePlayer=nullptr,int theNumberOfPlayers=0){
tree=nullptr; advance=nullptr;
initialize(thePlayer,theNumberOfPlayers);
}
~MinimumLoserTree(){
delete[] tree;delete[] advance;}
void initialize(T* thePlayer,int theNumberOfPlayers);//初始化
int getTheWinner() const {
return tree[0];};//输出当前的赢者
void rePlay(int thePlayer,T newvalue);//重构
private:
int numberOfPlayers;
int* tree;//记录内部结点,tree[0]是最终的赢者下标,不使用二叉树结点,因为父子关系都是通过计算得出
int* advance;//记录比赛晋级的成员
T* player;//参与比赛的元素
int lowExt;//最底层外部结点的个数,2*(n-s)
int offset;//2*s-1
void play(int,int,int);
int winner(int x,int y){
return player[x]<=player[y]?x:y;};//返回更小的元素下标
int loser(int x,int y){
return player[x]<=player[y]?y:x;};//返回更大的元素下标
};
template <class T>
void MinimumLoserTree<T>::initialize(T* thePlayer,int theNumberOfPlayers)
{
int n=theNumberOfPlayers;
if(n<2) {
cout<<"Error! the number must >= 2"<<endl;
return;
}
player=thePlayer;
numberOfPlayers=n;
delete[] tree; delete[] advance;
tree=new int[n+1];
advance=new int[n+1];
int s; for (s=1; 2*s<=n-1; s+=s);//s=2^log(n-1)-1(常数优化速度更快),s是最底层最左端的内部结点
lowExt=2*(n-s); offset=2*s-1;
for (int i=2; i<=lowExt; i+=2)//最下面一层开始比赛
play((i+offset)/2,i-1,i);//父结点计算公式第一条
int temp=0;
if(n%2==1){
//如果有奇数个结点,处理下面晋级的一个和这个单独的结点
play(n/2,advance[n-1],lowExt+1);
temp=lowExt+3;
}
else temp=lowExt+2;//偶数个结点,直接处理次下层
for (int i=temp; i<=n; i+=2)//经过这个循环,所有的外部结点都处理完毕
play((i-lowExt+n-1)/2,i-1,i);
tree[0]=advance[1];//tree[0]是最终的赢者,也就是决赛的晋级者
}
template <class T>
void MinimumLoserTree<T>::play(int p, int leftChild, int rightChild)
{
//tree结点存储相对较大的值,也就是这场比赛的输者
tree[p]=loser(leftChild,rightChild);
//advance结点存储相对较小的值,也就是这场比赛的晋级者
advance[p]=winner(leftChild,rightChild);
while(p % 2 == 1 && p > 1){
tree[p/2]=loser(advance[p-1],advance[p]);
advance[p/2]=winner(advance[p-1],advance[p]);
p /= 2;//向上搜索
}
}
template <class T>
void MinimumLoserTree<T>::rePlay(int thePlayer,T newvalue)
{
int n=numberOfPlayers;
if(thePlayer <= 0 || thePlayer > n){
cout<<"Error! the number must >0 & <=n"<<endl;
return;
}
player[thePlayer]=newvalue;
int matchNode,//将要比赛的场次
leftChild,//比赛结点的左儿子
rightChild;//比赛结点的右儿子
if(thePlayer<=lowExt){
//如果要比赛的结点在最下层
matchNode=(offset+thePlayer)/2;
leftChild=2*matchNode-offset;
rightChild=leftChild+1;
}
else {
//要比赛的结点在次下层
matchNode=(thePlayer-lowExt+n-1)/2;
if(2*matchNode==n-1){
//特殊情况,其中一方是晋级后的人
leftChild=advance[2*matchNode];
rightChild=thePlayer;
}
else{
leftChild=2*matchNode-n+1+lowExt;//这个操作是因为上面matchNode计算中/2取整了
rightChild=leftChild+1;
}
}
//到目前位置,我们已经确定了要比赛的场次以及比赛的选手
//下面进行比赛重构,也就是和赢者树最大的不同,分两种情况
if(thePlayer==tree[0]){
//当你要重构的点是上一场比赛的赢家的话,过程比赢者树要简化
for (; matchNode>=1; matchNode/=2){
int oldLoserNode=tree[matchNode];//上一场比赛的输者
tree[matchNode]=loser(oldLoserNode,thePlayer);
advance[matchNode]=winner(oldLoserNode,thePlayer);
thePlayer=advance[matchNode];
}
}
else {
//其他情况重构和赢者树相同
tree[matchNode]=loser(leftChild,rightChild);
advance[matchNode]=winner(leftChild,rightChild);
if(matchNode==n-1 && n%2==1){
//特殊情况,比赛结点是最后一层的最后一场比赛
//特殊在matchNode/2后,左儿子是晋级的选手,右儿子是一场都没有比过赛的选手
matchNode/=2;
tree[matchNode]=loser(advance[n-1],lowExt+1);
advance[matchNode]=winner(advance[n-1],lowExt+1);
}
matchNode/=2;
for (; matchNode>=1; matchNode/=2){
tree[matchNode]=loser(advance[matchNode*2],advance[matchNode*2+1]);
advance[matchNode]=winner(advance[matchNode*2],advance[matchNode*2+1]);
}
}
tree[0]=advance[1];//最终胜者
}
void init(Variable &va)
{
cout<<"请输入您想要的模拟磁盘位置,接下来的操作都是在当前路径下进行,输入样例:/Users/longzhengtian/Desktop/text/"<<endl;
cout<<"请输入:"; cin>>va.path; va.file=va.path+va.fileName;
cout<<"请输入您想要在磁盘中初始化数字的个数,这些数字将用于模拟外排序过程:"; cin>>va.n;
cout<<"请输入缓冲区大小(此处为缓冲区能存储数字的个数):"; cin>>va.m;
cout<<"请问您是否想要将原始数据,顺串,最终数据显示在控制台中('y' or 'n'):"; cin>>va.ch1; cout<<endl;
ofstream fout1(va.file);
if(!fout1.is_open()){
cout<<"无法打开指定磁盘文件,无法初始化磁盘"<<endl;
exit(0);
}
if(va.ch1=='y') cout<<"原始磁盘文件有:"<<endl;
for (int i=1; i<=va.n; i++){
int x=random()%1000+1;
fout1<<x<<' ';//random是C++11标准
if(va.ch1=='y') cout<<x<<' ';
}
if(va.ch1=='y') cout<<endl<<endl;
fout1.close();
}
void SequentialStringConstruction(Variable &va,SequentialStringPlayer* ssplayer)
{
ifstream fin1(va.file);
if(!fin1.is_open()){
cout<<"无法打开指定磁盘文件,无法进行顺串构造"<<endl;
exit(0);
}
for (int i=1; i<=va.m; i++){
//将数据读入缓冲区,进行顺串构造
fin1>>ssplayer[i].key;
ssplayer[i].id=1;
va.visitDiskTime++;//访存次数+1
}
MinimumLoserTree<SequentialStringPlayer> sstree(ssplayer,va.m);
int num=0;
for (int i=1; i<=va.n; i++){
//依次从磁盘中取出元素,放入顺串生成树
if(!(fin1>>num)) num=INT_MIN;
else va.visitDiskTime++;
SequentialStringPlayer tempwinner=ssplayer[sstree.getTheWinner()];
SequentialStringPlayer tempnum; tempnum.key=num;
if(num >= tempwinner.key) tempnum.id=tempwinner.id;
else tempnum.id=num=(num==INT_MIN) ? INT_MAX :tempwinner.id+1;
sstree.rePlay(sstree.getTheWinner(),tempnum);
string smallfile=va.path+"smallfile"+to_string(tempwinner.id)+".txt";
va.numberOfDisk=max(va.numberOfDisk,tempwinner.id);
ofstream fout2(smallfile, ios::app);
fout2<<tempwinner.key<<' ';
fout2.close();
va.visitDiskTime++;
}
fin1.close();
cout<<"顺串分配完毕,生成"<<va.numberOfDisk<<"个顺串,顺串文件见您当前路径下出现的新文件"<<endl;
if(va.ch1=='y'){
cout<<"我们将这些数据在这里显示如下:"<<endl;
for (int i=1; i<=va.numberOfDisk; i++)
{
string smallfile=va.path+"smallfile"+to_string(i)+".txt";
ifstream finx(smallfile);
int tempx=0;
cout<<"smallfile"<<i<<".txt: ";
while(finx>>tempx)
cout<<tempx<<' ';
cout<<endl;
finx.close();
}
}
}
void GenerateTheFinalResult(Variable &va)
{
cout<<endl<<"请问是否将最终排序结果放入原文件,如果否,则程序将新建一个Disk2.txt文件并放入此文件中(输入'y'或'n'代表'是'与'否'):"; cin>>va.ch;
string newFile;
if(va.ch=='y') newFile=va.file;
else newFile=va.path+"Disk2.txt";
ofstream fout3(newFile);
if(va.numberOfDisk==1){
//只生成了一个顺串文件,直接将其加入目标文件
string smallfile=va.path+"smallfile"+to_string(1)+".txt";
ifstream fin4(smallfile);
int tempnumber;
while(fin4>>tempnumber){
fout3<<tempnumber<<' ';
va.visitDiskTime+=2;
}
fout3.close();
fin4.close();
cout<<"由于只生成了1个顺串,直接将此结果放入目标文件中,磁盘访存次数为"<<va.visitDiskTime<<"次,原因是每个数据都读写4次"<<endl;
if(va.ch1=='y'){
cout<<"最终外排序结果如下:"<<endl;
ifstream finy(newFile);
int tempy;
while(finy>>tempy)
cout<<tempy<<' ';
cout<<endl;
finy.close();
}
exit(0);
}
int dplayer[va.numberOfDisk+10];//初始化队列
int pointer[va.numberOfDisk+10];//各个小磁盘文件的指针
for (int i=1; i<=va.numberOfDisk; i++){
string smallfile=va.path+"smallfile"+to_string(i)+".txt";
ifstream fin2(smallfile);
fin2>>dplayer[i];
pointer[i]=fin2.tellg();
fin2.close();
}
MinimumLoserTree<int> dtree(dplayer,va.numberOfDisk);
int cnt=0;
while(cnt<va.n){
cnt++;
int temp=dtree.getTheWinner();
int tempwinner=dplayer[temp];
fout3<<tempwinner<<' ';
va.visitDiskTime++;
string smallfile=va.path+"smallfile"+to_string(temp)+".txt";
ifstream fin3(smallfile);
fin3.clear(); fin3.seekg(pointer[temp]+1);
int tempnum;
if(pointer[temp]+1==0) tempnum=INT_MAX;
else {
fin3>>tempnum;
pointer[temp]=fin3.tellg();
if(pointer[temp]+1==0) tempnum=INT_MAX;
}
va.visitDiskTime++;
dtree.rePlay(temp,tempnum);
fin3.close();
}
fout3.close();
cout<<endl;
cout<<"将这些文件进行"<<va.numberOfDisk<<"路归并,已经结果存入到目标文件中。磁盘访存次数为"<<va.visitDiskTime<<"次,原因是每个数据都读写4次"<<endl;
if(va.ch1=='y'){
cout<<"最终外排序结果如下:"<<endl;
ifstream finy(newFile);
int tempy;
while(finy>>tempy)
cout<<tempy<<' ';
cout<<endl;
finy.close();
}
}
int main()
{
srand(time(nullptr));
Variable va;
init(va);//初始化,生成随机磁盘文件
SequentialStringPlayer ssplayer[va.n+10];
SequentialStringConstruction(va,ssplayer);//构造顺串
GenerateTheFinalResult(va);//生成最终结果
return 0;
}
代码参考教材源码以及这篇博客
文章浏览阅读2w次,点赞7次,收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案,在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建:添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体,挺好看的。注重颜值的网站都会使用,例如知乎:font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时,向何处发送表单中的数据,地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理,get方式直接显示在url地址中,数据可以被缓存,且长度有限制;而post方式数据隐藏传输,_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证(即Google Authenticator服务)后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次,点赞5次,收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节,实现了多层数据的堆叠,为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制(CoW)策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的,不建议用于生成环境。_docker 保存容器
文章浏览阅读834次,点赞27次,收藏13次。网络拓扑结构是指计算机网络中各组件(如计算机、服务器、打印机、路由器、交换机等设备)及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式,也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次,点赞5次,收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时,通常的做法是:new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的,而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠,也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑,需要做一些额外的特殊处理,笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数,一劳永逸,避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一:用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头,使全列成选中状态,然后粘贴,最后commit提交即可。(前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明:转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数