Dificuldade com erro de segmentação

[MBruno 0]

Estou com uma dificuldade com erro de segementação. Meu código até o momento, olhei e está gerando os números tanto ordenados, quanto aleatórios. No entanto, quando vai na opção de realizar uma pesquisa é onde ocorre o erro, pois a árvore AVN não é gerada para quantidade de chaves de 10.000 para cima. O problema é que isto só ocorre com números ordenados. Poderia me ajudar aqui nessa?

 

/*
 * File:   main.cpp
 * Author: bruno
 *
 * Created on 27 de Outubro de 2017, 11:58
 */

#include <cstdlib>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <time.h>
#include <sstream>
#include <string>
#include <cstring>
#include <string.h>

using namespace std;

//  Cria-se as structs responsáeis por armazenar os dados, ligar uma struct ?
//  outra e por fim uma a qual aponta para o primeiro e último termo

typedef long int tipoChave;

struct dados {
    tipoChave chave;
    long int dado1;
    char dado2[1000];
};

struct Elemento {
    dados info;
    Elemento *anterior, *proximo;
};

typedef struct {
    Elemento *primeiro, *ultimo;
} ListaEncadeada;

typedef struct TipoNo *aponta;

typedef struct TipoNo {
    dados registro;
    int alturaEsq, alturaDir, FB;
    aponta esq, dir;
} TipoNo;

//  Funções
void criarLista(ListaEncadeada &lista);
void inserirElemento(ListaEncadeada &lista, dados dado);
void exibeLista(ListaEncadeada lista);
void gerarchaves(ListaEncadeada &lista, int quant, int op);
bool verificar(ListaEncadeada &lista, tipoChave chave);
void escrevearquivo(ListaEncadeada &lista, int quant, string tipo);
void lerarquivo(ListaEncadeada &lista, string nome);
void iniciarArvore(aponta *s);
void insereAVL(dados dado, aponta *r);
void insereAVN(dados dado, aponta *p);
int AVLAltura(aponta *r);
void rotacionaEsq(aponta *r);
void rotacionaDir(aponta *r);
void balancear(aponta *r);
void atualizar(aponta * r);
//void altura(aponta * r);
void exibirEmOrdem(aponta *p);
void menubusca(ListaEncadeada lista, aponta *p);
void buscaSeq(ListaEncadeada &lista, dados &dado);
bool verifOrd(ListaEncadeada lista);
void buscaAVN(dados *dado, aponta *p);
void menu();
int main();

void criarLista(ListaEncadeada &lista) {
    //  Aloca memóia para a lista e a declara vazia, definindo que ponteiros
    //  de primeiro e último apontam para o mesmo elemento null
    lista.primeiro = NULL;
    lista.ultimo = lista.primeiro;
}

void inserirElemento(ListaEncadeada &lista, dados dado) {
    //  Aloca memória para o dado a ser inserido
    Elemento *elemento = (Elemento *) malloc(sizeof (Elemento));

    //  Insere o elemento ao final da lista, e este mesmo ao final é atualizado
    //  como o último dado inserido
    elemento->info = dado;
    elemento->proximo = NULL;
    elemento->anterior = NULL;

    //  Se a lista estiver vazia
    if (lista.primeiro == NULL) {
        lista.primeiro = elemento;
        lista.ultimo = elemento;
    }//  Senão?
    else {
        lista.ultimo->proximo = elemento;
        elemento->anterior = lista.ultimo;
        lista.ultimo = elemento;
    }
}

void exibeLista(ListaEncadeada lista, int escolha) {
    //  Cria uma variável struct dinamica para receber o primeiro elemento da lista
    Elemento *elemento = lista.primeiro;

    //  Verifica o lista presente armazenada e exibe ao usuário
    switch (escolha) {
        case 1:
            cout << "\nLista Aleatória gerada:\n";
            break;
        case 2:
            cout << "\nLista Ordenada gerada:\n";
            break;
        case 3:
            cout << "\nLista contida no arquivo:\n";
            break;
        default:
            cout << "\nLista Inválida ou vazia!\n";
            menu();
            break;
    }
    //  Realiza a escrita no arquivo enquanto houver dados a ser inseridos
    while (elemento != NULL) {
        cout << "\nChave: " << elemento->info.chave;
        cout << "  Dado1: " << elemento->info.dado1;
        cout << "  Dado2: " << elemento->info.dado2;
        elemento = elemento->proximo;
    }

    free(elemento);
}

void escrevearquivo(ListaEncadeada &lista, int quant, string tipo) {
    //  Cria uma variável struct dinâmica para receber o primeiro elemento da lista
    Elemento *elemento = lista.primeiro;

    //  Verifica se a lista está vazia
    if (elemento == NULL) {
        cout << "\nLista Vazia!\nArquivo não escrito!\n";
        menu();
    }

    //  Declara o arquivo de saida a ser gerado, definindo o nome
    ofstream arquivo;

    //  Converte inteiro em string
    stringstream result;
    result << quant;

    //  Concatena o tipo de chave geradas, com a quantidade e o extensão txt do
    //  arquivo a ser gerado.
    string nome = (tipo.c_str() + result.str() + ".txt");
    arquivo.open(nome.c_str());


    //  Teste de verificação se o arquivo foi gerado com sucesso
    if (arquivo.fail()) {
        cout << "Error ao criar o arquivo.";
        exit(1);
    }

    //  Realiza a escrita no arquivo enquanto houver dados a ser inseridos
    while (elemento != NULL) {
        arquivo << elemento->info.chave << "  " << elemento->info.dado1 << "  ";
        arquivo << elemento->info.dado2 << endl;
        elemento = elemento->proximo;
    }

    //  Fecha o arquivo
    arquivo.close();

    free(elemento);
}

void lerarquivo(ListaEncadeada &lista, string nome) {
    //  Declara um arquivo de entrada
    ifstream arquivo;

    //  Concatena o nome com a extensão txt
    nome = nome + ".txt";

    //  Verifica se há repetição do nome da extensão
    if (nome.substr(nome.length() - 8, nome.length()) == (".txt.txt")) {
        nome = nome.substr(0, nome.length() - 4);
        cout << nome;
    }

    //  Realiza sua abertura
    arquivo.open(nome.c_str());

    //  Caso falha ao abrir ou arquivo não exitir
    if (arquivo.fail()) {
        cout << "\nArquivo não encontrado!\n";
        menu();
    }

    //  Declara uma variável struct dados para receber os parametros de dentro
    //  do arquivo
    dados dado;

    //  Enquanto não encontrar sinal de final de arquivo, realizará a leitura e
    //  a inserção na lista
    while (!arquivo.eof()) {
        arquivo >> dado.chave >> dado.dado1 >> dado.dado2;
        if (lista.ultimo != NULL) {
            if (dado.chave == lista.ultimo->info.chave) {
                goto fim;
            }
        }
        inserirElemento(lista, dado);
    }

fim:
    //  Mensagem de leitura completa do arquivo
    cout << "\nLeitura completa do arquivo " << nome << "!\n";

    //  Fecha o arquivo
    arquivo.close();
}

bool verificar(ListaEncadeada &lista, tipoChave chave) {
    //  Realiza o laço para verificação de existência de valores iguais.
    //  Caso sim, retorna então verdadeiro(true).
    //  Admite como limite a posição do elemento atualmente sendo inserido.
    Elemento *elementoP = lista.primeiro, *elementoU = lista.ultimo;

    while (elementoP != NULL) {
        if (elementoP->info.chave == chave || elementoU->info.chave == chave) {
            return true;
        }

        elementoP = elementoP->proximo;
        elementoU = elementoU->anterior;

        //  Caso ponteiros de apontem para o mesmo endere?
        if (elementoP == elementoU && elementoP != NULL) {
            if (elementoP->info.chave == chave) {
                return true;
            }
        }
    }
    return false;
}

void gerarchaves(ListaEncadeada &lista, int quant, int op) {
    //  Declaração de variáveis
    tipoChave chave;
    long int dado1;
    int TAM;
    //char dado2[1000];
    dados dado;

    //  Toda vez que executar o programa será gerado um aleatória diferente
    srand(time(NULL));

    //  Laço para gerar a quantidade informada de estrutura com os dados
    for (int i = 0; i < quant; i++) {
        //  Define um tamanho aleatório para a sequencia de caracteres
        //  srand(time(NULL));
        TAM = 1 + (rand() % 10);
        char *dado2 = new char[TAM];

        //  Define um número aleatório para as vari?eis dentro da faixa:

        //  Verifica qual op?o selecionada: 1.Aleatória ou 2.Ordenada
        if (op == 1) {
            //  1 até 10:
            //  srand(time(NULL));
            chave = 1 + (rand() % quant);

            //  Verificação se há uma repetição no laço. Caso sim, gerará um novo
            //  número aleatório e atribuirá a este como sendo o novo valor e então,
            //  a variável j recebe 0 para que possa realizar todas checagens possíveis
            //  e corrigindo caso haja repeti?o. Ao fim, o valor é atribuido às
            //  referentes variáveis
            while (verificar(lista, chave)) {
                //  srand(time(NULL));
                chave = 1 + (rand() % quant);
            }
        } else if (op == 2) {
            //  Crescente a partir do 1:
            chave = i + 1;
        }

        //  Sem limite superior:
        dado1 = 1 + (rand());

        //  Exibe a sequencia de caracteres alphanúmericos
        for (int j = 0; j < TAM; j++) {
            //  Converte para char o número inteiro
            dado2[j] = ('a' + (rand() % 26));
        }

        //  Cria-se uma estrutura com os dados gerados
        dado.chave = chave;
        dado.dado1 = dado1;
        for (int j = 0; j < TAM; j++) {
            dado.dado2[j] = dado2[j];
        }

        //  Insere os elementos gerados em uma Lista Encadeada
        inserirElemento(lista, dado);

        delete dado2;
    }

    //  Informa ao final do laço que a lista foi preenchida
    cout << "\nLista Preenchida!";
}

void buscaSeq(ListaEncadeada &lista, dados &dado) {
    //  Declaração de variáveis
    Elemento *elemento = lista.primeiro;
    int i = 0;

    //  Enquanto elemento não for nulo ou vazio
    while (elemento != NULL) {
        //  Verifica se a chave do elemento corresponde a chave pesquisada
        i++;
        if (elemento->info.chave == dado.chave) {
            //  Informa a posição do registro e atribui o restante dos dados ao dados dado
            cout << "\nPosição encontrada: " << (i + 1) << "? termo\n";
            dado = elemento->info;
            cout << "\nComparações " << i;
            return;
        }
        elemento = elemento->proximo;
    }
    free(elemento);
    i++;
    cout << "\nRegistro não encontrado.";
    cout << "\nComparações " << i;
    dado.chave = -1;
    return;
}

int binaria(dados *v, int inicio, int final, dados &dado) {
    int meio;

    if (inicio < final) {
        meio = (inicio + final) / 2;
        if (v[meio].chave == dado.chave) {
            return meio;
        } else if (v[meio].chave < dado.chave) {
            return binaria(v, meio + 1, final, dado);
        } else if (v[meio].chave > dado.chave) {
            return binaria(v, inicio, meio - 1, dado);
        }
    } else {
        return -1;
    }
}

void buscaSeqRec(ListaEncadeada &lista, dados &dado) {
    Elemento *elemento = lista.primeiro;
    int i = 0, tam = lista.ultimo->info.chave;
    dados * v = new dados[tam];
    while (elemento != NULL) {
        v = elemento->info;
        elemento = elemento->proximo;
        i++;
    }
    int t = binaria(v, 0, tam, dado);
    if (t == -1) {
        cout << "\nRegistro não encotrado.";
    } else {
        cout << "\nChave: " << v[t].chave;
        cout << "  Dado1: " << v[t].dado1;
        cout << "  Dado2: " << v[t].dado2;
    }
}

void iniciarArvore(aponta *s) {
    (*s) = (aponta)malloc(sizeof(TipoNo));
    (*s)->esq = NULL;
    (*s)->dir = NULL;
}

int AVLAltura(aponta *r) {
    if ((*r) == NULL) {
        return 0;
    }
    int esq = AVLAltura(&(*r)->esq);
    int dir = AVLAltura(&(*r)->dir);

    if (esq > dir) {
        return esq + 1;
    }
    return dir + 1;
}

void rotacionaEsq(aponta *r) {
    aponta *aux = (aponta *) malloc(sizeof (TipoNo));
    (*aux) = (*r)->dir;
    (*r)->dir = (*aux)->esq;
    (*aux)->esq = (*r);
    (*r) = (*aux);
    free(aux);
}

void rotacionaDir(aponta *r) {
    aponta *aux = (aponta *) malloc(sizeof (TipoNo));
    (*aux) = (*r)->esq;
    (*r)->esq = (*aux)->dir;
    (*aux)->dir = (*r);
    (*r) = (*aux);
    free(aux);
}

void balancear(aponta *r) {
    if ((*r) == NULL) {
        return;
    }
    balancear(&(*r)->esq);
    balancear(&(*r)->dir);
    int pai = (*r)->FB;
    if (pai == 2) {
        int filho = (*r)->dir->FB;
        if (filho == 1 || filho == 0) {
            rotacionaEsq(&(*r));
        } else if (filho == -1) {
            rotacionaDir(&(*r)->dir);
            rotacionaEsq(&(*r));
        }
    }
    if (pai == -2) {
        int filho = (*r)->esq->FB;
        if (filho == -1 || filho == 0) {
            rotacionaDir(&(*r));
        } else if (filho == 1) {
            rotacionaEsq(&(*r)->esq);
            rotacionaDir(&(*r));
        }
    }
}

void atualizar(aponta * r) {
    if ((*r) == NULL) {
        return;
    }
    (*r)->alturaDir = AVLAltura(&(*r)->dir);
    (*r)->alturaEsq = AVLAltura(&(*r)->esq);
    (*r)->FB = AVLAltura(&(*r)->dir) - AVLAltura(&(*r)->esq);
    atualizar(&(*r)->esq);
    atualizar(&(*r)->dir);
}

void insereAVL(dados dado, aponta * r) {
    if ((*r) == NULL) {
        (*r) = (aponta) malloc(sizeof (TipoNo));
        (*r)->registro = dado;
        (*r)->esq = NULL;
        (*r)->dir = NULL;
        (*r)->FB = 0;
        (*r)->alturaEsq = 0;
        (*r)->alturaDir = 0;
        return;
    }
    if (dado.chave < (*r)->registro.chave) {
        insereAVL(dado, &(*r)->esq);
        (*r)->alturaEsq = AVLAltura(&(*r)->esq);
        (*r)->alturaDir = AVLAltura (&(*r)->dir);
        (*r)->FB = (*r)->alturaDir - (*r)->alturaEsq;
        return;
    }
    if (dado.chave > (*r)->registro.chave) {
        insereAVL(dado, &(*r)->dir);
        (*r)->alturaEsq = AVLAltura(&(*r)->esq);
        (*r)->alturaDir = AVLAltura (&(*r)->dir);
        (*r)->FB = (*r)->alturaDir - (*r)->alturaEsq;
    } else {
        cout << "\nError: O registro já existe!\n";
    }
}

void insereAVN(dados dado, aponta * p) {
    if ((*p) == NULL) {
        (*p) = (aponta) malloc(sizeof (TipoNo));
        (*p)->registro = dado;
        (*p)->esq = NULL;
        (*p)->dir = NULL;
        (*p)->FB = 0;
        (*p)->alturaEsq = 0;
        (*p)->alturaDir = 0;
        return;
    }
    if (dado.chave < (*p)->registro.chave) {
        insereAVN(dado, &(*p)->esq);
        return;
    }
    if (dado.chave > (*p)->registro.chave) {
        insereAVN(dado, &(*p)->dir);
        return;
    }
    if (dado.chave == (*p)->registro.chave) {
        cout << "\nError: O registro já existe!\n";
        return;
    }
}

void buscaAV(dados *dado, aponta * p, int i) {
    if ((*p) == NULL) {
        i++;
        cout << "\nError: Registro não está presente na árvore!\n";
        cout << "\nComparações " << i;
        dado->chave = -1;
        return;
    }
    if (dado->chave < (*p)->registro.chave) {
        i++;
        buscaAV(dado, &(*p)->esq, i);
        return;
    }
    if (dado->chave > (*p)->registro.chave) {
        i++;
        buscaAV(dado, &(*p)->dir, i);
    } else {
        i++;
        cout << "\nComparações " << i;
        *dado = (*p)->registro;
    }
}

void exibirEmOrdem(aponta * p) {
    if ((*p) != NULL) {
        exibirEmOrdem(&(*p)->esq);
        cout << "\nChave: " << (*p)->registro.chave;
        cout << "  Fator Balanceamento: " << (*p)->FB;
        cout << "  Altura Direita . . ." << (*p)->alturaDir;
        cout << "  Altura Esquerda . . ." << (*p)->alturaEsq;
        exibirEmOrdem(&(*p)->dir);
    }
}

bool verifOrd(ListaEncadeada lista) {
    Elemento *elemento = lista.primeiro;

    //  Verifica se a lista está ordenada
    if (elemento->proximo != NULL) {
        if (elemento->info.chave < elemento->proximo->info.chave) {
            while (elemento != NULL && elemento->proximo != NULL) {
                if (elemento->proximo->info.chave < elemento->info.chave) {
                    return true;
                }
                elemento = elemento->proximo;
            }
        } else if (elemento->info.chave > elemento->proximo->info.chave) {
            while (elemento != NULL && elemento->proximo != NULL) {
                if (elemento->proximo->info.chave > elemento->info.chave) {
                    return true;
                }
                elemento = elemento->proximo;
            }
        }
    }
    return false;
}

void menubusca(ListaEncadeada lista, aponta *p, aponta * r) {
    //  Solicita ao usuário que informe uma chave. Atribui este valor
    //  recebido a variável declarada aqui
    dados *dado = (dados *) malloc(sizeof (dados));
    int metodo, chave = 0;
    clock_t tempof, tempo;


pesquisa:
    cout << "\n\nInforme a chave a ser pesquisada: ";
    cin >> chave;
    if (chave <= 0) {
        cout << "\nChave informa está incorreta!\n";
        goto pesquisa;
    }
    dado->chave = chave;

metodo:
    cout << "\nEscolha um metodo de pesquisa:\n ";
    cout << "\n1. Pesquisa Sequencial";
    cout << "\n2. Arvore Não Balanceada";
    cout << "\n3. Arvore Balanceada";
    cout << "\n4. Pesquisa Binária Recursiva";
    cout << "\n\nEscolha: ";
    cin >> metodo;
    if (chave <= 0) {
        cout << "\nO metodo selecionado não encontra-se!\n";
        goto metodo;
    }

    switch (metodo) {
        case 1:
            tempo = clock();
            buscaSeq(lista, *dado);
            tempof = clock() - tempo;
            break;
        case 2:
            tempo = clock();
            buscaAV(&(*dado), &(*p), 0);
            tempof = clock() - tempo;
            break;
        case 3:
            tempo = clock();
            buscaAV(&(*dado), &(*r), 0);
            tempof = clock() - tempo;
            break;
        case 4:
            if (verifOrd(lista)) {
                cout << "\nA Pesquisa Binária Recursiva funciona somente com lista ordenadas!\n";
                cout << "\nSelecione outro metodo de busca:\n";
                goto metodo;
            }
            tempo = clock();
            buscaSeqRec(lista, *dado);
            tempof = clock() - tempo;
            break;
        default:
            cout << "\nOpção Inválida!\n";
            goto metodo;
            break;
    }

    if (metodo >= 1 && metodo <= 3 && dado->chave != -1) {
        cout << "\nChave: " << dado->chave;
        cout << "  Dado1: " << dado->dado1;
        cout << "  Dado2: " << dado->dado2;
    }

    //  Exibe ao usuário o tempo gasto no algoritmo de busca
    cout << "\n\nTempo gasto: " << ((tempof * 1000000) / CLOCKS_PER_SEC) << "ns.\n";

    char op;
    cout << "\nRealizar outra pesquisa? S/N \n";
    cin >> op;
    if (op == 'S' || op == 's') {
        goto pesquisa;
    }

    free(dado);
}

void menu() {
    //  Declara uma variável que receberá a opção desejada pelo usuário
    int op, quant, escolha;
    string tipo, nome;

    //  Cria variável lista
    ListaEncadeada lista;
    criarLista(lista);

    //  Cria variável árvore Não Balanceada
    aponta p;

    Elemento *elemento = (Elemento *) malloc(sizeof (Elemento));

    //  Cria variável árvore Balanceada
    aponta r;

inicio:
    //  Exibe um menu com opções e pede para que o usuário informe uma escolha
    do {
        cout << "\n\nInforme uma escolha:\n";
        cout << "\n1. Gerar chaves de entrada aleat?ias";
        cout << "\n2. Gerar chaves de entrada ordenada.";
        cout << "\n3. Exibir chaves geradas.";
        cout << "\n4. Escrever um arquivo com as chaves geradas.";
        cout << "\n5. Ler arquivo de entrada com chaves";
        cout << "\n6. Realizar uma pesquisa";
        cout << "\n0. Sair do programa.";
        cout << "\n\nEscolha: ";
        cin >> op;

        //  Limpar tela ap? selecionar a escolha
        //  Linux:
        //  system("clear");

        //  Windows
        system("cls");

        switch (op) {
            case 1:
                //  Inicializa-se uma Lista Encadeada
                criarLista(lista);
                cout << "\nInforme a quantidade de chaves a ser geradas: ";
                cin >> quant;
                if (quant <= 0) {
                    cout << "\nQuantidade informada inv?ida!\n";
                    goto inicio;
                }
                gerarchaves(lista, quant, op);
                tipo = ("Aleatorio-");
                escolha = 1;
                break;
            case 2:
                //  Inicializa-se uma Lista Encadeada
                criarLista(lista);
                cout << "\nInforme a quantidade de chaves a ser geradas: ";
                cin >> quant;
                if (quant <= 0) {
                    cout << "\nQuantidade informada inv?ida!\n";
                    goto inicio;
                }
                gerarchaves(lista, quant, op);
                tipo = ("Ordenado-");
                escolha = 2;
                break;
            case 3:
                //  Exibe ao usu?io a lista atualmente em manuseio
                exibeLista(lista, escolha);
                break;
            case 4:
                escrevearquivo(lista, quant, tipo);
                //  Ao final, exibe uma mensagem escrita concluida. E ent?, fecha-se o arquivo.
                cout << "\nArquivo escrito!";
                break;
            case 5:
                //  Inicializa-se uma Lista Encadeada
                criarLista(lista);
                cout << "\nInforme o nome do arquivo: ";
                cin.ignore();
                getline(cin, nome);
                lerarquivo(lista, nome);
                escolha = 3;
                break;
            case 6:
                elemento = lista.primeiro;
                if (lista.primeiro == NULL) {
                    cout << "\nLista Inv?ida!\n";
                    goto inicio;
                } else {
                    cout << "\nInicializando . . .";
                    iniciarArvore(&(p));
                    iniciarArvore(&(r));
                    // Cria variável Elemento dinâmica
                    cout << "\nArvore Iniciada!";
                    while (elemento != NULL) {
                        insereAVN(elemento->info, &(p));
                        insereAVL(elemento->info, &(r));
                        //atualizar(&(r));
                        balancear(&(r));
                        atualizar(&(r));
                        elemento = elemento->proximo;
                    }
                    cout << "\nRaiz da AVN: " << p->registro.chave;
                    cout << "\nRaiz da AVL: " << r->registro.chave;
                    //  Ir?deslocar o usu?io para a fun?o de busca
                    menubusca(lista, &p, &r);
                    //  exibirEmOrdem(&(r));
                }
                break;
            case 0:
                //  Finaliza?o do programa
                cout << "\n\n";
                break;
            default:
                //  Caso nenhuma das anteriores, ?informado ao usu?io que houve sele?o de alternativa inv?ida.
                //  Retorna ao menu principal
                cout << "\nOpçãoo informada inválida!\n";
                goto inicio;
                break;
        }
    } while (op != 0);
    free(elemento);
}

int main() {
    menu();
    cout << "\nSaída com sucesso!\n\n\n";
    return 0;
}

 

[MBruno 0]

Pelo Depurador, indica que o erro está na função insere, mas não consigo achar onde.