MBruno

Estou em duvida na função insereAVN que está sempre dando erro de segmetação quando chaves ordenadas, não passando do valor de 7939. /* * 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 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(); // Função para inicializar a lista 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; } // Função para inserir na lista 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, o dado inserido será o primeiro e o último da lista. if (lista.primeiro == NULL) { lista.primeiro = elemento; lista.ultimo = elemento; }// Senão, a inserção é realizada ao final da lista. else { lista.ultimo->proximo = elemento; elemento->anterior = lista.ultimo; lista.ultimo = elemento; } } // Função para exibir dados da lista 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 exibição dos dados na tela do usuário 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; } // Libera espaço alocado na criação da variável dinâmica free(elemento); } // Função para escrever no arquivo os dados gerados 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. Se sim, retorna ao menu. 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."; menu(); } // 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; // Se o próximo elemento a ser escrito for diferente de NULL, realiza uma quebra de linha if (elemento->proximo != NULL){ arquivo << endl; } elemento = elemento->proximo; } // Fecha o arquivo arquivo.close(); // Libera espaço alocado na criação da variável dinâmica free(elemento); } // Função para ler o arquivo e armazenar os dados na lista 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; } } // Chama a função de inserção na lista, passando o dado e a lista como parametros inserirElemento(lista, dado); } fim: // Mensagem de leitura completa do arquivo cout << "\nLeitura completa do arquivo " << nome << "!\n"; // Fecha o arquivo arquivo.close(); } // Função para verificar se a chave aleatória gerada já existe na lista 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; // Enquanto elementoP for diferente de elementoU realiza o laço de verificação while (elementoP != elementoU) { // Caso a chave do elemento seja igual a chave gerada retorna verdade 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ço e a chave do elemento seja igual a chave gerada if (elementoP == elementoU && elementoP->info.chave == chave) { return true; } // Caso contrário, retorna falso. return false; } // Função para gerar os dados e chaves referentes ao mesmos void gerarchaves(ListaEncadeada &lista, int quant, int op) { // Declaração de variáveis tipoChave chave; long int dado1; int TAM; 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 TAM = 1 + (rand() % 10); // Aloca dinamicamente um vetor de char dado2 char *dado2 = new char[TAM]; // Verifica qual op?o selecionada: 1.Aleatória ou 2.Ordenada if (op == 1) { // 1 até 10: 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)) { chave = 1 + (rand() % quant); } } else if (op == 2) { // Crescente a partir do 1: chave = i + 1; } // Gera dado1 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); // Libera espaço alocado na criação da variável dinâmica delete dado2; } // Informa ao final do laço que a lista foi preenchida cout << "\nLista Preenchida!"; } // Função para realizar a pesquisa sequencial void buscaSeq(ListaEncadeada &lista, dados &dado) { // Declaração de variáveis Elemento *elemento = lista.primeiro; // Contador de comparações 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; } // Libera espaço alocado na criação da variável dinâmica free(elemento); // Caso não encontre, exibe a mensagem na tela do usuário. Declara chave como -1. cout << "\nRegistro não encontrado."; cout << "\nComparações " << i++; dado.chave = -1; return; } // Função recursiva para encontra a chave pesquisada na lista Crescente int binariaC(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 binariaC(v, meio + 1, final, dado); } else if (v[meio].chave > dado.chave) { return binariaC(v, inicio, meio - 1, dado); } } else { return -1; } } // Função recursiva para encontra a chave pesquisada na lista Decrescente int binariaD(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 binariaD(v, meio + 1, final, dado); } else if (v[meio].chave < dado.chave) { return binariaD(v, inicio, meio - 1, dado); } } else { return -1; } } // Função de pesquisa sequencial recursiva void buscaSeqRec(ListaEncadeada &lista, dados &dado) { // Cria variáveis para manipulação na pesquisa sequencial recursiva Elemento *elemento = lista.primeiro; int i = 0, tam, t, op; // Analisa se a lista esta ordenada ou desordenada e declara o tamanho do vetor corretamente if (elemento->info.chave < elemento->proximo->info.chave){ tam = lista.ultimo->info.chave; op = 1; } else if (elemento->info.chave > elemento->proximo->info.chave){ tam = lista.primeiro->info.chave; op = 2; } // Aloca dinamicamente um vetor de dados para armazena a lista e realizar assim, a pesquisa sequencial recursiva dados * v = new dados[tam]; while (elemento != NULL) { v[i] = elemento->info; elemento = elemento->proximo; i++; } // Analisa se a lista esta ordenada ou desordenada e invoca a função certa if (op == 1){ int t = binariaC(v, 0, tam, dado); } else if (op == 2){ int t = binariaD(v, 0, tam, dado); } // Exibe o resultado da pesquisa if (t == -1) { cout << "\nRegistro não encotrado."; } else { cout << "\nChave: " << v[t].chave; cout << " Dado1: " << v[t].dado1; cout << " Dado2: " << v[t].dado2; } // Libera espaço alocado na criação da variável dinâmica delete v; } // Função para incializar a árvore void iniciarArvore(aponta *s) { (*s) = NULL; } // Função que retorna a altura da árvore ou nó 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; } // Função da AVL de rotação para a esquerda void rotacionaEsq(aponta *r) { aponta *aux = (aponta *) malloc(sizeof (TipoNo)); (*aux) = (*r)->dir; (*r)->dir = (*aux)->esq; (*aux)->esq = (*r); (*r) = (*aux); free(aux); } // Função da AVL de rotação para a Direita void rotacionaDir(aponta *r) { aponta *aux = (aponta *) malloc(sizeof (TipoNo)); (*aux) = (*r)->esq; (*r)->esq = (*aux)->dir; (*aux)->dir = (*r); (*r) = (*aux); free(aux); } // Função da AVL para analisar em qual caso encontra-se se o nó estiver desbalanceado 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)); } } } // Função da AVL para atualizar a altura direita,esquerda e Fator de balanceamento de cada nó da árvore. 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); } // Função de inserção da AVL 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"; } } //Função de inserção da AVN 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); } else { cout << "\nError: O registro já existe!\n"; } } // Função de busca na estrutura de árvore 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; } } // Função para exibir os dados presentes na árvore de maneira ordenada 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); } } // Função para verificar se a árvore está ordenada (Crescente ou Decrescente) 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; } // Função menu busca (Exibe ao usuário opções de métodos de busca) do programa 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; 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; 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; } // Libera espaço alocado na criação da variável dinâmica free(dado); } // Função menu principal do programa void menu() { // Declara uma variável que receberá a opção desejada pelo usuário int op, quant, escolha; string tipo, nome; // Cria e inicializa a variável lista ListaEncadeada lista; criarLista(lista); // Cria variável árvore Não Balanceada e Balanceada, respectivamente aponta p, r; // Cria variável dinâmica elemento para manipulação de dados Elemento *elemento = (Elemento *) malloc(sizeof (Elemento)); 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) { // Gerar chaves Aleatórias 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; // Gerar chaves Ordenadas 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; // Exibe ao usuário os dados armazenados case 3: // Exibe ao usu?io a lista atualmente em manuseio exibeLista(lista, escolha); break; // Escrever no arquivo os dados gerados case 4: escrevearquivo(lista, quant, tipo); // Ao final, exibe uma mensagem escrita concluida. E ent?, fecha-se o arquivo. cout << "\nArquivo escrito!"; break; // Ler do arquivo os dados gerados 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; // Realizar pesquisa no dados armazenados 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; // Sair do programa 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); // Libera espaço alocado na criação da variável dinâmica free(elemento); } // Função principal para início do programa int main() { // Invoca a função menu para fornecer ao usuário opções menu(); // Mensagem exibida na tela do usuário quando o programa é finalizado com sucesso cout << "\nSaída com sucesso!\n\n\n"; return 0; }