avl tree — использование массива struct, подсчитывающего количество вхождений слова в текстовый файл Stack Overflow

Привет всем, это мой первый раз в Stackoverflow. У меня есть вопрос, касающийся подсчета появления слов в текстовом файле с использованием C ++. Это мой код до сих пор. Я должен создать массив массива индекса слова и счетчик каждого слова, а затем сохранить их все в дереве AVL. Открыв файл и прочитав слово, я ищу его в дереве avl или в trie. Если он есть, используйте индекс узла, чтобы увеличить Cnt слова. Если его там нет, добавьте его в массив слов, поместите его положение в следующую структуру и поместите положение структур в дерево avl. Также я установил struct Cnt на 1. Проблема, с которой я столкнулся сейчас, заключается в том, что моя программа не обрабатывает счет правильно, поэтому выводит только 0. Пожалуйста, дайте мне рекомендации, как я могу исправить ошибку. Пожалуйста, найдите мой код ниже:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <cstring>
#include <ctype.h>
#include <stdio.h>
#include <string>
#include <cctype>
#include <stdlib.h>
#include <stdbool.h>
using namespace std;

struct Node* insert(struct Node* node, int key) ;
void preOrder(struct Node *root) ;
void removePunct(char str[]);
int compareWord(char word1[], char word2[] );

struct Stats {
int wordPos, wordCnt;
};
Stats record[50000];
int indexRec = 0;
char word[50000*10] ;
int indexWord = 0;

int main() {
ifstream fin;
string fname;
char line[200], wordArray[500000];

cout << "Enter the text file name:" << endl;
cin >> fname;
fin.open(fname.c_str());
if (!fin) {
cerr << "Unable to open file" << endl;
exit(1);
}
struct Node *root = NULL;
while (!fin.eof() && fin >> line) { //use getline
for(int n=0,m=0; m!=strlen(line); m+=n) {
sscanf(&line[m],"%s%n",word,&n);
removePunct(word);
//strcpy(&wordArray[indexWord],word);
int flag = compareWord(wordArray, word);
if(flag==-1) {
strcpy(&wordArray[indexWord],word);
record[indexRec].wordPos = indexWord;
record[indexRec].wordCnt = 1;
root = insert(root, record[indexRec].wordPos);
indexWord+=strlen(word)+1;
// indexes of the word array
indexRec++;
cout << wordArray[indexWord] << " ";
} else
record[flag].wordCnt++;

cout << record[indexRec].wordCnt;
cout << endl;

}
/*for(int x = 0; x <= i; x++)
{
cout << record[x].wordPos << record[x].wordCnt << endl;
}*/

}

fin.close();
return 0;

}

void removePunct(char str[]) {
char *p;
int bad = 0;
int cur = 0;
while (str[cur] != '\0') {
if (bad < cur && !ispunct(str[cur]) && !isspace(str[cur])) {
str[bad] = str[cur];
}
if (ispunct(str[cur]) || isspace(str[cur])) {
cur++;
} else {
cur++;
bad++;
}
}
str[bad] = '\0';
for (p= str; *p!= '\0'; ++p) {
*p= tolower(*p);
}
return;
}
int compareWord(char word1[], char word2[] ) {
int x = strcmp(word1, word2);
if (x == 0 ) return x++;
if (x != 0) return -1;
}

struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get maximum of two integers
int max(int a, int b);

// A utility function to get height of the tree
int height(struct Node *N) {
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key) {
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key   = key;
node->left   = NULL;
node->right  = NULL;
node->height = 1;  // new node is initially added at leaf
return(node);
}

// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct Node *rightRotate(struct Node *y) {
struct Node *x = y->left;
struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;

// Return new root
return x;
}

// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct Node *leftRotate(struct Node *x) {
struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

//  Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;

// Return new root
return y;
}

// Get Balance factor of node N
int getBalance(struct Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert key in subtree rooted
// with node and returns new root of subtree.
struct Node* insert(struct Node* node, int key) {
/* 1.  Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));

if (key < node->key)
node->left  = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then
// there are 4 cases

// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left =  leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */
return node;
}
void preOrder(struct Node *root) {
if(root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

0

Решение

Одна проблема (я не вижу, является ли это единственной проблемой) состоит в том, что у вас есть такой код, удаляющий все промежуточные строки:

record[indexRec].wordCnt = 1;
if find word fails
indexRec++;
cout << record[indexRec].wordCnt;

Поэтому, когда у вас есть новое слово (если я правильно понимаю код!), Вы распечатываете следующую запись. Одним из исправлений будет:

if (flag==-1)
cout << record[indexRec-1].wordCnt;
else
cout << record[indexRec].wordCnt;

Есть много других вопросов, таких как compareWord() является очень неправильно, вы должны решить, действительно ли вы хотите использовать C ++ или просто C с std::coutкод чтения файла странный, вы включаете версии C и C ++ стандартных заголовков и т. д., но это проблемы другого вопроса!

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]