Dictionay - implementation

[snezic]

I'm supposed to do a dictionary impplementation using a binary tree that's shown by pointers, this is what I did:

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

typedef char elementtype[30];

typedef struct cell_tag{
        elementtype element;
        struct cell_tag *leftchild;
        struct cell_tag *rightchild;
        } celltype;
        
typedef celltype *DICTIONARY;

void MAKE_NULL(DICTIONARY *Ap){
     *Ap=NULL;
     return;
     }

int MEMBER (elementtype x, DICTIONARY A){
    if (A == NULL) return 0;
    else if (strcmp(x, A->element)==0) return 1;
    else if (strcmp(x, A->element)<0) return (MEMBER(x,A->leftchild));
    else return (MEMBER(x,A->rightchild));
}

void INSERT (elementtype x, DICTIONARY *Ap){
     if (*Ap == NULL){
             *Ap = (celltype*)malloc(sizeof(celltype));
             strcpy((*Ap)->element, x);
             (*Ap)->leftchild = (*Ap)->rightchild = NULL;
             }
     else if (strcmp(x, (*Ap)->element)<0) INSERT(x, &((*Ap)->leftchild));
     else if (strcmp(x, (*Ap)->element)>0) INSERT(x, &((*Ap)->rightchild));
     }
     
elementtype DELETE_MIN(DICTIONARY *Ap){
            celltype *temp;
            elementtype minel;
            if (((*Ap)->leftchild) == NULL){
                                   strcpy(minel, (*Ap)->element);
                                   temp = (*Ap);
                                   (*Ap) = (*Ap)->rightchild;
                                   free(temp);
                                   }
            else strcpy(minel, DELETE_MIN(&((*Ap)->leftchild)));
            return minel;
            }
            
void DELETE (elementtype x, DICTIONARY *Ap){
     celltype *temp;
     if (*Ap != NULL)
        if (strcmp(x, (*Ap)->element)<0)
           DELETE(x, &((*Ap)->leftchild));
        else if (strcmp(x, (*Ap)->element)>0)
             DELETE(x, &((*Ap)->rightchild));
        else if( ((*Ap)->leftchild==NULL) && ((*Ap)->rightchild == NULL)){
             free(*Ap);
             *Ap=NULL;
             }
        else if( (*Ap)->leftchild == NULL){
             temp=*Ap;
             *Ap=(*Ap)->rightchild;
             free(temp);
             }
        else strcpy((*Ap)->element, DELETE_MIN( &((*Ap)->rightchild)));
        }

this doesn't work, the problem is in the DELETE_MIN function, but I don't know how to fix it...Any help at all would be great...

[sean]

Moved to the C forum (previously under C++)

[Dino]

I'm supposed to do a dictionary impplementation using a binary tree that's shown by pointers, this is what I did:

. . .

this doesn't work, the problem is in the DELETE_MIN function, but I don't know how to fix it...Any help at all would be great...

Ah, the 'ol "doesn't work" problem. I think we fixed that last week.

[Salem]

So add a main() to it, which creates a very simple tree (say 1 node), then try to delete that node.
Does it work?

What about 2 nodes - or even 3 nodes?

What you need to do is create a really simple test framework around the code and then step through it all using the debugger.


> elementtype minel;
..
> return minel;
Ah, but you have
typedef char elementtype[30];

You're returning a POINTER to a local array!

[snezic]

I tested the code and it works just fine, all except the DELETE_MIN function, I also know

> elementtype minel;
..
> return minel;
Ah, but you have
typedef char elementtype[30];

You're returning a POINTER to a local array!

but I don't know what to do to fix that, any hints...

[Salem]

One way would be to make a struct

typedef struct {
    char element[30];
} elementtype;

and then change all the references in the code, say
strcpy((*Ap)->element.element, DELETE_MIN( &((*Ap)->rightchild)));

Structs are returned by value, so this should work.
But it is not the most efficient of things, so if you're doing this a lot, or your struct is much bigger, then another approach would be a good idea.

[snezic]

salem - Thank you sooo much,you saved my life...
I did what you said and now everything is working just fine, finally