2亿个浮点数中求最大的100万之和

2653885

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[nTop];
  
• 
  
•     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[0])
  
•             {
  
•                 //交换并调整堆
  
•                 m_pfData[0] = 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[2 * nStart + 1] < pnData[2 * nStart + 2])
  
•             {
  
•                 nMaxChild = 2 * nStart + 2;
  
•             }
  
•         }
  
• 
  
•         //change data
  
•         if (pnData[nStart] < pnData[nMaxChild])
  
•         {
  
•             //交换nStart与nMaxChild的数据
  
•             fTemp = pnData[nStart];
  
•             pnData[nStart] = pnData[nMaxChild];
  
•             pnData[nMaxChild] = fTemp;
  
• 
  
•             //堆被破坏,需要重新调整
  
•             nStart = nMaxChild;
  
•         }
  
•         else
  
•         {
  
•             //比较左右孩子均大则堆未破坏,不再需要调整
  
•             break;
  
•         }
  
•     }
  
• }
  
• 
  
• //堆排序
  
• void CTopSum::HeapSort(float* pnData, int nLen)
  
• {
  
•     int i = 0;
  
•     float nTemp = 0;
  
• 
  
•     //将pnData[0, Len-1]建成大根堆
  
•     for (i = nLen / 2  - 1; i >= 0; i--)
  
•     {
  
•         CTopSum::HeapAdjust(pnData, i, nLen);
  
•     }
  
• 
  
•     for (i = nLen - 1; i > 0; i--)
  
•     {
  
•         nTemp = pnData[0];
  
•         pnData[0] = pnData;
  
•         pnData = nTemp;
  
• 
  
•         //将pnData[0...i]重写建成大根堆
  
•         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[2 * nStart + 2] < pnData[2 * nStart + 1])
  
•             {
  
•                 nMinChild = 2 * nStart + 2;
  
•             }
  
•         }
  
• 
  
•         //change data
  
•         if (pnData[nStart] > pnData[nMinChild])
  
•         {
  
•             //交换nStart与nMaxChild的数据
  
•             fTemp = pnData[nStart];
  
•             pnData[nStart] = pnData[nMinChild];
  
•             pnData[nMinChild] = 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[MAX_PATH] = {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;
  
• }
  
• 
  
• 
  
•