Beginner trying to use BST please help 
Author Message
 Beginner trying to use BST please help

I am trying to use a dictionary I created but really don't know if I am on
the right track.
Let me include the code I have got so far - (the first bit [usedict.c] is
the bit I am not sure about) :

Quote:
>From the file usedict.c

/*attempting to use the readict bst */
/*creation date: 5/23/99 1:15:54 PM*/

#include <stdio.h>
#include "utilio.h"
#include  "readict.h"

int main()
{
  readerdict RD;
  reader  readers;
  name    middle;
  char    str[20];
  int     comp;

  strcpy(str,"Henry");
  *readers = readict_create();
  readict_insert (RD, comp, middle, str);

Quote:
}

----------------------------------------------------

Quote:
>From the file readict.c

/*Name:             reader_dict.c*/
/*Function:         To implement the reader_dict ADT*/
/*Creation Date:    5/23/99 12:36:00 PM*/

/* ************************** Includes **************** */
#include "readict.h"
#include "dict_bst.i"
-----------------------------------------------------------------

Quote:
>From the file readict.h

/*Name: readict.h*/
/*Task: Specify the Reader_Dict ADT*/
/*Creation Date: 5/23/99 12:25:45 PM*/

#ifndef HDR_READERDICT
#define HDR_READERDICT

#define   Dict       readerdict
#define   DictKey    name
#define   DictItem   reader

typedef   char       *name;
typedef   char       *reader;

#include  "dict_bst.h"

#endif
-------------------------------------------------

Quote:
>From the file dict_bst.h (a template)

 /* Template for the Dict[ionary] ADT family,
 * representing a dictionary of items of any type.
 * This file should be included in another .h that defines a specific ADT.
 * To define a type FooDict with base type Foo (a single typename)
 * and key type Bar, create foodict.h with this structure:
 * #define  Dict  FooDict
 * #define  DictKey Bar # must be a single typename
 * #define  DictItem Foo # must be a single typename
 *     if necessary, provide typedefs for types Foo and Bar
 * #include  "dict_bst.h"
 */

#include "adt.h"

#if !defined(Dict) || !defined(DictKey) || !defined(DictItem)
#error Dict, DictKey and DictItem must be defined before #including
dict_bst.h
#endif

/* The following defines the specific dict type.
 * All members of the Dict family are unbalanced Binary Search Trees
 * with standard field names */
#define DictObj _concat(Dict, Obj)
typedef struct DictObj   *Dict;
struct DictObj {
 DictKey  key; /* Field on which the BST is ordered */
 DictItem item; /* Associated data */
 Dict left, right; /* keys(left) < key < keys(right) */

Quote:
};

/* These map the general Dict_func names into ADT-specific names */
#define Dict_Create _concat(Dict, _Create)
#define Dict_Destroy _concat(Dict, _Destroy)
#define Dict_Insert _concat(Dict, _Insert)
#define Dict_Delete _concat(Dict, _Delete)
#define Dict_Retrieve _concat(Dict, _Retrieve)
#define Dict_Traverse _concat(Dict, _Traverse)

/* Types of the function argument passed to Insert, Delete and Retrieve */
#define KeyComparator _concat(Dict, KeyComparator)
typedef int (*KeyComparator) (DictKey key1, DictKey key2);
/* A function of type KeyComparator returns less than zero if key1 < key2,
 * zero if key1 = key2 and greater than zero if key1 > key2
 */

/* Types of the function argument passed to Traverse */
#define ItemProcessor _concat(Dict, ItemProcessor)
typedef void (*ItemProcessor) (Generic handle, DictKey key, DictItem value);

/* Dict operations -- Macros. These are common to all Dict family members */
#define Dict_IsEmpty(dict) ((dict) == NULL)
#define Dict_NonEmpty(dict) Assert(! Dict_IsEmpty(dict), \
    "attempt to access contents of an empty dict")

/* Dict operations -- functions */
/* Notation:
 * IsDict(T)  T is a binary search tree ordered on key
 * keys(T)  the set of keys stired in the nodes of T
 * item(T,k) the item associated with k stored in T
 *   (undefined if k notin keys(T))
 * S + { k } set formed by including k in the set S
 * S - { k } set formed by excluding k from the set S
 */

Dict Dict_Create(void);
  /* Post: IsEmpty(return_value)
   */

void Dict_Destroy(Dict *dictRef);
  /* Post: IsEmpty(*dictRef') and all space used by *dictRef reclaimed
   */

 Bool Dict_Insert(Dict *dictRef, KeyComparator comp, DictKey k, DictItem
*valueRef);
  /* Pre: IsDict(*dictRef)
   * Post: return_value = k in keys(*dictRef)
   *  and IsDict(*dictRef')
   *  and keys(*dictRef') = keys(*dictRef) + { k }
   *  and item(*dictRef', key) = *valueRef
   *  and k in keys(*dictRef) => item(*dictRef, key) = *valueRef'
   */

 Bool Dict_Delete(Dict *dictRef, KeyComparator comp, DictKey k, DictItem
*valueRef);
  /* Pre: IsDict(*dictRef)
   * Post: return_value = k in keys(*dictRef)
   *  and IsDict(*dictRef')
   *  and keys(*dictRef') = keys(*dictRef) - { k }
   *  and k in keys(*dictRef) => item(*dictRef, key) = *valueRef'
   */

Bool Dict_Retrieve(Dict dict, KeyComparator comp, DictKey k, DictItem
*valueRef);
  /* Pre: IsDict(dict)
   * Post: return_value = k in keys(dict)
   *  and (k in keys(dict)) => *valueRef = item(dict,k)
   */

void Dict_Traverse(Dict dict, Generic handle, ItemProcessor func);
  /* Post: for each key k in dict in order
   *   func(handle, k, item(dict,k)) called
   */

/* Auxiliary operation, available only with BST implementation */

#ifndef BST_SHOW_TYPES
#define BST_SHOW_TYPES
typedef enum { IS_ROOT, IS_LEFT_SUBTREE, IS_RIGHT_SUBTREE } Orientation;
#define OrientChar(c) (("*\\/")[c])  /* Corresponding display codes */
typedef struct {
 size_t depth;
 Orientation orient;

Quote:
} NodePosition;  /* Type of structure passed to func below */

#endif

#define Dict_ShowTree _concat(Dict, _ShowTree)
void Dict_ShowTree(Dict dict, ItemProcessor func);
  /* Post: for each key k in dict in order
   *   func(np, k, item(dict,k)) called
   *  where (*np) is the position of the node containing k
   */
-------------------------------------------------------

Quote:
>From the File dict_bst.i (template)

/* Template for the Dict[ionary] ADT family,
 * representing a dictionary of items of any type.
 * This file should be included in another .c that implements a specific
ADT,
 * preceded by the corresponding .h file.
 * For example, foodict.i should contain just these two lines:
 * #include "foodict.h"
 * #include "dict_bst.i"
 */
#if !defined(Dict) || !defined(DictKey) || !defined(DictItem)
#error an ADT header file based on dict_bst.h must precede dict_bst.i
#endif

/* Dict operations -- functions */
/* Notation:
 * IsDict(T)  T is a n AVL tree ordered on key
 * keys(T)  the set of keys stored in the nodes of T
 * item(T,k) the item associated with k stored in T
 *   (undefined if k notin keys(T))
 * S + { k } set formed by including k in the set S
 * S - { k } set formed by excluding k from the set S
 */

Dict Dict_Create(void)
  /* Post: Dict_IsEmpty(return_value)
   */
{
 return NULL;

Quote:
}

static void clear(Dict d)
{
 if (d != NULL) {
     clear(d->left);
     clear(d->right);
     Dispose(d);
 }
Quote:
}

void Dict_Destroy(Dict *dictRef)
  /* Post: Dict_IsEmpty(*dictRef') and all space used by *dictRef reclaimed
   */
{
 Defined(dictRef);
 clear(*dictRef);
 *dictRef = NULL;

Quote:
}

Bool Dict_Insert(Dict *dictRef, KeyComparator comp, DictKey k, DictItem
*valueRef)
  /* Pre: IsDict(*dictRef)
   * Post: return_value = k in keys(*dictRef)
   *  and IsDict(*dictRef')
   *  and keys(*dictRef') = keys(*dictRef) + { k }
   *  and item(*dictRef', key) = *valueRef
   *  and k in keys(*dictRef) => item(*dictRef, key) = *valueRef'
   */
{
 Dict t = *dictRef;
 int match;
 DictItem oldValue; /* Used in exchange of old and new items */

 Defined(dictRef);
 t = *dictRef; /* Avoid repeated (*dictRef) references */
 if (Dict_IsEmpty(t)) {
     New(t);
     t->left = t->right = NULL;
     t->key =k;
     t->item = *valueRef;
     *dictRef = t;
     return FALSE; /* k did not previously exist */
 }
 else if ((match = comp(k, t->key)) < 0)
     return Dict_Insert(&t->left, comp, k, valueRef);
 else if (match > 0)
     return Dict_Insert(&t->right, comp, k, valueRef);
 else { /* match == 0: Key already exists, update item */
     oldValue = t->item;  t->item = *valueRef;  *valueRef = oldValue;
     return TRUE; /* k already exists */
 }

Quote:
}

#ifndef FANCY_DELETE
static void delete_largest(Dict *p, DictKey *kp, DictItem *ip)
{
 Dict t = *p;

 if (t->right != NULL)
     delete_largest(&t->right, kp, ip);
 else {
     *kp = t->key;  *ip = t->item;
     *p = t->left;
     Dispose(t);
 }

Quote:
}

#endif

#ifdef FANCY_DELETE
static void delete_nearest(Dict p, DictKey *kp, DictItem *ip)
{
 Dict pleft, pright,  /* Cursors for each subtree of p */
  leftParent, rightParent; /* Their parents */
 size_t leftDepth, rightDepth; /* Depths of the cursor nodes */
 Dict *delp;   /* Address of reference to be deleted */
 Dict q;   /* Temporary reference for disposal */

 Assert(!Dict_IsEmpty(p), "empty tree is delete_nearest");
 leftParent = rightParent = p;
 leftDepth = rightDepth = 0;
 for (pleft = p->left; pleft->right != NULL; pleft = pleft->right) {
     rightParent = pleft->right;
     leftDepth++;
 }
 for (pright = p->right; pright->left != NULL; pright = pright->left) {
     leftParent = pright->left;
     rightDepth++;
 }
 /* parent is the parent node of the node to be deleted */
 delp = leftDepth >= rightDepth? &leftParent->right : &rightParent->left;
 q = *delp;
 *kp = q->key;  *ip = q->item;
 *delp = q->left != NULL? q->left : q->right;
 Dispose(q);

Quote:
}

#endif

 Bool Dict_Delete(Dict *dictRef, KeyComparator comp, DictKey k, DictItem
*valueRef)
  /* Pre: IsDict(*dictRef)
   * Post: return_value = k in keys(*dictRef)
   *  and IsDict(*dictRef')
   *  and keys(*dictRef') = keys(*dictRef) - { k }
   *  and k in keys(*dictRef) => item(*dictRef, key) = *valueRef'
   */
{
 Dict t;
 int match;

 Defined(dictRef);
 t = *dictRef;
 if (! Dict_IsEmpty(t)) {
     if ((match = comp(k, t->key)) < 0)
  return Dict_Delete(&t->left, comp, k, valueRef);
     else if (match > 0)
  return Dict_Delete(&t->right, comp, k, valueRef);
     else { /* Key found: delete node */
  *valueRef = t->item;
  if (Dict_IsEmpty(t->left)) {
      *dictRef = t->right;
      Dispose(t);
  }
  else if (Dict_IsEmpty(t->right)) {
      *dictRef = t->left;
      Dispose(t);
  }
  else /* t has two non-empty subtrees: replace key and item
    * from the node with the next lexically smaller
    * or larger key */
#ifdef FANCY_DELETE
       delete_nearest(t, &t->key, &t->item);
#else
       delete_largest(&t->left, &t->key, &t->item);
#endif
  return TRUE;
     }
 }
 return FALSE;

Quote:
}

Bool Dict_Retrieve(Dict dict, KeyComparator comp, DictKey k, DictItem
*valueRef)
  /* Pre: IsDict(dict)
   * Post: return_value = k in keys(dict)
   *  and (k in keys(dict)) => *valueRef = item(dict,k)
   */
{
 Dict p = dict;
 int match;

 while (! Dict_IsEmpty(p))
     if ((match = comp(k, p->key)) == 0) {
  *valueRef = p->item;
  return TRUE;
     }
     else
  p = match < 0? p->left : p->right;
 return FALSE;

Quote:
}

void Dict_Traverse(Dict dict, Generic handle, ItemProcessor func)
  /* Post: for each key k in dict in order
   *   func(handle, k, item(dict,k)) called
   */
{
 if (! Dict_IsEmpty(dict)) {
     Dict_Traverse(dict->left, handle, func);
     func(handle, dict->key, dict->item);
     Dict_Traverse(dict->right, handle, func);
 }

Quote:
}

/* Auxiliary Operation */

static void show(Dict dict, ItemProcessor func, size_t depth, Orientation
orient)
{
 NodePosition np;

 if (! Dict_IsEmpty(dict)) {
     show(dict->right, func, depth+1, IS_RIGHT_SUBTREE);
     np.depth = depth;  np.orient = orient;
     func((Generic) &np, dict->key, dict->item);
     show(dict->left, func, depth+1, IS_LEFT_SUBTREE);
 }

Quote:
}

void Dict_ShowTree(Dict dict, ItemProcessor func)
{
 show(dict, func, 0, IS_ROOT);

Quote:
}

--



Fri, 09 Nov 2001 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Beginner trying to use BST please help

2. Please help!!!!Please help!!!!Please help!!!!Please help!!!!Please help!!!!Please help!!!!Please help!!!!

3. BST using Strings as the data type.

4. Acess denied in ASP.NET when it tries to import dll- please help

5. Clarification: Trying to master binary trees - please help.

6. Trying to master binary trees - please help.

7. 2nd try - ShellExecute - PLEASE HELP

8. Please help!!!!Please help!!!!Please help!!!!

9. CEdit::CharFromPos -- trying to write a bugfix, please help (having problems with tabs)

10. try...catch newbie, please help

11. C problem for beginner, help please

12. Please help this beginner.

 

 
Powered by phpBB® Forum Software