linco@eng.umd.edu (Sam Lin) (07/21/90)
A friend of mine who doesn't have network access has a programming
question.
It follows below after my signature.
----------------------------------------------------------------------------
/// Sam C. Lin
/// Internet: linco@eng.umd.edu
/// /// ///|| /// /////// //////// UUCP: {ames,uunet}!eng.umd.edu!linco
/// /// /// ||/// /// /// /// USnail: 5708 Wyngate Drive
/// /// /// |/// /////// //////// Bethesda, MD 20817
/// ------------------------------------
////////// Are you wearing clean underwear? Are you wearing underwear?
-----------------------------------------------------------------------------
I am new to C++ and am having trouble with the following:
I have a set of AVL tree routines written in C and I want to
try using C++. The C routines work like:
TreeStatus Insert(Tree **Head, void *key, int (*comp)(), Tree *(*alloc)(), Tree **NewNode);
status = Insert(&Head,key,Comp,Alloc,&NewNode);
It would be nice to define a superclass `Tree' from which various data
structures ould be derived. The Comp() and Alloc() functions would be virtual.
Problem #1 is:
It would be nice to have a virtual constructor to replace the Alloc() function.
This does not appear to be permitted. (Why is that?)
Ignoring problem #1, here is my attempt:
***** Tree.h ****
#ifndef TREE_H
#define TREE_H
#ifndef NULL
#include <stdio.h>
#endif
class Tree {
private:
Tree *right, *left;
char bal;
public:
enum TreeStatus { NORMAL, KEYALRINS };
virtual int Compare(void *key) = 0;
virtual Tree *Alloc(void *key) = 0;
Tree() {right = left = NULL; bal = 0;}
TreeStatus Insert(void *key, int insdup, Tree *&newnode);
};
#endif
***** NameTree3.h ******
#ifndef NAMETREE_H
#define NAMETREE_H
#ifndef TREE_H
#include "Tree3.h"
#endif
#include <string.h>
class NameTree : public Tree {
private:
char *Name;
public:
Compare(void *key) {return(strcmp((char *)key,Name));}
Tree *Alloc(void *key) {
NameTree *NT = new NameTree;
NT->Name = new char[strlen((char *)key) + 1];
strcpy(NT->Name, (char *)key);
return(NT);
}
};
#endif
******** test.c *******
#include "Tree3.h"
#include "NameTree3.h"
main()
{
NameTree *Head = NULL, *NT;
Head->Insert("hello",0,NT);
}
***********
Problem #2:
In the C version of this code, I would start with a Tree *Head
= NULL. This represents an empty tree. Calling a virtual function
through this NULL pointer results in a segmentation fault! Any
suggestions?
Problem #3:
Insert() returns a new node as arg #3. It expects *&Tree.
Passing `NT' in the above code causes the translator to generate a
temporary variable and pass that, which doesn't work at all. I can't
think of any good solution to this. I can declare arg 3 of Insert()
as Tree ** instead of Tree *&, and then cast `NT' to Tree **.
However, this violates good OOPS design, since all clases derived from
NameTree will always have to cast back to Tree **. (Why is it that
the translator will convert NameTree * to Tree *, but not NameTree **
to Tree ** or NameTree *& to Tree *& ?)