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

Question

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

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

以上是我们在 class.

中设计的 append 和 prepend 函数

下面是删除功能，我们在class中也做过：

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以链表作为输入，并且应该return链表中的最小整数值。我已经多次测试这个功能，它似乎工作得很好。

最后，下面的排序应该创建一个新的链表 new_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 函数中。

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

Sorting a linked list in ascending order in C

c

sorting

linked-list