Usando múltiplos rewind()
e fseek()
vai deixar tudo muito lento. E também não está fácil de ler.
Vou deixar um exemplo de como fazer isso usando uma técnica comum e abrindo cada arquivo uma única vez. A idéia é usar uma estrutura de dados e nesse caso uma variação de uma árvore de prefixos, chamada Trie na literatura.
Exemplo da estrutura
Sejam os nomes azul
, ama
, ver
e amar
a v
/ \ \
m z e
/ \ \
a* u r*
/ \
r* l*
A idéia é que não se precisa repetir os prefixos para todos os nomes. Os nomes já saem ordenados da estrutura e ainda há lugar para algumas otimizações, como compactar os dados quando só há uma palavra num certo ramo. O asterisco indica o fim de uma palavra e assim amar e ama por exemplo não repetem o prefixo.
A árvore em C
typedef struct st_tree
{
size_t size; // em nodes
size_t words; // em palavras
Node* root; // raiz
} Tree;
E um nó seria
typedef struct st_node
{
char letra; // cada node tem uma letra
char fim; // termina uma palavra aqui?
struct st_node* L; // letra antes
struct st_node* R; // letra depois
struct st_node* S; // letras abaixo deste
} Node;
Essa função
Tree* def_dicionario(const char* arquivo)
{
char linha[LIMITE_PAL];
if (arquivo == NULL) return NULL;
FILE* arq = fopen(arquivo, "r");
if (arq == NULL) return NULL;
char* p = fgets(linha, sizeof(linha), arq);
Tree* nomes = create();
while (p != NULL)
{
if (*p != '\n') // linha em branco?
{
if (linha[strlen(linha) - 1] == '\n')
linha[strlen(linha) - 1] = 0;
add(linha, &nomes->root, nomes);
}
p = fgets(linha, sizeof(linha), arq);
}
fclose(arq);
return nomes;
}
recebe o nome do arquivo e retorna o endereço de uma árvore com todas as palavras, já em ordem como no exemplo, considerando um arquivo simples com um nome por linha.
As palavras e o arquivo 'relato.txt'
Um problema em seu código é que não está claro quais letras são válidas na string e o que delimita uma delas.
Uma maneira simples pode ser essa: uma tabela de 256 posições onde os símbolos que são aceitos para compor a string são passados por uma função.
exemplo
char* def_letras(const char* valido)
{
char* tbl = (char*)malloc(256);
if (tbl == NULL) return NULL;
memset(tbl, 0, 256);
const char* p = valido;
while (*p != 0) *(tbl + *p++) = 1;
return tbl;
}
Essa função resolve isso e é uma solução comum. Qual a idéia? É chamada assim
char* valido = def_letras(
"abcdefghijklmnopqrstuvxywz"
"ABCDEFGHIJKLMNOPQRSTUVXYWZ");
E assim na tabela retornada apenas essas letras estarão marcadas e não precisa testar nada. Trata-se de uma look-up table. E mudar a definição fica simples e direto. Para aceitar apenas números e alguns operadores por exemplo:
char* exemplo = def_letras(
"0123456789"
" +-*/()=.");
juntando a tabela e a árvore
Então se os nomes já estão na estrutura e os caracteres válidos já estão na tabela basta ler o arquivo uma única vez, usando a tabela para extrair as strings e buscando na árvore o nome como se faria numa folha de papel. E é muito rápido. Algo assim
int busca_palavras(
Tree* lista, const char* delim, const char* arquivo)
{
char palavra[LIMITE_PAL];
char pos = 0;
if (arquivo == NULL) return 0;
FILE* arq = fopen(arquivo, "r");
if (arq == NULL) return 0;
int letra = fgetc(arq);
char st = 0;
while (1)
{
if (feof(arq)) break;
if (delim[letra] != 0)
st = 1, palavra[pos++] = letra;
if ((st == 1) && (delim[letra] == 0))
{
palavra[pos] = 0;
if (nome_valido(palavra, lista))
printf("+ \"%s\"\n", palavra);
pos = 0;
st = 0;
}
letra = fgetc(arq);
}; // while()
fclose(arq);
return 0;
}
Que é chamado assim no exemplo
char* valido = def_letras(
"abcdefghijklmnopqrstuvxywz"
"ABCDEFGHIJKLMNOPQRSTUVXYWZ");
busca_palavras(nomes, valido, "relato.txt");
E faz sentido: vai ler o arquivo e usando a lista de letras aceitas vai extrair as palavras e buscar no dicionário nomes
.
main para o exemplo
#include "tree.h"
int main(void)
{
Tree* nomes = def_dicionario("nomes.txt");
if (nomes == NULL) return -1;
mostra_palavras(nomes, "Nomes encontrados:");
char* valido = def_letras(
"abcdefghijklmnopqrstuvxywz"
"ABCDEFGHIJKLMNOPQRSTUVXYWZ");
mostra_letras_ok(valido, "\nLetras validas na string:\n");
printf("\nNomes encontrados no arquivo:\n");
busca_palavras(nomes, valido, "relato.txt");
nomes = destroi_dicionario(nomes);
free(valido);
return 0;
}
- cria o dicionário com os nomes
- mostra os nomes encontrados, só para confirmar
- define as letras que podem formar uma string, no exemplo apenas letras maiúsculas e minúsculas
- mostra as letras aceitas, só para confirmar. Algo simples assim
int mostra_letras_ok(const char* lt, const char* titulo)
{
if (titulo != NULL) printf("%s", titulo);
char col = 1;
for (int i = 0; i < 256; i += 1)
{
if (*(i + lt) != 0)
{
printf("%c ", i);
if (col == 10) printf("\n");
col = (col == 10) ? 1 : col + 1;
}
}
printf("\n");
return 0;
}
mostra
Letras validas na string:
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z a b c d
e f g h i j k l m n
o p q r s t u v w x
y z
- busca os nomes no arquivo `relato``e mostra na tela
- apaga as estruturas
Saída do Exemplo
Nomes encontrados:
109 nodes, 20 palavras
Palavras:
[Alice]
[Arthur]
[Bernardo]
[Davi]
[Gabriel]
[Heitor]
[Helena]
[Isabela]
[Julia]
[Laura]
[Livia]
[Lorenzo]
[Lucca]
[Luiza]
[Manuela]
[Matheus]
[Miguel]
[Pedro]
[Sofia]
[Valentina]
Letras validas na string:
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z a b c d
e f g h i j k l m n
o p q r s t u v w x
y z
Nomes encontrados no arquivo:
+ "Laura"
+ "Arthur"
+ "Manuela"
+ "Matheus"
O código completo
tree.h
#pragma once
#define LIMITE_PAL 80
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct st_node
{
char letra; // cada node tem uma letra
char fim; // termina uma palavra aqui?
struct st_node* L; // letra antes
struct st_node* R; // letra depois
struct st_node* S; // letras abaixo deste
} Node;
typedef struct st_tree
{
size_t size; // em nodes
size_t words; // em palavras
Node* root; // raiz
} Tree;
int busca_palavras(Tree* lista,const char* letras_validas,const char* arquivo);
Tree* def_dicionario(const char*);
char* def_letras(const char*);
Tree* destroi_dicionario(Tree*);
int mostra_letras_ok(const char*, const char*);
int nome_valido(const char*,Tree*);
int mostra_palavras(Tree*, const char*);
tree.c
#include "tree.h"
// helpers
int add(const char*, Node**, Tree*);
Tree* create();
Node* create_node(char);
Node* destroi_nodes(Node*);
Node* find_subt(const char, Node**, Tree*);
int find_all_words(Node*, size_t);
// insere *pal a partir de *raiz na arvore *arv
// nivel, porque pode mudar com *pal
int add(const char* pal, Node** raiz, Tree* arv)
{
if (arv == NULL) return -1; // erro
if (*pal == 0) return 0; // ok
if (raiz == NULL) return -1; // erro
// encontra ramo da arvore com essa letra
// ou cria se nao tiver ainda
Node* subt = find_subt(*pal, raiz, arv);
// subt aponta para a sub-arvore da letra
if (*(1 + pal) == 0)
{
subt->fim = 1;
arv->words += 1;
return 1;
}
return add(1 + pal, &subt->S, arv);
}
Tree* create()
{
Tree* nova = (Tree*)malloc(sizeof(Tree));
if (nova == NULL) return NULL;
nova->size = 0;
nova->words = 0;
nova->root = NULL;
return nova;
}
Node* create_node(char letra)
{
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) return NULL;
node->letra = letra;
node->fim = 0;
node->L = NULL;
node->R = NULL;
node->S = NULL;
return node;
}
// busca palavras da lista no arquivo considerando
// a tabela de letras validas
int busca_palavras(
Tree* lista, const char* delim, const char* arquivo)
{
char palavra[LIMITE_PAL];
char pos = 0;
if (arquivo == NULL) return 0;
FILE* arq = fopen(arquivo, "r");
if (arq == NULL) return 0;
int letra = fgetc(arq);
char st = 0;
while (1)
{
if (feof(arq)) break;
if (delim[letra] != 0)
st = 1, palavra[pos++] = letra;
if ((st == 1) && (delim[letra] == 0))
{
palavra[pos] = 0;
if (nome_valido(palavra, lista))
printf("+ \"%s\"\n", palavra);
pos = 0;
st = 0;
}
letra = fgetc(arq);
}; // while()
fclose(arq);
return 0;
}
// retorna uma arvore com as palavras que estao no arquivo
Tree* def_dicionario(const char* arquivo)
{
char linha[LIMITE_PAL];
if (arquivo == NULL) return NULL;
FILE* arq = fopen(arquivo, "r");
if (arq == NULL) return NULL;
char* p = fgets(linha, sizeof(linha), arq);
Tree* nomes = create();
while (p != NULL)
{
if (*p != '\n') // linha em branco?
{
if (linha[strlen(linha) - 1] == '\n')
linha[strlen(linha) - 1] = 0;
add(linha, &nomes->root, nomes);
}
p = fgets(linha, sizeof(linha), arq);
}
fclose(arq);
return nomes;
}
char* def_letras(const char* valido)
{
char* tbl = (char*)malloc(256);
if (tbl == NULL) return NULL;
memset(tbl, 0, 256);
const char* p = valido;
while (*p != 0) *(tbl + *p++) = 1;
return tbl;
}
Tree* destroi_dicionario(Tree* dict)
{
if (dict == NULL) return NULL;
if (dict->root == NULL)
{
free(dict);
return NULL;
}
Node* nd = dict->root;
if (nd->R != NULL) destroi_nodes(nd->R);
if (nd->S != NULL) destroi_nodes(nd->S);
free(nd);
free(dict);
return NULL;
}
Node* destroi_nodes(Node* node)
{
if (node == NULL) return NULL;
Node* nd = node;
if (nd->R != NULL) destroi_nodes(nd->R);
if (nd->S != NULL) destroi_nodes(nd->S);
free(nd);
return NULL;
}
int mostra_letras_ok(const char* lt, const char* titulo)
{
if (titulo != NULL) printf("%s", titulo);
char col = 1;
for (int i = 0; i < 256; i += 1)
{
if (*(i + lt) != 0)
{
printf("%c ", i);
if (col == 10) printf("\n");
col = (col == 10) ? 1 : col + 1;
}
}
printf("\n");
return 0;
}
// mostra na tela a palavra encontrada no arquivo
// se ela esta no dicionario
int nome_valido(const char* nome, Tree* lista)
{
if (nome == NULL) return 0;
if (lista == NULL) return 0;
Node* dict = lista->root;
while (dict != NULL)
{
if (dict->letra > *nome) return 0;
if (dict->letra < *nome)
{
dict = dict->R;
continue;
}
// ok tem a letra
nome += 1; // passa para a proxima letra
dict = dict->S; // desce na arvore
}; // while()
if (*nome == 0) return 1;
return 0;
};
// retorna endereco do ramo de *arv onde esta
// a letra 'letra'. Cria se nao existir
// pode alterar *ramo se mudar o inicio da lista
// de letras
Node* find_subt(const char letra, Node** ramo, Tree* arv)
{
if (letra == 0) return NULL; // sem letra
if (arv == NULL) return NULL; // sem arvore
if (*ramo == NULL)
{
*ramo = create_node(letra);
arv->size += 1;
return *ramo;
}
Node* p = *ramo;
Node* nv = NULL;
char estado = 1;
while (1)
{
switch (estado)
{
case 1:
if (p->letra < letra)
{
if (p->R != NULL)
p = p->R; // continua
else
estado = 3; // acabou: poe no fim
break;
}
if (p->letra == letra) return p;
// letra maior que p->letra: insere antes
estado = 2;
break;
case 2:
// fim da linha: nao tem a letra:
// vai inserir ANTES de p
nv = create_node(letra);
arv->size += 1;
if (p->L != NULL)
{
p->L->R = nv;
nv->L = p->L;
nv->R = p;
p->L = nv;
}
else
{ // nv vai ser o novo inicio
nv->L = NULL;
nv->R = p;
p->L = nv;
*ramo = nv;
}
return nv;
break;
case 3:
// insere no fim das letras
// p aponta para a ultima letra
// mas e menor que 'letra'
nv = create_node(letra);
arv->size += 1;
p->R = nv;
nv->L = p;
return nv;
break;
default:
break;
}; // switch()
}; // while()
return NULL;
}
int find_all_words(Node* node, size_t pos)
{
static char palavra[1024]; // 1K limite
palavra[pos] = 0;
Node* p = node;
palavra[pos] = p->letra;
if (p->fim == 1)
{
palavra[pos + 1] = 0;
printf("\t\t[%s]\n", palavra);
}
if (p->S != NULL) find_all_words(p->S, 1 + pos);
if (p->R != NULL) find_all_words(p->R, pos);
return 0;
}
int mostra_palavras(Tree* arv, const char* tit)
{
if (tit != NULL) printf("%s\n", tit);
if (arv == NULL) return 0;
if (arv->root == NULL)
{
printf("dicionario vazio\n");
return 0;
}
printf(
"%d nodes, %d palavras\n", arv->size, arv->words);
printf("\nPalavras:\n");
find_all_words(arv->root, 0);
return 0;
}
main.c
#include "tree.h"
int main(void)
{
Tree* nomes = def_dicionario("nomes.txt");
if (nomes == NULL) return -1;
mostra_palavras(nomes, "Nomes encontrados:");
char* valido = def_letras(
"abcdefghijklmnopqrstuvxywz"
"ABCDEFGHIJKLMNOPQRSTUVXYWZ");
mostra_letras_ok(valido, "\nLetras validas na string:\n");
printf("\nNomes encontrados no arquivo:\n");
busca_palavras(nomes, valido, "relato.txt");
nomes = destroi_dicionario(nomes);
free(valido);
return 0;
}
nomes.txt
Alice
Helena
Isabela
Julia
Laura
Livia
Luiza
Manuela
Sofia
Valentina
Arthur
Bernardo
Davi
Gabriel
Heitor
Lucca
Lorenzo
Miguel
Matheus
Pedro
relato.txt
Jose chegou de uma longa viagem vindo de Manacapuru no estado do
Amazonas e entrou pela porta da sala da casa de Laura.
Ela chegou pela cozinha com seu irmao Arthur, ao que Jose
perguntou onde eles estavam e eles responderam: na casa da
amiga Manuela. Infelizmente o relogio atrasou e ela marcava
a hora que seu filho Matheus chegava de Coari (cidade vizinha).
Na manha seguinte a televisao noticiou um acidente que
ocorrera na cidade de Parintins onde varias pessoas ficaram
feridas, inclusive Marcos e Roberto, conhecidos da familia.