I'm doing a job that performs a search for a key (an int value) in a binary tree populated from a txt file. The file txt has the following registry in each row: a key (int), a given1 (long int) and a given2 (char [1000]). For example, the first line could be: "5 13734842 paper house" .
I made a simple program to randomly generate the data in the txt file, formatted and with the desired number of lines. In the main function I populated my tree by reading the created txt file and inserting each record in the tree created with the insere_ArvBin(ArvBin *raiz, Registro valor) function. Then calling the function consulta_ArvBin(ArvBin *raiz, int valor) passes an integer value to perform the search in the tree. This function returns 0 when the element is not found and 1 when it is found in the tree.
The program usually works for a small record in the txt file (with 5 lines, for example, and with few characters worked normally), the problem happens when you generate a large record with the < in> txt containing several lines and many characters, then accusing the error with the Segmentation fault; dump the core
I think the error is related to some bad memory allocation, I tried to use a libera_ArvBin(ArvBin *raiz) function that frees memory from the tree at the end of the program but nothing has changed. I do not know where this error could be and how it would modify some routine to solve this problem, since it works normally for small records. This is the code with the functions I used for creating, inserting, and querying the search tree:
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include "ArvoreBinaria.h"
#define TAM_REG 100000
using namespace std;
struct registro{
int chave;
int dado1;
char dado2[1000];
};
struct NO{
Registro info;
struct NO *esq;
struct NO *dir;
};
ArvBin* cria_ArvBin(){
ArvBin* raiz = (ArvBin*) malloc(sizeof(ArvBin));
if(raiz != NULL){
*raiz = NULL;
}
return raiz;
}
void libera_NO(struct NO* no){
if(no == NULL)
return;
libera_NO(no->esq);
libera_NO(no->dir);
free(no);
no = NULL;
}
void libera_ArvBin(ArvBin *raiz){
if(raiz == NULL)
return;
libera_NO(*raiz);//libera cada nó
free(raiz);//libera a raiz
}
int insere_ArvBin(ArvBin *raiz, Registro valor){
if(raiz==NULL)
return 0;
struct NO* novo;
novo = (struct NO*) malloc(sizeof(struct NO));
if(novo == NULL)//se deu erro na alocação
return 0;
novo->info = valor;
novo->dir = NULL;
novo->esq = NULL;
//procura onde inserir!
if(*raiz==NULL)//se minha arvore é uma arvore vazia. se for só inserir
*raiz = novo;
else{
struct NO* atual = *raiz;
struct NO* ant = NULL;
//navega nos nós da arvore até chegar em um nó folha
while(atual!=NULL){
ant = atual;
if(valor.chave == atual->info.chave){
free(novo);
return 0;//elemento já existe
}
if(valor.chave > atual->info.chave)
atual = atual->dir;
else
atual = atual->esq;
}
//insere como filho desse nó folha
if(valor.chave > ant->info.chave)
ant->dir= novo;
else
ant->esq=novo;
}
return 1;
}
//busca
int consulta_ArvBin(ArvBin *raiz, int valor){
if(raiz==NULL)
return 0;
struct NO* atual = *raiz;
while(atual != NULL){
if(valor == atual->info.chave){
return 1;
}
if(valor > atual->info.chave)
atual = atual->dir;
else
atual = atual->esq;
}
return 0;
}
int main(int argc, char** argv) {
ArvBin* raiz = cria_ArvBin();
int i = 0;
Registro valor[TAM_REG];
//carrega arquivo, lê dados e insere na árvore criada
FILE* arq = fopen("arquivo.txt", "r");
if(arq!=NULL){
while(fscanf(arq, "%d %d %[^\n]s", &valor[i].chave,
&valor[i].dado1, valor[i].dado2) != EOF) {
insere_ArvBin(raiz, valor[i]);
++i;
}
}
int busca = consulta_ArvBin(raiz, 5);
if(busca == 0)
printf("Não encontrado!\n");
else
printf("Encontrado!\n");
return 0;
}
.h with all the functions of the TAD:
#ifndef ARVOREBINARIA_H
#define ARVOREBINARIA_H
typedef struct registro Registro;
typedef struct NO* ArvBin;
ArvBin* cria_ArvBin();
void libera_ArvBin(ArvBin *raiz);
int estaVazia_ArvBin(ArvBin *razi);
int altura_ArvBin(ArvBin *raiz);
int totalNO_ArvBin(ArvBin *raiz);
void preOrdem_ArvBin(ArvBin* raiz);
void emOrdem_ArvBin(ArvBin* raiz);
void posOrdem_ArvBin(ArvBin *raiz);
int insere_ArvBin(ArvBin *raiz, Registro valor);
int remove_ArvBin(ArvBin *raiz, int valor);
int consulta_ArvBin(ArvBin *raiz, int valor);
#endif /* ARVOREBINARIA_H */
I noticed that in tests of up to 8000 the program works normally, from 9000 the Segmentation fault; dump of the core .
The code to generate random txt files for testing:
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <unistd.h>
#define TAM_TXT 100000
#define MAX_STR_SIZE 50
#define MIN_STR_SIZE 5
using namespace std;
char* geraStringAleatoria(){
char *validchars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *novastr;
register int i;
int str_len;
// inicia o contador aleatório
//srand ( time(NULL ));
// novo tamanho
str_len = (rand() % MAX_STR_SIZE );
// checa tamanho
str_len += ( str_len < MIN_STR_SIZE ) ? MIN_STR_SIZE : 0;
// aloca memoria
novastr = ( char * ) malloc ( (str_len + 1) * sizeof(char));
if ( !novastr ){
printf("[*] Erro ao alocar memoria.\n" );
exit ( EXIT_FAILURE );
}
// gera string aleatória
for ( i = 0; i < str_len; i++ ) {
novastr[i] = validchars[ rand() % strlen(validchars) ];
novastr[i + 1] = 0x0;
}
return novastr;
}
int escreverArquivo(){
//srand( (unsigned)time(NULL) );
int chave = rand() % INT_MAX;
long int dado1 = rand() % LONG_MAX;
FILE* info = fopen("arquivo[100000L].txt", "w");
int i=0;
while(i<TAM_TXT){
fprintf(info,"%d %ld %s\n", (rand() % INT_MAX), (rand() % LONG_MAX), geraStringAleatoria());
++i;
}
}
int main() {
escreverArquivo();
return 0;
}