C: Store The Content Of Linked List Into BST

[gruba]

Homework Statement

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.

Homework Equations

Linked list
Binary search tree
File handling

The Attempt at a Solution

Mod note: Indented code and added "=c" to code tag.

#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 **'|

 

[Mark44]

Homework Statement

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.

Homework Equations

Linked list
Binary search tree
File handling

The Attempt at a Solution

Mod note: Indented code and added "=c" to code tag.

#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 **'|

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.

 

[rcgldr]

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:

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