Попытка реализовать HeapSort - PullRequest
Новая
       6

Попытка реализовать HeapSort

0 голосов
/ 17 февраля 2011

Я застреваю на сортировке кучи.У меня есть код, но я думаю, что он довольно неправильный, так как мне трудно его компилировать.Какие-либо предложения?Сортировка кучи должна быть довольно простой для реализации, но у меня есть куча синтаксических ошибок.Вот мой код: 

/* Framework for Heap Sort
 * CS333 Spring 2011
 * 
 */
#include <stdio.h>
#define MAX_SIZE 1000000
int data[MAX_SIZE];
int n;
int j;

int parent(int j) {
if(j==1)
    return 0;

if(j%2==0)
    return ( (j / 2)-1);
else
    return ( (j / 2));
}

int left(int j) {
  return (2 * j) + 1;
}

int right(int j) {
  return (2 * j) + 2;
}

void heapify(int data[], int j) {
  int l = left(j), great;
  int r = right(j);
  if ( (data[l] > data[j]) && (l < sizeof(data))) {
    great = l;
  }
  else {
    great = j;
  }
  if ( (data[r] > data[great]) && (r < sizeof(data))) {
    great = r;
  }
  if (great != j) {
    int temp = data[j];
    data[j] = data[great];
    data[great] = temp;
    heapify(data, great);
  }
}

int BuildMaxHeap(int data[]) {
  for (int j = (sizeof(data) - 1) / 2; j >= 0; j--) {
    heapify(data, j);
    return data;
  }
}

void HeapSort(int data[]) {
  BuildMaxHeap(data);
  for (int j = sizeof(data); j > 0; j--) {
    int temp = data[0];
    data[0] = data[data.sizeof() - 1];
    data[sizeof(data) - 1] = temp;
    sizeof(data) = sizeof(data) - 1;
    heapify(data, 0);
  }

}

int main()
{
  int i;

  /* Read in the data */
  n = 0;
  while (scanf("%d", &data[n]) == 1)
    ++n;
    /* Sort the numbers low to high */

     HeapSort(data);

  /* Print out the data */
  for (i = 0; i < n; ++i)
    printf("%d", data[i]);
}

1 Ответ

2 голосов
/ 17 февраля 2011

Большинство ваших проблем, кажется, в вашей программе HeapSort: 

void HeapSort(int data[]) {
  BuildMaxHeap(data);
  for (int j = sizeof(data); j > 0; j--) {

Когда вы передаете массив функции, подобной этой, то, что получает функция, на самом деле является указателем. Использование sizeof для этого указателя не скажет вам о размере данных, на которые указывает указатель - он просто скажет вам, сколько байтов занимает сам указатель (обычно 4). Вы, вероятно, хотите передать размер массива в качестве параметра: 

void HeapSort(int *data, size_t data_size) {

и на протяжении оставшейся части процедуры вы будете ссылаться на data_size, а не sizeof(data). 

int temp = data[0];
data[0] = data[data.sizeof() - 1];
data[sizeof(data) - 1] = temp;
sizeof(data) = sizeof(data) - 1;

sizeof(whatever) также по существу постоянная, а не переменная; Вы не можете использовать его в качестве цели назначения (но, опять же, использование data_size, как предложено выше позволит позволить вам выполнить назначение).

...