0
I am doing a job that performs a key search (an int value) in a binary tree populated from a file txt. The archive txt has in each row the following record: a key (int), a date1 (long int) and a date2 (char[1000]). For example, the first line could be: "5 13734842 paper box".
I made a simple program to randomly generate the data in txt file, formatted and with the desired number of lines. In function main populated my tree by performing file reading txt created and inserting each record into the tree created with the function insere_ArvBin(ArvBin *raiz, Registro valor). Then calling the function consulta_ArvBin(ArvBin *raiz, int valor) step an integer value to perform the tree search. 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 file txt (with 5 lines, for example, and with few characters worked normally), the problem happens when Gero a large record, with the file txt containing several lines and many characters, then accusing the error with the message Segmentation fault; core dump
I believe the error is related to some misplaced memory allocation, I tried to use a function libera_ArvBin(ArvBin *raiz) which frees the tree’s memory at the end of the program but nothing has changed. I don’t 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 creation, insertion and query in 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;
}
The .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 performing tests that in records of up to 8000 the program works normally, from 9000 already happens the error Segmentation fault; core dump.
The code to generate the files txt random 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;
}
Isn’t it because only 3 entries fit in your array? Few lines with many characters work? And many lines with few characters?
– Bruno Pastre
Can you put the file that crashes you in a Pastebin so it’s easy to test? In an additional note your code is basically C code with
cout, in which you should then use only C andprintffor consistency reasons. Otherwise you should consider using all of C++, for examplenewanddeleteinstead ofmallocandfree, among other things.– Isac
@Brunopastre I forgot to change the size of the array of records which is according to the size of the txt file generated. I made the correction of the code in the question. The problem continues for records above 8000.
– Caio Teixeira
@Isac I cannot put the file with many records in Pastebin, I edited the question and put the code to generate the txt files for the tests. Obg for the tip :)
– Caio Teixeira