在链表上实现合并排序 [英] Implementing mergesort on a linked list

问题描述

我的任务是在以C/C ++编写的列表上实现合并排序算法.我记下了总体思路，编写了代码并成功编译了代码.但是，当我运行它时，它会开始正常运行，但是会挂在准备好的列表，现在开始排序"上，而不会出现任何错误.我试图查看我的代码，但是对于可能出现的问题我完全不知所措.我在调试方面也很业余，因此尽我所能使用gdb导致我无所适从.任何建议或提示都将为您带来巨大的帮助，谢谢大家！

I was tasked with implementing a merge sort algorithm on a list written in C/C++. I have the general idea down, wrote my code and have successfully compiled it. However, when I run it, it will begin fine but then hang on "prepared list, now starting sort" without giving any kind of error. I have tried to look through my code but I am at a complete loss as to what the issue could be. I am also pretty amateurish with debugging, so using gdb to the best of my abilities has lead me no where. Any advice or tips would be a tremendous help, thank you all!

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

struct listnode
{
    struct listnode *next;
    int key;
};

    //Finds length of listnode
int
findLength (struct listnode *a)
{
    struct listnode *temp = a;
    int i = 0;
    while (temp != NULL)
    {
        i++;
        temp = temp->next;
    }
    return i;
}


struct listnode *
sort (struct listnode *a)
{
    // Scenario when listnode is NULL
    if (findLength (a) <= 1)
        return a;

    //Find middle
    int mid = findLength (a) / 2;
    struct listnode *temp = a;
    struct listnode *first = a;
    struct listnode *second;

    for (int i = 0; i < mid - 1; i++)
    {
        temp = a->next;
    }
    second = temp->next;
    temp->next = NULL;

    //Recursive calls to sort lists
    first = sort (first);
    second = sort (second);

    if (first != NULL && second != NULL)
    {
        if (first->key < second->key)
        {
            a = first;
            first = first->next;
        }
        else
        {
            a = second;
            second = second->next;
        }
    }

    struct listnode *head = a;
    struct listnode *tail = a;

    while (first != NULL && second != NULL)
    {
        if (first->key < second->key)
        {
            tail = first;
            first = first->next;
            tail = tail->next;
        }
        else
        {
            tail = second;
            second = second->next;
            tail = tail->next;
        }
    }

    if (first == NULL)
    {
        while (second != NULL)
        {
            tail = second;
            second = second->next;
            tail = tail->next;
        }
    }

    while (first != NULL)
    {
        tail = first;
        first = first->next;
        tail = tail->next;
    }

    return a;
}

以下是提供的测试代码，用C:int编写

Here is the test code provided, written in C:int

main (void)
{
    long i;
    struct listnode *node, *tmpnode, *space;
    space = (struct listnode *) malloc (500000 * sizeof (struct listnode));
    for (i = 0; i < 500000; i++)
    {
        (space + i)->key = 2 * ((17 * i) % 500000);
        (space + i)->next = space + (i + 1);
    }
    (space + 499999)->next = NULL;
    node = space;
    printf ("\n prepared list, now starting sort\n");
    node = sort (node);
    printf ("\n checking sorted list\n");
    for (i = 0; i < 500000; i++)
    {
        if (node == NULL)
        {
            printf ("List ended early\n");
            exit (0);
        }
        if (node->key != 2 * i)
        {
            printf ("Node contains wrong value\n");
            exit (0);
        }
        node = node->next;
    }
    printf ("Sort successful\n");
    exit (0);
}

推荐答案

您很亲密，但有一些愚蠢的错误.在合并步骤中检查追加操作.他们没有按照您的想法去做.当然，您的意思是拆分循环中的temp = temp->next;.

You're close, but with some silly errors. Check the append operations in the merge step. They're not doing what you think they are. And of course you meant temp = temp->next; in the splitting loop.

如果gdb势不可挡，则添加printf是调试此类代码的绝佳方法.实际上，您想编写一个列表打印功能并在每个递归级别上打印子列表以及合并步骤的结果.看着很有趣.保持整洁，完成后删除所有内容.

If gdb is overwhelming, adding printf's is a perfectly fine way to go about debugging code like this. Actually you want to write a list printing function and print the sublists at each level of recursion plus the results of the merge step. It's fun to watch. Just be neat and delete all that when you're done.

以下代码可供参考:

struct listnode *sort(struct listnode *lst) {
  if (!lst || !lst->next) return lst;
  struct listnode *q = lst, *p = lst->next->next;
  while (p && p->next) {
    q = q->next;
    p = p->next->next;
  }
  struct listnode *mid = q->next;
  q->next = NULL;
  struct listnode *fst = sort(lst), *snd = sort(mid);
  struct listnode rtn[1], *tail = rtn;
  while (fst && snd) {
    if (fst->key < snd->key) {
      tail->next = fst;
      tail = fst;
      fst = fst->next;
    } else {
      tail->next = snd;
      tail = snd;
      snd = snd->next;
    }
  }
  while (fst) {
    tail->next = fst;
    tail = fst;
    fst = fst->next;
  }
  while (snd) {
    tail->next = snd;
    tail = snd;
    snd = snd->next;
  }
  tail->next = NULL;
  return rtn->next;
}

在我的旧MacBook上，它会在4秒内对1000万个随机整数进行排序，这似乎还不错.

On my old MacBook this sorts 10 million random integers in a bit over 4 seconds, which doesn't seem too bad.

您还可以将append操作放在宏中，并使其简洁明了:

You can also put the append operation in a macro and make this quite concise:

struct listnode *sort(struct listnode *lst) {
  if (!lst || !lst->next) return lst;
  struct listnode *q = lst, *p = lst->next->next;
  while (p && p->next) {
    q = q->next;
    p = p->next->next;
  }
  struct listnode *mid = q->next;
  q->next = NULL;
  struct listnode *fst = sort(lst), *snd = sort(mid);
  struct listnode rtn[1], *tail = rtn;
  #define APPEND(X) do { tail->next = X; tail = X; X = X->next; } while (0)
  while (fst && snd) if (fst->key < snd->key) APPEND(fst); else APPEND(snd);
  while (fst) APPEND(fst);
  while (snd) APPEND(snd);
  tail->next = NULL;
  return rtn->next;
}

这篇关于在链表上实现合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！