c - 在C中按升序对链表进行排序

Question

我正在为我的 C 编程类(class)开发一个程序，该程序应该能让我们获得使用链表的经验。作业的最后一部分要求我们获取一个链表，并使用我们之前在程序中编写的前置或追加函数对其进行升序排序。

struct lnode
{
  int datum;
  struct lnode *next;
};


struct lnode*
prepend(struct lnode *list, int x)
{
  struct lnode *node = (struct lnode *)malloc(sizeof(struct lnode));
  node -> datum = x;
  node -> next = list;
  list = node;
  return list;
}

struct lnode*
append(struct lnode *list, int x)
{
  if(list==NULL){
    list = (struct lnode *)malloc(sizeof(struct lnode));
    list -> datum = x;
    list -> next = NULL;
  }else{
    list -> next = append(list->next,x);li
  }
  return list;
}

以上是我们在类里面设计的append和prepend函数。

下面是删除函数，我们在类里面也做过:

struct lnode*
delete(struct lnode *list, int x)
{
  struct lnode* tmp;
  if(list == NULL){
    return list;
  }else if(list-> datum == x){
    tmp = list -> next;
    list -> next = NULL;
    free(list);
    list = tmp;
    return list;
  }else{
    list->next = delete(list->next,x);
    return list;
  }
}

int
find_smallest(struct lnode*list)
{
  int smallest;
  smallest = list->datum;
  while(list!=NULL){
    if(list->datum < smallest){
      smallest = list->datum;
    }
    list = list->next;
  }
  return smallest;
}

函数 find_smallest 将链表作为其输入，并应返回链表中的最小整数值。我已经多次测试此功能，它似乎运行良好。

最后，下面的 sort 应该创建一个新的链表 new_list 并且应该追加 list 中最小整数的值，然后从 list 中删除该值，直到 list 不再有任何值。

struct lnode*
sort(struct lnode *list)
{
  struct lnode *new_list;
  while(list != NULL && list->next != NULL){
    new_list = append(new_list, find_smallest(list));
    list = delete(list, find_smallest(list));
  }
  return new_list;
}

我遇到的问题是我似乎遇到了无限循环。我运行了一个测试用例，在每次运行循环后打印列表的元素，其中列表最初是 5 4 1 2 3，打印出来的是 5 4 2 3 一遍又一遍，直到我强制程序停止。所以我相信它只正确运行一次？

Answer 1

变量new_list 没有在sort 函数中初始化。 append 函数然后错误地附加到一个不存在的节点。

改变

struct lnode *new_list;

到

struct lnode *new_list = NULL;

在 sort 函数中。