Сортировка вставки в связанный список с указателями, сбой программы на C

Question

Я "перевожу" эту программу с псевдо-паскальского языка.Недавно я изучил структуры C и функции указателей, и с самого начала я заметил, что указатели очень раздражают.Так что это рекурсивная версия алгоритма Sorted Insertion в Linked List, и он все еще доставляет мне проблемы, такие как сбой.

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node *head, Node *new_node)
{
  if(!head)
  {
    new_node->link = head;
    head = new_node;
  }

  if(new_node->info < head->info)
  {
    new_node->link = head;
    head = new_node;
  }
  else
  {
    ordered_insert_rec(head->link, new_node);
  }

Это главное:

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;

  inserting_node.info = 5;

  ordered_insert_rec(&head, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
    if(!front)
    {
      exit(1);
    }
  }
}

Может бытьЯ делаю что-то не так с печатью списка в конце алгоритма, не так ли?В командной строке выводится «1 3 7», но программа вылетает через некоторое время.Это должно быть "1 3 5 7", поэтому я заметил, что процедура "orders_insert_rec" работает неправильно.

Спасибо за помощь.:)

Answer 1

Вот исправленный код:

#include <stdio.h>

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node **head, Node *new_node)
{
  // You are inserting at head. So you need to update head pointer.
  // If you don't use double pointers, you only change it locally.
  if(!(*head))
  {
    new_node->link = *head;
    *head = new_node;
    return;
  }

  if(new_node->info < (*head)->info)
  {
    new_node->link = *head;
    *head = new_node;
  }
  else
  {
    ordered_insert_rec(&((*head)->link), new_node);
  }
}

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;
  node2.link = 0;

  inserting_node.info = 5;
  inserting_node.link = 0;

  Node * start = &head;

  ordered_insert_rec(&start, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
  }

  return 0;
}

Я не улучшил ваш код , просто изменил его для рабочего кода в качестве учебника указателя.Вы можете написать этот код лучше.

Проблемы:

1. Неинициализированные ссылки (head и insertion_node).
2. Ваш код обновляет head в функции, которая является указателем.Поэтому вам нужно использовать двойные указатели, или вы просто измените его в функции, и результаты не будут отправлены обратно в main.
3. . Этот разрыв внутри цикла while для печати списка бесполезен.Условие while не будет выполнено на следующей итерации и остановится.
4. Вы пропустили return, когда вставляете в пустой список.
5. Как правило, люди неt использовать переменные стека в качестве членов списка.Обычно вам нужно выделить их.Но в этом конкретном случае вы можете использовать его.