Solved

Question For Nietod - Need help on routines involving trees & lists (pertains to 'C')

Posted on 2000-04-03
31
281 Views
Last Modified: 2010-04-10
I need help coding basic routines for trees & lists such as adding deleting...


ANSWER:


/*********************  Function Declarations/Definitions *****************/


      /* -------------------------- CheckLength() --------------------------
      *      Descrip:      This procdure evalutes the length of a string comparing it
                              to the value provided in the second parameter.  

      *      Input:            The first parameter is a character pointer to the string
                              needing evaluated.  The second parameter is an integer
                              specifying the length that the string should be.                              
                              
      *      Returns:    Returns an integer indicating success or failure
                              '1' = true, '0' = false

      *      Requires:      A parameter having a NUL terminated string

      *       Precond:      -

      *       Postcond:   -
      */      

      int CheckLength(char *charptr, int fieldlength)
      {
            int check = strlen(charptr);      // obtain string length

            if (check <= fieldlength)
                  return 1;            
            else
                  return 0;            
      }



      /*--------------------------   CountFields()   ---------------------------

      * Descrip      :      This procedure counts the number of fields in the character
                              string of the input parameter.  A field is defined as characters
                              located between delimeters.  The delimeter is provided by the
                              caller. The fields are counted by using strtok() which traverses
                              the line      until no delimeters remain.


      * Input            :      The 1st parameter specifies the NUL terminated string which is to
                              be      evaluated.  The second parameter specifies the delimeter.

      * Returns      :      Returns an integer


      * Requires      :      A NUL terminated string in the first parameter

      * Precond      :      The string in parameter one should be preserved or copied before
                              using this function.

      * Postcond      :      The exact string passed to this function should not be used by
                              other functions.  The use of strtok() may corrupt the data
                              contained in the string.  Subsequent use of the string may
                              produce inaccurate results.
      */


      int CountFields(char *FileLine, char * delim)
      {
            int tokencount = 0;                  // used as a counter to test lines in the file
            char *token;                        // used to extract fields from the file

                  token = strtok(FileLine, delim);      // get first field of data
                  // while there are tokens to get
                  while(token != NULL){
                        tokencount++;                        // increase counter
                        token = strtok(0, delim);         // get next field of data

                  }
            return tokencount;                                    // return token count
      }


      /* -------------------------- RemoveSpace() --------------------------

      *      Descrip:      This procdure evalutes a string for leading spaces and
                              returns a pointer to the first 'non-space' character.

      *      Input:            A character pointer to the string needing evaluated
                              
      *      Returns:    A pointer to the string which identifies a non-space
                              character

      *      Requires:      A parameter having a NUL terminated string

      *       Precond:      -

      *       Postcond:   -
      */      

      char * RemoveSpace(char *charptr)
      {
            while (*charptr == ' ')
                  ++charptr;

            return charptr;
            
      }

      /******************************   Write To Log  ****************************
      
      * Descrip      : This procedure writes the message of the input parameter to a
                          log.  
                
      * Input            : Takes a character pointer to the string which needs written

      * Returns      : -
         
      * Output      : Prints a message to the screen if the file stream cannot be opened

      * Requires      : The parameter must be a NUL terminated string.
      
      * Precond      : -

      * Postcond      : -
      */


      void WriteToLog(char* Message)
      {                              
            FILE *outputFile;                  // output file pointer
            char fname[100];                  // stores dirpath plus file name
            char dirpath[_MAX_PATH];      // stores working directory path

      
            // copy owner input file to 'fname' variable
            strcpy(fname, "\\report_out.txt");

            /* Get the current working directory: */
            if( _getcwd( dirpath, _MAX_PATH ) == NULL )
                  perror( "_getcwd error" );
            else
                  strcat(dirpath, fname);

            if ((outputFile = fopen(dirpath,"a")) == NULL){
                  // alert the user that the file could not be written to
                  printf("Unable to write the following message:\n");
                  printf("'%s'\n", Message);
                  printf("to file '%s'\n", dirpath);
                  return;
            }

               else
                  fprintf(outputFile, "'%s'\n", Message);
                              
            fclose(outputFile);
            return;
      }



      // ************************* List Procedures ***************************


      /*      -------------------------  AddListNode()  --------------------------

      * Descrip:      This procedure stores the data specified by the 2nd parameter
                        to the start of the list specified by the first parameter.
                        The 2nd parameter should be a pointer to a dynamically
                        allocated block of memory.  The list will store a pointer to
                        this memory so it can be retrieved at a later time.  When the
                        list entry added by this procedure is later deleted from the
                        list, this block of memory will be deleted.

      * Input      :      The first parameter is a pointer to a list structure that
                        defines the linked list to which the specified data should be
                        added.

                        The second parameter is a pointer to a dynamically allocated
                        block of memory.  The ListNode created by this function will
                        store the pointer to this memory at the start of the list.
                        The list will "own" this memory in the sense that it will
                        preserve the memory until this item is removed from the list,
                        then it will delete the memory.

      * Returns:      This procedure returns a ListNode pointer that refers to the
                        item just added.  This pointer can be passed as a parameter
                        to several other list procedures in order to identify the
                        particular item added to the list.  If no memory is available
                        on the heap for the new ListNode, the program is terminated.

      * Requires:      This procedure requires that the specified list structure
                        defines a valid linked list.  The second parameter must
                        specify a pointer to a block of dynamically allocated memory
                        that the list may assume "ownership" for.  Since this
                        procedure allocates memory to store the the specified data,
                        sufficient memory must be available on the heap.

      * Precond:      The list structure of the first parameter must be initialized
                        as a valid list.  The pointer of the second parameter must
                        be void in order to utilize the linked list as a generic
                        container.  The void pointer should be initialized as a valid
                        data structure for this program (owner, dealer, offender)

      * Postcond:      The linked list specified by the first parameter is altered
                        to specify a new first item in the list.  The program's heap
                        space is diminished by the amount required to store this new
                        item in the list.
      */

      struct ListNode *AddListNode(struct List *list, void *DataPointer)
      {
            // create a ListNode pointer
            struct ListNode *p;

            // assign memory to the ListNode pointer
            p = (struct ListNode*) malloc(sizeof(struct ListNode));

            // if memory was not assigned to p
            if(!p){
                  // alert the user of program termination
                  printf("Program terminated, no memory available for list struct!\n");
                  // terminated program - no memory
                  exit(0);
            }

            // store the data pointer in p's 'RecordPtr' member
            p->RecordPtr = DataPointer;

            // place p at the head
            p->next = list->head;
            // set previous pointer
            p->prev = NULL;

            // if the list head is not NULL
            if(list->head != NULL)
                  // set the head's previous pointer
                  list->head->prev = p;
                  // else if the head is NULL
            else
                  // assign the new node also as the tail
                  list->tail = p;
            // in any case, assign p as the new list head
            list->head = p;

            // return the pointer p (head)
            return p;
      }

      /*--------------------------  DeleteList()  -------------------------------
      * Descrip:      This procedure traverses the specified list and deletes all
                        items in the list  When this procedure returns, the list
                        structure will specify a valid, empty linked list.

      *      Input:      The "List" parameter is a pointer to a list structure that
                        defines the linked list whose stored data is to be deleted.
                        When the procedure returns the linked list will be empty.
                        The list structure will indicate that the list is empty, so
                        it can safely be used in other list operations like adding
                        new items to the list.

      * Returns      : -

      * Requires:      The linked list specified by the parameter be a valid
                        linked list, this means that the nodes are all dynamically
                        allocated and properly linked to each other and that the list
                        structure points to the terminal nodes.  Each node in the
                        linked list must have a pointer to a dynamically allocated
                        DB record structure to be deleted by the procedure.

      * Precond:      The list parameter points to a linked list structure
                        specifying a list with 0 or more nodes.

      * Postcond:      When the procedure returns, the DB records stored by the
                        linked list will be deleted.  All of the resources used by
                        the linked list to store the records, i.e. the dynamnically
                        allocated nodes, will also be deleted.  The list structure
                        will be set to indicate a valid empty list.
      */

      void DeleteList(struct List *list)
      {
            // create a pointer to the ListNode head
            struct ListNode *CurPtr = list->head;
            // ListNode pointer used to hold the value of CurPtr
            struct ListNode *temp = NULL;

            while(CurPtr != NULL){
                  // store the pointer of CurPtr
                  temp = CurPtr;
                  // advance CurPtr to next ListNode
                  CurPtr = CurPtr->next;
                  // delete the memory block held by the ListNode
                  free(temp->RecordPtr);
                  // delete current ListNode
                  free(temp);
            }
            list->head = NULL;
            list->tail = NULL;
            return;
      }

      /*-------------------------   DeleteListNode()  ---------------------------

      * Descrip:      This procedure deletes a specified item from a specified
                        linked list.  The other items in the list, if any, remain in
                        the list in their same order.  The procedure will delete the
                        memory block that is associated with this list item, that is,
                        it will delete the memomry pointed to by the ListNode's
                        'RecordPtr' member.

      * Input:      The first parameter is a pointer to a list structure defining
                        the linked list from which the item is to be deleted.

                        The second parameter is a pointer to an index node that
                        provides access to the list item needing deleted.  This
                        pointer should be obtained from a previous call to one of the
                        index procedures.

      * Returns:      -

      * Requires:      The list pointed to by the 1st parameter must be a valid
                        linked list.  The node pointer of the 2nd parameter must refer
                        to an item that is currently stored in the specified list.
                        (It may not be a pointer that refers to an item in a different
                        list and it may not be a pointer to an item that was
                        previously removed from the list.)

      * Precond:  The specified node pointer refers to an item stored in the
                        specified linked list.  The node pointer refers (indirectly)
                        to a block of dynamically allocated data that was stored in
                        the ListNode when the ListNode was added to the list.

      * Postcond:      The list will be altered to indicate that the specified item
                        is no longer stored in the list.  The other items, if any,
                        will remain in the list in their same order.  The item refered
                        to by the node pointer will be deleted, so the node pointer
                        is now invalid and thus may not be used in other list
                        procedure calls.  The block of dynamically allocated data
                        that was stored by the deleted item will also be deleted and
                        other pointers to this block of memory, if any, will now be
                        invalid.

      */
      void DeleteListNode(struct List *list, struct ListNode *NodPtr)
      {
      
            // if NodPtr points to a next node
            if(NodPtr->next)
                  // set the next node's previous pointer
                  NodPtr->next->prev = NodPtr->prev;
            // NodPtr must be the tail
            else
                  // assign new list tail
                  list->tail = NodPtr->prev;

            // if NodPtr points to a previous node
            if(NodPtr->prev)
                  // set the previous node's next pointer
                  NodPtr->prev->next = NodPtr->next;
            // NodPtr must be the head
            else
                  // assign new list head
                  list->head = NodPtr->next;

            // delete the node of parameter 2
            free(NodPtr->RecordPtr);
            free(NodPtr);

            return;
      }


      /*      -------------------------  GetFirstListNode() ---------------------------

      * Descrip:      This procedure returns a node pointer that refers to the
                        first item in the linked list.  This pointer may be passed
                        to many of the other linked list procedures in order to
                        specify this item to those procedures.  The list is not
                        affected by this procedure.

      * Input:      The parameter is a pointer to a list structure defining
                        the linked list whose first item is to be returned.

      * Returns:  A Listnode pointer that may be used to refer to the first item
                        in the linked list.  A NULL pointer is returned if the list
                        is empty.

      * Requires: The specified list structure must define a valid linked list.

      * Precond:  N/A

      * Postcond:      Nothing will be altered by this procedure.
      */


      struct ListNode *GetFirstListNode(const struct List *list)
      {
            // return head ListNode
            return list->head;

      }

      /*      ------------------------- GetLastListNode() -----------------------------

      * Descrip:      This procedure returns a node pointer that refers to the
                        last item in the linked list.  This pointer may be passed
                        to many of the other linked list procedures in order to
                        specify this item to those procedures.  The list is not
                        affected by this procedure.

      * Input:    The parameter is a pointer to a list structure defining
                        the linked list whose last item is to be returned.

      * Returns:  A node pointer that may be used to refer to the last item
                        in the linked list.  A NULL pointer is returned if the list
                        is empty.

      * Requires:  The specified list structure must define a valid linked list.

      * Precond:  N/A

      * Postcond: Nothing will be altered by this procedure.
      */

       struct ListNode *GetLastListItem(const struct List *list)
       {
            // return tail ListNode
            return list->tail;

       }

      /*------------------------  GetNextListNode() -------------------------------

      * Descrip:      This procedure returns a ListNode pointer that refers to the
                        node which comes after the node specified in the input
                        parameter.  The node pointer returned may be passed to many
                        of the other linked list procedures in order to access the
                        next node for those procedures.  The list is not affected by
                        this procedure.

      * Input:      The parameter is a pointer to a list node that refers to the
                        item whose next item is to be returned.

      * Returns:  A node pointer that may be used to refer to the next item
                        in the linked list.  A NULL pointer is returned if there is
                        no next item in the list, that is, if the item specified in
                        the parameters was the last item in the list.

      * Requires: The specified node pointer must refer to a node in a valid
                        linked list.

      * Precond:  N/A

      * Postcond: Nothing will be altered by this procedure.
      */

      struct ListNode *GetNextListNode(const struct ListNode *listNode)
      {
            return listNode->next;
      }

  /*------------------------  GetPreviousListNode() ----------------------------

      * Descrip:      This procedure returns a ListNode pointer that refers to the
                        node which comes before the node specified in the input
                        parameter.  The node pointer returned may be passed to many
                        of the other linked list procedures in order to access the
                        next node for those procedures.  The list is not affected by
                        this procedure.

      * Input:    The parameter is a pointer to a list node that refers to the
                        item whose previous item is to be returned.

      * Returns:  A node pointer that may be used to refer to the previous item
                        in the linked list.  A NULL pointer is returned if there is
                        no previous item in the list, that is, if the item specified
                        in the parameters was the first item in the list.

      * Requires: The specified node pointer must refer to a node in a valid
                        linked list.

      * Precond:  N/A

      * Postcond: Nothing will be altered by this procedure.
      */

      struct ListNode *GetPreviousListNode(const struct ListNode *listNode)
      {
                  return listNode->prev;
      }

      
       /*--------------------------   InitializeList()   ---------------------------
       *      Descrip:      This procedure initializes a linked list structure so that it
                              defines a valid empty list, that is, a linked list with no
                              items stored in it.

       *      Input:
                              The parameter is a pointer to the list structure
                              that is to be initialized

       *      Returns:    N/A

       *      Requires:      N/A

       *  Precond:    N/A

       *  Postcond:      The specified list structure will be altered so that it
                              specifies a valid empty list.

      */
       void InitializeList(struct List *list)
       {
            list->head = NULL;
            list->tail = NULL;
            return;
       }


      // ************************* Index Procedures ***************************


      /*---------------------------  AddIndexNode()  --------------------------

      * Descrip:      This function tries to add the specified index key and the
                        associated ListNode pointer into the specified index.  If
                        the specified key is not already in the index, it is added to
                        the index and the specified data pointer is stored with it,
                        then the procedure returns true, indicating no error occured.
                        If the specified key is already in the index, the procedure
                        returns false to indicate an error occured.  If no memory is
                        available to create the IndexNode, the program is terminated.

      * Input:      The first parameter is a pointer to the index structure
                        defining the index that the key is supposed to be added to.

                        The second parameter is a pointer to a NUL terminated string
                        specifying the key to be added to the index.  This string
                        may not be longer than MaxKeyLen characters long.  The
                        procedure will store a copy of the specified string in the
                        index, so the caller's copy does not need to be preserved
                        after the procedure returns with the associated key.

                        The third parameter is  a 'ListNode' pointer which is stored
                        with the associated key.  The procedure will store this
                        pointer in the index.  So that it can be retreived by other
                        index operations in order to access the data.

      * Returns:      This procedure returns an integer value that indicates if the
                        specified key was added to the index.  The procedure returns
                        false if the specified key was not added to the index, or if
                        the 'KeyValue' parameter was too long.

      * Requires:      The index structure specified in the first parameter must
                        define a valid index and the key specified in the second
                        paremaeter must specify a NUL termianted string that is not
                        longer than MaxKeyLen charaters long.  Otherwise, the procedure
                        returns 0 (false).  Sufficient heap memory must be available to
                        store the key and associated ListNode.


      * Precond:      The index parameter must point to an index which has been initialized
                        by the 'IntializeIndex()' function.  The listNode parameter must
                        point to a valid/created ListNode.

      * Postcond:      The index will be altered to store the specified key and the
                        associated data pointer, if the key wasn't already in the
                        index.  The program's heap      space is diminished by the amount
                        required to store this new item in the index.
      */

      int AddIndexNode(struct Index *index, char *KeyValue, struct ListNode *listNode)
      {

            int KeyDif;                                    // holds value of each 'Key' comparison
            struct IndexNode *CurPtr;            // used when traversing the tree
            struct IndexNode *NewIndexNode;      // used as the new tree node to be inserted
            Boolean Done = FALSE;                  // used to terminate while loop

            // allocate memory for IndexNode
            NewIndexNode = (struct IndexNode*) malloc(sizeof(struct IndexNode));

            // if no memory was available to create the new node
            if(!NewIndexNode){
                  // alert the user of program termination
                  printf("Program terminated, no memory available for index struct!\n");
                  // terminate program
                  exit(0);
            }

            // copy the incoming key to the new index member 'key' member
            strcpy(NewIndexNode->Key, KeyValue);
            // copy the incoming node pointer to the new index member 'NodePtr'
            NewIndexNode->NodePtr = listNode;
            // initialize left & right node pointers
            NewIndexNode->LeftPtr = NULL;
            NewIndexNode->RightPtr = NULL;

            // node pointer for traversing
            CurPtr = index->root;

            // if index is empty
            if (CurPtr == NULL){
                  // assign new node as the tree root
                  index->root = NewIndexNode;
                  return 1;
            }

            // while CurPtr isn't NULL, search for node placement
            while(CurPtr && !Done){

                  // make comparison of IndexNode's Key member
                  KeyDif = strcmp(KeyValue, CurPtr->Key);

                  // if key value falls after CurPtr's key
                  if (KeyDif > 0){
                        // if the tree continues to the right.
                        if (CurPtr->RightPtr)
                              // continue searching to the right.
                              CurPtr = CurPtr->RightPtr;
                        // othewise if tree is done here.
                        else{
                              // Add a node to the right.
                              CurPtr->RightPtr = NewIndexNode;
                              Done = TRUE;
                        }
                  }
                  // otherwise if key is before CurPtr->Key
                  else{
                        // If the tree continues to the left.
                        if (CurPtr->LeftPtr)
                              // continue searching to the left.
                              CurPtr = CurPtr->LeftPtr;
                        // othewise if tree is done here.
                        else{
                              // Add a node to the left.
                              CurPtr->LeftPtr = NewIndexNode;
                              // set loop condition to done
                              Done = TRUE;
                        }
                  }
            } // end of while loop
            return 1; // NewIndexNode was inserted
      }

      /* -------------------------  DeleteIndex() -----------------------------

      * Descrip:      Recursively traverses an index/tree      using the postorder method,
                        deleting all IndexNodes                              

      * Input:      Takes a pointer to an IndexNode - the root node of the tree.

      * Returns:      N/A

      * Requires:      A valid IndexNode must be passed, otherwise the procedure
                              terminates

      * Precond:      The calling function, GetRootIndexNode(), must pass the
                        root IndexNode

      * Postcond:      When the procedure returns, the index records stored by the
                        index tree will be deleted.  All of the resources used by
                        the index to store the records, i.e. the dynamnically
                        allocated nodes, will also be deleted.  The index structure
                        should be set to indicate a valid empty index/tree by the
                        caller.
      */
      

      void DeleteIndex(struct IndexNode *index)
      {

            // if the IndexNode is not NULL
            if(!index)
                  return;
            else{
            
                  DeleteIndex(index->LeftPtr);      // traverse left subtree
                  DeleteIndex(index->RightPtr);      // traverse right subtree
                  free(index);                              // delete node
            }
            
            return;
      }

      /* -------------------------  HookIndexNode() -----------------------------

      * Descrip:      This procedure is called to attach separate parts of a
                        tree when nodes are deleted.

      * Input:      The first parameter is a pointer to an index structure
                        identifying the index to be repaired.

                        The second, third and fourth parameters are pointers to
                        IndexNodes required for the repair:  
                        Child, Parent, and CurPtr (current)

      * Returns:      N/A

      * Requires:      The index, and IndexNode parameters, must be valid.
                  

      * Precond:      -

      * Postcond:      -
      */

      void HookIndexNode(struct Index *index, struct IndexNode *Child,
                                                                  struct IndexNode *Parent,
                                                                  struct IndexNode *CurPtr)
      {

            // if there is no parent
            if(CurPtr == Parent)
                  index->root = Child;
            // if there is a left child
            else if(CurPtr == Parent->LeftPtr)
                  // set parent's left pointer to new child
                  Parent->LeftPtr = Child;
            // if there is a right child
            else
                  // set parent's right pointer to new child
                  Parent->RightPtr = Child;
            return;
      }

      /* -------------------------  DeleteIndexNode() -----------------------------


      * Descrip:      This procedure deletes the specified key and its associated
                        list node pointer from the specifed index.  The other keys,
                        if any, will remain in the index.  The procedure does not
                        delete the associated list node from its linked list.

      * Input:      The first parameter is a pointer to the index structure
                        defining the index that the key is supposed to be removed from.

                        The second parameter is a pointer to a NUL terminated string
                        specifying the key to be removed from the index.  This string
                        must specify a key that is currently stored in the index.

      * Returns:      N/A

      * Requires:      The index specified by the index structure must be valid.
                        The key specified must currently be stored in the index.

      * Precond:      The specified key must be stored in the index.

      * Postcond: The specified key and its associated data will be removed
                        from the index.  The memory used to store the key and its
                        associated list node pointer in the index will be returned
                        to the heap.
      */

      void DeleteIndexNode(struct Index *index, char *KeyValue)
      {
            
            int KeyDif;                                                // holds value returned by strcmp()
            struct IndexNode *CurPtr = index->root;      // identifies node to be deleted
            struct IndexNode *Parent = CurPtr;            // identifies parent of CurPtr
            struct IndexNode *Successor;                  // identifies in-order successor

            // make comparison of IndexNode's Key member
            KeyDif = strcmp(KeyValue, CurPtr->Key);

            //********************  find node to be replaced *********************

            // while no matching index
            while((CurPtr) && (KeyDif != 0)){

                  // store a pointer to the parent node
                  Parent = CurPtr;

                  // if key value falls after CurPtr's key
                  if (KeyDif > 0){
                        // if the tree continues to the right.
                        if (CurPtr->RightPtr){
                              // set Parent pointer
                              Parent = CurPtr;
                              // continue searching to the right.
                              CurPtr = CurPtr->RightPtr;
                        }
                  }
                  // otherwise if key is before CurPtr->Key
                  else{
                        // If the tree continues to the left.
                        if (CurPtr->LeftPtr){
                              // set Parent pointer
                              Parent = CurPtr;
                              // continue searching to the left.
                              CurPtr = CurPtr->LeftPtr;
                        }
                  }
                  // make comparison of IndexNode's Key member
                  KeyDif = strcmp(KeyValue, CurPtr->Key);
            } // end of while loop

            // matching node not found
            if(!CurPtr)
                  return;

            //******************  reassign pointers and delete  *********************

            // if no left child from current position
            if(!CurPtr->LeftPtr)
                  // hook up the right child
                  HookIndexNode(index, CurPtr->RightPtr, Parent, CurPtr);

            // if no right child from current position
            else if(!CurPtr->RightPtr)
                  // hook up the left child
                  HookIndexNode(index, CurPtr->LeftPtr, Parent, CurPtr);
            // CurPtr has both children present, find inorder successor to CurPtr
            else{
                  // create temp IndexNode pointer
                  struct IndexNode * TempPtr = CurPtr->RightPtr;
                  // already at inorder successor
                  if(!TempPtr->LeftPtr){
                        // make TempPtr's left pointer the same as CurPtr's left
                        TempPtr->LeftPtr = CurPtr->LeftPtr;
                        // hook up the left child
                        HookIndexNode(index, TempPtr, Parent, CurPtr);
                  }
                  else{
                        // while there are inorder successors
                        while(TempPtr->LeftPtr && TempPtr->LeftPtr->LeftPtr){
                              // set TempPtr to parent of inorder successor
                              TempPtr = TempPtr->LeftPtr;
                              // create successor pointer & set to Temp's left child
                              Successor = TempPtr->LeftPtr;
                              // hook up subtree
                              TempPtr->LeftPtr = Successor->RightPtr;

                              Successor->LeftPtr = CurPtr->LeftPtr;
                              Successor->RightPtr = CurPtr->RightPtr;
                              HookIndexNode(index, Successor,Parent, CurPtr);
                        }
                  }
            } // end of else - find inorder successor
            // delete IndexNode
            free(CurPtr);
            return;
      }


      /* --------------------------   GetRootIndexNode() --------------------------

      * Descrip:      This procedure returns a pointer to the root node of the
                        specified index.  The index is not altered by this procedure.

      * Input:      A pointer to the index structure defining the index whose first
                        node is to be returned.

      * Returns:      A pointer to the root node of the index parameter.

      * Requires:      The index specified by the index structure must be valid.


      * Precond:  N/A

      * Postcond: N/A
      */

      struct IndexNode *GetRootIndexNode(struct Index *index)
      {
            return index->root; // assign node pointer to root node
      }


      /* -------------------------- InitializeIndex() --------------------------
      *      Descrip:      This procedure initializes an index structure so that it
                              defines a valid empty index, that is, an index with no keys
                              stored in it.

      *      Input:
                              The parameter is a pointer to the index structure that is to
                              be initialized

      *      Returns:    N/A

      *      Requires:      N/A

      *       Precond:    N/A

      *       Postcond:   The specified index structure will be altered so that it
                              specifies a valid empty index.
      */

      void InitializeIndex(struct Index *index)
      {
            index->root = NULL;                        // set root pointer to NULL

            return;

      }

      /* -------------------------  SearchIndexNode()  --------------------------

      * Descrip:      This procedure searches the specified index for a stored key
                        that matches the specified key.  If a matching key is found,
                        the ListNode pointer associated with that key is returned.  If
                        no matching key is found the procedure returns a NULL pointer

      * Input:      The first pointer is a pointer to the index structure
                        defining the index to be searched for the desired key.
      
                        The second parameter is a pointer to a NUL terminated string
                        specifying the search key.  This string must match the
                        string length and type of the index type in order to be a
                        valid search value.

      * Returns:      If the key to be searched for was in the index, this
                        procedure returns the ListNode pointer that is stored along
                        with that key, otherwise, if the key was not stored in the
                        index, the procedurreturns a NULL pointer.

      * Requires:      The Index pointed to by the first parameter must store indexes
                        of the same type specified in the second parameter.  The search
                        key of the second parameter must also correspond to the index
                        type of the 1st parameter.

      * Precond:      The first parameter must point to a index structure that
                        defines a valid index.  The second parameter must point to a
                        NUL terminated string.

      * Postcond:      The specified index is not changed by this procedure
      */

      struct ListNode *SearchIndexNode(struct Index *index, char *KeyValue)
      {
            
            int KeyDif;                              // holds value of each Key comparison
            struct IndexNode *CurPtr;      // used when traversing the tree

            // assign CurPtr the value of the tree root
            CurPtr = index->root;

                               
            // while there are nodes to search
            while (CurPtr){
             
              KeyDif = strcmp(CurPtr->Key,KeyValue);

              if(KeyDif == 0)
                    return(CurPtr->NodePtr);
              else if (KeyDif > 0)
                    CurPtr = CurPtr->LeftPtr;
              else
                    CurPtr = CurPtr->RightPtr;
            }
            return NULL;  // value returned if node was not found.
      }
0
Comment
Question by:John500
  • 13
  • 12
  • 3
  • +1
31 Comments
 
LVL 22

Expert Comment

by:nietod
Comment Utility
I guess you got the points.  

Thanks.
0
 
LVL 22

Accepted Solution

by:
nietod earned 1000 total points
Comment Utility
Opps.  I'll try again.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
"John500", I'm NOT being sarcastic or snide in my comment, but because I didn't see a question I wondered what prompted you to ask for this kind of help.  In checking your profile, I noticed you list yourself as a Computer Scientist (which is pretty cool).

As it turns out, three of my friends are Computer Scientists, all three with PhD's.

I was wondering at what point does someone become a Computer Scientist?
0
 
LVL 7

Expert Comment

by:KangaRoo
Comment Utility
And now we're at it, what do PhD and MS mean?
I'm dutch, just curious about the titles and what they mean.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
The question was an assigment that he has been working on with me via e-mail for several months.  

Outside of the computer world, a scientist is someone who uses the scientific method, it has nothing to do with degrees.  Inside the computer world....
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
PhD is a doctorate of philosophy, i.e. an accademic doctorate degree.  The highest degree typically awarded in a field.
MS is a master's degree.  A gratuate level degree confired by some schools  before the PhD.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
I think I'll hold off calling myself a Computer Scientist until I receive my PhD.
0
 
LVL 7

Expert Comment

by:KangaRoo
Comment Utility
I see. Mhh, I don't think I will call my self a Computer Scientist then. I only use scientific methods (I think) when I can't find a solution otherwise ;)
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
To get a PhD, you must shed blood, sweat, and tears.  Afterwards, it doesn't matter what method you use (scientific or otherwise), the world knows you have the right stuff and if your method is unscientific, so long as IT WORKS, thereafter it becomes scientific.  What others will do to it then is simply improve on it.

(AAMOF, that's how someone gets his/her PhD; they have to do something that's useful AND novel!!!)

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

I don't want to say much about it, but I was thinking about proving Euler's PRIME theorem and submit it as part of my dissertation:-)

It's a thought, OK!!!  Besides, I've been 'sweating' on this one for a while now, which makes me having satisfied the 'sweat' part of the requirement.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
That is hardly universal.  Difficulty and requirements vary from one institution to another and from one field to another.   Not all programs require you to complete a thesis or similar project.
0
 

Author Comment

by:John500
Comment Utility
Thanks
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
It was never my intention to get into a discussion with you.  If you are looking for a discussion, you're looking at the wrong person.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
No, your intention seems to be to criticise John for calling himself a "computer scientist" when he is still a student.  Is that really such a terrible slight to your status?
0
 

Author Comment

by:John500
Comment Utility
Try,

When you said:

"I think I'll hold off calling myself a Computer Scientist until I receive my PhD."

I think you may be giving the title more glory than it deserves.  To say that a person works in the capacity of a scientist only when he/she gains  knowledge at the level of a PHD is a bit presumptuous.

It's my opinion that many if not all subjects which end up in universities as curriculum, got there because of work done in the field, not from a professional student.

The title 'Computer Scientist' happens to be a title used by many employers and it's usually given to those who have a BS degree in computer science, but now always.

That should answer your question to me.

0
 

Author Comment

by:John500
Comment Utility
Try,

If your employer doesn't classify you as a 'Computer Scientist' now, then chances are you will have to wait until you get your PHD.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 3

Expert Comment

by:Try
Comment Utility
I wasn't critizing anyone, OK.  I asked the question based on what I know of my three friends with their PhD's.

I don't have to explain ANYTHING to you "nietod", and if you want to take this beyond explanation, I'll be happy to take you on!!!  It's not unusual for you to suddenly feel the urge to surge when you have the backing and support of your kinsmen.  So let me ask you, "Do you that urge now?" because if you do, I'll take you on!!!

"John500", maybe you can read something into this, "I have never felt the need, nor the significance to bring the subject up regarding the title."
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> I wasn't critizing anyone
Perhaps not, but it certainly seemed that way to me.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
All of a sudden your sensibilities seem to go into overdrive when you have kinsmen by your side.  Besides, I didn't even direct the question to you; I directed it to "John500".

What is it about you that makes you feel you MUST take up the cause of others?  Is it because you feel you are the ONLY one who must gallantly take up arms in their defense?  That, "poor little things, they cannot do so for themselves," so you MUST be their white knight who comes "a charging" to their rescue?  Is that how you get your mental high, by psychologically asserting yourself as the defender of the weak and the savior of the downtrodden?

Did you feel you were suppressed as a child?
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
Are you working on you PhD in psychology too?  

I have an interest in seeing this site work smoothly.  
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
Yeah, right!

The Guardian Of The Bastion!

The Righter Of The Wrong!

The Protector Of The Unprotected!

The Valiant Hero Of The Village!


(Did I miss out any?)
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
How about EE board member?
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
That is supposed to make me shiver.  Right?  Or am I supposed to genuflect before I reply to messages?

I have never been less than intrigued by the things that seem to play high in people's lives.  Fascinating!!  Absolutely fascinating!!
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> What is it about you that makes you feel you
>> MUST take up the cause of others?
You asked.  Now that there is a good answer, do you want dissregard the question?  

I have never before even mentioned that I am part of the board because I don't think it should matter to anyone not on the board, but I am getting tired of your personal attacks.  I do what I can to make the site run smoothly.  I feel I am justified in doing so.  If you dissagree, notify Linda in the customer service topic area.  
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
You are the one who started it, and now that you find things are not so comfortable you want to be portrayed as the victim, the one who is being beaten up on.

If you had read and understood the first few words of my very first comment, "... I'm NOT being sarcastic or snide in my comment", perhaps you would have deemed it unnecessary to take the position you did in remarking, "your intention seems to be to criticise John for calling himself a "computer scientist".

I wasn't the one who started this with you.  I even said, "It was never my intention to get into a discussion with you.  If you are looking for a discussion, you're looking at the wrong person."

Did you stop there?  NO!  You kept doing what you do best; you kept agitating.  And now that you find things a little too far gone, you want to reverse roles now portraying yourself as the innocent one.

I have never underestimated your intelligence, nor your cleverness to switch strategy.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
I am not accusing you of anything, but look back at what you wrote an how it SOUNDS.

I noticed you list yourself as a Computer Scientist

three of my friends are Computer Scientists, all three with PhD's.

I was wondering at what point does someone become a Computer Scientist?

I think I'll hold off calling myself a Computer Scientist until I receive my PhD.

To get a PhD, you must shed blood, sweat, and tears

It sounds to me like "Why are you calling yourself a computer scientist, I wouldn't dream of calling myself a computer scientist untiil I get my PhD."  That may not be what you intended, but it is likely to be the way it will be read.

0
 
LVL 7

Expert Comment

by:KangaRoo
Comment Utility
Why do things always escalate with you two?

It seems no hard words were written at the beginning, or at least intended, but step by step you two skillfully escalated the discussion.

Too bad, neither of you deserves this anger.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
"nietod" is the kind that if someone were to say, "Darkness rules the night, as light rules the day," he'd retort that darkness rules the night only because someone removed the light from the day.  He must assert himself with the TRUTH!!!

He is, "The Reincarnation Of Don Quixote de la Mancha."  He who sees giants where there are windmills, armies, where there are sheep, insults, where there are none.  HE! is on a quest, and dare any of us convince him otherwise.

I said, "... I'm NOT being sarcastic or snide in my comment," but he does NOT believe that, because he sees giants, and armies, and great wrongs to make right!
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
Try, no one else has ever complained to me.  Not ever.  Yet you have said on numerious occassions "I'll take you on any day".  (That is word-for word repeated.)  Does that sound like I'm looking for a fight?  I try very very hard to never accuse you of any wrong doing.  I didn't once accuse you of anything in this question.  I explained how it seemed to me and how it might very well seem to others.   Yet you continually accuse me of ludicrious things.  Is it possible Try that maybe you are the one that is looking for the fight?  i.e. maybe you are on a quest?  I don't need an answer.  But I think you need to think about the question.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
Yet another diversion in strategy; trying to sound like the pacifist who is been pursued; the person who took it on one cheek before turning the other.

The pacifist does not go out of his way to centrally implicate himself in an issue for which there wasn't a need for him to be involved in the first place.  Neither does he choose to ignore statements that speaks its clear intent to not being insultive and sarcastic for purpose of the reader's construe.  And lastly, the pacifist is the one who initiates and promotes restraint, calmness and non-confrontation.  The pacifist is the one who offers the olive branch, perfectly willing to assign benefit of doubt as substitute for misunderstandings, ... in the interest of peace.

You did not demonstrate any of these qualities.  You were NEVER the pacifist, and you don't beguile me.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
Look if you think I have done anything wrong, the contact customer service and let them handle it.  That is what they are there for.
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
KISS OFF!!!
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now