以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  外排序算法探讨  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=50359)

--  作者：lgliu
--  发布时间：7/22/2007 7:49:00 PM

--  外排序算法探讨
遇到了一个题目:
5G的文本数据（每行长度不超过1024字节），存在一组文件中in.0,in.1,….，每个文件的大小为500M~1G。
请编写C程序对这批数据以行为单位进行排序，输出到一组新文件中out.0,out.1,out.2,……
输出文件的有序定义为：按照词典序，在同一文件中，前面的行小于等于后面的行；编号小的文件中的任意行都小于等于编号大的文件中的任意行
可用资源：内存不超过1.5G，硬盘不限制

经过思考我觉得可以通过两种方法来做:
一,利用多路归并排序,先将每个文件排好,然后归并
二,桶排序,首先将各个数据分发到不同的子文件中,且保证子文件间是有序的,这样将每个子文件排序即可.

但是一个小的技术问题是:我该如何利用C语言快速地进行按行读取?
还望各位能够多提算法和具体实现方面的建议.

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 2,315.430ms