滴水逆向联盟
标题:
VC++2012编程演练数据结构《36》磁盘文件进行排序
[打印本页]
作者:
大灰狼
时间:
2014-8-13 08:30
标题:
VC++2012编程演练数据结构《36》磁盘文件进行排序
如何给磁盘文件排序
问题描述：
输入：一个最多含有n个不相同的正整数的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间越短越好。
分析：一步一步地解决这个问题，
创建一个工程
声名如下
[cpp]
view plain
copy
#include "stdafx.h"
//对外存文件(磁盘文件)进行排序的算法
typedef struct
{int key;
int stn;}ElemType;
int b=sizeof(ElemType);
//类定义
class LoadFile
{public:
//构造函数
//向物理文件名为fname指针所指文件中输出n个记录
LoadFile(char* fname,int n);
//采用选择排序法对文件A的记录进行排序
void FMergeSort(fstream &A,ElemType (&a)[10],int n);
//顺序打印ff文件中每个记录
void Print(fstream &ff);
};
//类的实现
//向物理文件名为fname指针所指文件中输出n个记录
LoadFile::LoadFile(char* fname,int n)
{fstream f(fname,ios::out|ios::dec|ios::trunc);
//用所给的物理文件名定义一个输出文件流对象f，
//它是与物理文件相对应的逻辑文件
if(!f) {
cerr<<fname<<' '<<"not found!"<<endl;exit(1);}
for(int i=0;i<n;i++)
{//假定向每个记录的排序码域输入数据,其值由随机产生
ElemType x;
x.key=i;x.stn=rand()%200;
f.write((char *)&x,b);}
f.close();}//关闭逻辑文件f
//采用选择排序法对文件A的记录进行排序
void LoadFile::FMergeSort(fstream &A,ElemType (&a)[10],int n)
{int i,j,k;
A.seekg(0,ios::end);//将文件指针移至文件未
A.seekg(0);//将文件指针移至文件首
for(i=0;i<n;i++)
A.read((char*)&a
,b);//从文件中读一记录到a
中
for(i=0;i<n-1;i++)
{k=i;
for(j=i+1;j<n;j++)
if(a[k].stn>a[j].stn) k=j;
if(k!=i)
{int t;
t=a[k].stn;a[k].stn=a
.stn;a
.stn=t;
t=a[k].key;a[k].key=a
.key;a
.key=t;}
}
A.seekg(0);
for(i=0;i<10;i++)
A.write((char *)&a
,b);
}
//顺序打印ff文件中每个记录
void LoadFile::Print(fstream &ff)
{ElemType x;
ff.seekg(0,ios::end);//将文件指针移至文件未
int n=ff.tellg()/b; //用n表示文件所含的记录数
ff.seekg(0); //将文件指针移至文件首
for(int i=0;i<n;i++) {
ff.read((char*)&x,b);//从文件中读一记录到x中
cout<<setw(4)<<x.stn;}
cout<<endl;
}
调用如下
[cpp]
view plain
copy
void main()
{cout<<"运行结果:\n";
int m=10;
char *fa=".\\ak1.dat";
ElemType d[10];
srand(time(0));
fstream fna(fa,ios::out|ios::in|ios::dec|ios::trunc);
cout<<"文件未排序前的结果:\n";
LoadFile myfile(fa,m);
myfile.Print(fna);
cout<<"文件排序后的结果:\n";
myfile.FMergeSort(fna,d,m);
myfile.Print(fna);
fna.close();cin.get();
}
运行如下
欢迎光临 滴水逆向联盟 (http://www.dtdebug.com/)
Powered by Discuz! X3.2
