改善我的链接列表的Mergesort。如何？

Question

在我深入解释之前，您应该意识到以下代码可能真的很糟糕。我大约2个月前开始编程（那里几个小时和那里）。因此，我没有经验，我的编码风格非常改进，我仍然错过练习和很多（基本）知识。这也包括我用错误的名字打电话给东西:)。

我对算法（大学）感兴趣，并想练习一些指针处理（最初有很多问题），所以我决定与单独的链接列表一起使用Mergesort，并与我的教授的Mergesort算法相比，它的性能（哪个是什么）排序阵列）。不，这不是作业（我的大学课程（电气工程）都没有作业 - 这是我在理解算法，C和简单地练习事物方面的理解。

---

我的代码已经有效。为了测试目的，我总是创建反向排序的列表。对于此类列表而言，它仍然缺少一些案例。

因此，在发布代码之前，我正在使用的结构：

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

我得到了两个功能，Mergesort and Merge。 Mergesort返回分类（子）列表的新头部，并合并返回合并序列的头部。

现在，我向Mergesort提供了未分类列表的当前负责人和元素的数量。然后，它递归地分解列表（显然：）。我不确定在以下代码上要说多少。如果有什么不清楚的话，我会回答并尽快解释，但是

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

合并接收两个子列表的头（这是一个元素或已经排序的序列）和第一个和第二个列表的元素。

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

因此，我欢迎对我做什么简单地愚蠢的任何评论，在那里我没有考虑可能的问题，某些输入代码中断代码或如何做得更好，我敢肯定还有很多改进的可能性。提前致谢。

Answer 1

合并阶段的“正常”结构是：

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

“移动”操作包括将指针更新为列表中的下一个项目。

您的结构有些不同 merge() 功能。

要求计算列表也是如此。通常，您可以使用“下一步为null”或“下一个是头”来确定列表的结尾，具体取决于列表是纯线性的还是是圆形列表。