1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dynamic allocation problem with linked lists

  1. Sep 12, 2015 #1
    1. The problem statement, all variables and given/known data
    I need to create data structure which contains three linked lists that are connected to one root node.
    2. Relevant equations
    -Data structures


    3. The attempt at a solution
    I can't find what is wrong with the following code:
    Code (Text):

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

    typedef struct node
    {
      struct node *next;
      int y;
    }NODE;

    typedef struct root
    {
      struct node *first;
      struct node *middle;
      struct node *last;
      int x;
    }ROOT;

    ROOT *form_root(int x)
    {
      ROOT *new_root=(ROOT *)malloc(sizeof(ROOT));
      new_root->first=new_root->middle=new_root->last=0;
      new_root->x=x;
      return new_root;
    }

    void add_in_list(NODE *list,int y)
    {
      NODE *new_node=(NODE *)malloc(sizeof(NODE));
      new_node->y=y;
      new_node->next=NULL;
      if(list == 0)
      list=new_node;
      else
      return ;
    }

    ROOT *add(ROOT *root,int x)
    {
      if(root==0)
      return form_root(x);
      if(x < root->x)
      add_in_list(root->first,x);
      else
      if(x > root->x)
      add_in_list(root->last,x);
      else
      add_in_list(root->middle,x);
      return root;
    }

    int erase_from_list_(NODE *node,int y)
    {
      NODE *p=node->next;
      if(p==0)
      return 0;
      node->y=p->y;
      node->next=p->next;
      free(p);
      return 1;
    }

    ROOT *erase(ROOT *root, int x)
    {
      if(root==0)
      return 0;
      else if(x < root->x)
      root->first=erase_from_list_(root->first,x);
      else if(x > root->x)
      root->last=erase_from_list_(root->last,x);
      else if(x==root->x)
      root->middle=erase_from_list_(root->middle,x);
      else
      return 0;
      return root;
    }

    void sort_list(NODE *head)
    {
      for(;head && head->next;head=head->next)
      {
      NODE *min=head,*p;
      for(p=head->next;p;p=p->next)
      if(min->y > p->y)
      min=p;
      if(min!=head)
      {
      int temp=head->y;
      head->y=min->y;
      min->y=temp;
      }
      }
    }

    void sort(ROOT *root)
    {
      sort_list(root->first);
      sort_list(root->middle);
      sort_list(root->last);
    }

    void print_list(NODE *head)
    {
      while(head)
      {
      printf("%d",head->y);
      head=head->next;
      }
    }

    void print(ROOT *root)
    {
      print_list(root->first);
      print_list(root->middle);
      print_list(root->last);
    }

    int main()
    {
      ROOT *root=0;
      int array[][3]={{0,1,2},{3,4,5},{12,7,8}};
      int i;
      for(i=0;i<3;i++)
      root=add(root,*array[i]);
      int num;
      printf("enter the number to be removed:");
      scanf("%d",&num);
      root=erase(root,num);
      sort(root);
      NODE *head=0;
      print(head);
      return 0;
    }
     
    Could someone help?
     

    Attached Files:

  2. jcsd
  3. Sep 13, 2015 #2

    Mark44

    Staff: Mentor

    A clue as to what's wrong would be helpful. Does your code compile? If not, what compiler and/or linker errors are you getting (including the line number where the error occurs)? Does your code compile, but produce run-time errors? Does your code run, but produce incorrect results?

    We're happy to help, but please give us some information to go on.
     
  4. Sep 13, 2015 #3

    Zondrina

    User Avatar
    Homework Helper

    Just looking at this function:

    Code (Text):

    ROOT *form_root(int x)
    {
      ROOT *new_root=(ROOT *)malloc(sizeof(ROOT));
      new_root->first=new_root->middle=new_root->last=0; ********* Really look at this line.
      new_root->x=x;
      return new_root;
    }
     
    Can you see why your code is wrong? It should read like so:

    Code (Text):

    ROOT *new_root = (Insert a new root here);
    new_root->first = (Insert a new node here);
    new_root->second = (Insert a new node here);
    new_root->third = (Insert a new node here);
    new_root->x = x;
    The first, second and third fields are not integers you can set to zero. They are actually nodes with a next and y field.

    Look at your code more.
     
  5. Sep 13, 2015 #4

    Mark44

    Staff: Mentor

    The OP's first line of code uses malloc() to allocate heap memory for a new node. This is the appropriate thing to do, not "insert a new root here" as you wrote.
    Correct, they are not integers, but the OP is initializing these pointers to NULL What the OP has done is not the best way to do things, but I get what the intent is.


    This is also good advice for you, @Zondrina.

    I'm waiting for the OP to give us more information about what is wrong with the posted code.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Dynamic allocation problem with linked lists
Loading...