使用冒泡排序对单链表进行排序

Question

我编写了以下代码，用于使用冒泡排序对单链表进行排序。排序过程应根据列表中的节点包含的数据对它们进行排序。仅在节点之间交换数据的节点排序是不被接受的。我的代码触发了分段错误（核心转储）。我认为我没有正确跟踪头指针。我正在分享用于重现结果的完整代码。

#include<iostream>
using namespace std;   

typedef struct node
{
    int data;
    struct node *next;
} node;

node* create_node(node *head, int data)
{
    node *baby = (node*)malloc(sizeof(node));
    baby->data = data;
    baby->next = NULL;
    
    if(head==NULL)
        head = baby;
    else
    {
        node *curr = head;
        while(curr->next != NULL)
            curr = curr->next;
        curr->next = baby;  
    }
    return head;    
}

void sort_bubble(node *head)
{
    int count=0, i, j, temp;
    bool swapped;
    node *curr, *tempo, *p1, *p2;
    for(curr=head; curr!=NULL; curr=curr->next)
        count = count+1;
    
    for(i=0; i<=(count-2); i++)
    {
        curr = head;
        swapped = false;
        for(j=0; j<=(count-2-i); j++)
        {
            p1 = curr;
            p2 = p1->next;
            if(p1->data > p2->data)
            {
                tempo = p2->next;
                p2->next = p1;
                p1->next = tempo;
                curr = p2;
                swapped = true;
            }
            curr = curr->next;
        }
        if(swapped = false)
            break;
    }
}

void print_list(node *head)
{
    node *curr = head;
    while(curr)
    {
        cout<<curr->data<<" ";
        curr = curr->next;
    }
    cout<<"\n";
}

int main()
{
    int count = 6;
    node *head = NULL;
    
    head = create_node(head, 40);
    head = create_node(head, 10);
    head = create_node(head, 60);
    head = create_node(head, 50);
    head = create_node(head, 20);
    head = create_node(head, 30);
    print_list(head);
    
    sort_bubble(head);
    print_list(head);
    
    return 0;
}

Answer 1

几个问题：

1. 头节点交换：在您的代码中，如果需要交换头节点，则不会更新它。在更正的版本（如下）中，使用

   *head_ref = next;

   适当更新了头指针。

2. 前一个节点跟踪：在您的代码中，您没有考虑正在交换的节点之前的节点。我引入了一个

   prev

   变量来跟踪，以便我们可以在交换期间更新

   prev->next

   。

3. 终止条件：原始代码有

   if (swapped = false),

   ，无法按预期工作。这是一个任务，而不是一个比较。修复为

   if (!swapped) break;

   。

4. 指向头的指针：该函数现在采用指向头指针的指针（

   node **head_ref

   ）。这允许我们修改头指针，而不仅仅是它指向的节点。

#include<iostream>

typedef struct node {
  int data;
  struct node *next;
} node;

node *create_node(node *head, int data) {
  node *baby = (node *) malloc(sizeof(node));
  baby->data = data;
  baby->next = nullptr;
  if (head == nullptr)
    head = baby;
  else {
    node *curr = head;
    while (curr->next != nullptr)
      curr = curr->next;
    curr->next = baby;
  }
  return head;
}

void sort_bubble(node **head_ref) {
  node *curr, *prev, *next;
  bool swapped;
  int count = 0;
  // Counting nodes
  for (curr = *head_ref; curr != nullptr; curr = curr->next)
    count++;
  for (int i = 0; i < count - 1; i++) {
    curr = *head_ref;
    prev = nullptr;
    swapped = false;
    for (int j = 0; j < count - 1 - i; j++) {
      next = curr->next;
      if (curr->data > next->data) {
        if (prev == nullptr) {
          *head_ref = next;
        } else {
          prev->next = next;
        }
        curr->next = next->next;
        next->next = curr;
        swapped = true;
        prev = next;
      } else {
        prev = curr;
        curr = next;
      }
    }
    if (!swapped) {
      break;
    }
  }
}

void print_list(node *head) {
  node *curr = head;
  while (curr) {
    std::cout << curr->data << ' ';
    curr = curr->next;
  }
  std::cout << '\n';
}

int main() {
  node *head = nullptr;
  head = create_node(head, 40);
  head = create_node(head, 10);
  head = create_node(head, 60);
  head = create_node(head, 50);
  head = create_node(head, 20);
  head = create_node(head, 30);
  print_list(head);
  sort_bubble(&head);
  print_list(head);
  return 0;
}

新输出：

40 10 60 50 20 30 
10 20 30 40 50 60