2亿个浮点数中求最大的100万之和
2亿个浮点数中求最大的100万之和题目：有一个文件中保存了2亿个浮点数，每个浮点数都以'/n'分隔。求最大的100万个浮点数之和。
算法：1. 首先建立一个容量为100万(nTop)的float数组，从文件读取浮点数填充。2. 利用堆排序对该100万条记录排序(确保第一个元素为最小值)3. 从文件中读取一个浮点数与第一个元素比较，如果大于第一个元素则替换该元素，并调整堆的结构。4. 重复步骤3一直到数据读取完5. 将数组中的元素全部相加，得到结果
源代码:
[*]//CTopSum.h
[*]#pragma once
[*]#include <windows.h>
[*]
[*]class CTopSum
[*]{
[*]public:
[*] CTopSum();
[*] ~CTopSum(void);
[*]
[*]public:
[*] static void HeapAdjust(float* pnData, int nStart, int nLen);
[*] static void HeapSort(float* pnData, int nLen);
[*]
[*]public:
[*] float GetTopSum(LPCTSTR lpszFile, int& nTop);
[*]
[*]private:
[*] void Clear();
[*] static void HeapAdjustLit(float* pnData, int nStart, int nLen);
[*]private:
[*] float* m_pfData;
[*]};
[*]
[*]//CTopSum.cpp
[*]#include "StdAfx.h"
[*]#include "topsum.h"
[*]#include <iostream>
[*]
[*]using namespace std;
[*]
[*]CTopSum::CTopSum()
[*]{
[*] m_pfData = NULL;
[*]}
[*]
[*]CTopSum::~CTopSum(void)
[*]{
[*] Clear();
[*]}
[*]
[*]void CTopSum::Clear()
[*]{
[*] if (NULL != m_pfData)
[*] {
[*] delete[] m_pfData;
[*] m_pfData = NULL;
[*] }
[*]}
[*]
[*]//获取前top位的总和
[*]float CTopSum::GetTopSum(LPCTSTR lpszFile, int& nTop)
[*]{
[*] FILE* fp = NULL;
[*] float fData = 0.0f;
[*] float fSum = 0.0f;
[*] int i = 0;
[*]
[*] //判断输入参数
[*] if ( (NULL == lpszFile) || (nTop <= 0) )
[*] {
[*] cout << "error parameter" << endl;
[*] return 0.0f;
[*] }
[*]
[*] //清除操作
[*] Clear();
[*]
[*] //打开文件
[*] fp = ::fopen(lpszFile, "r");
[*]
[*] if (NULL == fp)
[*] {
[*] cout << "open file failed!" << endl;
[*] return 0.0f;
[*] }
[*]
[*] //分配空间
[*] m_pfData = new float;
[*]
[*] if (NULL == m_pfData)
[*] {
[*] cout << "new operator failed!" << endl;
[*] return 0.0f;
[*] }
[*]
[*] cout << "please wait..." << endl;
[*]
[*] //读取前nTop个数据
[*] for (i = 0; i < nTop; i++)
[*] {
[*] if (EOF != ::fscanf(fp, "%f/n", &fData))
[*] {
[*] m_pfData = fData;
[*] }
[*] else
[*] {
[*] break;
[*] }
[*] }
[*]
[*] //最大的个数小于nTop,求前i个数据
[*] if (i < nTop)
[*] {
[*] nTop = i;
[*] }
[*] else
[*] {
[*] CTopSum::HeapSort(m_pfData, nTop);//排序
[*]
[*] while (EOF != ::fscanf(fp, "%f/n", &fData))
[*] {
[*] if (fData > m_pfData)
[*] {
[*] //交换并调整堆
[*] m_pfData = fData;
[*] CTopSum::HeapAdjustLit(m_pfData, 0, nTop);
[*] }
[*] }
[*] }
[*]
[*] fSum = 0;
[*] for (i = 0; i < nTop; i++)
[*] {
[*] fSum += m_pfData;
[*] }
[*]
[*] return fSum;
[*]}
[*]
[*]//调整大根堆
[*]void CTopSum::HeapAdjust(float* pnData, int nStart, int nLen)
[*]{
[*] int nMaxChild = 0;
[*] float fTemp = 0;
[*]
[*] while ( ( 2 * nStart + 1) < nLen)
[*] {
[*] nMaxChild = 2 * nStart + 1;
[*] if ( (2 * nStart + 2) < nLen)
[*] {
[*] //比较左子树和右子树,记录最大值的Index
[*] if (pnData < pnData)
[*] {
[*] nMaxChild = 2 * nStart + 2;
[*] }
[*] }
[*]
[*] //change data
[*] if (pnData < pnData)
[*] {
[*] //交换nStart与nMaxChild的数据
[*] fTemp = pnData;
[*] pnData = pnData;
[*] pnData = fTemp;
[*]
[*] //堆被破坏,需要重新调整
[*] nStart = nMaxChild;
[*] }
[*] else
[*] {
[*] //比较左右孩子均大则堆未破坏,不再需要调整
[*] break;
[*] }
[*] }
[*]}
[*]
[*]//堆排序
[*]void CTopSum::HeapSort(float* pnData, int nLen)
[*]{
[*] int i = 0;
[*] float nTemp = 0;
[*]
[*] //将pnData建成大根堆
[*] for (i = nLen / 2 - 1; i >= 0; i--)
[*] {
[*] CTopSum::HeapAdjust(pnData, i, nLen);
[*] }
[*]
[*] for (i = nLen - 1; i > 0; i--)
[*] {
[*] nTemp = pnData;
[*] pnData = pnData;
[*] pnData = nTemp;
[*]
[*] //将pnData重写建成大根堆
[*] CTopSum::HeapAdjust(pnData, 0, i);
[*] }
[*]}
[*]
[*]void CTopSum::HeapAdjustLit(float* pnData, int nStart, int nLen)
[*]{
[*] int nMinChild = 0;
[*] float fTemp = 0;
[*]
[*] while ( ( 2 * nStart + 1) < nLen)
[*] {
[*] nMinChild = 2 * nStart + 1;
[*] if ( (2 * nStart + 2) < nLen)
[*] {
[*] //比较左子树和右子树,记录最大值的Index
[*] if (pnData < pnData)
[*] {
[*] nMinChild = 2 * nStart + 2;
[*] }
[*] }
[*]
[*] //change data
[*] if (pnData > pnData)
[*] {
[*] //交换nStart与nMaxChild的数据
[*] fTemp = pnData;
[*] pnData = pnData;
[*] pnData = fTemp;
[*]
[*] //堆被破坏,需要重新调整
[*] nStart = nMinChild;
[*] }
[*] else
[*] {
[*] //比较左右孩子均大则堆未破坏,不再需要调整
[*] break;
[*] }
[*] }
[*]}
[*]
[*]//main.cpp
[*]#include "stdafx.h"
[*]#include "topsum.h"
[*]#include <iostream>
[*]
[*]using namespace std;
[*]
[*]int _tmain(int argc, _TCHAR* argv[])
[*]{
[*] TCHAR szFile = {0};
[*] int nNum = 0;
[*] CTopSum objTopSum;
[*]
[*] cout << "please input count file name:" << endl;
[*] cin >> szFile;
[*]
[*] cout << "please input top num:"<< endl;
[*] cin >> nNum;
[*]
[*] cout << "top " << nNum << " value = " << objTopSum.GetTopSum(szFile, nNum) << endl;
[*]
[*] ::system("pause");
[*]
[*] return 0;
[*]}
[*]
[*]
[*]
页:
[1]