1. Not finding help here? Sign up for a free 30min 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!

C: Store The Content Of Linked List Into BST

  1. Nov 19, 2015 #1
    1. The problem statement, all variables and given/known data
    The following program should create singly circular linked list
    which has n arbitrary stored positive integer numbers.
    Then, create BST which has all primes from the list,
    and store them in text file in descending order.

    2. Relevant equations
    Linked list
    Binary search tree
    File handling

    3. The attempt at a solution
    Mod note: Indented code and added "=c" to code tag.
    Code (C):

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

    typedef struct list_node
    {
       int info;
       struct list_node *next;
    } NODE;

    typedef struct tree_node
    {
       NODE plist;
       struct tree_node *left,*right;
    }TREE_NODE;

    void read(NODE *plist)
    {
       printf("Positive integer: ");
       scanf("%d", &plist->info);
    }

    void insert_list_node(NODE *n_ptr,int info)
    {
       NODE *start=n_ptr;
       while(n_ptr->next != start)
          n_ptr=n_ptr->next;
       n_ptr->next=(NODE*)malloc(sizeof(NODE));
       n_ptr=n_ptr->next;
       n_ptr->info=info;
       n_ptr->next=start;
    }

    int prime(int x)
    {
       int div;
       int num_of_div=2;
       for(div=0;div<x/2;div++)
       {
          if(x % div == 0)
          num_of_div++;
       }
       if(num_of_div == 2)
          return 1;
       return 0;
    }

    TREE_NODE *form_node(NODE *plist)
    {
       TREE_NODE *new_node=(TREE_NODE*)malloc(sizeof(TREE_NODE));
       new_node->left=new_node->right=0;
       new_node->plist=*plist;
       return new_node;
    }

    TREE_NODE *add_to_tree(NODE *plist,TREE_NODE *root,int (*prime_ptr)(int))
    {
       if(root == 0)
          return form_node(plist);
       if((plist->info <= root->plist.info) && ((*prime_ptr)(plist->info) == 1))
       {
          root->left=add_to_tree(plist,root->left,prime);
          insert_list_node(plist,plist->info);
       }
       else if((plist->info > root->plist.info) && ((*prime_ptr)(plist->info) == 1))
       {
          root->right=add_to_tree(plist,root->right,prime);
          insert_list_node(plist,plist->info);
       }
       return root;
    }

    void print_tree_to_file(TREE_NODE *root,FILE *fptr)//reversed inorder traversion
    {
       if(root != 0)
       {
          print_tree_to_file(root->right,fptr);
          fprintf(fptr,"%d\n",root->plist.info);
          print_tree_to_file(root->left,fptr);
       }
    }

    int main()
    {
       TREE_NODE *root=0;
       NODE *plist;
       /*FILE *fptr="file.txt";*/
       int n,i;
       do
       {
          printf("n=");
          scanf("%d",&n);
       }
       while(n<1);
       for(i=1;i<=n;i++)
       {
          read(&plist);
          root=add_to_tree(&plist,root,&prime);
       }
       /*print_tree_to_file(root,fptr);*/
       return 0;
    }
     
    Segmentation faults:
    |96|warning: passing argument 1 of 'read' from incompatible pointer type [enabled by default]|
    |16|note: expected 'struct NODE *' but argument is of type 'struct NODE **'|
    |97|warning: passing argument 1 of 'add_to_tree' from incompatible pointer type [enabled by default]|
    |55|note: expected 'struct NODE *' but argument is of type 'struct NODE **'|
     
    Last edited by a moderator: Nov 19, 2015
  2. jcsd
  3. Nov 19, 2015 #2

    Mark44

    Staff: Mentor

    There are a number of things wrong with your code, starting with the errors shown above.
    In main(), the two lines in the for loop show &plist, but plist is already a pointer, so & is not needed. A more serious problem is that you are attempted to store values in plist -> info (in your read() function), but you haven't allocated any memory to hold what plist is supposed to point to. That is what is giving you the segmentation faults.

    The declaration NODE * plist that you have in main() merely allocates memory on the stack for a pointer (to a NODE struct), but that pointer is uninitialized, meaning that it isn't pointing to a location that is safe for you to store something in. For each NODE struct that you use, you need to allocate memory from the heap, using malloc() or other memory allocation function.
     
  4. Nov 19, 2015 #3

    rcgldr

    User Avatar
    Homework Helper

    Tree node should not need a NODE plist member, just an int info member, since a tree node will not be using the next pointer. Are the nodes in the circular list with prime numbers to be removed from the list, or left in the list as the BST is created?

    Somewhat faster prime function:

    Code (Text):

    // largest prime        < 2^??  largest prime square root
    //           2147483647 < 2^31       45337
    //           4294967291 < 2^32       65521
    //  9223372036854775783 < 2^63  3037000493
    // 18446744073709551557 < 2^64  4294967291

    int prime(int n)
    {
    int d;
        if(n <= 2)
            return 1;
        if((n & 1) == 0)
            return 0;
        for(d = 3; d <= 46337 && d * d <= n; d += 2){
            if((n % d) == 0)
                return 0;
        }
        return 1;
    }
     
     
    Last edited: Nov 19, 2015
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: C: Store The Content Of Linked List Into BST
Loading...