Освобождение стека C и удаление висящих указателей - PullRequest
Новая
       15

Освобождение стека C и удаление висящих указателей

0 голосов
/ 27 марта 2011

Я реализовал стек в C, используя структуру stackADT и набор функций: 

#ifndef _stack_h
#define _stack_h

// Macros
#define MaxStackSize 100
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// The type of element that may 
// be stored in the stack
typedef int stackElementT;

// The stackADT represents the abstract type used to store
// the elements that have been pushed
typedef struct stackCDT
{
    // A pointer to an array of elements
    stackElementT* elements;
    // Number of elements on the stack
    int count;
    // Number of elements we can push onto
    // the stack before having to resize
    int size;
}* stackADT;

// This function allocates and returns a new stack, which is
// initially empty... AKA - The Constructor
stackADT NewStack(void)
{
    // The stack to return
    stackADT stack;

    // Instanitate a new stack
    stack = (stackCDT*)(malloc(sizeof(stackCDT)));

    // Start with 0 elements of course
    stack->count = 0;
    // Allocate memory for 50 integers
    stack->elements = (stackElementT*)(malloc(50*sizeof(stackElementT)));
    // Establish the size of the stack
    stack->size = 50;

    return stack;
}


/********* GETTER FUNCTIONS *********/
// Returns the number of elements currently pushed 
// onto the stack
int StackDepth(stackADT stack)
{
    return (stack->count);
}

// This function returns the element a the specified index in
// the stack, where the top is defined as index 0
stackElementT GetStackElement(stackADT stack, int index);

// Function to print contents of stack
void PrintStack(stackADT stack)
{
    int i = 0;
    printf("count = %d\nsize = %d\n",stack->count,stack->size);

    for(i = (stack->count - 1); i >= 0; i--)
    {
        if((i%10 == 0) && (i != 0))
            printf("\n");
        printf("%d\t",*(stack->elements + i));
    }
}


// Functions to determine if stack is empty or full
int StackIsEmpty(stackADT stack)
{
    if(stack->count == 0)
        return 1;
    else
        return 0;
}
int StackIsFull(stackADT stack)
{
    if(stack->count == stack->size)
        return 1;
    else
        return 0;
}


// This function pushes the specified element onto the stack
void Push(stackADT stack, stackElementT element)
{
    // A temporary array that we may use later on
    stackElementT* temp = NULL;
    int oldCount = stack->count;
    int i = 0;

    // If the stack if full we need to do a
    // a transfer, resize, and retransfer, then push
    if(StackIsFull(stack))
    {
        // temp will be the same size as the old stack
        temp = (stackElementT*)(malloc((oldCount)*sizeof(stackElementT)));

        // Now we perform the transfer
        for(i = 0; i < oldCount; i++)
        {
            *(temp + i) = *((stack->elements) + i);
        }

        // Free the old memory
        free(stack->elements);
        stack->elements = NULL;

        // Recreate the stack with a 50% increase in size/capacity
        stack->elements = (stackElementT*)(malloc((3*oldCount/2)*sizeof(stackElementT)));
        // Re-establish the size
        stack->size = 3*oldCount/2;

        // Now we perform the transfer back
        for(i = 0; i < oldCount; i++)
        {
            *((stack->elements) + i) = *(temp + i);
        }

        // Free the temp array and 
        // remove dangling pointer
        free(temp);
        temp = NULL;

        // Now we push the element onto the stack
        *((stack->elements) + oldCount) = element;
        // Increase the count
        stack->count = oldCount + 1;
    }
    // If the stack isn't full
    else
    {
        *((stack->elements) + oldCount) = element;
        stack->count = oldCount + 1;
    }

}

// This function pops the top element from the stack and returns
// that value
stackElementT Pop(stackADT stack);


// This function frees the storage associated with the stack
void FreeStack(stackADT stack)
{
    // Start by freeing the elements on the stack
    // and remove dangling pointers
    free(stack->elements);
    stack->elements = NULL;

    // Finally free the stack
    free(stack);
    stack = NULL;
}

#endif

Очевидно, я еще не закончил (нужна функция pop).Меня беспокоит нижняя функция (FreeStack).Я протестировал приведенный ниже код следующим образом: 

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"
#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>

int main(void)
{
    stackADT stack;
    int i = 0;

    stack = NewStack();
    PrintStack(stack);

    for(i = 0; i < 60; i++)
    {
        Push(stack,i);
    }

    PrintStack(stack);
    FreeStack(stack);

    _CrtDumpMemoryLeaks();

    return 0;
}

Функция _CrtDumpMemoryLeaks () предназначена для Visual Studio и указывает, есть ли утечка памяти.По-видимому, я закрыл все утечки при вызове функции FreeStack (стек stackADT).Однако указатель стека по-прежнему содержит адрес памяти, что является проблемой, поскольку предполагается, что функция FreeStack освобождает память, указанную переменной стека, и устанавливает ее равной NULL.Это происходит внутри функции, но когда я возвращаюсь к основной функции во время отладки, я вижу адрес памяти все еще там.Что мне здесь не хватает?Если я могу освободить память, почему я не могу удалить висящий указатель?

Ответы [ 2 ]

2 голосов
/ 27 марта 2011

Вы передаете стек функции по значению, а не по адресу, модифицируете функцию для приема (stackADT *), и все будет в порядке.как прокомментировал Кристиан, вызов функции и использование стека, конечно же, должны быть изменены (поскольку теперь это указатель на указатель ...)

1 голос
/ 27 марта 2011

Вы передаете этот stackADT объект (указатель) по значению в вашем методе pop: 

void FreeStack(stackADT stack)

Итак, stack относится к локальной копии этого указателя.Когда вы устанавливаете этот указатель = NULL, вы изменяете его только внутри FreeStack.Метод main имеет собственную копию указанного указателя, не указывающую на NULL.

...