论坛 › 数据结构与算法 › 链表删除结点函数，在free节点时报错

MzJy 发表于 2023-11-24 00:10:55

链表删除结点函数，在free节点时报错

才疏学浅，按照书上的示例，自己的思路编写的循环链表的操作函数，其余函数都可以用，在删除链表元素释放结点时，VS报错：
Debug Error!

Program: ...ure\Code\3. CirLinkList\CirLinkList\x64\Debug\CirLinkList.exe

HEAP CORRUPTION DETECTED: after Normal block (#110) at 0x00000215E64C6B30.
CRT detected that the application wrote to memory after end of heap buffer.

在网上搜寻后大概是因为内存溢出，动态分配空间的问题。
但是我怎么也看不出是哪里导致的溢出。希望论坛的大佬赐教。
ps：在Debug模式下运行报错，在release模式下运行不会报错，想知道原因和两者的区别。
感谢！下面是所有的链表功能代码。

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

#define OK 1;
#define ERROR 0;
#define ERROR_1 -1;

#define TRUE 1;
#define FALSE 0;

typedef int ElemType;
typedef struct Node
{
        ElemType data;
        structNode* next;
};

typedef struct Node* CirLinkList;
typedef int Status;

static inline int ListLength(CirLinkList L)
{
        CirLinkList p = L->next;
        int length = 0;
        while (p != L)
        {
                p = p->next;
                length++;
        }
        return length;
}

static inline Status InitLinkList(CirLinkList &L)
{
        L = (CirLinkList)malloc(sizeof(Node*));
        if (L)
        {
                L->next = L;
                L->data = ListLength(L);
                return OK;
        }
        return ERROR_1;
}

static inline Status ListEmpty(CirLinkList L)
{
        if (L->next == L)
                return TRUE;
        return FALSE;
}

static inline Status visit(ElemType e)
{
        printf("%d ", e);
        return OK;
}

static inline Status compare(ElemType i,ElemType e)
{
        if (i == e)
                return TRUE;
        return FALSE;
}


static inline Status CreateList_Tail(CirLinkList& L, int n)
{
        if (ListEmpty(L))
        {
                CirLinkList p, r;
                r = L;
                srand(time(0));
                for (int i = 0; i < n; i++)
                {
                        p = (CirLinkList)malloc(sizeof(Node*));
                        if (p)
                        {
                                p->data = rand() % 100 + 1;
                                r->next = p;
                                r = p;
                        }
                        else
                                return ERROR_1;
                }
                r->next = L;
                L->data = ListLength(L);
                return OK;
        }
        else
                return ERROR;
}

static inline Status ListInsert(CirLinkList& L, int i,ElemType e)
{
        CirLinkList p = L;
        if (i < 1 || i > L->data + 1)
        {
                return ERROR;
        }
        for (int j = 0; j < i - 1; j++)
                p = p->next;
        CirLinkList s = (CirLinkList)malloc(sizeof(Node*));
        if (s)
        {
                s->data = e;
                s->next = p->next;
                p->next = s;
                L->data ++;
                return OK;
        }
        return ERROR_1;
}

inline Status ListDelete(CirLinkList& L, int i, ElemType &e)
{
        CirLinkList p = L;
        CirLinkList q;
        if (i < 1 || i > L->data )
        {
                return ERROR;
        }
        for (int j = 0; j < i - 1; j++)
                p = p->next;
        q = p->next;
        p->next = q->next;
        e = q->data;
        free(q);
        L->data--;
        return OK;
}

static inline int LocateElem(CirLinkList L,ElemType e)
{
        CirLinkList p;
        int i = 0;
        for ( p = L->next; p != L; p=p->next )
        {
                i++;
                if (compare(p->data, e))
                        return i;
        }
        return ERROR;
}
static inline Status ListTraverse(CirLinkList L)
{
        if (!ListEmpty(L))
        {
                CirLinkList p = L->next;
                printf("循环链表内容如下：\n");
                while (p != L)
                {
                        visit(p->data);
                        p = p->next;
                }
                printf("\n");
                return OK;
        }
        return ERROR;
}

小甲鱼的二师兄 发表于 2023-11-24 00:10:56

MzJy 发表于 2023-11-24 00:32


他们是对的，应该是 sizeof(Node) 而非 sizeof(Node *)

FishC_GPT 发表于 2023-11-24 00:11:52

问题出在ListInsert函数中，你在定义s时使用了sizeof(Node*)，这是一个指针的大小，而不是Node结构体的大小。所以，正确的写法应该是sizeof(Node)。

这里是修改后的代码：

static inline Status ListInsert(CirLinkList& L, int i, ElemType e)
{
    CirLinkList p = L;
    if (i < 1 || i > L->data + 1)
    {
      return ERROR;
    }
    for (int j = 0; j < i - 1; j++)
      p = p->next;
    CirLinkList s = (CirLinkList)malloc(sizeof(Node));
    if (s)
    {
      s->data = e;
      s->next = p->next;
      p->next = s;
      L->data++;
      return OK;
    }
    return ERROR_1;
}

至于为什么在Debug模式下会报错而Release模式不会，这是因为Debug模式下编译器会对内存进行一些额外的检查和控制，因此更容易发现和报告错误。而Release模式下为了性能考虑，这些额外的检查被省略了，所以不会报错。

希望对你有帮助！
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

Mike_python小 发表于 2023-11-24 00:13:07

代码中有几个问题可能导致内存溢出和释放错误：

1. 在初始化链表函数InitLinkList中，分配内存的语句应该是L = (CirLinkList)malloc(sizeof(Node));，而不是L = (CirLinkList)malloc(sizeof(Node*));。因为sizeof(Node*)是指针的大小，而我们实际需要的是结点的大小。

2. 在创建链表函数CreateList_Tail中，分配内存的语句应该是p = (CirLinkList)malloc(sizeof(Node));，而不是p = (CirLinkList)malloc(sizeof(Node*));。同样的原因，我们需要分配结点的大小。

3. 在删除结点函数ListDelete中，需要先判断要删除的位置是否合法，即if (i < 1 || i > L->data + 1)。因为循环链表的结点个数为L->data，所以判断条件应为i > L->data 而不是 i > L->data - 1。

请你修改以上代码中的这些问题，然后再编译运行看看是否还会报错。同时，Debug模式和Release模式的区别是Debug模式下编译器会进行更多的检查和调试信息输出，因此在调试程序时可以方便地定位错误。而Release模式下则会进行一些优化，生成的可执行文件体积较小、运行速度较快，但对于错误的检测和定位可能会不够详细。因此，在调试阶段建议使用Debug模式，而发布正式版本时可以使用Release模式。

回复来自于CHAT-GPT。回复仅供参考，如有人工回答，最佳答案请优先选择人工

MzJy 发表于 2023-11-24 00:32:44

{:10_266:}

查看完整版本: 链表删除结点函数，在free节点时报错