Ndtyjky

I'm new to C programming, but what I'm trying to do is create a BST using arrays. Here is my code for the headers that I am using:

bst.h

#ifndef ASSIGNMENT4_BST_H

#define ASSIGNMENT4_BST_H



// ====== this is in bst.h

#include "data.h"

typedef struct {Node *tree_nodes; unsigned char *is_free; int size;} BStree_struct;

typedef BStree_struct* BStree;

BStree bstree_ini(int size);

void bstree_insert(BStree bst, Key *key, int data);

void bstree_traversal(BStree bst);

void bstree_free(BStree bst);



#endif //ASSIGNMENT4_BST_H

data.h

#ifndef ASSIGNMENT4_DATA_H

#define ASSIGNMENT4_DATA_H



typedef struct {char *name; int id;} Key;

typedef struct {Key *key; int data;} Node;

Key *key_construct(char *in_name, int in_id);

int key_comp(Key key1, Key key2);

void print_key(Key *key);

void print_node(Node node);



#endif //ASSIGNMENT4_DATA_H

And here is the code for my actual source files:

bst.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "bst.h"

// Input: ’size’: size of an array

// Output: a pointer of type BStree,

// i.e. a pointer to an allocated memory of BStree_struct type

// Effect: dynamically allocate memory of type BStree_struct

// allocate memory for a Node array of size+1 for member tree_nodes

// allocate memory for an unsigned char array of size+1 for member is_free

// set all entries of is_free to 1

// set member size to ’size’;



void bstree_insert_helper (BStree, Key *, int, int);



BStree bstree_ini(int size) {

    BStree bstree = (BStree*) malloc(sizeof(BStree));

    bstree->tree_nodes = (Node*) malloc(size+1 * sizeof(Node));

    bstree->is_free = (unsigned char *) malloc (size+1 * sizeof(unsigned char));

    memset (bstree->is_free, '1', size+1);

    for (int i = 0 ; i < size; i++){

//        printf("%c", bstree->is_free[i]);

    }

    return bstree;

}



// Input: ’bst’: a binary search tree

// ’key’: a pointer to Key

// ’data’: an integer

// Effect: ’data’ with ’key’ is inserted into ’bst’

// if ’key’ is already in ’bst’, do nothing

void bstree_insert(BStree bst, Key *key, int data) {

    bstree_insert_helper(bst, key, data, 1);

}



void bstree_insert_helper (BStree bst, Key *key, int data, int index){

    if (bst->is_free[index] == '1'){

        bst->tree_nodes[index].key = key;

        bst->tree_nodes[index].data = data;

        bst->is_free[index] = '0';

    } else {

        int value = key_comp(*key, *bst->tree_nodes[index].key);

        if (value < 0){

            int newIndex = 2*index;

            if (bst->is_free[newIndex] == '1'){

                bst->tree_nodes[newIndex].key = key;

                bst->tree_nodes[newIndex].data = data;

                bst->is_free[newIndex] = '0';

            } else {

                bstree_insert_helper(bst, key, data, newIndex);

            }

        } else if (value > 0){

            int newIndex = 2*index+1;

            if (bst->is_free[newIndex] == '1'){

                bst->tree_nodes[newIndex].key = key;

                bst->tree_nodes[newIndex].data = data;

                bst->is_free[newIndex] = '0';

            } else {

                bstree_insert_helper(bst, key, data, newIndex);

            }

        } else {

            puts("Key already exists... Aborting");

        }

    }

}



int main (){

    BStree bsTree = bstree_ini(10);

    bstree_insert_helper(bsTree, key_construct("Ilya", 1), 11, 1);

    bstree_insert_helper(bsTree, key_construct("Covin", 2), 12, 1);

    bstree_insert_helper(bsTree, key_construct("adolf", 3), 13, 1);

    bstree_insert_helper(bsTree, key_construct("henlo", 4), 14, 1);

    print_node(bsTree->tree_nodes[1]);

    return 0;

}

data.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "data.h"





// Input: ’in_name’: a string ends with ’’

// ’in_id’: an integer

// Output: a pointer of type pointer to Key,

// pointing to an allocated memory containing a Key

// Effect: dynamically allocate memory to hold a Key

// set Key’s id to be in_id

// dynamically allocate memory for the Key’s name

// so that name will contain what is in ’in_name’.

// Note: may use strdup()

Key *key_construct(char *in_name, int in_id) {

    Key *key = (Key*) malloc(sizeof(Key));

    key->name = strdup(in_name);

    key->id = in_id;

    return key;

}

// Input: ’key1’ and ’key2’ are two Keys

// Output: if return value < 0, then key1 < key2,

// if return value = 0, then key1 = key2,

// if return value > 0, then key1 > key2,

// Note: use strcmp() to compare key1.name and key2.name

// if key1.name = key2.name, then compare key1.id with key2.id

int key_comp(Key key1, Key key2) {

    int value = strcmp(key1.name, key2.name);

    if (value < 0 || value > 0){

        return value;

    } else {

        if (key1.id < key2.id){

            return -1;

        }else if (key1.id > key2.id){

            return 1;

        } else {

            return 0;

        }

    }

}



// Input: ’key’: a pointer to Key

// Effect: ( key->name key->id ) is printed

void print_key(Key *key) {

    char *name = key->name;

    int id = key->id;



    printf("%s, %i", name, id);

}



// Input: ’node’: a node

// Effect: node.key is printed and then the node.data is printed

void print_node(Node node) {

    printf("%s, %d n", node.key->name, node.data);

}

The issue is that when I run the print_node function in main in bst.c, I expect it to print the key.name and data for indices 1,2,3, and 7 in the array properly. However, the key.name for indices 1 and 3 are not printed properly. Instead, I get a bunch of gibberish that looks something like this - 0+@]�, 11 if I used print_node(bsTree->tree_nodes[1]). I have a feeling it has something to do with me incorrectly allocating memory for the keys in data.c but I cannot figure out exactly what I'm doing wrong.

I believe the error is here:

(size+1 * sizeof(Node))

inside BStree bstree_ini(int size):

bstree->tree_nodes = (Node*) malloc(size+1 * sizeof(Node));

bstree->is_free = (unsigned char *) malloc (size+1 * sizeof(unsigned char));

memset (bstree->is_free, '1', size+1);

* is executed first, then + (like in normal math), see operator precedence, the expression:

size+1 * sizeof(Node)

is equal to:

size + (1 * sizeof(Node))

which is not what you wanted!

Use proper braces:

malloc((size + 1) * sizeof(Node));

or use calloc:

calloc(sizeof(Node), size + 1);

Some friendly notices:

• Nice code!


• Please don't cast the result of malloc.


• 
  bstree->is_free would be clearer if it would be bool type. And it would be clearer (to me) if it would be bstree->is_used as I can expect it is initialized to zero on a new object, it would be also easy to clear it memset(bstree->is_used, 0, ...). You just assign '1' and '0' to it, I find boolean to be clearer for this indent, bstree->us_used[obj_num] = true; In the future you may go for a bit-container.