C链表在末尾插入节点而不替换先前的节点

I'm having some trouble with my insertion method for a linked list in C. It looks like every insertion i make only replaces the previous one. so at the end the list always contains only one cell . i think the problem starts with "insertToEndList" function. Do you see any reason why it's failing?

我在C中使用我的插入方法遇到一些链接列表的问题。看起来我所做的每个插入只替换了前一个插入。所以最后列表总是只包含一个单元格。我认为问题始于“insertToEndList”函数。你有没有看到它失败的原因？

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

typedef struct listNode{
    int* dataPtr;
    struct listNode* next;
}ListNode;

typedef struct list
{
    ListNode* head;
    ListNode* tail;
}List;

void deleteFromBeginnigOfList (List *list);
void deallocateListCell (ListNode *cell);
void freeList (List *list);
void printList (List *list);
void insertDataToBeginningList (List *list, int num);
void addToBeginningList (List *list, ListNode *cell);
List merge (List list1, List list2);
ListNode *createCell (int num);
void addToEmtyList(List *list, ListNode *cell);
void addToEndList(List *list, ListNode *cell);
void insertDataToEndList(List *list, int num);
void makeEmptyList(List *list);
List getList();
void main()
{

    List lst1, lst2, mergedList;

    lst1 = getList();
    lst2 = getList();
    mergedList = merge(lst1,lst2);

    printf("Merged list:\n");
    printList(&mergedList);

    freeList(&lst1);
    freeList(&lst2);
    freeList(&mergedList);

}

List getList()
{
    List res;
    int size, num, i;

    makeEmptyList(&res);

    printf("Please enter the number of items to be entered:\n");
    scanf("%d", &size);

    printf("Please enter the numbers:\n");
    for(i = 0; i < size; i++)
    {
        scanf("%d", &num);
        insertDataToEndList(&res, num);
    }

    return res;

}
void makeEmptyList(List *list){
    list->head=list->tail=NULL;
}
void insertDataToEndList(List *list, int num){

    ListNode *cell_to_add= createCell (num);
    if (list->head==NULL)
        addToEmtyList(list, cell_to_add);
    else
        addToEndList(list, cell_to_add);
}
ListNode *createCell (int num){
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    if (!cell)
    {
        printf("memory allocation failed\n");
        exit(1);
    }
    cell->dataPtr=&num;
    cell->next=NULL;

    return cell;
}
void addToEmtyList(List *list, ListNode *cell){
    list->head=list->tail=cell;
}
void addToEndList(List *list, ListNode *cell){
    list->tail->next=cell;
    list->tail=cell;
}
List merge (List list1, List list2){
    List merge_res; 
    ListNode *curr_cell1=list1.head, *curr_cell2=list2.head; 
    ListNode *cell_to_add;

    makeEmptyList (&merge_res); 
    while (curr_cell1 && curr_cell2) 
    {
        if (*(curr_cell1->dataPtr)>*(curr_cell2->dataPtr))
        {
            insertDataToEndList(&merge_res, *(curr_cell1->dataPtr));
            curr_cell1=curr_cell1->next;
        }
        else
        {
            insertDataToEndList(&merge_res, *(curr_cell2->dataPtr));
            curr_cell2=curr_cell1->next;
        }
    }
    while (curr_cell1)
    {
        insertDataToEndList(&merge_res, *(curr_cell1->dataPtr));
        curr_cell1=curr_cell1->next;
    }
    while (curr_cell2)
    {
        insertDataToEndList(&merge_res, *(curr_cell2->dataPtr));
        curr_cell2=curr_cell2->next;
    }
    return merge_res;
}

void printList (List *list){
    ListNode *curr_cell=list->head;

    while (curr_cell)
    {
        printf("%d, ", *(curr_cell->dataPtr));
        curr_cell=curr_cell->next;
    }
}
void freeList (List *list){
    while (list->head)
        deleteFromBeginnigOfList(list);
}
void deleteFromBeginnigOfList (List *list){
    ListNode *cell_to_delete=list->head;
    list->head=list->head->next;
    if (list->head==NULL)
        list->tail=NULL;
    deallocateListCell (cell_to_delete);
}
void deallocateListCell (ListNode *cell){
    free(cell->dataPtr);
    free (cell);
}

2 个解决方案

#1

There are a few errors here. Most are relatively simple pointer errors:

这里有一些错误。大多数是相对简单的指针错误：

In one place you have

在一个地方你有

curr_cell2=curr_cell1->next;

where it should be

它应该在哪里

curr_cell2 = curr_cell2->next;

In addToEmtyList, you have

在addToEmtyList中，你有

list->head->next=list->tail->next=cell

but if the list is empty, then both head and tail are null. Similarily, the condition in insertDataToEndList should check list->head and not list->head->next.

但如果列表为空，则head和tail均为null。类似地，insertDataToEndList中的条件应该检查list-> head而不是list-> head-> next。

A more aggravating error is that you're taking the address of a local variable (num) and saving it in each cell. Saving the address of a local variable is something you should almost never do, since the pointer will become invalid as soon as you leave its scope (in this case, when you leave createCell).

更加严重的错误是您获取局部变量（num）的地址并将其保存在每个单元格中。保存局部变量的地址是你几乎不应该做的事情，因为一旦离开其范围（在这种情况下，当你离开createCell时）指针将变为无效。

What you should do, if you really want to have a pointer to the data, is allocate memory for it separately. I.e.:

你应该做什么，如果你真的想拥有一个指向数据的指针，那就是分别为它分配内存。即：

ListNode *createCell (int num){
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    int *data = malloc(sizeof(*data));

    if (!cell || !data)
    {
        printf("memory allocation failed\n");
        exit(1);
    }

    *data = num;
    cell->dataPtr=data;
    cell->next=NULL;

    return cell;
}

Another option is to change listNode to contain an int instead of an int*. Then you'd have

另一种选择是将listNode更改为包含int而不是int *。然后你就拥有了

typedef struct listNode{
    int data;
    struct listNode* next;
}ListNode;

and in createCell simply

而在createCell中

cell->data = num;

#2

In this function, you access to list->head->next but on the first insertDataToEndList, list->head == NULL since you used makeEmptyList so the result will be a segmentation fault. Also, you want to check if the list is Empty so do list->head == NULL instead.

在此函数中，您可以访问list-> head-> next但是在第一个insertDataToEndList，list-> head == NULL，因为您使用了makeEmptyList，因此结果将是分段错误。此外，您要检查列表是否为空，所以请执行list-> head == NULL。

void insertDataToEndList(List *list, int num)
{    
    ListNode *cell_to_add= createCell (num);
    if (list->head->next==NULL)
        addToEmtyList(list, cell_to_add);
    else
        addToEndList(list, cell_to_add);
}

In this method, you have to set the first and the last node of your list, not the next so replace by list->head and list->tail instead of lis->head->nest. and list->tail->next.

在这个方法中，你必须设置列表的第一个和最后一个节点，而不是下一个节点，所以用list-> head和list-> tail代替lis-> head-> nest。和list-> tail-> next。

void addToEmtyList(List *list, ListNode *cell)
{
    list->head->next=list->tail->next=cell;

}

You can do that instead :

你可以这样做：

ListNode *createCell (int num)
{
    ListNode *cell=(ListNode*)malloc(sizeof(ListNode));
    if (!cell)
    {
        printf("memory allocation failed\n");
        exit(1);
    }
    int *temp = (int*)malloc(sizeof(int));
    *temp = num;
    cell->dataPtr=temp;
    cell->next=NULL;

    return cell;
}

Else, I advise you to do one assignement by line to be more lisible.

否则，我建议你按行进行一次分配，使其更加隐形。

#1