所以我正在编写一个用于管理堆数据结构的程序。我进行了两次动态内存分配,并且(我认为)我在打包时正确地释放了它们。
#include "heapFunctions.h"
#include "util.h"
#include <stdio.h>
#include <stdlib.h>
//Function Prototypes
static element* getArray(int*);
int main(void){
int result=0;
int i,v;
heap myHeap;
myHeap.H = NULL;
int arrayLength;
element* myArray = NULL;
char menuSelection = nextCommand(&i,&v); //get selection from user
while(!(menuSelection == 'S' || menuSelection == 's')){
switch(menuSelection){
case 'c':
case 'C':
if(myHeap.H == NULL)
myHeap = initialize(i); //initialize heap and identify any errors
else{
free(myHeap.H);
myHeap=initialize(i);
}
if(myHeap.H != NULL)
printf("Command Entered %c. Heap Initialized with capacity %d\n", menuSelection, i);
else
printf("Command Entered %c. Heap space not allocated\n", menuSelection);
break;
case 'r':
case 'R':
if(myArray == NULL)
myArray = getArray(&arrayLength); //populate array from text file
else{
free(myArray);
myArray = getArray(&arrayLength);
}
result=buildHeap(&myHeap, myArray, arrayLength); //build heap with array
if(result==1)
printf("Command Entered %c. Heap was built with size %d\n", menuSelection, arrayLength);
else if (result == -1)
printf("Command Entered %c. Heap build was unsuccesful\n", menuSelection);
else if (result == -2)
printf("Command Entered %c. Heap capacity can't accomodate array\n", menuSelection);
break;
case 'w':
case 'W':
printf("Command Entered %c. Printing Heap\n", menuSelection);
printHeap(&myHeap); //print contents of heap
break;
case 'i':
case 'I':
result = insert(&myHeap, i); //insert new key i into heap
if (result == 1)
printf("Command Entered %c. Heap insert with key %d was succesful\n", menuSelection, i);
else
printf("Command Entered %c. Heap insert was unsuccesful\n", menuSelection);
break;
case 'd':
case 'D':
result = deleteMax(&myHeap); //extract max value from heap
if (result > 0)
printf("Command Entered %c. Deletion of max heap value %d was succesful\n", menuSelection, result);
break;
case 'k':
case 'K':
result = increaseKey(&myHeap, i, v); //increase key at index i to v
if(result == 1)
printf("Command Entered %c. Key was succesfully increased to %d at index %d\n", menuSelection, v, i);
else if(result == -1)
printf("Command Entered %c. Key increase failed, %d not a valid index\n", menuSelection, i);
else if (result == -2)
printf("Command Entered %c. Key increase failed, %d is not larger than current key\n", menuSelection, v);
else if (result == -3)
printf("Command Entered %c. Key increase failed, Index starts at 1!", menuSelection);
}
menuSelection = nextCommand(&i,&v);
}
printf("You have entered command %c and stopped the program.\n", menuSelection);
//free resources
free(myArray);
free(myHeap.H);
return 1;
}
//get array from text file for heap
static element* getArray(int *Length){
element *arrayKey; //declare pointer for new array
int arrayLength=0;
char inputBuffer[10];
FILE *fp;
fp = fopen("HEAPinput.txt","r"); //open text file
if (fp == NULL){ /*check to make sure file was opened*/
fprintf(stderr, "Cannot open input file!!\n");
exit(1);
}
if(fgets(inputBuffer, sizeof(inputBuffer), fp) != NULL){ //get line of text
sscanf(inputBuffer, "%d", &arrayLength); //parse line for number of inputs
}
if(arrayLength < 1){ //error if array length is invalid
printf("Invalid Array Length\n");
exit(1);
}
arrayKey = (element *) malloc(sizeof(element)*arrayLength); //dynamically allocate memory for values
if(arrayKey == NULL){
printf("Memory for array not allocated\n");
exit(1);
}
int count;
for (count =0; count < arrayLength; count++){ //populate array with input from file
fscanf(fp, "%d", &arrayKey[count].key);
}
*Length = arrayLength;
fclose(fp); //close file
return arrayKey; //return array
}
//initialize new heap with size 0 and designated capacity
heap initialize(int capacity){
heap myHeap;
myHeap.size = 0;
myHeap.capacity = capacity;
myHeap.H = (element*) malloc(sizeof(element)*capacity); //dynamically allocate memory blocks for heap with designated capacity
return myHeap;
}
//copy contents of heap into H element,
int buildHeap(heap *myHeap, element * myArray, int arrayLength){
if(arrayLength > myHeap->capacity) //error if capacity is to small
return -2;
if(myHeap->H == NULL)
return -3;
if(memcpy(myHeap->H, myArray, sizeof(element)*arrayLength) == NULL) //error if memory not allocated properly
return -1;
myHeap->size=arrayLength; //set size to arrayLength
int count=0;
for(count=(arrayLength/2); count >= 0; count--){ //buildHeap
heapify(myHeap, count);
}
return 1;
}
我不太确定这是如何工作的,我尝试只发布我认为必要的代码片段。我只在两个位置动态分配内存,我认为我在离开 main 之前正确释放了它们。我看不出还有什么地方可以泄漏。
我使用了 valgrind 并得到了错误
LEAK SUMMARY:
==4042== definitely lost: 13,546 bytes in 70 blocks
==4042== indirectly lost: 53 bytes in 5 blocks
==4042== possibly lost: 29 bytes in 2 blocks
==4042== still reachable: 33,958 bytes in 53 blocks
我还让它打印了整个跟踪(带有调试符号),但所有输出几乎相同(对大多数块重复以下内容)。我尝试使用带有 -g 标志和 fulltrace 的 valgrind 使用 gcc + g++ 进行编译,但我仍然得到 ??? 用于内存位置后的输出。
==5804== 3 bytes in 1 blocks are possibly lost in loss record 2 of 97
==5804== at 0x4C2C73C: malloc (vg_replace_malloc.c:270)
==5804== by 0x440137: ??? (in /usr/bin/g++-4.7)
==5804== by 0x43CDEB: ??? (in /usr/bin/g++-4.7)
==5804== by 0x414C80: ??? (in /usr/bin/g++-4.7)
==5804== by 0x41592F: ??? (in /usr/bin/g++-4.7)
==5804== by 0x40296E: ??? (in /usr/bin/g++-4.7)
==5804== by 0x4E5576C: (below main) (libc-start.c:226)
349 (320 direct, 29 indirect) bytes in 2 blocks are definitely lost in loss record 73 of 96
==4098== at 0x4C2C92E: realloc (vg_replace_malloc.c:662)
谁能指出我正确的方向,至于我为什么泄漏内存。