-4

我必须将文件中的所有数据（整数）读取到数组中，然后迭代数组以生成最小堆并将它们添加到当前堆的最后一个元素之后。读入数组后，我必须调用SiftUp()每个元素，这意味着将 int 移动到数组中的正确位置。此外，我必须在读取整数时对其进行计数并将全局 heapSize 设置为该值。在所有输入结束时，我试图打印出最小堆数组的前五个元素。输出错误。我的代码没有做任何最小堆，这就是为什么输出是随机的。逻辑有什么问题？

输入文件有 97 个整数：

347
765
654
44
15
567
098 
//and so on

输出：

Please enter the name of the file to open :data.txt
 at index 1 :284
 at index 2 :870
 at index 3 :319
 at index 4 :47
 at index 5 :312
 at index 1 :284    // i dont know why it started again
 at index 2 :870
 at index 3 :319
 at index 4 :47
 at index 5 :312     //stops here

我的程序：

using namespace std;

int heapSize;
void SiftUp(int arr[], int heapSize);
const int arr_Size=100;
int heapArr[arr_Size];
void minHeap(int heapArr[]);

int main()
{
    int integers;
    string fileName;
    ifstream infile;
    cout << "Please enter the name of the file to open :";
    cin >> fileName;
    infile.open(fileName.c_str());
    if(!infile)
    {
        cerr << "An eror occurred while openieng the file.";
        exit(1);
    }
    while(!infile.eof())
    {

        for (int i=0; i<arr_Size; i++){
            infile >> integers;
            heapArr[i]=integers;
            heapSize=i;
    }
}
infile.close();
minHeap(heapArr);
for (int count =1 ; count <=5 ; count ++)
{
    cout << " Min at index " << count  <<" :"<< heapArr[count] << endl;
}
return 0;
}

void SiftUp(int arr[], int heapSize)
{
    int p;
    if (heapSize==1) return;
    else p = heapSize/2;
    if (arr[p] > arr[heapSize]) return;
    else swap (arr[heapSize],arr[p]);
    SiftUp(arr, p);
    }

void minHeap(int arr[])
{
    for (int i=0; i <arr_Size ; i++){ 
        SiftUp(arr, heapSize);
    }
}
4

2 回答 2

1

为什么要使用数组作为已经全局定义的参数传递。我试图修复你的代码。看看并照原样做。希望，它会奏效。

 int main()
{
    int integer;
    string fileName;
    ifstream infile;
    cout << "Please enter the name of the file to open :";
    cin >> fileName;                                                  // asks user to     input filename
    infile.open(fileName.c_str());                                    // opens file
    if(!infile)
    {
    cerr << "An eror occurred while openieng the file.";
    exit(1);
    }
    int i;
    for (i=1; i<arr_Size; i++){
    infile >> integer;
    if(infile.fail())break;
    heapArr[i]=integer;
    SiftUp(i);
    }
    infile.close();
    heapSize=i;
    for (int count =1 ; count <=5 ; count ++)
    {
    cout << count  <<" :"<< heapArr[count] << endl;
    }

    return 0;
}

void SiftUp(int heapSize){
int p;
if (heapSize==1) return;
p = heapSize/2;
if (heapArr[p] < heapArr[heapSize]) return;
swap (heapArr[heapSize],heapArr[p]);
SiftUp(p);
}
于 2018-08-16T07:25:08.773 回答
1 
using namespace std;

int heapSize;
const int arr_Size=100;
int heapArr[arr_Size];
int main()
{
 int integers;
 string fileName;
 ifstream infile;
 cout << "Please enter the name of the file to open :";
 cin >> fileName;
 infile.open(fileName.c_str());
 if(!infile)
 {
     cerr << "An eror occurred while openieng the file.";
     exit(1);
 }
 while(!infile.eof())
 {

     for (int i=0; i<arr_Size; i++){
         infile >> integers;
         heapArr[i]=integers;
         heapSize=i;
 }

 infile.close();
 build_minheap(heapArr,heapSize);
 for (int count =1 ; count <=5 ; count ++)
 {
     cout << " Min at index " << count  <<" :"<< heapArr[count] << endl;
 }
 return 0;
}

void min_heapify(int *a,int i,int n)
{
   int j, temp;
   temp = a[i];
   j = 2 * i;
   while (j <= n)
   {
       if (j < n && a[j+1] < a[j])
           j = j + 1;
       if (temp < a[j])
           break;
       else if (temp >= a[j])
       {
           a[j/2] = a[j];
           j = 2 * j;
       }
   }
  a[j/2] = temp;
  return;
 }
 void build_minheap(int *a, int n)
 {
    int i;
    for(i = n/2; i >= 1; i--)
    {
        min_heapify(a,i,n);
     }
 }
于 2018-08-07T05:41:56.923 回答