c - C 链表中的内存泄漏

Question

我一直在为学校做一个项目(今晚到期!)，我有一些严重的内存问题。我是 C 的新手，在分配指针和诸如此类的东西时仍然被抛出一个循环，所以我真的需要一些帮助。

代码如下。文件的顺序是 LinkedLists.h(LinkedList 模块的头文件)、LinkedLists.c(LinkedList 模块)和 TestList.c(主模块)。

/******************************************************************************
* Base struct to contain data structure element information: deterimined by
* the application needs.
******************************************************************************/
#ifndef _LINKED_LISTS_H_
#define _LINKED_LISTS_H_

typedef struct ElementStructs
  {
        int ElementPosition;
        char* ElementValue;
  } ElementStructs;

/**************  Nothing else in the module needs to be modified *************/



/******************************************************************************
* Base struct of list nodes, contains user information and link pointers.
* The "ElementStructs" typemark must be defined based on specific needs of the
* application.
******************************************************************************/
typedef struct LinkedListNodes
  {
   /* The user information field */
   ElementStructs *ElementPtr;
   /* Link pointers */
   struct LinkedListNodes *Next;
   struct LinkedListNodes *Previous;
  } LinkedListNodes;

/******************************************************************************
* Base struct used to manage the linked list data structure.
******************************************************************************/
typedef struct LinkedLists
  {
   /* Number of elements in the list */
   int NumElements;
   /* Pointer to the front of the list of elements, possibly NULL */
   struct LinkedListNodes *FrontPtr;
   /* Pointer to the end of the list of elements, possibly NULL */
   struct LinkedListNodes *BackPtr;
  } LinkedLists;

/******************************************************************************
* Initialized the linked list data structure
******************************************************************************/
void InitLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* Adds a record to the front of the list.
******************************************************************************/
void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr);

/******************************************************************************
* Adds a record to the back of the list.
******************************************************************************/
void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr);

/******************************************************************************
* Removes (and returns) a record from the front of the list ('works' even on 
* an empty list by returning NULL).
******************************************************************************/
ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* Removes (and returns) a record from the back of the list ('works' even on 
* an empty list by returning NULL).
******************************************************************************/
ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* De-allocates the linked list and resets the struct fields as if the
* list was empty.
******************************************************************************/
void DestroyLinkedList(LinkedLists *ListPtr);

#endif /* _LINKED_LISTS_H_ */

链表.c:

/******************************************************************************
* Extracts and prints the first and last 6 elements from the specified data 
* set and prints the total number of words in the input file. Utilizes the
* LinkedList module as specified in LinkedLists.h
* Written by xxxxxxx
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "LinkedLists.h"

void InitLinkedList(LinkedLists *ListPtr)
{
        ListPtr->NumElements = 0;
        ListPtr->FrontPtr = NULL;
        ListPtr->BackPtr = NULL;
}

void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs
        *DataPtr)
{

        /* If there are no other elements, create new node and add it,
         * assigning it to both the front and back pointers */
        if(ListPtr->NumElements == 0)
        {
                ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Next = NULL;
                ListPtr->FrontPtr->Previous = NULL;
                ListPtr->BackPtr = ListPtr->FrontPtr;
        }

        /* If there are other elements, create new node and add it to the front
         * while retaining previous node order */
        else
        {
                /* Initialize new LinkedListNode */
                ListPtr->FrontPtr->Previous = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->Previous->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Previous->Next = ListPtr->FrontPtr;
                ListPtr->FrontPtr->Previous->Previous = NULL;

                /* Assign newly initialized node as front node of LinkedList */
                ListPtr->FrontPtr = ListPtr->FrontPtr->Previous;
        }

        /* List size plus one */
        (ListPtr->NumElements)++;
}

void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs
        *DataPtr)
{
        /* If there are no other elements, create new node and add it,
         * assigning it to both the front and back pointers */
        if(ListPtr->NumElements == 0)
        {
                ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Next = NULL;
                ListPtr->FrontPtr->Previous = NULL;
                ListPtr->BackPtr = ListPtr->FrontPtr;
                /*printf("Adding %s\n", DataPtr->ElementValue);*/
        }

        /* If there are other elements, create new node and add it to the back
         * while retaining previous node order */
        else
        {
                /* Initialize new LinkedListNode */
                ListPtr->BackPtr->Next = malloc(sizeof(LinkedListNodes));
                ListPtr->BackPtr->Next->ElementPtr = DataPtr;
                ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr;
                ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr;
                ListPtr->BackPtr->Next->Next = NULL;

                /* Assign newly initialized node as back node of LinkedList */
                ListPtr->BackPtr = ListPtr->BackPtr->Next;
                printf("Adding %s\n", ListPtr->BackPtr->ElementPtr->ElementValue);
        }

        /* List size plus one */
        (ListPtr->NumElements)++;
}

ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements > 0)
        {
                ElementStructs *removedElement = ListPtr->FrontPtr->ElementPtr;
                LinkedListNodes *removedNode = ListPtr->FrontPtr;
                 if(ListPtr->NumElements == 1)
            {
                    ListPtr->FrontPtr = NULL;
            }
            else
            {
                    ListPtr->FrontPtr = ListPtr->FrontPtr->Next;
                    ListPtr->FrontPtr->Previous = NULL;
            }
            (ListPtr->NumElements)--;
            free(removedNode);
            return removedElement;
    }
    else
    {
            ElementStructs *nullElement = NULL;
            return nullElement;
    }
}

ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements > 1)
        {
                ElementStructs *removedElement = ListPtr->BackPtr->ElementPtr;
                LinkedListNodes *removedNode = ListPtr->BackPtr;
                if(ListPtr->NumElements == 1)
                {
                        ListPtr->BackPtr = NULL;
                }
                else
                {
                        ListPtr->BackPtr = ListPtr->BackPtr->Previous;
                        ListPtr->BackPtr->Next = NULL;     
                }
                (ListPtr->NumElements)--;
                free(removedNode);
                return removedElement;
        }
        else
        {
                ElementStructs *nullElement = NULL;
                return nullElement;
        }
}


void DestroyLinkedList(LinkedLists *ListPtr)
{
        while(ListPtr->FrontPtr != NULL)
        {
                LinkedListNodes *removedNode = ListPtr->FrontPtr;
                ListPtr->FrontPtr = ListPtr->FrontPtr->Next;

                /* Deallocate element in node */
                free(removedNode->ElementPtr->ElementValue);
                free(removedNode->ElementPtr);

                /* Deallocate node */
                free(removedNode);
        }
        free(ListPtr);
}

测试列表.c:

/******************************************************************************
 * Tests the functionality of the LinkedList specified in LinkedLists.h using
 * the file "american-english-words". Reads in individual words and stores them
 * as node elements in the LinkedList.
 * Written by xxxxx
 *****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkedLists.h"

#define MAX_LENGTH 100 /* Length of longest word in any major English dictionary */

int main(int argc, char** args)
{
        if(argc == 2)
        {
                /* Initialize LinkedList */
                LinkedLists *LL;

                /* File pointer to input file */
                FILE *fp;

                /* Node to store input data from file */
                ElementStructs *NodeData;

                /* Loop completion boolean */
                int Done;

                /* Loop position counter */
                int Position;

                /* Iterator */
                ElementStructs *CurElement;

                /* Open input file and check that it is readable. If not, exit */
                fp = fopen(args[1], "r");

                if(fp == NULL)
                {
                        fprintf(stderr, "File open failed.");
                        return 2;
                }

                /* Initialize linked list and other necessary variables */
                LL = malloc(sizeof(*LL));
                InitLinkedList(LL);

                Done = 0;
                Position = 0;

                do
                {
                        if(!feof(fp))
                        {
                                /* Allocate space for new node data */
                                NodeData = malloc(sizeof(ElementStructs));

                                /* Allocate space in node element for input string */
                                NodeData->ElementValue = malloc(MAX_LENGTH * sizeof(char));

                                /* Read new node data from file */
                                fscanf(fp, "%s", NodeData->ElementValue);

                                /* Assign scanned values to node elements */
                                NodeData->ElementPosition = Position;
                                /*strcpy(NodeData->ElementValue, readString);*/

                                /* Add data node to LinkedList */
                                AddToFrontOfLinkedList(LL, NodeData);
                        }
                        else
                                Done = 1;
                        Position++;
                }while(Done == 0);

                do
                {
                        CurElement = RemoveFromFrontOfLinkedList(LL);

                        if(CurElement != NULL)
                                printf("Word #%d: %s\n", CurElement->ElementPosition,
                                CurElement->ElementValue);
                }while(CurElement != NULL);

                /* Deallocate linked list */
                DestroyLinkedList(LL);
                fclose(fp);

        }
        /* Bad command line input */
        else
        {
                fprintf(stderr, "Incorrect number of arguments");
                return 1;
        }

        return 0;
}

程序编译正常。但是，运行它会在执行结束时导致段错误，并且 valgrind 会报告多个内存泄漏(如下所示)。如果您能提供任何帮助，我将不胜感激。问题主要出在 LinkedList.c 模块中的 RemoveFromBackOfLinkedList 和 RemoveFromFrontOfLinkedList 方法中。主模块 (TestList.c) 中有一段代码调用其中一个函数(我都试过了，但它们的功能几乎相同，但都不起作用)。该 block 是一个 do/while 循环，如下所示:

do
                {
                CurElement = RemoveFromFrontOfLinkedList(LL);

                        if(CurElement != NULL)
                                printf("Word #%d: %s\n", CurElement->ElementPosition,
                                CurElement->ElementValue);
                }while(CurElement != NULL);

Valgrind 结果:

Word #225921: stoich
.
.
.
.
Word #6: Cam's
Word #5: petrochemistry's
Word #4: Tera
Word #3: benedictions
Word #2: wisted
Word #1: toxins
==4849== Invalid write of size 8
==4849==    at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4849==    by 0x40085B: main (in /home/amb2189/hw3/TestList)
==4849==  Address 0x10 is not stack'd, malloc'd or (recently) free'd
==4849== 
==4849== 
==4849== Process terminating with default action of signal 11 (SIGSEGV)
==4849==  Access not within mapped region at address 0x10
==4849==    at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4849==    by 0x40085B: main (in /home/amb2189/hw3/TestList)
==4849==  If you believe this happened as a result of a stack
==4849==  overflow in your program's main thread (unlikely but
==4849==  possible), you can try to increase the size of the
==4849==  main thread stack using the --main-stacksize= flag.
==4849==  The main thread stack size used in this run was 8388608.
==4849== 
==4849== HEAP SUMMARY:
==4849==     in use at exit: 23,965,172 bytes in 413,185 blocks
==4849==   total heap usage: 619,775 allocs, 206,590 frees, 28,923,332 bytes allocated
==4849== 
==4849== 16 bytes in 1 blocks are possibly lost in loss record 1 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007E2: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== 200 bytes in 2 blocks are possibly lost in loss record 5 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007F0: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== 23,963,992 (3,305,392 direct, 20,658,600 indirect) bytes in 206,587 blocks are definitely lost in loss record 9 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007E2: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== LEAK SUMMARY:
==4849==    definitely lost: 3,305,392 bytes in 206,587 blocks
==4849==    indirectly lost: 20,658,600 bytes in 206,586 blocks
==4849==      possibly lost: 216 bytes in 3 blocks
==4849==    still reachable: 964 bytes in 9 blocks
==4849==         suppressed: 0 bytes in 0 blocks
==4849== Reachable blocks (those to which a pointer was found) are not shown.
==4849== To see them, rerun with: --leak-check=full --show-reachable=yes
==4849== 
==4849== For counts of detected and suppressed errors, rerun with: -v
==4849== Use --track-origins=yes to see where uninitialised values come from
==4849== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 2 from 2)
Segmentation fault (core dumped)

Answer 1

==4769== 8 bytes in 1 blocks are definitely lost in loss record 1 of 4
==4769==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4769==    by 0x400B46: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4769==    by 0x400869: main (in /home/amb2189/hw3/TestList)

这里指的是下面的代码:

LinkedListNodes *removedNode = malloc(sizeof(removedNode));
removedNode = ListPtr->FrontPtr;

您malloc 一 block 内存，然后将其分配给removedNode，然后立即覆盖指针值。这不会分配给 removedNode 的内容，但会覆盖指针。

---

正如 Valgrind 所指出的，下一次内存泄漏发生在 main 中:

CurElement = malloc(sizeof(*CurElement));

CurElement 的下一次使用会立即覆盖指针值，这意味着您丢失了对已分配内存的引用:

CurElement = RemoveFromFrontOfLinkedList(LL);