In c++, construct a cross-reference index for a given text file. Such index stru

Question

In c++, construct a cross-reference index for a given text file. Such index structures have applications in the design of compilers and databases.

Our task is to write a program that while reading a text file collects all words of the text and retains the numbers of the lines in which each word occurred. When this scan is terminated, a table is printed showing all collected words in alphabetical order with lists of line numbers where they occurred. There would be only one line for each word.

Represent the words encountered in the text by a binary search tree (also called a lex- icographic tree). For example, if there were three words

Explanation / Answer

#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>
#include <sstream>

using namespace std;

struct line{
   int num;
   line *next;
};

void addToList(line *&temp, int num){
   line *n = new line;
   n->num = num;
   n->next = NULL;
   if (temp == NULL){
       temp = n;
   }
   else{
       line *t = temp;
       while (t->next != NULL){
           t = t->next;
       }
       t->next = n;
   }
}

struct node{
   string word;
   line *lines;
   node *left;
   node *right;
};

class BST{
private:
   node *head;
   int count;
public:
   BST();
   int size();
   void insert(string value, int num);
   void insert(node *&temp, string value, int num);
   node *search(node *temp, string value);
   void display();
   void display(node *root);
};

BST::BST(){
   head = NULL;
   count = 0;
}

int BST::size(){
   return count;
}

void BST::insert(node *&temp, string value, int num){
   if (temp == NULL){
       node *newone = new node;
       newone->word = value;
       newone->left = NULL;
       newone->right = NULL;
       newone->lines = NULL;
       addToList(newone->lines, num);
       temp = newone;
       return;
   }
   else{
       if (temp->word <= value){
           insert(temp->right, value, num);
       }
       else{
           insert(temp->left, value, num);
       }
   }
}

void BST::insert(string value, int num){
   if (head == NULL){
       node *newone = new node;
       newone->word = value;
       newone->left = NULL;
       newone->right = NULL;
       newone->lines = NULL;
       addToList(newone->lines, num);
       head = newone;
       count++;
       return;
   }
   else{
       node *f = search(head, value);
       if (f != NULL){
           addToList(f->lines, num);
       }
       else{
           insert(head, value, num);
           count++;
       }
       return;
   }
}

node *BST::search(node *temp, string value){
   if (temp == NULL){
       return NULL;
   }
   else{
       if (temp->word == value){
           return temp;
       }
       else{
           node *l = search(temp->left, value);
           node *r = search(temp->right, value);
           if (l != NULL){
               return l;
           }
           else if (r != NULL){
               return r;
           }
           else{
               return NULL;
           }
       }
   }
}

void BST::display(node *root){
   if (root == NULL){
       return;
   }
   else{
       display(root->left);
       cout << setw(15) << root->word << " " << setw(10);
       line *t = root->lines;
       while (t != NULL){
           cout << t->num << " ";
           t = t->next;
       }
       cout << endl;
       display(root->right);
   }
}

void BST::display(){
   if (count == 0){
       cout << "Tree is Empty" << endl;
   }
   else{
       cout << setw(15) << "Word" << setw(15) << "lines" << endl;
       display(head);
       cout << endl;
   }
}

int main(){
   BST tree = BST();
   ifstream in;
   string fName;
   cout << "Enter File Name: ";
   cin >> fName;
   in.open(fName.c_str());
   if (in.is_open()){
       int lcount = 0;
       while (!in.eof()){
           lcount++;
           string temp;
           getline(in, temp);
           stringstream ss;
           ss << temp;
           string t = "";
           while (ss >> t){
               if (t.size() > 10){
                   t = t.substr(0, 10);
               }
               char end = t[t.size() - 1];
               if (end == ',' || end == '.' || end == ';'){
                   t = t.substr(0, t.size() - 1);
               }
               tree.insert(t, lcount);
           }
       }
       tree.display();
   }
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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