CODEWITHSUNDEEP
csortingpointerslinked-listcrash
RalphTheCreator
RalphTheCreator

Reputation: 15

Sorted Insertion in linked list with pointers, C program crashes

I'm "translating" this program from a pseudo Pascal language. Recently I learned C structs and pointers features, and from the start I noticed that pointers are very annoying. So this is a recursive version of the Sorted Insertion in a Linked List algorithm, and it still gives me problems, like crashing.

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

This is the main:

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

Maybe I'm doing something wrong with the list printing at the end of the algorithm, is it? In the prompt the output is "1 3 7" but the program crashes after a while. It must be "1 3 5 7", by this way I noticed up that the procedure "ordered_insert_rec" doesn't work correctly.

Thanks for the help. :)

Upvotes: 1

Views: 88

Answers (1)

Afshin
Afshin

Reputation: 9173

Here is corrected code:

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

I didn't improve your code, just changed it for a working code as pointer tutorial. you can write this code better.

Problems:

  1. Uninitialized links (head and insertion_node).
  2. Your code updates head in function which is a pointer. So you need to use double pointers or you will just change it in function and results will not send back to main.
  3. That break inside while loop for printing list is useless. Condition of while will not met on next iteration and it will stop.
  4. You missed a return for when you are inserting in an empty list.
  5. In general, people don't use stack variables as list members. Normally you need to allocate them. But in this specific case, you can use it.

Upvotes: 1

Related Questions