奇怪的内存问题在简单链表实现中的C

huangapple go评论54阅读模式
英文:

Weird Memory Problem in Simply Linked-List Implementation C

问题

我正在编写一个包含元素结构{name, price}的简单链表(Simply Linked-List),在我实现的一些函数中出现了奇怪的行为。这些函数包括:

  1. PopFront(移除链表的第一个元素)
  2. PopByIndex(根据给定的索引移除链表中的元素)

到底发生了什么事情?这些函数确实移除了它们应该移除的元素,但它们不知何故改变了另一个元素的价格值 😓。

示例:

在使用移除函数之前:

Name:        A  Price: 1.00
Name:        B  Price: 2.00
Name:        C  Price: 3.00
Name:        D  Price: 4.00
	--------
	 |Menu|
	--------
(1) Add Element in Front
(2) Add Element in Back
(3) Add Element in Position
(4) Remove Element from Front
(5) Remove Element from Back
(6) Remove Element by Position
(7) Print List
(8) Calculate Itens Sum
(0) Exit Program

在移除 D 元素之后,它将价格 A 的价格设为 0:

Name:        A  Price: 0.00
Name:        B  Price: 2.00
Name:        C  Price: 3.00
	--------
	 |Menu|
	--------
(1) Add Element in Front
(2) Add Element in Back
(3) Add Element in Position
(4) Remove Element from Front
(5) Remove Element from Back
(6) Remove Element by Position
(7) Print List
(8) Calculate Itens Sum
(0) Exit Program

我使用了GDB来查看元素确切何时被修改,发现是在调用free()来释放被移除元素的内存地址时发生的。

最小可重现示例(Minimal Reproducible Example):

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

typedef struct Node Node;
typedef struct List List;

// 其他代码...

我已经提供了你的代码和问题的总结,没有进行额外的翻译。如果你有任何进一步的问题或需要进一步的帮助,请随时提问。

英文:

I am coding a Simply Linked-List that has a struct of elements composed by {name, price}, and in some of the function I'm implementing are presenting a weird behavior. These functions are:

  1. PopFront(That remove the last element of the list)
  2. PopByIndex(That given an entry index, it will remove the element on that position)

What's happening exactly? Well, these functions do remove the element they are supposed to remove, but they somehow change the value of the price of another element of the list 😕.

Example:

Before use remove functions

Name:        A  Price: 1.00
Name:        B  Price: 2.00
Name:        C  Price: 3.00
Name:        D  Price: 4.00
	--------
	 |Menu|
	--------
(1) Add Element in Front
(2) Add Element in Back
(3) Add Element in Position
(4) Remove Element from Front
(5) Remove Element from Back
(6) Remove Element by Position
(7) Print List
(8) Calculate Itens Sum
(0) Exit Program

After remove D element it puts 0 to the price of A

Name:        A  Price: 0.00
Name:        B  Price: 2.00
Name:        C  Price: 3.00
	--------
	 |Menu|
	--------
(1) Add Element in Front
(2) Add Element in Back
(3) Add Element in Position
(4) Remove Element from Front
(5) Remove Element from Back
(6) Remove Element by Position
(7) Print List
(8) Calculate Itens Sum
(0) Exit Program

I used gdb to see what moment exactly, the element is modified and found that is when I call free() to free the memory of the address of the element removed

Minimal Reproducible Example:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

typedef struct Node Node;
typedef struct List List;

struct Node {
    char name[100];
    float price;
    int code;
    struct Node *prox; 
};

struct List{
    struct Node *head;
    int size;
};

Node* InstantiateNode() {
    Node *new_node = malloc(sizeof new_node);
    new_node-&gt;prox = NULL;
    return new_node;
}

void InitNode(Node *node, char *name, float price) {
    strcpy(node-&gt;name, name);
    node-&gt;price = price;
}

void PrintNode(Node node){
    printf(&quot;Name: %8s  Price: %.2f\n&quot;, node.name, node.price);
}

int EmptyList(List list) {
    return list.size == 0 ? 1 : 0;
}

List *InstantiateList(void) {
    List *new_list = malloc(sizeof new_list);
    new_list-&gt;head = NULL;
    new_list-&gt;size = 0;
    return new_list;
}

void InitList(List *list, Node *new_node) {
    new_node-&gt;prox = list-&gt;head;
    list-&gt;head = new_node;
    list-&gt;size++;
}

void PushFront(List *list, Node *new_node) {
    if (EmptyList(*list)) {
        InitList(list, new_node);
        return;
    }
    Node *tracker = list-&gt;head;
    while (tracker-&gt;prox != NULL)
        tracker = tracker-&gt;prox;
    tracker-&gt;prox = new_node;
    list-&gt;size++;
}

void PushBack(List *list, Node *new_node) {
        InitList(list, new_node);
}

Node *TrackListbyIndex(List lista, int index) {
    if (index &gt; lista.size) {
        printf(&quot;Unreachable List index \n&quot;); // Warning
        return NULL;
    }
    int cont = 0;
    Node *aux = lista.head;
    while (cont != index) {
        aux = aux-&gt;prox;
        cont++;
    }
    return aux;
}

void PushByIndex(List *list, Node *new_node, int index) {
    if (index == 0) {
        PushBack(list, new_node);
        return;
    }
    Node *aux = TrackListbyIndex(*list, index - 1);
    Node *aux2 = aux-&gt;prox;
    if (aux) {
        new_node-&gt;prox = aux-&gt;prox;
        aux-&gt;prox = new_node;
        list-&gt;size++;
    }
}

void PopFront(List *list) {
    if (EmptyList(*list))
        return;
    Node* aux = list-&gt;head;
    Node* tracker, *tracker_next;
    tracker = list-&gt;head;
    if (tracker-&gt;prox != NULL) {
        tracker_next = tracker-&gt;prox;
        while (tracker_next-&gt;prox != NULL) {
            tracker = tracker_next;
            tracker_next = tracker_next-&gt;prox;
        }    
        tracker-&gt;prox = NULL;
        aux = tracker_next;
    }
    if (aux == list-&gt;head) {
        list-&gt;head = NULL;
    }
    free(aux);
    list-&gt;size--;
}

void PopBack(List* list){
    if(EmptyList(*list))
        return;
    Node* aux = list-&gt;head;
    list-&gt;head = list-&gt;head-&gt;prox;
    free(aux);
    list-&gt;size--;   
}
void PopByIndex (List *list, int index) {
    if (index == 0) {
        PopBack(list);
        return;
    }
    //if (index + 1 == list-&gt;size) {
    //    PopFront(list);
    //    return;
    //}
    Node *aux, *aux_next;
    aux = TrackListbyIndex(*list, index - 1);
    if (aux) {
        aux_next = aux-&gt;prox;
        aux-&gt;prox = aux_next-&gt;prox;
        free(aux_next);
        list-&gt;size--;
    }
}

void PrintList(List list) {
    Node *tracker = list.head;
    while (tracker != NULL) {
        PrintNode(*tracker);
        tracker = tracker-&gt;prox;
    }
}

void Menu(void);
void HandleMenu(int);

int main(void) {
    int option;
    for (;;) {
        Menu();
        printf(&quot;Type your choosen:&quot;);
        scanf(&quot;%d&quot;, &amp;option);
        system(&quot;clear&quot;);
        HandleMenu(option);
    }
    return 0;
}

void Menu(void) {
    printf(&quot;\t--------\n&quot;);
    printf(&quot;\t |Menu|\n&quot;);
    printf(&quot;\t--------\n&quot;);
    printf(&quot;(1) Add Element in Front\n&quot;);
    printf(&quot;(2) Add Element in Back\n&quot;);
    printf(&quot;(3) Add Element in Position\n&quot;);
    printf(&quot;(4) Remove Element from Front\n&quot;);
    printf(&quot;(5) Remove Element from Back\n&quot;);
    printf(&quot;(6) Remove Element by Position\n&quot;);
    printf(&quot;(7) Print List\n&quot;);
    printf(&quot;(8) Calculate Itens Sum\n&quot;);
    printf(&quot;(0) Exit Program\n&quot;);
}

void HandleMenu(int option) {
    static List *market_list = NULL;
    Node* new_node = NULL;
    char node_name[100];
    float node_price;
    int index;
    if (market_list == NULL)
       market_list = InstantiateList();
    switch (option) {
      case 0:
        exit(1);
        break;
      case 1:
        new_node = InstantiateNode();
        printf(&quot;Type the product&#39;s name: &quot;);
        scanf(&quot; %[^\n]&quot;, node_name);
        printf(&quot;Type the product&#39;s price: &quot;);
        scanf(&quot;%f&quot;, &amp;node_price);
        InitNode(new_node, node_name, node_price);
        PushFront(market_list, new_node);
        printf(&quot;Item Added\n&quot;);
        break;
      case 2:
        new_node = InstantiateNode();
        printf(&quot;Type the product&#39;s name: &quot;);
        scanf(&quot; %[^\n]&quot;, node_name);
        printf(&quot;Type the product&#39;s price: &quot;);
        scanf(&quot;%f&quot;, &amp;node_price);
        InitNode(new_node, node_name, node_price);
        PushBack(market_list, new_node);
        printf(&quot;Item Added\n&quot;);
        break;
      case 3:
        new_node = InstantiateNode();
        printf(&quot;Type the product&#39;s name: &quot;);
        scanf(&quot; %[^\n]&quot;, node_name);
        printf(&quot;Type the product&#39;s price: &quot;);
        scanf(&quot;%f&quot;, &amp;node_price);
        InitNode(new_node, node_name, node_price);
        printf(&quot;Type Index: &quot;);
        scanf(&quot;%d&quot;, &amp;index);
        PushByIndex(market_list, new_node, index-1);
        printf(&quot;Item Added\n&quot;);
        break;
      case 4:
        PopFront(market_list);
        break;
      case 5:
        PopBack(market_list);
        break;
      case 6:
        printf(&quot;Type Index: &quot;);
        scanf(&quot;%d&quot;, &amp;index);
        PopByIndex(market_list, index-1);
        break;
      case 7:
        PrintList(*market_list);
        break;
    }
}

答案1

得分: 2

  1. InstantiateNode() 分配了一个 Node * 的空间,但您需要分配 Node 的空间:
Node *new_node = malloc(sizeof *new_node);
  1. InstantiateList() 分配了一个 List * 的空间,但您需要分配 List 的空间:
List *new_list = malloc(sizeof *new_list);

进行这两个更改后,移除后的输出如下:

名称:      A  价格:1.00
名称:      B  价格:2.00
名称:      C  价格:3.00
英文:
  1. InstantiateNode() allocates space for a Node * but you want space for the Node:
Node *new_node = malloc(sizeof *new_node);
  1. InstantiateList() allocates space for a List * but you want space for the List:
List *new_list = malloc(sizeof *new_list);

After those two changes here is the output after the removal:

Name:        A  Price: 1.00
Name:        B  Price: 2.00
Name:        C  Price: 3.00

huangapple
  • 本文由 发表于 2023年3月12日 07:15:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/75710158.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定