Heap实现中的BubbleUp方法c

Question

我早些时候在这里发布了我的堆实现，并在我的 add() 函数方面得到了一些急需的帮助，对此我深表感谢，但我仍然遇到无效读取和内存泄漏，需要进一步的帮助.

heap.h头文件：

#ifndef HEAP_H
#define HEAP_H
#include <stdbool.h>
struct Entry {
  int key;
  char* value;
};

typedef struct Entry Entry;

struct Heap {
  int capacity;
  int size;
  Entry** elements;
};

typedef struct Heap Heap;

Heap* makeHeap(int capacity);
void add(Heap* heap, int priority, char* value);
char* removeMin(Heap* heap);
char* peek(Heap* heap);
int size(Heap* heap);
void cleanupHeap(Heap* h);

#endif

heap.c 文件:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "heap.h"

Heap* makeHeap(int capacity) {
   //Make the heap
   Heap* theHeap = calloc(1, sizeof(Heap));
   //set its capacity to param
   theHeap->capacity = capacity;
   //inital size is 0
   theHeap->size = 0;
   //elements contains pointers (references) to Entry objects.
   theHeap->elements = calloc(capacity, sizeof(Entry*));
   //iterate capacity times allocating an entry reference for each element to be placed
   int i = 0;
   for(; i < capacity; i++) {
     theHeap-> elements[i] = calloc(1, sizeof(Entry));
   }

   return theHeap;
}

void expandCapacity(Heap* h) {
   Entry** oldcontents = h->elements;
   Entry** newarr = calloc(h->capacity * 2, sizeof(Entry*));
   int i = 0;
   for(; i < h->size; i += 1) {
      newarr[i] = h->elements[i];
   }

   h->capacity = h->capacity * 2;
   h->elements = newarr;
   free(oldcontents);
}

void add(Heap* h, int priority, char* val) {
  if (h->size >= h->capacity) {
    expandCapacity(h);
  }
  //insert at end of storage array and bubble up
  Entry* toAdd = calloc(1, sizeof(Entry));
  toAdd->key = priority;
  toAdd->value = val;
  h->elements[h->size]=toAdd;
  h->size += 1;
  bubbleUp(h, h->size);
}

void bubbleUp(Heap* h, int index) {
   if(index <= 0) { return; }
   Entry* e = h->elements[index];
   Entry* parent = h->elements[(index-1)/2];
   int comp = strcmp(e->value, parent->value);
   if(comp > 0) {
     swap(h, index, parent->key);
     bubbleUp(h, parent->key);
   }
   else {
     return;
   }
}

void swap(Heap* h, int index1, int index2) {
   Entry* tmp = h->elements[index1];
   h->elements[index1] = h->elements[index2];
   h->elements[index2] = tmp;
}
void cleanupHeap(Heap* h) {
   int i = 0;
   for (; i < h->capacity; i++) {
      free(h->elements[i]);
   }
   free(h->elements);
   free(h);
}

bubbleUp() 和 swap() 在 Java 中被赋予了函数，所以我所要做的就是使它们适应这个项目以使用 heap.h 文件，当然还要翻译它们到c。从我之前的帮助中，我对 add() 和 swap() 充满信心，因为它看起来非常简单，但我认为我对 bubbleUp() 的 c 翻译存在问题。非常感谢任何输入。

Java代码：

 void bubbleUp(int index) {
    if(index <= 0) { return; }
    Entry<K,V> e = this.entries.get(index);  
    Entry<K,V> parent = this.entries.get(parent(index));  
    int comp = this.comparator.compare(e.key, parent.key);
    if(comp > 0) {
      swap(index, parent(index));
      bubbleUp(parent(index));
    }
    else {
      return;
    }
}

void swap(int i1, int i2) {
    Entry<K,V> tmp = this.entries.get(i1);
    this.entries.set(i1, this.entries.get(i2));
    this.entries.set(i2, tmp);
}

测试：

#include "cutest/CuTest.h"
#include "heap.h"
#include <stdio.h>
#include <stdlib.h>

void TestAdd(CuTest *tc) {
  Heap* h = makeHeap(10);
  add(h, 4, "lol");
  CuAssertIntEquals(tc, 1, h->size);
  cleanupHeap(h);
}

CuSuite* StrUtilGetSuite() {
  CuSuite* suite = CuSuiteNew();
  SUITE_ADD_TEST(suite, TestAdd);
  return suite;
}

// Don't edit below this line

void RunAllTests(void) {
  CuString *output = CuStringNew();
  CuSuite* suite = CuSuiteNew();
  CuSuite* ourSuite = StrUtilGetSuite();

  CuSuiteAddSuite(suite, ourSuite);

  CuSuiteRun(suite);
  CuSuiteSummary(suite, output);
  CuSuiteDetails(suite, output);
  printf("%s\n", output->buffer);

  CuStringDelete(output);
  CuSuiteDelete(suite);
  free(ourSuite);
}

int main(void) {
  RunAllTests();
  return 0;
}

Answer 1

翻译不够接近。在 Java 中你有 parent(index)。在 C 中，您已将其内联为 (index-1)/2。 这是需要作为参数进入其他函数的内容:

swap(h, index, (index-1)/2);
bubbleUp(h, (index-1)/2);

Heap实现中的BubbleUp方法c

BubbleUp method in Heap implementation in c

c

arrays

heap

pointers