Чтение файла для каждого слова и сортировка этих слов с помощью бинарного дерева поиска (лексикографически)

Question

Привет коллеги программисты,

Я работаю над заданием, которое требует от нас прочитать файл, взять каждое слово из этого файла и отсортировать его в таблице, которая отображает слово и номер строки, в которой оно существует.

пример:

Файл, который нужно прочитать, содержит:

this is a
text file is

Таким образом, он выведет следующее:

a       1
file    2
is      1   2
text    2
this    1

Таким образом, оно берет каждое слово, а затем сортирует его по алфавиту, а затем печатает, на каких строках оно появляется. У меня есть этот код до сих пор (отредактировано):

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>

using namespace std;

struct TreeNode{
        string word;               //word will store the word from text file
        vector<int>lines;          //for keeping record of lines in which it was found
        TreeNode*left;             //pointer to left subtree
        TreeNode*right;            //pointer to right subtree
        TreeNode*temp;
    }; //end TreeNode

//check function for comparing strings
bool check(string a,string b)
{
    if(a<b)
      return false;
    return true;
}//end check

void insert(TreeNode *root,string word,int lineNumber){
    //Tree is NULL
   if(root==NULL){
      root=new TreeNode();
      root->word=word;
      root->lines.push_back(lineNumber);
   }//end if
    //words match
   if(root->word==word)
      root->lines.push_back(lineNumber);

   //check(a,b)is function that returns 1 if 'string a' is bigger than 'string b' lexographically
   if(check(root->word,word)){ //present word is lexographically bigger than root's word
      if(root->right)          //if right node to root is not null we insert word recursively
        insert(root->right,word,lineNumber);
      else{                    //if right node is NULL a new node is created
        TreeNode*temp=root->right;
        temp=new TreeNode();
        temp->word=word;
        temp->lines.push_back(lineNumber);
     }//end else
    }//end if
    else{ //present word is lexographically smaller than root's word
      if(root->left)
        insert(root->left,word,lineNumber);
      else{
        TreeNode*temp=root->left;
        temp=new TreeNode();
        temp->word=word;
        temp->lines.push_back(lineNumber);
      }//end nested else
    }//end else
}//end insert

//Print tree in In-Order traversal
void InOrder(TreeNode* node)
{
    if(!node) //end if pointing to null
        return;
    InOrder(node->left);        //display the left subtree
    cout << node->word << " ";  //display current node
    InOrder(node->right);        //display the right subtree
}//end InOrder

int main() { //main
 //int lineNumber = 0; //number of lines
 ifstream file("text.txt"); //takes input stream from designated file
 if(file) { //if file is there
  string line, word ; //setting line and word strings
  while(getline(file, line)) { //getting the lines from the file
            //++lineNumber; //incrementing number of lines when a new line is read
   istringstream is(line); //checking for a line
   while(is >> word) { //while a word exists
    InOrder(root); //<< lineNumber << "\n"; //outputting the words and tabbing to then print the line number and then a new line
   }//end word while
  }//end getline while
 }//end file if
 file.close();
 file.clear();
 return 0;
}//end main

мой текущий вывод:

this    1
is      1
a       1
text    2
file    2
is      2
#

(Символ # показывает, что это конец таблицы)

Но я никогда раньше не создавал дерево, а также думал о том, чтобы дерево сначала проверило файл и поместило каждое слово в алфавитный связанный список. Затем поиск в этом связанном списке дубликатов слова и отправка его во вложенный связанный список для распечатки номеров строк исходного слова и дубликатов.

Я просто ищу помощи в этом задании, я действительно смущен этим, пока не считаю себя хорошим программистом, и поэтому я в школе! Буду признателен за любую помощь!

Answer 1

Вот структура, которую вы должны использовать вместе с функцией вставки для реализации проблемы с использованием бинарного дерева:

struct TreeNode{
        string word;               //word will store the word from text file
        vector<int>lines;     //for keeping record of lines in which it was found
        TreeNode*left;             //pointer to left subtree
        TreeNode*right;            //pointer to right subtree
    };

В вашем случае вы включили эту структуру в class LexTree который не сильно помогает, а усложняет вещи.

Вот как вы должны реализовать функцию вставки

TreeNode* insert(TreeNode *root,string word,int lineNumber)
{
    //Tree is NULL
   if(root==NULL){
      root=new TreeNode();
      root->word=word;
      root->lines.push_back(lineNUmber);
   }
    //words match
   else if(root->word==word)
      root->lines.push_back(linenumber);

   //check(a,b)is funtion that returns 1 if 'string a' is bigger than 'string b' lexographically
   else if(check(root->word,word)){//present word is lexographically bigger than root's word
      if(root->right)         //if right node to root is not null we insert word recursively
        root->right=insert(root->right,word,lineNumber);
      else{                   //if right node is NULL a new node is created
        Node*temp=new TreeNode();
        temp->word=word;
        temp->lines.push_back(lineNumber);
        root->right=temp;
     }
    }
    else{ //present word is lexographically smaller than root's word
      if(root->left)
        root->left=insert(root->left,word,lineNumber);
      else{
        Node*temp=new TreeNode();
        temp->word=word;
        temp->lines.push_back(lineNumber);
        root->left=temp;
      }
    }
} 

РЕДАКТИРОВАТЬ-

Вот ваша функция проверки

bool check(string a,string b)
{
    if(a>b)
      return false;
    return true;
}

Использовать insert просто пройдите root node of your BST вместе с вашим word в качестве аргументов insert

Некоторые твики в InOrder и главное, что должно решить проблему

//Print tree in In-Order traversal
void InOrder(TreeNode* node)
{
if(!node) //end if pointing to null
    return;
InOrder(node->left);        //display the left subtree
cout << node->word << " ";  //display current node



for(int i=0;i<node->lines.length();i++)  //vector lines contains all the line numbers where we had the word node->word
     cout<<nodes->lines[i]<<" "; 

 cout<<endl;


}//end InOrder

int main() { //main
//int lineNumber = 0; //number of lines


TreeNode *root=NULL;   //you need to declare root to make a BST


ifstream file("text.txt"); //takes input stream from designated file
if(file) { //if file is there
    string line, word ; //setting line and word strings
    while(getline(file, line)) { //getting the lines from the file
        //++lineNumber; //incrementing number of lines when a new line is read
        istringstream is(line); //checking for a line
        while(is >> word) { //while a word exists


            root=insert(root,word);  // insert word in your BST


        }//end word while
    }//end getline while


  Inorder(root);   //gives required output


}//end file if
file.close();
file.clear();
return 0;
}//end main  

Answer 2

Я думаю, что вы усложняете проблему. Если бы я был тобой, я бы определил структуру как

struct Whatever
{
    string word;
    vector<int> line;
};

и объявить vector<Whatever> text

После этого вы можете использовать алгоритм sort с пользовательской функцией сравнения, которая будет сортировать ваши text вектор в лексикографическом порядке.

Если вам действительно нужно использовать двоичные деревья поиска для назначения, найдите время и проведите некоторое исследование. Основная идея заключается в том, что каждый раз, когда вы хотите вставить узел в дерево, вы сравниваете его с текущим узлом (который в начале будет корневым) и смотрите, будет ли он больше или меньше по значению (в вашем случае, лексикографическое сравнение) и двигайтесь в указанном направлении (слева на меньшее, справа на большее), пока не дойдете до узла NULL и там не добавите его. После этого вы можете создать лексикографический порядок, выполнив left-root-right Разбор дерева. Опять же, я бы использовал это struct для простоты.