当前位置： 文江博客话题详情

使用 for 循环时合并两个排序链表算法不起作用

发布于 2025-01-10 23:24:47 字数 3140 浏览 1 评论 0原文

所以在我的下面的代码中，我有两个列表。它们中的每一个都应该按升序排序，然后使用 SortedMerge() 将它们合并到一个列表中。 当我在主体中单独插入数字时，代码工作得很好：

int main()
{
    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

但就我而言，我不想单独插入数字，而是有两个数组并使用 for 循环将它们插入到列表中。该代码再次将它们合并在一起，但不按升序对它们进行排序：

int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

以下代码既单独插入，又使用 for 循环。 如果为了清楚起见，有人需要整体代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
struct Node
{
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source);
 
struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    while (1) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        else if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &((*lastPointer)->next);
    }
    return (result);
}
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

void insert(struct Node **head, int data)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    if (newNode == NULL)
        printf(" Memory can not be allocated.");
    else {
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
    }
}

void printList(struct Node *node)
{
    while (node)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);
    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}
原文

So in my following code, I have two lists. Each of them should be sorted in increasing order and then merged together into one list with SortedMerge().
The code works just fine when in the main I insert the numbers separately:

int main()
{
    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

But in my case I don't want to insert numbers separately but rather have two arrays and insert them to the list using for loop. The code again merges them together, but does not sort them in increasing order:

int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

The following code has both insert separately and with for loop.
If for clarity anybody will need the overall code:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
struct Node
{
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source);
 
struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    while (1) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        else if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &((*lastPointer)->next);
    }
    return (result);
}
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

void insert(struct Node **head, int data)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    if (newNode == NULL)
        printf(" Memory can not be allocated.");
    else {
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
    }
}

void printList(struct Node *node)
{
    while (node)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
int main()
{
    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    struct Node *final = NULL;
    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);
    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

鱼窥荷 2025-01-17 23:24:47

您的 SortedMerge 函数需要两个按升序排序的列表，并将它们按升序合并为一个列表。

对于第一个示例：（

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

注意：insert 在列表的前面插入。）

  • List a: 5, 10, 15。List
  • b : 2, 3, 20

列表 a 和 b 按升序排列，因此对 SortedMerge 有效。

对于第二个示例：（

    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

注意：insert 在列表的前面插入。）

  • List a: 15, 10, 5
  • List b: 20, 3, 2

列表 a 和 b 按降序排列，因此对于 SortedMerge 无效。

对于第三个（组合示例）：

  • 列表 a：5, 10, 15, 15, 10, 5
  • 列表 b：2, 3, 20, 20, 3, 2

列表 a 和 b 未排序，因此对于 SortedMerge 无效。

Your SortedMerge function expects two lists sorted in ascending order and merges them into a single list in ascending order.

For the first example:

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);

(Note: insert inserts at the front of the list.)

  • List a: 5, 10, 15.
  • List b: 2, 3, 20

Lists a and b are in ascending order so are valid for SortedMerge.

For the second example:

    int list1[] = { 15, 10, 5 };
    int list2[] = { 20, 3, 2 };

    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = n1 - 1; i >= 0; i--) insert(&a, list1[i]);
    for (int i = n2 - 1; i >= 0; i--) insert(&b, list2[i]);

(Note: insert inserts at the front of the list.)

  • List a: 15, 10, 5
  • List b: 20, 3, 2

Lists a and b are in descending order so are not valid for SortedMerge.

For the third (combined example):

  • List a: 5, 10, 15, 15, 10, 5
  • List b: 2, 3, 20, 20, 3, 2

Lists a and b are not sorted so are not valid for SortedMerge.

回复 原文
听不够的曲调 2025-01-17 23:24:47

问题是 SortedMerge 假设列表按升序排序，而您打破了这个假设：您将元素从数组中的最后一个元素添加到第一个元素（该函数称为 insert，一个令人困惑的选择），但数组的内容已经按降序排列，因此您可以有效地按降序排列列表。然后您在前面添加更多元素，因此这些列表是未排序的。

  • 将插入循环更改为 for (int i = 0; i < n1; i++) insert(&a, list1[i]); 并且不要插入更多元素或
  • 更改数组内容，以便数组按升序排列，不会插入更多元素或
  • 更改 insert 函数以将新节点插入到正确的位置。

这是使用后者的修改版本：

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    for (;;) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &(*lastPointer)->next;
    }
    return result;
}
 
void insert(struct Node **head, int data)
{
    struct Node *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory cannot be allocated.\n");
        return;
    }
    while (*head != NULL && (*head)->data < data) {
        head = &(*head)->next;
    }
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void printList(const struct Node *node)
{
    while (node) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
 
int main()
{
    int list1[] = { 5, 10, 15 };
    int list2[] = { 2, 3, 20 };

    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = 0; i < n1; i++)
        insert(&a, list1[i]);
    for (int i = 0; i < n2; i++)
        insert(&b, list2[i]);

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    struct Node *final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}

The problem is SortedMerge assumes the lists are sorted in ascending order and you break this assumption: you prepend the elements from the last to the first in the arrays (the function is called insert, a confusing choice), but the contents of the arrays in already in decreasing order so you effectively get the list sorted in decreasing order. Then you prepend more elements, so these lists are unsorted.

  • change the insertion loop to for (int i = 0; i < n1; i++) insert(&a, list1[i]); and do not insert more elements or
  • change the array contents so the arrays are in increasing order and do not insert more elements or
  • change the insert function to insert the new node in the proper place.

Here is a modified version using the latter:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node *next;
};
 
void MoveNode(struct Node **destRef, struct Node **source)
{
    struct Node *newNode = *source;
    assert(newNode != NULL);
 
    *source = newNode->next;
    newNode->next = *destRef;
    *destRef = newNode; 
}

struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;
    struct Node **lastPointer = &result;
   
    for (;;) {
        if (a == NULL) {
            *lastPointer = b;
            break;
        }
        if (b == NULL) {
            *lastPointer = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(lastPointer, &a);
        else
            MoveNode(lastPointer, &b);
    
        lastPointer = &(*lastPointer)->next;
    }
    return result;
}
 
void insert(struct Node **head, int data)
{
    struct Node *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory cannot be allocated.\n");
        return;
    }
    while (*head != NULL && (*head)->data < data) {
        head = &(*head)->next;
    }
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void printList(const struct Node *node)
{
    while (node) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}
 
int main()
{
    int list1[] = { 5, 10, 15 };
    int list2[] = { 2, 3, 20 };

    struct Node *a = NULL;
    struct Node *b = NULL;
    
    int n1 = sizeof(list1) / sizeof(list1[0]);
    int n2 = sizeof(list2) / sizeof(list2[0]);

    for (int i = 0; i < n1; i++)
        insert(&a, list1[i]);
    for (int i = 0; i < n2; i++)
        insert(&b, list2[i]);

    insert(&a, 15);
    insert(&a, 10);
    insert(&a, 5);
 
    insert(&b, 20);
    insert(&b, 3);
    insert(&b, 2);
    struct Node *final = SortedMerge(a, b);
 
    printList(final);
 
    return 0;
}
回复 原文
~没有更多了~

关于作者

一页

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

Promise

文章 0 评论 0

qq_lbRlsh

文章 0 评论 0

待＂谢繁草

文章 0 评论 0

yy2010hell

文章 0 评论 0

漫无边际

文章 0 评论 0

傲娇萝莉攻

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文