處理一個類項目,我需要實現一個合併排序來排序500,000個項目。 經過多次嘗試後,我嘗試在線尋找源代碼,並在這裏找到了一些:http://www.sanfoundry.com/cpp-program-implement-merge-sort/合併排序:堆損壞刪除[]
我必須更改代碼以使用動態數組(大小)。當程序運行合併函數時,我使用要合併的元素(或高)數創建一個新的動態數組。一旦函數完成排序並將它們合併到原始數組中,我在新的動態數組上使用delete []。這是我得到「檢測到堆損壞」錯誤的地方。
下面是代碼(文字牆):
//Heap Sort
#include <iostream>
#include <fstream>
#include <sstream>
#include <ctime>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
//Function Prototypes
void mergesort(int *a, int low, int high);
void merge(int *a, int low, int high, int mid);
int main()
{
//Start with element 1 of the array
int line_no = 0;
int num;
int array_size = 500000;
int* num_array = new int[array_size];
//Open file for input
fstream in_file("CSCI3380_final_project_dataset.txt", ios::in);
//Test for file opening
if (!in_file)
{
cout << "Cannot open words1.txt for reading" << endl;
exit(-1);
}
//Read file
while(true)
{
//Read one line at a time
in_file >> num;
//Test for eof
if (in_file.eof())
break;
num_array[line_no] = num;
//Increment array position
line_no++;
}
//Close the file
in_file.close();
//Start Time
clock_t time_a = clock();
//Run Sorting Algorithim
mergesort(num_array, 0, array_size-1);
//End Time
clock_t time_b = clock();
//Elapsed Time
if (time_a == ((clock_t)-1) || time_b == ((clock_t)-1))
{
cout << "Unable to calculate elapsed time" << endl;
}
else
{
int total_time_ticks = time_b - time_a;
cout << "Elapsed time: " << total_time_ticks << endl;
}
delete[] num_array;
return 0;
}
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(int *a, int low, int high, int mid)
{
//--------------------------Create new array-------------------------------
int* sort_array = new int[high];
//--------------------------New Array Created-----------------------------
int i, j, k;
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
sort_array[k] = a[i];
k++;
i++;
}
else
{
sort_array[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
sort_array[k] = a[i];
k++;
i++;
}
while (j <= high)
{
sort_array[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = sort_array[i];
}
//---------------------------Delete the New Array--------------------
delete[] sort_array;
//--------------------------Oh No! Heap Corruption!------------------
}
你很喜歡空白! :D – Rubens
C++的第一條規則:不要做你自己的內存管理。 –
我想你正在訪問你在合併中創建的sort_array的末尾1。你不能訪問sort_array [高]。 – drescherjm