1

我试图销毁一个单链表，首先，我的销毁函数代码如下：

void destroy_list_v0 (SLINK *list)
{   
SLINK ptr = *list;

while (NULL != *list)
    {
    ptr = *list;
    *list = (*list)->next;
    free (ptr);
    }
}

函数 v0 表现完美。这是输出。

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 5.
The 2nd element is 93.
The 3rd element is 92.
The 4th element is 70.
The 5th element is 92.
traverse_end & destroy_start.
destroy_end & traverse_start.
traverse_end.
All operations done.

然后我觉得单指针就够了，于是我把函数调整为单指针版本：

void destroy_list_v1 (SLINK list)
{
SLINK ptr = list;   
while (NULL != list)
    {
    ptr = list;
    list = list->next;
    free (ptr);
    }
}

这是 v1 的输出：

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 27.
The 2nd element is 38.
The 3rd element is 20.
The 4th element is 66.
The 5th element is 30.
traverse_end & destroy_start.
destroy_end & traverse_start.
The 0th element is 0.
The 1st element is 32759808.
The 2nd element is 32759968.
The 3rd element is 32759936.
The 4th element is 32759904.
The 5th element is 32759872.
traverse_end.
All operations done.

为了确认销毁函数工作正常，我在链表被销毁后遍历它。我发现可以读取列表（如果是v0，则无法读取），尽管每个节点的值都已更改且不确定。我以为 v0 执行后，列表的指针指向 NULL，但 v1 执行后，它仍然指向原始地址。为了测试这个想法，我将 v0 调整为 v2：

void destroy_list_v2 (SLINK *list)
{   
SLINK p_list = *list;
SLINK ptr = *list;
while (NULL != *p_list)
    {
    ptr = *p_list;
    p_list = p_list->next;
    free (ptr);
    }
}

这是 v2 输出：

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 76.
The 2nd element is 53.
The 3rd element is 80.
The 4th element is 31.
The 5th element is 97.
traverse_end & destroy_start.
destroy_end & traverse_start.
The 0th element is 0.
The 1st element is 13860864.
The 2nd element is 13861024.
The 3rd element is 13860992.
The 4th element is 13860960.
The 5th element is 13860928.
traverse_end.
All operations done.

我认为我的分析是正确的，但它导致了新的问题。

节点结构在这里：

typedef struct tag_node
{
int elem;
struct tag_node *next;
}NODE, *SLINK; //SLINK means SINGLE LINK

我有两个问题：

1：指针'next'存储在当前指针指向的内存空间中，释放当前节点后，为什么指针'next'的内存空间仍然可以读取？指针“下一个”还活着吗？我有这个问题是因为我认为在 v1 或 v2 执行之后，它应该只是可以读取的 header 节点。

2：我toutht v1和v2破坏了整个列表，在v1或v2执行之后，为什么header的值仍然存在？我认为应该是第 1 到第 5 变成了一个不确定的数字。

这是整个代码，环境是Debian，clang：

#include    <stdio.h>
#include    <stdlib.h>
#include    <time.h>
#include    <string.h>

#define     i_track(n)  printf ("The %s's is %d.\n", #n, (n))
#define     s_track(n)  printf ("%s.\n", #n);

typedef struct tag_node
{
int elem;
struct tag_node *next;
}NODE, *SLINK; //SLINK means SINGLE LINK

void  node_track (SLINK list);

NODE *node_generate (void);
SLINK init_list (int len);
SLINK locate_cur (SLINK list, int target_elem);
void insert_node (SLINK *list, int new_elem, int tag_elem);
SLINK traverse_list (SLINK list);
void clear_list (SLINK list);
void destroy_list_v0 (SLINK *list);
void destroy_list_v1 (SLINK list);
void destroy_list_v2 (SLINK *list);
void list_info (SLINK list, int node_elem);

int main (int argc, char *argv[])
{
int len;
SLINK list;
printf ("Input a number for length of the link.\n");
scanf ("%d", &len);
s_track(init_start);
list = init_list (len);
s_track(init_end & traverset_start);
traverse_list (list);
s_track(traverse_end & destroy_start);
//  destroy_list_v0 (&list);
//  destroy_list_v1 (list);
destroy_list_v2 (&list);
s_track(destroy_end & traverse_start);
traverse_list (list);
s_track(traverse_end);
s_track(All operations done);

return EXIT_SUCCESS;
}               /* ----------  end of function main  ---------- */

NODE *node_generate (void)
{
NODE *new_node = malloc (sizeof (NODE));
if (NULL == new_node)
{
    printf ("ERROR: malloc failed.\n");
    exit (EXIT_FAILURE);
}
memset (new_node, 0, sizeof(NODE));
return new_node;
}

SLINK locate_cur (SLINK list, int target_elem)
{
NODE *prev, *cur;
prev = node_generate ();
cur = node_generate ();
for (prev = list, cur = list->next; NULL != cur && target_elem != cur->elem; prev = cur, cur = cur->next)
    ;
return cur;
}

void insert_node (SLINK *list, int new_elem, int tag_elem)
{
NODE *new_node = node_generate ();
NODE *cur = *list;
new_node->elem = new_elem;
if ((int)NULL == tag_elem)
{
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
else
{
    *list = locate_cur (cur, tag_elem);
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
}

SLINK init_list (int len)
{
SLINK header = node_generate ();
srand ((unsigned) time(0));
int elem;
for (int i = 0; i < len; i++)
    {
        elem = rand () % 100;

        if (4 == elem / 10)
        {
            elem = elem + 50;
        }
        if (4 == elem % 10)
        {
            elem = elem + 5;
        }
        if (0 == elem % 100)
        {
            elem = elem + 999;
        }
        insert_node (&header, elem, (int)NULL); 
    }
return header;
}

void clear_list (SLINK list)
{
for (SLINK cur = list->next; NULL != cur; )
{
    cur = cur->next;
    free (list->next);
    list->next = cur;
}
}

void destroy_list_v0 (SLINK *list)
{   
SLINK ptr = *list;

while (NULL != *list)
{
    ptr = *list;
    *list = (*list)->next;
    free (ptr);
}
}

void destroy_list_v1 (SLINK list)
{   
SLINK ptr = list;

while (NULL != list)
{
    ptr = list;
    list = list->next;
    free (ptr);
}
}

void destroy_list_v2 (SLINK *list)
{
SLINK p_list = *list;
SLINK ptr = *list;
while (NULL != p_list)
{
    ptr = p_list;
    p_list = p_list->next;  
    free (ptr);
}
}

SLINK traverse_list (SLINK list)
{
SLINK ptr = list;
for (int node_num = 0; ptr != NULL; ptr = ptr->next)
{
    list_info (ptr, node_num);
    ++node_num;
}
return list;
}

void list_info (SLINK list, int node_num)
{
if (1 == node_num % 10 && 11 != node_num)
{
    printf ("The %dst element is %d.\n", node_num, list->elem);
}
else if (2 == node_num % 10 && 12 != node_num)
{
    printf ("The %dnd element is %d.\n", node_num, list->elem);
}
else if (3 == node_num % 10 && 13 != node_num)
{
    printf ("The %drd element is %d.\n", node_num, list->elem);
}
else
{
    printf ("The %dth element is %d.\n", node_num, list->elem);
}
}

void node_track (NODE *flag)
{
printf ("The flag element is %d.\n", flag->elem);
}
4

5 回答 5

4

释放内存与更改指针变量中包含的地址不同。

调用free将内存释放回malloc管理的堆。如果你有一个变量仍然指向你之前分配的内存，那么在释放操作之后它仍然指向那里。但是，在 free 之后将指针用于任何内容是一个错误。

如果你想确保你的链表不再指向释放的内存，你可以在相关的内存被释放后将 NULL 分配给结构中的每个指针。

于 2012-12-04T16:09:57.877 回答
2

在 C 中习惯这一点。“行为未定义”这句话是你很快就会习惯的口头禅，它意味着做某些事情可能会导致任何事情，从崩溃到明显完美的行为。

指针是这个口头禅的经典案例。您释放了内存并且仍然可以访问它？嗯，它是未定义的。等等，现在是夏令时，现在它崩溃了？好吧，它是未定义的。等等，你在 Windows 上运行它，它工作正常，除了以 Y 结尾的日子？好吧，它是未定义的。

记住咒语；它会很好地为您服务。当你做错事时期望C大声抱怨是错误的期望，记住这一点可以为你节省很多悲伤和眼泪。

于 2012-12-04T16:15:57.790 回答
1

  1. 欢迎来到 C 的土地，在那里你可以做任何事情（即使它不合法）。您所做的是调用未定义的行为。您不再被允许访问已删除的内存，但没有人阻止您尝试。C 不会检查您是否确实在访问有效内存。即使你告诉它做错事，它也会继续做你告诉它的事情。它“有效”的事实是运气和实现定义的东西的混合。像这样的错误很难找到，因为程序没有崩溃，而是继续运行，直到很长一段时间后，当它最终开始崩溃时，您才发现错误。一旦你调用未定义的行为（当你访问已删除的内存时会发生这种情况），任何事情都可能发生，从黑洞打开并吞噬我们所有人，到程序崩溃，

  2. v1并v2确实销毁整个列表，但释放内存并不意味着您也会擦除内存中的值。这些值仍然存在，只是不再允许您访问它们，因为您已将这些内存桶还给了操作系统。桶仍然保存值。它们不再是你的了。

于 2012-12-04T16:15:06.873 回答
0

free() 将缓冲区标记为空闲，这意味着后续的 malloc() 可以使用相同的日期区域，这并不意味着它将被擦除或其他任何东西，但它可以返回给操作系统（并因此访问它可能导致分段错误）。

访问已释放的内存是一个错误，因为即使它通常仍然未触及，您也可能正在访问其他一些函数使用的内存。

于 2012-12-04T16:14:03.577 回答
0

C99 说：

free 函数会导致 ptr 指向的空间被释放，也就是说，可用于进一步分配。如果 ptr 是空指针，则不会发生任何操作。否则，如果参数与 calloc、malloc 或 realloc 函数先前返回的指针不匹配，或者如果空间已通过调用 free 或 realloc 被释放，则行为未定义。

于 2012-12-04T16:21:45.283 回答