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);
    }    
}

您可以将重复的移除和插入重构到一个新函数中。

Answer 2

您正在使用l1->head而不是l1->head->项对结果链表调用insertNode（）。

相反，尝试在释放前插入头部的项目以获得结果：

while (l1->size > 0 && l2->size > 0) {
    if (l1->head < l2->head) {
        insertNode(result, index++, l1->head->item);
        removeNode(l1, 0);
    } else {
        insertNode(result, index++, l2->head->item);
        removeNode(l2, 0);
    }
}

此外，当你的一个列表用完时，你会退出并忽略另一个列表中的其余项目。你可以在上面的循环后添加这个代码：

while (l1->size > 0) {
    insertNode(result, index++, l1->head->item);
    removeNode(l1, 0);
}
while (l2->size > 0) {
    insertNode(result, index++, l2->head->item);
    removeNode(l2, 0);
}

不是最有效的，但它应该有效。

Answer 3

示例合并排序列表函数，以及使用指向列表节点的指针数组的排序列表函数和合并列表函数来实现链表的快速排序。

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    if(pSrc1 == NULL)
        return pSrc2;
    if(pSrc2 == NULL)
        return pSrc1;
    while(1){
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            if(pSrc2 == NULL){
                *ppDst = pSrc1;
                break;
            }
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            if(pSrc1 == NULL){
                *ppDst = pSrc2;
                break;
            }
        }
    }
    return pDst;
}
#define NUMLISTS 32                     /* size of aList[] */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];                 /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)                   /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)       /* zero array */
        aList[i] = NULL;
    pNode = pList;                      /* merge nodes into aList[] */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;                       /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}