C++

Forum

 
Dictionary-implementation

snezic (3)
I have to do a dictionary implementation, using a binary search tree that's shown by pointers. Normally I would do sth. like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
typedef struct cell_tag{
        elementtype element;
        struct cell_tag *leftchild;
        struct cell_tag *rightchild;
        } celltype;
        
typedef celltype *DICTIONARY;

void MAKE_NULL (*DICTIONARY A){
     *A=NULL;
     }

int MEMBER (elementtype x, DICTIONARY A){
    if (A == NULL) retunr 0;
    else if (x == A->element) return 1;
    else if (x < A->element) 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));
             (*Ap)->element =x;
             (*Ap)->leftchild = (*Ap)->rightchid = NULL;
             }
     else if (x < (*Ap)->element) INSERT(x, &((*Ap)->leftchild));
     else if (x > (*Ap)->element) INSERT(x, &((*Ap)->rightchild));
     }

elementtype DELETE_MIN(DICTIONARY *Ap){
            celltype *temp;
            elementtype minel;
            if (((*Ap)->leftchild) == NULL){
                                   minel = (*Ap)->element;
                                   temp = (*Ap);
                                   (*Ap) = (*Ap)->rightchild;
                                   free temp;
                                   }
            else minel=DELETE_MIN(&((*Ap)->leftchild));
            return minel;
            }

void DELETE (elementtype x, DICTIONARY *Ap){
     celltype *temp;
     if (*Ap != NULL)
        if (x < (*Ap)->element)
           DELETE(x, &((*Ap)->leftchild));
        else if (x >(*Ap)->element)
             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 (*Ap)->element=DELETE_MIN( &((*Ap)->rightchild));
        }


this would work just fine if for elementtype you would use numbers, or probably eaven chars, but I have to put strings in my dictionary and that is where my problem starts... so I defined the elementtype as char[30], I did the implementation for the functions INSERT and MEMBER, but I can't get the DELETE function to work, if anyone has any ideas please help...
this is what I did(if there are any mistakes please let me know):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
 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 (x == A->element) return 1;
    else if (x < A->element) 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 (x < (*Ap)->element) INSERT(x, &((*Ap)->leftchild));
     else if (x > (*Ap)->element) INSERT(x, &((*Ap)->rightchild));
     }
Last edited on
PanGalactic (1658)
Why not std::string instead of char[]?
snezic (3)
Because in the text of the assignment it says that I should use char[]...
PanGalactic (1658)
It looks like you are still using comparison operators for checking C string relationships. You cannot do that with strings. Instead you need to use strncmp().
moorecm (1932)
Where is it (the DELETE function)?
snezic (3)
PanGalactic - thanks, I totaly forgot about that...I will fix it...


moorecm - I didn't write it here, because I think it really made no sense... well it would probably look something like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
  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)));
        }

the probblem is in the function DELETE_MIN that I use which I can seem to get working...
Topic archived. No new replies allowed.