- 浏览: 1028205 次
-
文章分类
最新评论
-
l67721363：
感谢分享，要是有各个函数性能比较就好了。
SQL优化 数据库优化 -
hanmiao：
此图片来自QQ空间，未经允许不可引用。
Hacking QQ空间
外排序
用自己的思想写的外排序，还有很多地方需要改进。最先一位用搜索二叉树很好，但现在一想不是这样，如果把搜索二叉树改为最小堆会使程序执行的更好。
数据结构与算法设计课程设计
专业 信息与计算科学 班级 信息0601 学号 200601010102 姓名（签名） 完成日期 指导教师（签名）
【设计题目】外排序
【问题描述】
磁盘中的保存有大量的数据，需要分批导入内存，分批导入的数据排好序后再分批导出到磁盘中保存。最终实现磁盘文件数据的排序。
【软件功能】
1． 为用户保存在文本文件中的数据进行排序，其最大有效的数据量为内存字节的平方。
2． 排序的结果用户可以选择是否覆盖原文件，按提示输入是否。选择是的话排序的结构保存在原文件中，选择否的话排序结果保存在新建的文件中。
3． 程序默认建立于原文件名相似的文件用于存放分割后的数据。
【算法思想】
因为所用文件中的数据量不够大，所以采用模拟的办法。假设计算机每次只能读
十条记录，内存就满了。原文件中所记录的数据大于十条。
循环从文件中读入数据并进行排序，然后把排好序的数据保存到新建的文件（每读取一次新建一文件）直到数据读完。文件的名字用sprintf函数命名。假设此时新建文件数为n；
定义n个文件指针，并为之分配内存。打开文件。
循环，从每个新建文件中读取1条记录并进行排序，排序得到最小的数据，把最小的数据写入原文件，那最小的数据从那个文件中读取的就从那个文件中再读取一个文件，继续比较。如此重复。假设有一个文件读取完了，则不把刚才读的数据加到搜索二叉树中，因为刚读的是文件结尾标志，在内存中为原来的数据。因为每写进文件就要删除搜索二叉树中的一个节点。循环条件结束的标志为搜索二叉树中根节点为空。
【类的设计】
测试数据类；
class TestData{
public:
int Data;//测试数据的关键码
int num;//存放的文件编号
TestData();
};
排序用的搜索二叉树节点类
class BSTNode{
friend class BSTTree;
TestData Data;//数据
BSTNode * leftchild;//左孩子
BSTNode * rightchild;//右孩子
int threaded;//线索化标记(在这程序中不线索化)
public:
BSTNode();//空构造函数
BSTNode(TestData & Data);//构造函数
~ BSTNode();//析构函数
TestData GetData();//取节点数据
bool SetData(TestData & Da);//设置节点数据
};
搜索二叉树类：
class BSTTree{
BSTNode *root;//根节点
public:
BSTTree();
bool AddData(TestData &Da);
bool isempty();
bool InorderAndDelete(char * filename);
int orderminanddelete(char * filename);
};
【存储结构设计】
1． 序的数据文存放于本文档中。
2． 中的数据存放于搜索二叉树中。
3． 本文件，存放刚读取且排好序的数据。
4． 个新建文件中读取1个数据，存放在搜索二叉树中。
5． 数据到原文件中，并从新建文件中从新读取一个数据。
【模块划分及调用关系】
<textbox style="mso-next-textbox: #_x0000_s1026"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><font size="3"><span lang="EN-US"><font face="Times New Roman">Main</font></span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">函数</span></font></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1027"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">分批读取文件，排序并写入新文件。</font></span></p> </div> </td> </tr></tbody></table></textbox><stroke endarrow="block"><font size="3"></font></stroke><textbox style="mso-next-textbox: #_x0000_s1029; mso-fit-shape-to-text: t"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">从每个新建文件中读取数据，排序写入原文件。</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1030"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">结束</font></span></p> </div> </td> </tr></tbody></table></textbox><stroke endarrow="block"><font size="3"></font></stroke><stroke endarrow="block"><font size="3"></font></stroke>
【模块流程图】
<textbox style="mso-next-textbox: #_x0000_s1033"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">主函数</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1034"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">分批读取文件，排序并写入新文件。</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1035; mso-fit-shape-to-text: t"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">从每个新建文件中读取数据，排序写入原文件。</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1036"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center" align="center"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">结束</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1037"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><font size="3"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">选择对文件数据进行排序</span><span lang="EN-US"><span style="mso-spacerun: yes"><font face="Times New Roman"> </font></span></span></font></p> </div> </td> </tr></tbody></table></textbox><stroke endarrow="block"><font face="Times New Roman" size="3"></font></stroke><stroke endarrow="block"><font face="Times New Roman" size="3"></font></stroke><textbox style="mso-next-textbox: #_x0000_s1042"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">执行没错误</font></span></p> </div> </td> </tr></tbody></table></textbox><stroke endarrow="block"><font size="3"></font></stroke><stroke endarrow="block"><font size="3"></font></stroke><stroke endarrow="block"><font size="3"></font></stroke><textbox style="mso-next-textbox: #_x0000_s1049"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">选择放弃操作</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1050"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">执行出错误</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1051"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">选择返回主函数继续执行</font></span></p> </div> </td> </tr></tbody></table></textbox><textbox style="mso-next-textbox: #_x0000_s1052"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-RIGHT: #ece9d8; BORDER-TOP: #ece9d8; BORDER-LEFT: #ece9d8; BORDER-BOTTOM: #ece9d8; BACKGROUND-COLOR: transparent"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt; TEXT-INDENT: 5.25pt; mso-char-indent-count: .5"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">选择结束任务</font></span></p> </div> </td> </tr></tbody></table></textbox>
【用户手册】
此程序为Win32 控制台下的程序，用户安装了有关VC软件就能有效运行。
1、 程序上机调试报告
【语法错误及其排除】
无。
【算法错误及其排除】
蓝色为修正处。
1． 重载>和<号时返回值出错
bool operator >(TestData & a,TestData & aa){
if(a.Data>=aa.Data)//修正：if(a.Data<=aa.Data
return false;
return true;
}
2． 没有对很有可能出错的返回值进行处理
i=bsttree.orderminanddelete(filefrom))==-1)//返回刚才写入文件的是从第几个文件中读入的数据
修正：if((i=bsttree.orderminanddelete(filefrom))==-1)
return false;
3． 删除搜索二叉树中最小的一个节点出错：
i=temp->leftchild->Data.num;
delete temp->leftchild;
temp->leftchild=NULL;
修正：
i=temp->leftchild->Data.num;
p=temp->leftchild->rightchild;
delete temp->leftchild;
temp->leftchild=p;
4． 读取分割文件中的数据时忘记给文件来源编号赋值
for(i=0;i<sumfile;i++){//为每个输入文件流打开一个文件(刚新建的文件)
sprintf(fileto,"%s%d%s",filename,i+1,".txt");
fin[i][0].open(fileto,ios::in|ios::nocreate);
fin[i][0]>>Data;
修正：增加Data.num=i;
bsttree.AddData(Data);
}
5． 选择不覆盖源文件时忘记新建文件：
else{
sprintf(filefrom,"%s.txt",filesave);
修正：增加fout.open(filefrom);
fout.close();
}
2、 程序测试结果
【测试数据】
原文件中的数据（测试时选择的是不覆盖原文件）
文件名为file.txt
<shapetype id="_x0000_t75" coordsize="21600,21600" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 423pt; HEIGHT: 1in" type="#_x0000_t75"><imagedata cropright="25717f" cropleft="11377f" cropbottom="19795f" croptop="39290f" o:title="" src="file:///C:/DOCUME~1/JJJ/LOCALS~1/Temp/msohtml1/01/clip_image003.png"></imagedata></shape>
【输出结果】
分割成的文件
文件1，文件名为：file1.txt
<shape id="_x0000_i1026" style="WIDTH: 414pt; HEIGHT: 63pt" type="#_x0000_t75"><imagedata cropright="29983f" cropleft="11377f" cropbottom="21382f" croptop="39322f" o:title="" src="file:///C:/DOCUME~1/JJJ/LOCALS~1/Temp/msohtml1/01/clip_image005.png"><font face="Times New Roman" size="3"></font></imagedata></shape>
文件2，文件名为：file2.txt
<shape id="_x0000_i1027" style="WIDTH: 423pt; HEIGHT: 57.75pt" type="#_x0000_t75"><imagedata cropright="28561f" cropleft="9955f" cropbottom="21274f" croptop="39258f" o:title="" src="file:///C:/DOCUME~1/JJJ/LOCALS~1/Temp/msohtml1/01/clip_image007.png"><font face="Times New Roman" size="3"></font></imagedata></shape>
文件3，文件名为：file3.txt
<shape id="_x0000_i1028" style="WIDTH: 3in; HEIGHT: 57pt" type="#_x0000_t75"><imagedata cropright="45626f" cropleft="9955f" cropbottom="20475f" croptop="37616f" o:title="" src="file:///C:/DOCUME~1/JJJ/LOCALS~1/Temp/msohtml1/01/clip_image009.png"><font face="Times New Roman" size="3"></font></imagedata></shape>
排完序后保存道wjh.txt文件中的数据为：
<shape id="_x0000_i1029" style="WIDTH: 441pt; HEIGHT: 90.75pt" type="#_x0000_t75"><imagedata cropright="7229f" cropleft="9955f" cropbottom="19792f" croptop="35974f" o:title="" src="file:///C:/DOCUME~1/JJJ/LOCALS~1/Temp/msohtml1/01/clip_image011.png"><font size="3"></font></imagedata></shape>
【程序性能评价】
1．程序能很好的运行于WINDOWS的控制台下
2．能对数据有效的排序，其排序的结果符合预期的要求。
3．排序算法是先建立搜索二叉树，因为中序遍历搜索二叉树就能把二叉树中的数据按一定的顺序输出，这样对数据的排序时间会相对较少，提高了执行效率。
【性能改进方向】
1． 程序对数据的排序用搜索二叉树排的，其搜索二叉树的节点类中定义了线索化的标记，但在程序中并没有对搜索二叉树进行线索化，所以可以增加对搜索二叉树增加线索化代码。
2． 对于归并算法不是采用两两归并的思想，增加两两归并的代码，这样就不论数据的多少都能对之排序，因为单纯的两个数据不会大于内存。
3． 增加对错误处理能力上的代码。虽然可能出现错误的函数都有一个返回值，调用的代码中并没有对其返回值的处理。
4． 美化交互界面，使用户觉得更为友好。
【收获及体会】
外排序因为书本上很少提及，刚开始会觉得有点无从下手，但当明白了外排序的定义时就会有一个豁然开然的感觉。自己写的外排序程序用的是贵归并的思想，把一大堆的数据先分成n分，先把每一分的数据先排好序，再把排好序的数据集合成一堆数据。但用的归并算法又不是两两归并，而是n份数据一起归并。其实这样的算法和两两归并并没有多大的区别。
最开始以为自己的程序能不管文件中的数据量大小。但当把算法写完时才发现不是这样。因为我是把分割成的n份数据一起归并，当n乘以每个数据的字节数大于内存时排序就无能为力了。
学C++课程时我觉得写的程序代码越长越好，数据结构学完才觉得并不是这样。应该是所写的程序对同一功能的实现第一个应考虑程序执行的速度。而且很多时候有一种感觉：如果执行的速度加快了其代码就变得更为简练了。而且数据结构的课程设计主要体现的是数据的逻辑关系及程序执行速率的优化。
3、 源程序代码
#include <fstream.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
//声明结构体
class BSTTree;
//测试数据类
class TestData{
public:
int Data;//测试数据的关键码
int num;//存放的文件编号
TestData();
};
TestData::TestData(){
num=0;
}
//**************************************************************
ofstream & operator <<(ofstream &fout,TestData & aa)
{
fout<<aa.Data;
return fout;
}
ifstream & operator >>(ifstream &fin,TestData & aa)
{
fin>>aa.Data;
return fin;
}
bool operator >(TestData & a,TestData & aa){
if(a.Data<=aa.Data)
return false;
return true;
}
bool operator <(TestData & a,TestData & aa){
if(a.Data>=aa.Data)
return false;
return true;
}
//**************************************************************************
//排序用的搜索二叉树节点类
class BSTNode{
friend class BSTTree;
TestData Data;//数据
BSTNode * leftchild;//左孩子
BSTNode * rightchild;//右孩子
int threaded;//线索化标记(在这程序中不线索化)
public:
BSTNode();//空构造函数
BSTNode(TestData & Data);//构造函数
~ BSTNode();//析构函数
TestData GetData();//取节点数据
bool SetData(TestData & Da);//设置节点数据
};
BSTNode::BSTNode(){
leftchild=NULL;
rightchild=NULL;
threaded=0;
}
BSTNode::BSTNode(TestData & Da){
leftchild=NULL;
rightchild=NULL;
threaded=0;
Data=Da;
}
BSTNode::~ BSTNode(){
}
TestData BSTNode::GetData(){
return Data;
}
bool BSTNode::SetData(TestData & Da){
Data=Da;
return true;
}
//***************************************************************
//搜索二叉树类：
class BSTTree{
BSTNode *root;//根节点
public:
BSTTree();
bool AddData(TestData &Da);
bool isempty();
bool InorderAndDelete(char * filename);
int orderminanddelete(char * filename);
};
//////////////////////////////////////////
bool BSTTree::isempty(){
return !root;
}
//////////////////////////////////////////
BSTTree::BSTTree(){
root=NULL;
}
bool BSTTree::AddData(TestData & Da){
BSTNode *temp=root;
if(!root){
root=new BSTNode(Da);
}
else {
while(1){
if(Da>temp->Data&&temp->rightchild)
temp=temp->rightchild;
else if(Da>temp->Data){
temp->rightchild=new BSTNode(Da);
break;
}
else if(temp->leftchild)
temp=temp->leftchild;
else{
temp->leftchild=new BSTNode(Da);
break;
}
}
}
return true;
}
/////////////////////////////////////////////////
int BSTTree::orderminanddelete(char *filename){
BSTNode *temp=root;
BSTNode * p;
ofstream fout;
int i;
if(!temp)//二叉树中为空的时候
return -1;
fout.open(filename,ios::nocreate|ios::app);
if(fout.fail()){
cout<<filename<<"文件无法打开"<<endl;
return -1;
}
if(!temp->leftchild){//搜索二叉树没有左孩子时(即头节点为最小元素)
fout<<temp->Data<<" ";
i=temp->Data.num;
temp=root->rightchild;
delete root;
root=temp;
fout.close();
return i;
}
while(temp->leftchild->leftchild){
temp=temp->leftchild;
}
fout<<temp->leftchild->Data<<" ";
i=temp->leftchild->Data.num;
p=temp->leftchild->rightchild;
delete temp->leftchild;
temp->leftchild=p;
fout.close();
return i;
}
///////////////////////////////////////////////////
bool BSTTree::InorderAndDelete(char * filename){
while(root){
orderminanddelete(filename);
}
return true;
}
//****************************************************************
//定义全局变量
TestData Data;//用于测试的数据类型
BSTTree bsttree;//定义搜索二叉树类对象
//****************************************************************
//拆分文件
int SplitFile(char * filename,char *strError){
char fileto[30];
char filefrom[30];
sprintf(filefrom,"%s%s",filename,".txt");
ifstream fin;
ofstream fout;//文件流
int sumfile=0;
bool con=true;
fin.open(filefrom,ios::in|ios::nocreate);//打开要拆分的文件
if(fin.fail()){//如果打开文件出错
sprintf(strError,"%s","文件不存在,请检查输入的文件名!!!/n");
return -1;//错误标记
}
do{//开始读文件
for(int i=0;i<10;i++){
fin>>Data;
if(fin.eof()){//如果文件读到尾了
con=false;//跳出外层循环的标记
break;
}
bsttree.AddData(Data);
}
if(!i)//单纯从文件读取一个文件结尾符时i为0;这时不能执行下面的操作
break;
sumfile++;
sprintf(fileto,"%s%d.txt",filename,sumfile);//取新建文件的名字
fout.open(fileto);//打开新建文件
if(fout.fail()){
sprintf(strError,"不能新建%s文件",fileto);
return -1;
}
bsttree.InorderAndDelete(fileto);//把排好序的结构写入新建文件中
fout.close();
}while(con);
fin.close();
return sumfile;
}
//*****************************************************************
bool outquence(char *strError){
ifstream **fin;
ofstream fout;
int bestrow=-1;
char filename[30];//所用文件名
char filesave[30];
char filefrom[30];
char fileto[30];
int sumfile=0;//记录新建文件的数目
cout<<"/n/n/n/t请输入要排序的文件名:"<<flush;
cin>>filename;
sprintf(filefrom,"%s%s",filename,".txt");//给文件名加扩展名
while(-1==bestrow){
cout<<"/n/n/n/t排序完成后是否把原文件覆盖(Y/N)"<<endl;
switch(getch()){
case 'Y':case 'y':
bestrow=1;
break;
case 'N':case 'n':
cerr<<"请输入保存排序后数据的文件名:";
cin>>filesave;
bestrow=0;
break;
default:cout<<"/n/n/t输入有误,按任意键确定"<<endl;
getch();
}
}
sumfile=SplitFile(filename,strError);//返回把文件拆分的数目
if(sumfile==-1)//打开文件出错，错误信息在strError中保存
return false;
if(!sumfile){//拆分文件为0，说明是空文件
sprintf(strError,"%s 为空文件",strError);
return false;
}
if(sumfile>10){//拆分文件太大也不能排序
sprintf(strError,"%s%s",strError,"数据量过大,这种外排序方法不适合!!!");
return false;
}
fin=new ifstream*[sumfile];
for(int i=0;i<sumfile;i++)
fin[i]=new ifstream;
for(i=0;i<sumfile;i++){//为每个输入文件流打开一个文件(刚新建的文件)
sprintf(fileto,"%s%d%s",filename,i+1,".txt");
fin[i][0].open(fileto,ios::in|ios::nocreate);
fin[i][0]>>Data;
Data.num=i;
bsttree.AddData(Data);
}
if(bestrow){
fout.open(filefrom);
fout.close();
}
else{
sprintf(filefrom,"%s.txt",filesave);
fout.open(filefrom);
fout.close();
}
while(bsttree.isempty()==false){
if((i=bsttree.orderminanddelete(filefrom))==-1)//返回刚才写入文件的是从第几个文件中读入的数据
return false;
fin[i][0]>>Data;
if(fin[i][0].eof()){
continue;
}
Data.num=i;
bsttree.AddData(Data);
}
for(i=0;i<sumfile;i++)
fin[i][0].close();
bsttree.InorderAndDelete(filefrom);//把内存中剩余的数据写入原文件
return true;
}
//*****************************************************************
//主函数
void main(){
char strError[256];//错误描述
strError[0]=0;
do{
system("cls");
cout<<"/n/n/n/t请选择操作/n"
<<"/n/t按回车对文件进行排序/n"
<<"/n/t按Esc键放弃操作/n"
<<endl;
switch(getch()){
case 13:if(!outquence(strError))
cout<<"/n/n/n/t"<<strError<<"/n/t按任意键确定"<<endl;
else
cout<<"/n/n/n/t排序完成,按任意键确定"<<endl;
getch();
break;
case 27:return;
default:cout<<"/n/n/t输入有误,按任意键确定"<<endl;
getch();
}
}while(1);
}
发表评论
相关推荐
**外排序技术详解** 在大数据处理领域，当数据量超出计算机主存的限制时，外排序成为了一种不可或缺的技术。本文旨在深入解析外排序的基本原理及其在文件结构中的应用，结合给定文件“外排序图解.pdf”的内容，提供...
外排序中分为两步：初始游程的生成和有序文件的合并 请实现算法模拟初始游程的生成 假定系统中只能对规模为p的元素进行排序 现给定m个元素 m>p 对m个元素进行处理 给出所生成的若干个有序的初始游程 要求： 1...
在这个"数据结构课设_sdu_cs_大二_输者树外排序代码"项目中，我们聚焦于输者树（Loser Tree）这一特殊的数据结构，以及如何用它来执行外排序（External Sorting）。 输者树是一种用于高效比较多个元素的数据结构，...
标题 "外排序完整版代码" 暗示我们即将探讨的是一个关于外排序算法的实现。外排序是一种处理大量数据的排序算法，当数据量过大无法全部装入内存时，就需要借助外部存储进行排序。这类算法通常涉及磁盘I/O操作，通过...
外排序（External Sorting）是处理大规模数据时的一种关键技术，特别是在内存不足以容纳所有数据的情况下。在“山东大学数据结构课程设计第一部分代码——外排序”这个项目中，学生将学习并实现这种高级排序算法。 ...
Java归并外排序是一种在处理大量数据时，利用外部存储器进行排序的算法。当内存不足以容纳所有数据时，就需要借助硬盘等外部存储设备。这种排序算法通常由三个主要步骤组成：分块、内部排序和合并。 1. 分块：首先...
外排序 归并排序 源码 vc6.0环境 可以作为数据结构 c/c++课程的参考
### 外排序(磁盘排序)之多路归并排序的简单实现 #### 知识点概述 在计算机科学领域，排序算法是数据处理的重要组成部分。对于内存足够存放所有待排序元素的情况，我们通常采用诸如快速排序、堆排序等内部排序方法...
### Oracle外排序研究 #### 一、概述 在Oracle数据库管理中，排序是数据库操作中最基本也是最常用的功能之一。由于排序操作对于数据库性能的影响极大，因此如何优化排序过程成为了Oracle数据库管理员(DBA)的一项...
文件和外排序是计算机科学中处理大量数据时的重要概念，特别是在主存储器（内存）无法容纳整个数据集的情况下。外排序通常涉及到数据的预处理和合并排序两个阶段，以高效地在外存上进行数据操作。 **辅助存储器**，...
山东大学数据结构与算法课程设计竞赛树外排序实验（有详细注释） 实现源代码（本实验的全部源程序代码，程序风格清晰易理解，有充分的注释） 问题描述： 应用竞赛树结构模拟实现外排序。 基本要求： （1）设计并...
Oracle外排序是数据库管理系统中处理大量数据排序的一种方法，尤其在数据量超出内存容量时，Oracle会利用硬盘上的临时表空间进行数据的排序操作，即所谓的"外排序"。外排序相比内存排序效率低，因为它涉及到更多的...
根据排序操作的数据处理范围和数据存储位置的不同，可以将排序分为内排序和外排序两大类。 内排序，顾名思义，是指排序过程中所有待排序的元素都在内存中进行处理。这种方式适用于数据量不是很大的情况。内排序算法...
山东大学数据结构与算法课程设计实验2外排序实验报告（配图，配代码，详细解释，时间复杂度分析） 含数据结构与算法描述（整体思路描述，所需要的数据结构与算法）测试结果（测试输入，测试输出）实现源代码（本实验...
数据结构中的外排序是针对大型数据集的一种排序技术，它主要应用于当数据量超过内存容量，无法一次性加载到内存中进行排序的情况。外排序的基本思想是分治法，即通过多次内部排序和合并操作，逐步将整个大文件排序。...
在【标题】"Lec09 Query Processing 05 外排序1"中，主要讨论了外排序的实现方法，特别是【描述】中的两路归并外排序(Two-Way External Merge Sort)。 外排序的核心思想是通过多次磁盘读写操作，将大文件分成小的、...
数据结构中的外排序是针对大型数据集的一种排序技术，由于数据无法全部装入内存，因此需要借助外部存储设备，如磁盘。外排序的核心在于如何有效地利用内存和外存之间的交互来达到排序的目的。本教程主要讲解了外排序...
外排序是处理无法全部装入内存中的大数据量排序问题时采用的一种排序方法。它的核心思想是分阶段处理，主要包括两个相对独立的阶段：产生初始归并段和多路归并排序。初始归并段的生成是通过置换-选择排序算法来完成...
在吕鑫老师的C++第十课中，我们探讨的是如何构建一个学生系统，这个系统的核心是通过自定义的仿STL的list类以及采用表外排序技术来实现的。STL，即Standard Template Library，是C++标准库的一部分，提供了一系列...
第7章 文件与外排序是数据结构与算法领域的一个重要章节，主要探讨如何在处理大量数据时，尤其是在数据无法全部装入内存时的有效管理和排序方法。哈工大计算机科学与技术学院的张岩教授在此领域有深入研究，并在2018...