学步园

     这次读取的就是上一篇中的original文件的每一行到一个整数数组中。

     使用getline（缺省吧回车符endl作为行标记）分别把每一行读入到一个字符串数组，在这个字符数字最后加上/0构成一个字符串；

     使用strtok函数把每行组成的字符串以空格为标记划分多个单元返回为一个char*类型值pchTok；

     然后把pchTok使用atoi转化为int类型每个存入到一个整型数组的每个单元中sortArray[i]中；

     之后把数组使用堆排序算法排序后按照对齐格式输出到另外一个文本中。void heapSort_Write()中。

     为了使用字符串函数要包含string.h；为了使用setw要包含iomanip.h。

#include "heapSort.h"
#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
using namespace std;

#define  ARRAY_SIZE 1000
int heapcount = 0;//记录总共的比较次数

void FixHeap(int L[], int Hsize, int root, int k){
 //int larger = 0;
 if((2 * (root + 1)) > Hsize)//叶子节点
  L[root] = k;
 else{
  int larger = 0;
  if((2*(root + 1)) == Hsize)//只有左子树
   larger = 2 * root + 1;
  else if(L[2 * root + 1] > L[2 * (root + 1)])//有左右子树
   larger = 2 * root + 1;
  else
   larger = 2 * (root + 1);
  if(k > L[larger])
  {
   heapcount++;
   L[root] = k;
  }
  else{
   heapcount++;
   L[root] = L[larger];
   FixHeap(L, Hsize, larger, k);
  }
 }
 return;
}

void BuildHeap(int L[], int n){
 for(int i = n/2 - 1; i >= 0; i--)// 从第n/2-1个节点开始向上建堆
  FixHeap(L, n, i, L[i]);
 return;
}

void HeapSort(int L[], int n ){
 BuildHeap(L, n);
 for(int i = n -1; i >= 0; i-- ){
  int temp = L[i];
  L[i] = L[0];
  FixHeap(L, i , 0, temp);
 }
 return;
}

void HeapSort_Write(){

 int sortArray[15];//存储每行读入的数据，用于排序算法的调用

 string strLine;
 char achLine[ARRAY_SIZE];
 const char* pchTok;

 ifstream in_file("original.txt", ios::in);
 ofstream out_file("heapResult.txt");
 
 int precount = 0;//用于和thiscount作差来计算每次排序所需要比较的次数
 int num = 0;//用来记录是第几行的排序结果

 while(in_file.good()){
  num++;
  //每次读一行并且拷贝到achLine中构成一个数组
  getline(in_file, strLine);
  strLine.copy(achLine, strLine.size(), 0);
  achLine[strLine.size()] = '/0';

  //每行中的元素以空格为标识断开转换为int类型后存入数组
  pchTok = strtok(achLine, " ");
  int i = 0;
  while((pchTok != NULL)){
   sortArray[i] = atoi(pchTok);
   i++;
   //cout << atoi(pchTok) << " ";
   pchTok = strtok(NULL, " ");
  }

  //使用堆排序算法并将结果，第几行的比较结果以及这一行排序所用的比较次数写入到heapResult.txt文件
  HeapSort(sortArray, 15);

  for(int j = 0; j < 15; j++){
   //setw的使用方法
   out_file << setw(3) << setiosflags(ios::right)<< sortArray[j]  ;//数组中的每个数都在一个3字符的宽的空间右对齐输出
  }

  int thiscount = heapcount;
  out_file << "第" << setw(4) << num << "行总共比较了" << setw(4) << thiscount - precount << "次" <<"排序结果是：" << "   ";
  precount = thiscount;

  
  out_file << endl;
 }
 //cout << endl;
 out_file.close();
 in_file.close();
}