0
У меня возникли проблемы с получением моей программы сортировки кучи, чтобы правильно сортировать целые числа из прочитанного файла. Выходной ток выглядит следующим образом:Heap sort - C programnig
Heap created successfully!
size = 10
Insertion
9
8
7
6
3
4
2
5
1
0
Delete
8
7
6
5
4
3
2
1
0
0
Я не знаю, что происходит с секцией удаления (вставка, кажется, работает нормально) мой код и были изменения в течение нескольких часов и до сих пор не могу получить его. Если кто-то может пролить свет на этот код, пожалуйста, сделайте это. Буду весьма признателен за это!
struct heap_t {
int last;
int size;
int max;
int *data;
};
void heapify(struct heap_t *heap_array, int size);
void swap(int i, int min, struct heap_t *heap_array);
void deletion(int i, struct heap_t *heap_array);
enum {INIT = 1, GROW = 2};
int main(int argc, char **argv)
{
char buf[LEN];
FILE *fp = NULL;
int i = 0;
if (argc != 2) {
printf("error in input\n");
printf("usage: ./heap [FILE]\n");
printf("[FILE] is a list of integers one per line\n");
exit(EXIT_FAILURE);
}
else {
fp = fopen(argv[1], "r");
assert(fp);
}
struct heap_t *heap = malloc(sizeof(struct heap_t));
heap->size = INIT;
heap->max = INIT;
heap->data = NULL;
while (fgets(buf, LEN, fp)) {
/* read in data from file */
/* assign to heap->data */
/* grow the array as necessary */
if (heap->size > heap->max) {
heap->data = realloc(heap->data, GROW * heap->max *sizeof(int));
assert(heap->data);
heap->max = GROW * heap->max;
}
else if (heap->data == NULL) {
heap->data = malloc(INIT * sizeof(int));
assert(heap->data);
}
*(heap->data + i) = atoi(buf);
/* Heapifys as it inserts, thus building the heap*/
heapify(heap, i);
heap->size++;
i++;
}
printf("\nHeap created successfully!\n");
/* size is off by one */
heap->size--;
printf("size = %d\n", heap->size);
printf("Insertion\n");
for (i = 0; i < heap->size; i++) {
printf("%d\n", *(heap->data + i));
}
heap->last = (heap->size);
i = 0;
while(heap->size){
deletion(i, heap);
i++;
}
printf("Delete\n");
for (i = 0; i < heap->size; i++) {
printf("%d\n", *(heap->data + i));
}
/* send data to stdin -- if you correctly built a heapsort
* this will print the data in ascending order */
/*for (i = 0; i < heap->size; i++) {
printf("%d\n", *(heap->data + i));
}*/
/* cleanup */
free(heap->data);
free(heap);
fclose(fp);
return 0;
}
void heapify(struct heap_t *heap_array, int i)
{
int child = i, parent = (child - 1)/2;
while(child != 0 && *(heap_array->data + child) > *(heap_array->data + parent)){
swap(child, parent, heap_array);
child = parent;
parent = (child - 1)/2;
for(j = 0; j < heap_array->size; j++){
printf("%d, ", *(heap_array->data + j));
}
printf("\n");
}
}
void swap(int child, int parent, struct heap_t *heap_array)
{
int temp = 0;
temp = *(heap_array->data + child);
*(heap_array->data + child) = *(heap_array->data + parent);
*(heap_array->data + parent) = temp;
}
void deletion(int i, struct heap_t *heap_array)
{
int temp;
int j = 0;
temp = *(heap_array->data + 0);
*(heap_array->data + 0) = *(heap_array->data + (heap_array->size - 1));
*(heap_array->data + (heap_array->size)) = temp;
heap_array->size--;
for(i = j; j < heap_array->size; j++){
heapify(heap_array, j);
}
printf("%d -", *(heap_array->data + 0));
}
Поскольку код не содержит комментариев и не имеет никакого очевидного смысла, очень трудно понять, как его исправить. Например, 'deletion' принимает параметр' i', который он никогда не использует, и имя «i» не дает нам понять, что это означает. Цикл также озадачивает. Если вы удалите из кучи, не получите ли меньшую кучу? Поэтому, если предполагается, что 'i' является тем, какой элемент удалить из кучи, он быстро выходит за пределы. (Рассмотрите кучу с десятью пунктами. После того, как вы удалили 8 предметов, вы пытаетесь удалить элемент 9, но куча с двумя оставшимися останками не имеет элемента 9! Так что же означает код ?!) –