my program should display an alphabetized listing of the words that were found u

Question

my program should display an alphabetized listing of the words that were found using a array-based binary search, I have created the binary search array already but I'm having a lot of trouble alphabetizing it.

int binarySearch(string[], int, int, int);

int main() {
int binarySearch(string words[], int first, int last, int key) {
while(first <= last) {
int mid = (first + last)/2; //computer mid point
if(key > words[mid])
first = mid + 1; //repeat search in top half.
else if(key < words[mid])
last = mid - 1; //repeat search in bottom half.
else
return mid; //found it. return position
}
return -(first + 1); //failed to find key
} //end binary search

*************************************************************************

Queues.h

#include <iostream> 
#include <string>
#include <sstream>
#include <algorithm>
#define NUMWORDS 200

using namespace std;

const string Punctuation = ",.;:?"'!@#$%^&*[]{}|";

//int wordCount = 0;
struct WORDINFO {
    string word;
    int posOfLineReferences;
} extern words[NUMWORDS];

typedef WORDINFO QueueItemType;

class QUEUE {
private:
        struct QueueNode {
                QueueItemType item;
                QueueNode *next;
        };
        QueueNode *backPtr;
        QueueNode *frontPtr;

public:
       QUEUE();
       ~QUEUE();
      
      

  
       bool isEmpty();

       void enqueue(QueueItemType newItem);

       bool dequeue();

       bool dequeue(QueueItemType& queueFront);

       bool getFront(QueueItemType& queueFront);

       void display(int index);
     
       bool remove(int index, QueueItemType& item);
              

       QUEUE& operator=(const QUEUE &qIn);  // goes in Queue
      
       void clear();
              
//end of queue
};

extern QUEUE lineReference[NUMWORDS];

*****************************************************************************************************************

Queue.cpp

#include "Queue5.h"
 
QUEUE::QUEUE() {
  backPtr = frontPtr = NULL;
}  // end default constructor

QUEUE::~QUEUE() {
  while (!isEmpty())
    dequeue();
}  // end destructor
void QUEUE::clear() {
  while (!isEmpty())
    dequeue();
}  // end destructor

bool QUEUE::isEmpty() {
  return backPtr == NULL;
}  // end isEmpty

void QUEUE::enqueue(QueueItemType newItem) {
  // create a new node
  QueueNode *newPtr = new QueueNode;

  // set data portion of new node
  newPtr->item = newItem;
  newPtr->next = NULL;

  // insert the new node
  if (isEmpty()) // insertion into empty queue
    frontPtr = newPtr;
  else // insertion into nonempty queue
    backPtr->next = newPtr;

  backPtr = newPtr;  // new node is at back
}  // end enqueue

bool QUEUE::dequeue() {
  if (isEmpty()) return false;

  // queue is not empty; remove front
  QueueNode *tempPtr = frontPtr;
  if (frontPtr == backPtr) {   // special case?
    // yes, one node in queue
    frontPtr = NULL;
    backPtr = NULL;
    }
  else frontPtr = frontPtr->next;

  tempPtr->next = NULL;
  delete tempPtr;
  return true;
}  // end dequeue

bool QUEUE::dequeue(QueueItemType& queueFront) {
  if (isEmpty()) return false;
  // queue is not empty; retrieve front
  queueFront = frontPtr->item;
  dequeue();  // delete front
  return true;
}  // end dequeue

bool QUEUE::getFront(QueueItemType& queueFront) {
  if (isEmpty()) return false;
  // queue is not empty; retrieve front
  queueFront = frontPtr->item;
  return true;
}  // end getFront
// End of queue.cpp
void QUEUE::display(int index)
   {
   QueueNode *tempPtr = frontPtr;
    if(tempPtr == NULL) cout<< "Empty";
      else while (tempPtr != NULL){
       cout<< tempPtr->item.word << " ";
       tempPtr = tempPtr->next;
  }
 }


  QUEUE& QUEUE::operator=(const QUEUE &qIn) {  // goes in Queue.cpp 
    QueueNode *temp = qIn.frontPtr;
   clear();
    while (temp) {
      enqueue(temp->item);
      temp = temp->next;
      }
    return *this;
    }

//};

****************************************************************************************************************

Explanation / Answer

If you have made your binary search tree (array) correctly, then alphabetizing it is easy. If you traverse a binary tree in its inorder, then all of the elements will be alphabetized. To traverse a tree in inorder, you must recursively travel to the node's left child, then visit the node itself, then recursively travel to the node's right child. This is a simple example: void inorder(Node n) { inorder(n.getLeft()); visit(n); inorder(n.getRight()); } I wasn't quite sure what your question was, so I hope this helps somewhat.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.