C 编程链表指针返回奇怪的值

Question

我在尝试将两个排序链表合并为一个时遇到了一些问题。这是我的代码:

void sortedMerge(LinkedList *l1, LinkedList *l2, LinkedList *result)
{
    int i = 0;
    while (l1->size > 0 && l2->size > 0) {
        if (l1->head < l2->head) {
            removeNode(l1, 0);
            insertNode(result, i++, l1->head);
        }
        else {
            removeNode(l2, 0);
            insertNode(result, i++, l2->head);
        }
    }
}

int insertNode(LinkedList *ll, int index, int value)
{
    ListNode *pre, *cur;
    if (ll == NULL || index < 0 || index > ll->size + 1)
        return -1;
    if (ll->head == NULL || index == 0) {
        cur = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = value;
        ll->head->next = cur;
        ll->size++;
        return 0;
    }
    if ((pre = findNode(ll, index - 1)) != NULL) {
        cur = pre->next;
        pre->next = malloc(sizeof(ListNode));
        pre->next->item = value;
        pre->next->next = cur;
        ll->size++;
        return 0;
    } 
    return -1;
}

int removeNode(LinkedList *ll, int index)
{
    ListNode *pre, *cur;
    if (ll == NULL || index < 0 || index >= ll->size)
        return -1;
    if (index == 0) {
        cur = ll->head->next;
        free(ll->head);
        ll->head = cur;
        ll->size--;
        return 0;
    }
    if ((pre = findNode(ll, index - 1)) != NULL) {    
        if (pre->next == NULL)
            return -1;
        cur = pre->next;
        pre->next = cur->next;
        free(cur);
        ll->size--;
        return 0;
    }
    return -1;
}

我的主函数的代码片段:

case 1:
        printf("Input an integer that you want to add to the linked list 1:\n");
        scanf("%d", &i);
        j = insertSortedLinkedList(&ll1, i);
        printf("Linked list 1 : ");
        printList(&ll1);
        break;
    case 2:
        printf("Input an integer that you want to add to the linked list 2:\n");
        scanf("%d", &i);
        j = insertSortedLinkedList(&ll2, i);
        printf("Linked list 2 : ");
        printList(&ll2);
        break;
    case 3:
        sortedMerge(&ll1, &ll2, &resultMergedList); 
        printf("The resulting linked list is:\n");
        printList(&resultMergedList);
        break;

因此，我为 l1 输入了 2,4,6，为 l2 输入了 1,2,3。预期输出应为 1,2,2,3,4,6。但是，我收到 4229048, 4228432, 4228565, 0。 我在想是不是因为我得到的输出是内存位置？

有什么想法吗？提前致谢。

Answer 1

正如 kcraigie 所指出的，您应该使用它 item 创建一个新节点。编译器应该警告您，您正在传递一个需要整数的指针。

快速修复似乎是这样的:

    removeNode(l1, 0);
    insertNode(result, index++, l1->head->item);

但事实并非如此:removeNode 会改变 l1 的头部，很可能是 NULL。取消引用 NULL 可能会导致分段违规。

该修复还有其他问题:如果成功，它会在删除的头之后添加节点的项目。所以做这样的事情:

    int item = l1->head->item;

    removeNode(l1, 0);
    insertNode(result, index++, item);

更正后，您的合并仍然未完成:您最终会遇到其中一个列表为空的情况。你不处理这种情况。

还有改进的空间。您可以采取简单的方法，只需销毁列表并使用相同的数据创建一个新列表即可。这是解决您的问题的有效方法，但只需重新排列(或重新链接)现有节点即可解决问题。

以下是合并列表方法的更正版本:

void sortedMerge(LinkedList *l1, LinkedList *l2, LinkedList *result)
{
    int index = 0;
    while (l1->size > 0 && l2->size > 0) {
        if (l1->head->item < l2->head->item) {
            int item = l1->head->item;

            removeNode(l1, 0);
            insertNode(result, index++, item);
        } else {
            int item = l2->head->item;

            removeNode(l2, 0);
            insertNode(result, index++, item);
        }
    }

    while (l1->size) {
        int item = l1->head->item;

        removeNode(l1, 0);
        insertNode(result, index++, item);
    }

    while (l2->size) {
        int item = l2->head->item;

        removeNode(l2, 0);
        insertNode(result, index++, item);
    }    
}

您可以将重复的删除和插入重构为新函数。