[已解决]单链表的运用

starinblack

为什么输出·有时时正确的，有时又是这样莫名其妙的输出。类型是.cpp。如果改成.c在哪些地方改呢。

//线性表运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct LNode
{        ElemType data;                        //data为节点的数据信息
        struct LNode *next; //next为指向后继节点的指针
} LinkNode;                                                //单链表节点类型

void InitList(LinkNode *&L)                //初始化线性表
{
        L = (LinkNode *)malloc(sizeof(LinkNode));
        L ->next=NULL;
}

void DestroyList(LinkNode *&L)//销毁线性表
{
        LinkNode *pre = L,*p = L->next;
        while(p!=NULL){
                free(pre);
                pre = p;
                p= pre->next;
        }
        free(pre);
}

bool ListEmpty(LinkNode *L)//判断是否为空表
{
        return(L->next ==NULL);
}

int ListLength(LinkNode *L)//求线性表长度
{
        int cnt = 0;//计数器
        LinkNode *p = L;
        while(p->next!=NULL){
                cnt++;
                p = p->next;
        }
        return (cnt);
}

void DispList(LinkNode *L)//输出线性表
{
         LinkNode *p  = L->next;
         while(p!=NULL)
         {
                 printf("%c",p->data);
                 p = p->next;
         }
        printf("\n");
  }
  
bool GetElem (LinkNode *L,int i,ElemType &e)//求某个节点的值
{        int j = 0;
        LinkNode *p = L;
        if(i<=0) return false;
        while(j<i&&p!=NULL)
                {j++;
                p = p ->next;
                }
        if(p ==NULL) return false;
        else
        {e = p->data;
        return true;
               
        }
  }  

int LocateElem(LinkNode *L,ElemType e)//找到与e值相等的结点
{
        int i =1;
        LinkNode *p = L->next;
        while(p!=NULL&&p->data!=e)
        {
                p = p->next;
                i++;
         }
        if(p==NULL)
        {
                return (0);
         }
        else return(i);
}

bool ListInsert(LinkNode *&L,int i,ElemType e)//在第i个位置 插入元素e
{
        int j = 0;
        LinkNode *p = L,*s;
        if(i<=0)        return false;
        while(j <i-1&&p!=NULL){
                j++;
                p = p->next;
        }
        if(p==NULL)        return false;
        else
        {
                s = (LinkNode *)malloc(sizeof(LinkNode));
                s->data = e;
                s->next = p->next;
                p->next = s;
                return true;
        }
}

bool ListDelete(LinkNode *&L,int i,ElemType &e)//删除
{
        int j = 0;
        LinkNode * p = L ,*q;
        if(i<=0)        return false;
        while(j<i-1&&p!=NULL)
        {
                j++;
                p = p->next;
               
         }
        if(p==NULL) return false;
        else
        {
                q = p->next;
                if(q==NULL){
                        return false;
                }
                else
                {
                        e = q->data;
                        p->next=q->next;
                        free(p);
                        return true;
                }
         }
         
        
}

int main()
{
        LinkNode *L;
        ElemType e;
        printf("线性表的基本运算如下:\n");
        printf("  (1)初始化线性表L\n");
        InitList(L);
        printf("  (2)依次插入a,b,c,d,e元素\n");
        ListInsert(L,1,'a');
        ListInsert(L,2,'b');
        ListInsert(L,3,'c');
        ListInsert(L,4,'d');
        ListInsert(L,5,'e');
        printf("  (3)输出线性表L:");
        DispList(L);
        printf("  (4)线性表L长度:%d\n",ListLength(L));
        printf("  (5)线性表L为%s\n",(ListEmpty(L)?"空":"非空"));
        GetElem(L,3,e);
        printf("  (6)线性表L的第3个元素:%c\n",e);
        printf("  (7)元素a的位置:%d\n",LocateElem(L,'a'));
        printf("  (8)在第4个元素位置上插入f元素\n");
        ListInsert(L,4,'f');
        printf("  (9)输出线性表L:");
        DispList(L);
        printf("  (10)删除L的第3个元素\n");
    ListDelete(L,3,e);
        printf("  (11)输出线性表L:");
        DispList(L);
        printf("  (12)释放线性表L\n");
        DestroyList(L);
        return true;
}

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-5-27 16:33:30

您好，不知道您是否还未解决这个问题。
从结论来说，问题出现在代码的第129行，即 ListDelete 函数中。在进行被删除节点的释放时，您释放的节点和您代码其他部分显露的意图并不匹配。您将 q 的下一个节点连接到了 p 节点之后，我们认为您希望删除的应该是 q 所指向的节点，但是实际上您 free 的是指针 p 。显然这会导致链表的结构出现错误，这也是导致输出结果出现随机性的直接原因。
在阅读您的代码的过程中，我认为存在一些值得改进的地方可以从根本上帮助减少此类问题的出现。

• 位置的定义不够明确。我们建议通过注释或者其他方式写明所谓的在某个位置插入究竟是哪个位置，例如在链表的第 i 个位置插入究竟是令插入后的新节点成为链表的第 i 个节点，还是在链表中现有的第 i 个节点之后插入，删除同理。这样首先帮助自己理清逻辑，也可以帮助其他人理解代码
• 变量命名未对应意义。其他地方可能影响不大，但是在节点插入或删除时由于存在多个指针需要正确操作，明确的将其命名可以帮助减少错误的使用，如命名成 p_last（要删除节点的上一个节点）和 p_delete（要删除的节点）
• 常见的功能应该加以封装。如代码中多次出现的寻找链表第 i 个节点的代码片段，可以考虑封装成为独立的函数而不是复制粘贴，避免拼写错误并减少改动量
• 链表节点定位的逻辑不太常见。常见的定位在某处插入节点是通过指向插入位置的前一个节点的指针完成的，从表头开始计数的方案在性能上存在不足，也可能传入错误的位置
  

另外，通常程序使用返回值 0 作为程序正常结束的标志，非零值表示程序异常退出，因此您可能希望在主函数结尾返回 0 作为程序正常结束的标志，而不是返回通常定义为非零值的 true 。

修改为 C 代码主要需要修改两个部分，首先是 bool 型变量需要引入头文件 stdbool.h 方可使用，其次是 C 中没有引用，需要将引用传递修改为指针传递。给出一个简单的例子，如您 InitList 的实现和调用为

void InitList(LinkNode *&L)                //初始化线性表
{
        L = (LinkNode *)malloc(sizeof(LinkNode));
        L ->next=NULL;
}
LinkNode *L;
InitList(L);

而调整为 C 代码应该改动为

void InitList(LinkNode** L){
    *L = (LinkNode *)malloc(sizeof(LinkNode));
    (*L)->next = NULL;
}
LinkNode* L;
InitList(&L);

其余部分也存在需要改动的内容，您原先的代码有较好的完整度，相信您能够自行完成类似的改动。另外，如果您有意深入研究 C++ ，您的这份代码尽管需要使用 C++ 编译器进行编译，但是距离严谨的 C++ 风格还存在一定的距离，推荐您了解一下更现代的 C++ 。

最后，我个人正在收集一些有一定功能且存在 bug 的代码作为分享代码调试经验的材料，请问是否可以使用您的这份代码作为一个示例？

跳转到最佳答案楼层

dolly_yos2

您好，不知道您是否还未解决这个问题。
从结论来说，问题出现在代码的第129行，即 ListDelete 函数中。在进行被删除节点的释放时，您释放的节点和您代码其他部分显露的意图并不匹配。您将 q 的下一个节点连接到了 p 节点之后，我们认为您希望删除的应该是 q 所指向的节点，但是实际上您 free 的是指针 p 。显然这会导致链表的结构出现错误，这也是导致输出结果出现随机性的直接原因。
在阅读您的代码的过程中，我认为存在一些值得改进的地方可以从根本上帮助减少此类问题的出现。

• 位置的定义不够明确。我们建议通过注释或者其他方式写明所谓的在某个位置插入究竟是哪个位置，例如在链表的第 i 个位置插入究竟是令插入后的新节点成为链表的第 i 个节点，还是在链表中现有的第 i 个节点之后插入，删除同理。这样首先帮助自己理清逻辑，也可以帮助其他人理解代码
• 变量命名未对应意义。其他地方可能影响不大，但是在节点插入或删除时由于存在多个指针需要正确操作，明确的将其命名可以帮助减少错误的使用，如命名成 p_last（要删除节点的上一个节点）和 p_delete（要删除的节点）
• 常见的功能应该加以封装。如代码中多次出现的寻找链表第 i 个节点的代码片段，可以考虑封装成为独立的函数而不是复制粘贴，避免拼写错误并减少改动量
• 链表节点定位的逻辑不太常见。常见的定位在某处插入节点是通过指向插入位置的前一个节点的指针完成的，从表头开始计数的方案在性能上存在不足，也可能传入错误的位置
  

另外，通常程序使用返回值 0 作为程序正常结束的标志，非零值表示程序异常退出，因此您可能希望在主函数结尾返回 0 作为程序正常结束的标志，而不是返回通常定义为非零值的 true 。

修改为 C 代码主要需要修改两个部分，首先是 bool 型变量需要引入头文件 stdbool.h 方可使用，其次是 C 中没有引用，需要将引用传递修改为指针传递。给出一个简单的例子，如您 InitList 的实现和调用为

void InitList(LinkNode *&L)                //初始化线性表
{
        L = (LinkNode *)malloc(sizeof(LinkNode));
        L ->next=NULL;
}
LinkNode *L;
InitList(L);

而调整为 C 代码应该改动为

void InitList(LinkNode** L){
    *L = (LinkNode *)malloc(sizeof(LinkNode));
    (*L)->next = NULL;
}
LinkNode* L;
InitList(&L);

其余部分也存在需要改动的内容，您原先的代码有较好的完整度，相信您能够自行完成类似的改动。另外，如果您有意深入研究 C++ ，您的这份代码尽管需要使用 C++ 编译器进行编译，但是距离严谨的 C++ 风格还存在一定的距离，推荐您了解一下更现代的 C++ 。

最后，我个人正在收集一些有一定功能且存在 bug 的代码作为分享代码调试经验的材料，请问是否可以使用您的这份代码作为一个示例？

starinblack

dolly_yos2 发表于 2022-5-27 16:33
您好，不知道您是否还未解决这个问题。
从结论来说，问题出现在代码的第129行，即 ListDelete 函数中。在 ...

可以