- 浏览: 1188796 次
文章分类
最新评论
-
nightkid:
图全挂了,看不到哦
UML Profile框图设计和应用 -
liuyuhua0066:
StringBuffer#reverse() API有这样的方 ...
java实现字符串反转 -
zhouxiangang123:
先谢谢了。希望有点帮助。
android 蓝牙开发 蓝牙 bluetoothsocket connect 经常出错 解决方法 -
down_data01:
...
android截屏示例,适合流媒体 MediaPlayer截屏 -
heant:
你好,通过你的文章对stk的应用有了一定的了解,想请教两个问题 ...
android stk 服务解析
外排序
用自己的思想写的外排序,还有很多地方需要改进。最先一位用搜索二叉树很好,但现在一想不是这样,如果把搜索二叉树改为最小堆会使程序执行的更好。
数据结构与算法设计课程设计
专业 信息与计算科学 班级 信息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);
}
相关推荐
外排序中分为两步:初始游程的生成和有序文件的合并 请实现算法模拟初始游程的生成 假定系统中只能对规模为p的元素进行排序 现给定m个元素 m>p 对m个元素进行处理 给出所生成的若干个有序的初始游程 要求: 1...
输者树实现磁盘文件外排序内容
图文并茂地分析了外排序的基本原理.
外排序 归并排序 源码 vc6.0环境 可以作为数据结构 c/c++课程的参考
山东大学数据结构课程设计第一部分代码——外排序
java归并外排序
外排序(磁盘排序)之多路归并排序的简单实现外排序(磁盘排序)之多路归并排序的简单实现
Oracle外排序研究的研究最新成果,致力于ORACLE和外排序算法研究的可以看看。
NULL 博文链接:https://zealove.iteye.com/blog/1279549
文件和外排序: 在外存上进行排序的最通常的方法是合并排序。这种方法由两个相对独立的阶段组成:预处理和合并排序。
外排序--基于败者树的多路归并排序算法的java实现
外排序问题的出现,主要是因为内存不够。当需要排序的数据量过多,以至于无法一次性把所有的数据都放入内存,这导致了外排序问题的出现。解决大数据量排序的方法是:先分块排序,后进行块合并。
vc++实现使用败者树实现外排序 vc++实现使用败者树实现外排序
基于Qt实现的股票分析预测软件,实现外排序功能,程序加载数据内存限制不超过30MB算法逻辑,创建索引,加快数据获取,根据股票的年月和代码进行k线图展示,热力图展示,相关系数计算,最后价格预测和股票价格曲线...
Oracle外排序研究.pdf
吕鑫老师学生信息管理系统表外排序源码,申请堆空间,将内存中的链表结点POSITION存放进数组,之后对数组里的POSITION排序,打印数组,计算量小,效率高,POSITION本质上是指针,对指针数组里的指针排序比结构体数据...
第11章外排序.pdf
数据结构外排序专题培训课件.ppt
数据结构外排序PPT学习教案.pptx
第7章 文件与外排序数据结构与算法Data Structrues and张岩海量数据计算研究中心哈工大计算机科学与技术学院第7章 文件与外部排序哈工大计算机科学