Home > database >  display a sorted linked list with every new element in c
display a sorted linked list with every new element in c

Time:02-23

So I am trying to make a program in c that will let the user enter numbers until the number 0 in entered. Then create a linked list that will sort the entered integers from smallest to largest. Here is my code:

#include <stdio.h>
#include <stdlib.h>

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

node* insert(node* head, int num) {
    node *temp, *prev, *next;
    temp = (node*)malloc(sizeof(node));
    temp->data = num;
    temp->ptr = NULL;
    if(!head){
        head=temp;
    } else{
        prev = NULL;
        next = head;
        while(next && next->data<=num){
            prev = next;
            next = next->ptr;
        }
        if(!next){
            prev->ptr = temp;
        } else{
            if(prev) {
                temp->ptr = prev->ptr;
                prev-> ptr = temp;
            } else {
                temp->ptr = head;
                head = temp;
            }
        }
    }
    return head;
}

void free_list(node *head) {
    node *prev = head;
    node *cur = head;
    while(cur) {
        prev = cur;
        cur = prev->ptr;
        free(prev);
    }
}

int main(){
    int num;
    node *head, *p;
    head = NULL;

    do {
        printf("Enter a number: ");
        scanf("%d",&num);
        printf("%d->\n", num);
        if(num) {
            head = insert(head, num);
        }
    } while(num);

    p = head;
    printf("\nThe entered numbers are:\n");

    while(p) {
        printf("%d->", p->data);
        p = p->ptr;
    }
    free_list(head);
    printf("NULL");

    return 0;
}

As you can hopefully will see, the output will look something like this:

Enter number: 6
6->NULL
Enter number: 3
3->NULL
Enter number: 9
9->NULL
Enter number: 0
0->

The entered numbers are :
3->6->9->NULL

However, what I want is these numbers to be sorted as they are being entered and inserted into the list (also I need the 0 to not be displayed). So the output should look like this:

Enter number: 6
6->NULL
Enter number: 3
3->6->NULL
Enter number: 9
3->6->9->NULL
Enter number: 0

The entered numbers are :
3->6->9->NULL

Can somebody help me with this please???

CodePudding user response:

You are in fact inserting the elements into the list in sorted order. You're just printing the current value after reading it in instead of the whole list.

So put the printing code inside of a function, then call that function after inserting a value and after all values have been read.

CodePudding user response:

It is better to define a sorted binary search tree. The insert and print functions for the interface of such a tree have less than 5 lines of code.

  1. keep your loop of reading numbers.

  2. Each time when you read a number, you call INSERT_TREE (num)

  3. Use a tree->list function to convert your tree at any moment in a list. Or use a print-tree.

If you want to preserve a list-structure explicitly, you need to define an interface for your data and that interface must contain at least a print/list and an insert/list function.

CodePudding user response:

I have modified a bit of your code please check:

#include <stdio.h>
#include <stdlib.h>

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

node *
insert (node * head, int num)
{
  node *temp, *prev, *next;
  temp = (node *) malloc (sizeof (node));
  temp->data = num;
  temp->ptr = NULL;
  if (!head)
    {
      head = temp;
    }
  else
    {
      prev = NULL;
      next = head;
      while (next && next->data <= num)
    {
      prev = next;
      next = next->ptr;
    }
      if (!next)
    {
      prev->ptr = temp;
    }
      else
    {
      if (prev)
        {
          temp->ptr = prev->ptr;
          prev->ptr = temp;
        }
      else
        {
          temp->ptr = head;
          head = temp;
        }
    }
    }
  return head;
}

void
free_list (node * head)
{
  node *prev = head;
  node *cur = head;
  while (cur)
    {
      prev = cur;
      cur = prev->ptr;
      free (prev);
    }
}

int
main ()
{
  int num;
  node *head, *p;
  head = NULL;

  do
    {
      printf ("\nEnter a number: ");
      scanf ("%d", &num);
      if (num != 0)
    {
      printf ("%d->\n", num);
    }
      if (num)
    {
      head = insert (head, num);
      p = head;
      printf ("\nThe entered numbers are:\n");

      while (p)
        {
          printf ("%d->", p->data);

          p = p->ptr;
        }
    }
    }
  while (num);


  free_list (head);

  return 0;
}

output->
Enter a number: 8
8->

The entered numbers are:
8->
Enter a number: 2
2->

The entered numbers are:
2->8->
Enter a number: 4
4->

The entered numbers are:
2->4->8->
Enter a number: 1
1->

The entered numbers are:
1->2->4->8->
Enter a number: 0

CodePudding user response:

I do not see how you get this output

Enter number: 6
6->NULL
Enter number: 3
3->NULL
Enter number: 9
9->NULL
Enter number: 0
0->

Within this do-while loop

do {
    printf("Enter a number: ");
    scanf("%d",&num);
    printf("%d->\n", num);
    if(num) {
        head = insert(head, num);
    }
} while(num);

the only statement that outputs something is

    printf("%d->\n", num);

but it does not output the string ->NULL.

Within the function insert there is no output statement.

To get the desired output in the do while statement you need to write

do {
    printf("Enter a number: ");
    scanf("%d",&num);
    if(num) {
        head = insert(head, num);
        for ( p = head; p != NULL; p = p->ptr )
        {
            printf("%d->", p->data);
        }
        puts( "NULL " );   
    }
} while(num);

Also you function insert is too complicated. There are too many if statements and local variables. The function can be written simpler. For example

node * insert( node *head, int num ) 
{
    node *temp = malloc( sizeof( node ) );
    temp->data = num;

    if ( head == NULL || head->data < num )
    {
        temp->ptr = head;
        head = temp;
    }
    else
    {
        node *current = head;
        while ( ( current->next != NULL ) && 
                !( num < current->ptr->data ) )
        {
            current = current->ptr;
        }
        
        temp-ptr = current->ptr;
        current->ptr = temp;
    }

    return head;
}
  • Related