Ajuda - Erro "segmentation fault" programa em c.

francisc0mendes
(usa Ubuntu)

Enviado em 29/07/2014 - 10:24h

Ola, sou novo no forum, e estou fazendo um trabalho de faculdade em c, usando arvores avl e arvores b. Fiz o programa coforme o enunciado, mas fiz usando o windows como sistema operacional, so que depois o professor exigiu que tinha que compilar usando o linux. Usei tanto no windows quanto no linux o compilador gcc. No windows ta tudo perfeito sem erros. Ja ao compilar no linux o programa e compilado, e quando vou executar, da erro de segmentation fault.

Estou quebrando acabe;a e nao consigo achar o erro. Usei o gdb pra debugar e ele apontou problema na linha 157 do arquivo b_voo.c Vou postar o codigo e queria pedir a juda de vocês. Acho que deve ser coisa boba, mas como nao tenho muita experiencia com c ainda, nao estou achando a solucao para meu problema. Conto com todos. Obrigado.

MAIN

#include <stdio.h> // Leitura e escrita de arquivos, printf e scanf
#include <stdlib.h> // Alocamento dinâmico - malloc
#include <string.h> // strcpm (comparação) e strcpy (copia)
#include "data_voo.c" // acesso e atualização dos dados do arquivo data.dat
#include "b_voo.c" // arvore B, acesso e atualização do arquivo index.dat
#include "passageiros.c" // arvore AVL, acesso e atualização do arq. passa.txt

// tabela na memória do programa dos comandos conhecidos
// o ultimo registro não é um comando mas sim um aviso de fim de tabela
char t_com[][3] = {"IV", "RV", "BV", "IP", "BP", "RP", "PP", "IA", "FM","{TTEXTO}{TTEXTO}"};

// função principal do programa
int main(){
char com[3]; //buffer para leitura do comando digitado
char com_code; //codigo sequencial relativo ao comando digitado
char argumento[4][40]; //buffer para os argumentos dos comandos
int i; //variavel auxiliar para utilizar com o for e o while
short horaminuto; // buffer para converter a hora string em hora short int
// para economia de espaço em disco e optimizar calculos
// se fosse necessário
struct P_Voo *raiz_v; // ponteiro para lista encadeada de voos que
// que armazenam as alterações antes de salvar em
// disco com o comando FM, função salva_alterações
unsigned long raiz; // endereço RRN da raiz da árvore B no arquivo index.dat
raiz = carrega_raiz(); // lê os primeiros 4 bytes do arquivo index.dat, onde
// está localizado o RRN da raiz da árvore B
raiz_v = NULL; // registra que a lista encadeada para os vôos que ficam
// temporariamente na memória está vazia
while(1){ // laço indeterminado para leitura de comandos do usuário
// o laço encerra com o comando FM
printf(">>>"); // aviso de prompt, o usuário já pode digitar um comando
scanf("%2s",&com); // lê os dois primeiros caracteres mais o caractere
// 0x00 '{TTEXTO}' de final de string que representa o
// comando digitado
com_code = -1; // registra um código especial para o comando que será
// testado caso não encontre nenhum comando
i=0; // zera o registrador auxiliar que vai percorrer todos os
// elementos da tabela t_com
// laço que percorre toda a tabela t_com até chegar no registro
// 0x00 '{TTEXTO}' 0x00 '{TTEXTO}'
while(!(t_com[i][0]==t_com[i][1] && t_com[i][0] == '{TTEXTO}')){
if(strcmp(com,t_com[i]) == 0){ // compara se o comando digitado
// corresponde ao registro na
// tabela, independente de ser
// maiúscula ou minúscula.
com_code = i; // se for positivo, grava o numero serial do
// registro na tabela e
break; // encerra o percurso antes do fim da tabela
}
i++; // incrementa o registrador auxiliar para apontar para o
// proximo registro da tabela (no contexto)
}
if(com_code == -1){ // se nenhum comando coincidir
printf("ERRO\n"); // informa erro e volta para o prompt, pois
// será ignorado no switch e não tem mais
// nenhum comando depois dessa instrução
}
switch(com_code){ // testa o comando já a partir no número serial
// não seria permitido usar o switch com a string
// do comando digitado porque o C não compara
// nativamente uma string com outra.
case 0: // Comando IV - Insere Vôo
// Espera-se que esse comando só seja usado depois que
// o usuário já informou a lista dos passageiros com o
// comando IP
// Uma vez decifrado o comando, lê a quantidade de argumentos
// esperada. Aqui se utilizou Expressões Regulares para poder
// ler o caractere de espaço (no caso do nome do passageiro,
// quando se separa o prenome do sobrenome), ou seja o scanf
// deve ler o buffer do teclado enquanto o caracter for
// diferente de '@'. Em seguida ele deve ler e descartar o
// arroba e ler mais uma série de caracteres. Como o último
// argumento não termina em '@', mas sim em [ENTER], usamos
// a leitura padrão da função para strings, que tem esse
// comportamento.
scanf(" %[^@]@%[^@]@%[^@]@%[^@]@%s",argumento[0],argumento[1],
argumento[2],argumento[3],argumento[4]);
for(i=0;i<5;i++){ // Vamos percorrer os caracteres do
// argumento[3] para transformá-lo em
// numero inteiro.
// Para cada caracter lido no argumento[3], testamos se
// está no intervalo numérico na tabela ASCII, descartando
// assim os ':', por exemplo, que o usuário digita para
// separar as horas dos minutos.
if(argumento[3][i] >= '0' && argumento[3][i] <= '9'){
// O valor gravado na memória é codificado em BCD (<< 4)
// Binary-Coded Decimal, ou seja, o valor será
// facilmente lido por um humano quando acessar o
// arquivo data.dat pois será como se estivesse em
// decimal, mesmo que gravado em hexadecimal.
//
// A conversão é feita subtraindo o valor do caracter
// '0' do valor lido, já que a tabela ASCII é sequencial
horaminuto = (horaminuto << 4) + argumento[3][i]-'0';
}
}
// Chama a função inserir_voo_b que faz a operação mais complexa
// do programa. Ela primeiro insere o voo no arquivo data.dat,
// que é sequencial, e pega o RRN correspondende para poder
// inserir no index.dat, respeitando a sua posição na arvore B,
// e quando necessário balanceando a mesma. O arquivo passa.txt
// só será alterado quando o programa for finalizado. Caso o
// balanceamento altere a raiz da árvore B, a função retornará
// o endereço RRN da nova raiz, caso o contrário, retornará o
// endereço informado.
raiz = inserir_voo_b(raiz,argumento[0],argumento[1],argumento[2],horaminuto,argumento[4]);
break;
case 1: // Comando RV - Remove Vôo
scanf(" %s",argumento[0]); // Apenas lê a chave do vôo
// Inutiliza o voo da arvore B no arquivo index.dat
// O voo ainda estará "salvo" no data.dat e no passa.txt
remover_b(raiz,argumento[0]);
break;
case 2: // Comando BV - Busca Vôo
scanf(" %s",argumento[0]); // Apenas lê a chave do vôo
// Faz uma busca optimizada na árvore B do arquivo index.dat
busca_voo_b(argumento[0]);
break;
case 3: // Comando IP - Inserir Passageiro
// Segunda função mais complexa do programa. Insere um
// passageiro na arvore AVL da lista encadeada endereçada por
// raiz_v. (é uma lista encadeada de árvores AVLs)
// Se a árvore estiver desbalanceada, ele balanceia, podendo
// inclusive alterar a raiz, retornando a nova raiz nesse caso.
// Caso contrário, retorna a mesma raiz informada.
scanf(" %[^@]@%[^@]@%[^@]@%s",argumento[0],argumento[1],argumento[2],argumento[3]);
raiz_v = adiciona_passageiro(raiz_v,argumento[0],argumento[1],argumento[2],argumento[3]);
break;
case 4: // Comando BP - Busca Passageiro
// Faz uma busca optmizada na árvore AVL
scanf(" %[^ ] %s",argumento[0],argumento[1]);
busca_passageiro(raiz_v, argumento[0],argumento[1]);
break;
case 5: // Comando RP - Remove Passageiro
// Remove o passageiro da árvore e balanceia se for o caso.
scanf(" %[^ ] %s",argumento[0],argumento[1]);
raiz_v = remove_passageiro(raiz_v,argumento[0],argumento[1]);
break;
case 6: // Comando PP - imPrime Passageiros
// Imprime todos os passageiros de uma árvore AVL de um
// determinado vôo "EM ORDEM", representado apenas pelo
// passaporte seguido do seu fator de balanceamento.
scanf(" %s",argumento[0]);
imprime_passageiro(raiz_v,argumento[0]);
break;
case 7: // Comando IA - imprime Índice Atualizado
// imprime o conteúdo do arquivo index.dat, porém formatado.
imprime_b(raiz);
break;
case 8: // Comando FM - FiM do programa
// ao finalizar o programa, salva as alterações da árvore AVL
// registradas na memória RAM para o arquivo passa.txt. Caso
// seja alterado algum voo que já tenha sido adicionado a esse
// arquivo (ou seja, quando o programa for inciado numa outra
// oportunidade), o próprio programa vai fazer uma cópia da
// árvore AVL do voo em questão para a memória RAM, substituindo
// por uma cadeia de caracteres '#', para que quando o programa
// for novamente finalizado, não haja duplicação de registros.
salva_alteracoes(raiz_v);
return 0;
}
}
}


PASSAGEIROS.C

#include "avl_passageiros.c"

// Função semelhante as demais de carregamento de informação
// A diferença está apenas que agora o arquivo é lido na forma
// de texto e não na forma binária. Outra diferença é que os
// campos não tem comprimento fixo, e por isso a função fica
// interando até chegar no caracter de separação.
struct Passageiro * carrega_passageiros(unsigned long RRN){
FILE *f;
char buffer[256] ;
int buffer_pos;
char estado_hash; // referente se estra dentro ou fora das "hash tags"
char estado_campo;
char *destino;
char destino_pos;
char temp[17];
struct Passageiro *primeiro, *passageiro_atual;
estado_hash = 0;
estado_campo = 0;
primeiro = NULL;
passageiro_atual = (struct Passageiro*)malloc(sizeof(struct Passageiro));
destino = &destino_pos;
destino_pos = 0;
f = fopen("passa.txt","r");
if(f == NULL){
f = fopen("passa.txt","w");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return NULL;
}
fclose(f);
f = fopen("passa.txt","r");
}
fseek(f,RRN,SEEK_SET);
buffer_pos = 0;
fgets(buffer, 255, f);
while(buffer[buffer_pos] != '{TTEXTO}' && estado_hash != 3){
if(buffer_pos == 255){
buffer_pos = 0;
fgets(buffer, 255, f);
}
switch(buffer[buffer_pos]){
case '#':
destino[destino_pos] = '{TTEXTO}';
estado_hash++;
if(estado_hash == 1){
destino = temp;
destino_pos = 0;
}
else{
destino = passageiro_atual->passaporte;
destino_pos = 0;
}
break;
case '@':
destino[destino_pos] = '{TTEXTO}';
estado_campo++;
switch(estado_campo){
case 0:
destino = passageiro_atual->passaporte;
break;
case 1:
destino = passageiro_atual->nome;
break;
case 2:
destino = passageiro_atual->poltrona;
break;
case 3:
primeiro = inserir_avl(primeiro, passageiro_atual->passaporte, passageiro_atual->nome, passageiro_atual->poltrona, 0);
estado_campo = 0;
destino = passageiro_atual->passaporte;
}
destino_pos = 0;
break;
default:
destino[destino_pos] = buffer[buffer_pos];
destino_pos++;
}
buffer_pos++;
}
fclose(f);
return primeiro;
}


// semelhante as funções de atualização de informações, porém
// é texto e campos de tamanho variável
unsigned long salva_passageiros(char codigo[17], struct Passageiro *passageiro_atual){
FILE *f;
struct P_Pilha *pilha;
unsigned long RRN;
pilha = NULL;
f = fopen("passa.txt","r+");
if(f == NULL){
f = fopen("passa.txt","w");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return;
}
fclose(f);
f = fopen("passa.txt","r+");
}
fseek(f,0, SEEK_END);
RRN = ftell(f);
fputc('#',f);
fputs(codigo,f);
fputc('#',f);
while(passageiro_atual != NULL){
fputs(passageiro_atual->passaporte,f);
fputc('@',f);
fputs(passageiro_atual->nome,f);
fputc('@',f);
fputs(passageiro_atual->poltrona,f);
fputc('@',f);
passageiro_atual = proximo_avl(passageiro_atual, &pilha);
}
fclose(f);
return RRN;
}

// função que inutiliza uma área do arquivo passa.txt quando os passageiros
// são acrescidos ou removidos depois de utilizado o comando FM, sendo
// esta a solução mais optmizada encontrada, pois não precisará alterar os
// outras arquivos (index.dat e data.dat)
int anula_passageiros(unsigned long RRN){
FILE *f;
char buffer[256];
int buffer_pos;
char estado_hash;
char eof;
char c;
unsigned long pos;
estado_hash = 0;
f = fopen("passa.txt","r+");
if(f == NULL){
f = fopen("passa.txt","w");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return 0;
}
fclose(f);
f = fopen("passa.txt","r+");
}
fseek(f,RRN,SEEK_SET);
eof = 0;
pos = ftell(f);
c = fgetc(f);
eof = feof(f) || eof;
fseek(f, pos, SEEK_SET);
while(c != EOF && estado_hash != 3){
if(c == '#'){
estado_hash++;
}
fflush(f); // importante utilizar o fflush quando troca entre leitura
// e escrita
fputc('#',f);
eof = feof(f) || eof;
pos = ftell(f);
fflush(f);// importante utilizar o fflush quando troca entre leitura
// e escrita
c = fgetc(f);
eof = feof(f) || eof;
fseek(f, pos, SEEK_SET);
}
fclose(f);
}

// Função simples que verifica onde está o voo (memória RAM ou memória ROM), ou
// se é necessário criar um voo novo. Depois chama a função inserir_avl
struct P_Voo * adiciona_passageiro(struct P_Voo *raiz,char codigo[17],char passaporte[10],char nome[40],char poltrona[5]){
struct P_Voo *voo_atual;
struct Passageiro *passageiro_atual;
struct Passageiro *passageiro_anterior;
struct I_Voo indice_atual;
struct B_Pilha *pilha_indice;
struct D_Voo *data_atual;
char tmp[20];
if(raiz != NULL){
// busca da posição onde o elemento será adicionado, procurando
// pelo voo na memória RAM
voo_atual = raiz;
while(voo_atual != NULL){
if(strcmp(voo_atual->codigo, codigo) == 0){
if(voo_atual->primeiro != NULL){
if(strcmp(codigo,voo_atual->codigo) == 0){
voo_atual->primeiro = inserir_avl(voo_atual->primeiro, passaporte, nome, poltrona, 1);
return raiz;
}
}
}
if(voo_atual->proximo != NULL)
voo_atual = voo_atual->proximo;
else
break;
}
// Procura na memória ROM
indice_atual = busca_b(codigo,&pilha_indice);
if(strcmp(indice_atual.chave,"") != 0){
data_atual = carrega_voo(indice_atual.RRN);
voo_atual->proximo = (struct P_Voo *) malloc(sizeof(struct P_Voo));
voo_atual = voo_atual->proximo;
voo_atual->primeiro = carrega_passageiros(data_atual->passageiros);
anula_passageiros(data_atual->passageiros);
voo_atual->primeiro = inserir_avl(voo_atual->primeiro, passaporte, nome, poltrona, 1);
return raiz;
}
// insere se o vôo não for encontrado
voo_atual->proximo = (struct P_Voo *) malloc(sizeof(struct P_Voo));
voo_atual = voo_atual->proximo;
strcpy(voo_atual->codigo, codigo);
voo_atual->proximo = NULL;
voo_atual->primeiro = NULL;
voo_atual->primeiro = inserir_avl(voo_atual->primeiro, passaporte, nome, poltrona, 0);
return raiz;
}
else{
// se a raiz está vazia, procura na memória ROM
indice_atual = busca_b(codigo,&pilha_indice);
if(strcmp(indice_atual.chave,"") != 0){
data_atual = carrega_voo(indice_atual.RRN);
raiz = (struct P_Voo *) malloc(sizeof(struct P_Voo));
voo_atual = raiz;
strcpy(voo_atual->codigo, codigo);
voo_atual->proximo = NULL;
voo_atual->primeiro = NULL;
voo_atual->primeiro = carrega_passageiros(data_atual->passageiros);
anula_passageiros(data_atual->passageiros);
voo_atual->primeiro = inserir_avl(voo_atual->primeiro, passaporte, nome, poltrona, 1);
return raiz;
}
// insere se o vôo não for encontrado
raiz = (struct P_Voo *) malloc(sizeof(struct P_Voo));
strcpy(raiz->codigo, codigo);
raiz->proximo = NULL;
raiz->primeiro = NULL;
raiz->primeiro = inserir_avl(raiz->primeiro, passaporte, nome, poltrona, 0);
return raiz;
}
}

// Função simples que faz a busca de passageiro num vôo na memória RAM ou ROM
int busca_passageiro(struct P_Voo *raiz, char codigo[17],char passaporte[10]){
struct Passageiro *passageiro_atual, *passageiro_primeiro;
struct P_Voo *voo_atual;
struct P_Pilha *pilha_passageiros;
struct I_Voo indice_atual;
struct B_Pilha *pilha_indice;
struct D_Voo *data_atual;
int comparado;
pilha_indice = NULL;
pilha_passageiros = NULL;
voo_atual = raiz;
while(voo_atual != NULL){
if(strcmp(voo_atual->codigo,codigo) == 0){
passageiro_atual = busca_avl(voo_atual->primeiro, passaporte, &pilha_passageiros);
printf("%s %s %s\n",passageiro_atual->passaporte,passageiro_atual->nome,passageiro_atual->poltrona);
return;
}
voo_atual = voo_atual->proximo;
}
pilha_passageiros = NULL;
indice_atual = busca_b(codigo,&pilha_indice);
data_atual = carrega_voo(indice_atual.RRN);
if(strcmp(indice_atual.chave,"") != 0){
passageiro_primeiro = carrega_passageiros(data_atual->passageiros);
passageiro_atual = busca_avl(passageiro_primeiro, passaporte, &pilha_passageiros);
if(strcmp(passageiro_atual->passaporte,passaporte) == 0){
printf("%s %s %s\n",passageiro_atual->passaporte,passageiro_atual->nome,passageiro_atual->poltrona);
return 0;
}
}
printf("ERRO\n");
}

// Função simples que faz a remoção de passageiro num vôo na memória RAM ou ROM
struct P_Voo* remove_passageiro(struct P_Voo *raiz,char codigo[17],char passaporte[10]){
struct P_Voo * voo_atual;
struct Passageiro *passageiro_atual;
struct P_Pilha *pilha;
struct I_Voo indice_atual;
struct B_Pilha *pilha_indice;
struct D_Voo *data_atual;
pilha = NULL;
voo_atual = raiz;
while(voo_atual != NULL){
if(strcmp(codigo,voo_atual->codigo) == 0){
voo_atual->primeiro = remove_avl(voo_atual->primeiro,passaporte);
return raiz;
}
if(voo_atual->proximo != NULL)
voo_atual = voo_atual->proximo;
else
break;
}
indice_atual = busca_b(codigo,&pilha_indice);
if(strcmp(indice_atual.chave,"") != 0){
data_atual = carrega_voo(indice_atual.RRN);
if(raiz != NULL){
voo_atual->proximo = (struct P_Voo *) malloc(sizeof(struct P_Voo));
voo_atual = voo_atual->proximo;
}
else{
raiz = (struct P_Voo *) malloc(sizeof(struct P_Voo));
voo_atual = raiz;
}
strcpy(voo_atual->codigo, codigo);
voo_atual->proximo = NULL;
voo_atual->primeiro = NULL;
voo_atual->primeiro = carrega_passageiros(data_atual->passageiros);
anula_passageiros(data_atual->passageiros);
voo_atual->primeiro = remove_avl(voo_atual->primeiro,passaporte);
return raiz;
}
printf("ERRO\n");
}

// Função simples que faz a impressão em ordem de passageiro num vôo na
// memória RAM ou ROM
int imprime_passageiro(struct P_Voo *raiz,char codigo[17]){
struct P_Voo *voo_atual;
struct Passageiro *passageiro_atual;
struct P_Pilha *pilha_passageiros;
struct I_Voo indice_atual;
struct B_Pilha *pilha_indice;
struct D_Voo *data_atual;
pilha_passageiros = NULL;
pilha_indice = NULL;
voo_atual = raiz;
while(voo_atual != NULL){
if(strcmp(voo_atual->codigo,codigo) == 0){
passageiro_atual = voo_atual->primeiro;
while(passageiro_atual != NULL){
printf("%s %d\n",passageiro_atual->passaporte,balanco_avl(passageiro_atual));
passageiro_atual = proximo_avl(passageiro_atual,&pilha_passageiros);
}
return 0;
}
voo_atual = voo_atual->proximo;
}
indice_atual = busca_b(codigo,&pilha_indice);
if(strcmp(indice_atual.chave,"") != 0){
data_atual = carrega_voo(indice_atual.RRN);
passageiro_atual = carrega_passageiros(data_atual->passageiros);
while(passageiro_atual != NULL){
printf("%s %d\n",passageiro_atual->passaporte,balanco_avl(passageiro_atual));
passageiro_atual = proximo_avl(passageiro_atual,&pilha_passageiros);
}
return 0;
}
printf("ERRO\n");
}

// Função que salva as alterações da árvore AVL no arquivo passa.txt, bem como
// seu endereçamento no arquivo data.dat
int salva_alteracoes(struct P_Voo *raiz){
struct P_Voo *voo_atual;
struct B_Pilha *pilha;
struct I_Voo indice_atual;
struct D_Voo *data_atual;
unsigned long RRN;
voo_atual = raiz;
while(voo_atual != NULL){
indice_atual = busca_b(voo_atual->codigo,&pilha);
if(strcmp(indice_atual.chave, voo_atual->codigo) == 0){
RRN = salva_passageiros(voo_atual->codigo,voo_atual->primeiro);
data_atual = carrega_voo(indice_atual.RRN);
data_atual->passageiros = RRN;
atualiza_voo(data_atual);
}
voo_atual = voo_atual->proximo;
}
}



INDEX_VOO.C

// Estrutura de de vôo utilizada pelo índice, no arquivo index.dat. Ao contrário
// das demais estruturas de vôo ela é usada sempre com endereçamento direto e
// nunca como ponteiro. A razão disso é que na estrutura árvore B, o I_VOO não
// foi escolhido como ponteiro. A razão disso, é que o programa se tornaria
// mais lento se para cada página que alocasse dinamicamente tivesse que alocar
// cada estrutura I_Voo.
struct I_Voo{
char chave[17];
unsigned long RRN;
};

// Página da árvore B
struct Arvore_B{
short entradas;
struct I_Voo voo[2*ORDEM];
unsigned long link[2*ORDEM+1];
unsigned long RRN; //Próprio RRN no arquivo index.dat
};

// Função simples que carrega os primeiros quatro bytes do arquivo index.dat,
// represetando o ponteiro em RRN para a primeira raiz do arquivo. Caso o
// arquivo não exista, ela cria o arquivo e preenche os quatro primeiros bytes
// com 0xFF.
unsigned long carrega_raiz(){
FILE *f;
unsigned long acc;
unsigned char buffer[5];
char i;
f = fopen("index.dat","rb");
if(f == NULL){
f = fopen("index.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
// Caso o arquivo não exista, preenche os 4 primeiros bytes com 0xFF
fputc(0xFF,f);
fputc(0xFF,f);
fputc(0xFF,f);
fputc(0xFF,f);
fclose(f);
f = fopen("index.dat","rb");
}
fgets(buffer,5,f);
i = 0;
acc = 0;
while(i < 4){ // Percorre os primeiros quatro bytes e carrega no sistema
// Little Endian
acc = ((acc << 8) & 0xFFFFFF00) | buffer[i];
i++;
}
fclose(f);
return acc;
}

// Função semelhante a anteirio mas fazendo o oposto, isto é, atualizando uma
// nova posição na raiz
unsigned long salva_raiz(unsigned long RRN){
FILE *f;
unsigned long acc;
unsigned char buffer[5];
char i;
f = fopen("index.dat","rb+");
if(f == NULL){
f = fopen("index.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
fclose(f);
f = fopen("index.dat","rb+");
}
i = 0;
acc = RRN;
while(i < 4){ // Salva no sistema Litlle Endian
fputc((acc & 0xFF000000)>>24,f);
acc = (acc << 8);
i++;
}
fclose(f);
}


// Função que atualiza uma pagina da árvore B no arquivo index.dat a partir
// de uma árvore carregada na memória. É importante que o campo RRN esteja
// definido na memória para que a função realize o resultado esperado. Caso
// você deseje inserir uma nova página, utilize a função abaixo aloca_indice
unsigned long atualiza_indice(struct Arvore_B * arvore){
FILE *f;
unsigned long RRN, acc;
unsigned char campo,seq,len,fim,overflow;
f = fopen("index.dat","rb+");
if(f == NULL){
f = fopen("index.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
fclose(f);
f = fopen("index.dat","rb+");
}
RRN = arvore->RRN;
fseek(f,RRN,SEEK_SET);
fim = 0;
campo = 0;
seq = 0;
len = 0;
overflow = 0;
acc = arvore->entradas;
while(!fim){
switch(campo){
case 0: // Numero de entradas sistema Little Endian
fputc((acc&0xFF00)>>8,f);
acc = (acc & 0xFF) << 8;
len++;
if(len == 2){
len = 0;
acc = 0;
campo++;
}
break;
case 1: // Chave do vôo
if(len == 0){
if(seq < arvore->entradas)
overflow = 0;
else
overflow = 1;
}
if(!overflow){
if(arvore->voo[seq].chave[len] == '{TTEXTO}')
overflow = 1;
fputc(arvore->voo[seq].chave[len],f);
}
else{
if(len != 16){
fputc('#',f);
}
else{
fputc('{TTEXTO}',f);
}
}
len++;
if(len == 17){
len = 0;
campo++;
}
break;
case 2: // RRN para voo correspondente no arquivo data.dat sistema
// Little Endian
if(len == 0){
acc = arvore->voo[seq].RRN;
}
if(seq < arvore->entradas){
fputc((acc&0xFF000000)>>24,f);
acc = (acc&0x00FFFFFF) << 8;
}
else{
fputc(0xFF,f);
}
len++;
if(len == 4){
len = 0;
acc = 0;
if(seq+1 < 2*ORDEM){
seq++;
campo--;
}
else{
seq = 0;
campo++;
}
}
break;
case 3: // Links RRN para outras páginas sistema Little Endian
if(len == 0){
acc = arvore->link[seq];
}
fputc((acc&0xFF000000)>>24,f);
acc = (acc&0x00FFFFFF) << 8;
len++;
if(len == 4){
len = 0;
acc = 0;
if(seq < 2*ORDEM){
seq++;
}
else{
fim = 1;
}
}
}
}
fclose(f);
return RRN;
}

// Grava uma página numa região da memória no final do arquivo index.dat
unsigned long aloca_indice(struct Arvore_B * arvore){
FILE *f;
unsigned long RRN;
f = fopen("index.dat","rb+");
if(f == NULL){
f = fopen("index.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
fclose(f);
f = fopen("index.dat","rb+");
}
fseek(f,0,SEEK_END);
RRN = ftell(f);
arvore->RRN = RRN;
return atualiza_indice(arvore);
}

// Carrega uma página do arquivo index.dat para a memória e retorna o endereço
// onde foi carregado
struct Arvore_B * carrega_indice(unsigned long RRN){
FILE *f;
unsigned long acc;
unsigned char buffer[256], temp[17];
int buffer_pos;
char i,campo,seq,len,fim;
struct Arvore_B * arvore;
arvore = (struct Arvore_B *) malloc(sizeof(struct Arvore_B));
f = fopen("index.dat","rb");
if(f == NULL){
f = fopen("index.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return NULL;
}
fclose(f);
f = fopen("index.dat","rb");
}
buffer_pos = 0;
arvore->RRN = RRN;
fseek(f,0,SEEK_END);
acc = ftell(f);
if(RRN >= acc){
return NULL;
}
fseek(f,RRN,SEEK_SET);
fgets(buffer,256,f);
i = 0;
acc = 0;
campo = 0;
seq = 0;
len = 0;
fim = 0;
temp[16]= '{TTEXTO}';
while(!fim){
if(buffer_pos == 255){
buffer_pos = 0;
fgets(buffer, 256, f);
}
switch(campo){
case 0: // Número de entradas sistema Little Endian
acc = ((acc << 8) & 0xFF00) | buffer[buffer_pos];
len++;
if(len == 2){
arvore->entradas = acc;
len = 0;
acc = 0;
campo++;
}
break;
case 1: // Codigo do voo sistema Little Endian
temp[len] = buffer[buffer_pos];
len++;
if(len == 17){
len = 0;
temp[16] = '{TTEXTO}';
strcpy(arvore->voo[seq].chave,temp);
campo++;
}
break;
case 2: // RRN das informações do Voo no arquivo data.dat sistema
// Little Endian
acc = ((acc << 8) & 0xFFFFFF00) | buffer[buffer_pos];
len++;
if(len == 4){
len = 0;
arvore->voo[seq].RRN = acc;
acc = 0;
if(seq+1 < 2*ORDEM){
seq++;
campo--;
}
else{
seq = 0;
campo++;
}
}
break;
case 3: // Links para outras páginas sistema Little Endian
acc = ((acc << 8) & 0xFFFFFF00) | buffer[buffer_pos];
len++;
if(len == 4){
len = 0;
arvore->link[seq] = acc;
acc = 0;
if(seq < 2*ORDEM){
seq++;
}
else{
fim = 1;
}
}
}
buffer_pos++;
}
fclose(f);
return arvore;
}



DATA_VOO.C

// estrutura que recebe os atributos para os passageiros e também incorpora
// as propriedades da árvore AVL
struct Passageiro{
// atributos dos passageiros
char passaporte[10];
char nome[40];
char poltrona[5];

// propriedades da árvore AVL
struct Passageiro *esquerda;
struct Passageiro *direita;
char coeficiente;
};

// Estrutura que recebe o código do vôo e uma árvore AVL e incorpora as
// propriedades de uma lista encadeada. Ela é utilizada para oraganizar as
// árovres AVL na memória RAM antes de serem transferidas para o arquivo
// passa.txt
// Existem 3 tipos de estruturas para voo: P_Voo, D_Voo e I_Voo
struct P_Voo{
char codigo[17];
struct Passageiro *primeiro; // arvore AVL

// propriedades da lista encadeada
struct P_Voo *proximo;
};

// estrutura que recebe os atributos do voo, adicionados com o comando IV e
// que são registrados no arquivo data.dat. É utilizada para trabalhar com
// essas informações quando as mesmas são carregadas na memória RAM. A variável
// RRN indica o endereço do próprio vôo no arquivo data.dat, a fim de direcionar
// em qual posição do arquivo as informações devem ser atualizadas depois.
struct D_Voo{
char codigo[17];
char partida[4];
char chegada[4];
short horario;
char cia[3];

// a seguir, o tipo unsigned é utilizado para evitar problemas na converção
// de cadeias de carracter para um inteiro de 4 bytes (long)
unsigned long passageiros;
unsigned long RRN; // posição do próprio vôo no arquivo data.dat
};

// função que carrega um vôo especificado pelo endereço RRN e retorna o endereço
// da região da memória em que o voo foi carregado
struct D_Voo* carrega_voo(unsigned long RRN){
FILE *f; // Ponteiro para as variáveis de controle dos processo de leitura
// e escrita em arquivos
unsigned long acc; // Registrador acumulador para converter uma cadeia de
// caracteres em um inteiro de 4 bytes (long)
unsigned char buffer[256], temp[17]; // Buffer de leitura de arquivo
// Variável temporária
int buffer_pos; // Posição do buffer a ser lida
char campo,len,fim; // registrador auxiliar, campo a ser preenchido,
// comprimento já lido (length), e registrador
// de controle de laço.
struct D_Voo * voo; // ponteiro para a região da memória a ser retornada
// Alocação da região da memória
voo = (struct D_Voo *) malloc(sizeof(struct D_Voo));
f = fopen("data.dat","rb"); // Tenta abrir o arquivo para leitura binaria
if(f == NULL){ // Caso não conseguir (i.e. o arquivo não existe)
f = fopen("data.dat","wb"); // Tenta criar o arquivo
if(f == NULL){ // Se não conseguir, informa o erro e encerra a função
printf("Erro de leitura de arquivo.");
fclose(f);
return NULL;
}
fclose(f); // Fecha o arquivo criado e abre novamente para leitura
f = fopen("data.dat","rb");
}
buffer_pos = 0; // Aponta o registrador da posição do buffer para primeira
// posição
voo->RRN = RRN; // Carrega para a região da memória a ser retornada o seu
// respectivo endereço RRN no arquivo data.dat
fseek(f,RRN,SEEK_SET); // Desloca até a posição do arquivo em que as
// informações do vôo se encontram
fgets(buffer,256,f); // Carrega 256 caracteres (255 + '{TTEXTO}')
acc = 0; // Zera o acumulador que lerá as as cadeias de caracteres e
// transformará num inteiro de 4 bytes ou 2 bytes
campo = 0; // Inicializa o registrador informando que está na leitura
// do primeiro campo.
len = 0; // Inicializa o registrador informando que está lendo o primeiro
// caractere do campo
fim = 0; // Inicializa o registrador informando que o loop não chegou
// ao fim
while(!fim){ // Percorre o arquivo data.dat da posição RRN até ler todos
// os capos correspondentes totalizando 34 bytes. O buffer
// é maior, entretanto, caso o programa venha sofrer alguma
// atualização
if(buffer_pos == 255){ // Caso o buffer chegar ao fim, lê os próximos
// 255 caracteres + '{TTEXTO}' e reincia o buffer_pos
buffer_pos = 0;
fgets(buffer, 256, f);
}
switch(campo){ // Executa uma função diferente dependendo do contexto,
// isto é, do campo que está sendo lido
case 0: // Lendo o código do vôo
temp[len] = buffer[buffer_pos]; // Carrega o caractere para o
// buffer temporário
len++; // Incrementa o tamanho de caracteres já lido
if(len == 17){ // Tamanho do campo codigo de vôo
len = 0; // Reseta o registrador de tamanho
temp[16] = '{TTEXTO}'; // Finaliza a string, para ter certeza
strcpy(voo->codigo,temp); // Copia o buffer temporário
// para o região da memória
campo++; // Indica a leitura do próximo campo
}
break;
case 1: // Lendo o código do aeroporto de partida
temp[len] = buffer[buffer_pos];
len++;
if(len == 4){
len = 0;
temp[3] = '{TTEXTO}';
strcpy(voo->partida,temp);
campo++;
}
break;
case 2: // Lendo o código do aeroporto de chegada
temp[len] = buffer[buffer_pos];
len++;
if(len == 4){
len = 0;
temp[3] = '{TTEXTO}';
strcpy(voo->chegada,temp);
campo++;
}
break;
case 3: // Lendo o horário
// Lendo o horário em BCD em sistema Little Endian
acc = ((acc << 8) & 0xFF00) | buffer[buffer_pos];
len++;
if(len == 2){
len = 0;
voo->horario = acc;
acc = 0;
campo++;
}
break;
case 4: // Lendo o código da companhia aéria
temp[len] = buffer[buffer_pos];
len++;
if(len == 3){
len = 0;
temp[2] = '{TTEXTO}';
strcpy(voo->cia,temp);
campo++;
}
break;
case 5: // Lendo o offset que indica a posição da arvore AVL de
// passageiros em sistema Litle Endian
acc = ((acc << 8) & 0xFFFFFF00) | buffer[buffer_pos];
len++;
if(len == 4){
len = 0;
voo->passageiros = acc;
acc = 0;
fim =1;
}
}
buffer_pos++; // Indica a leitura da próxima posição do buffer
}
fclose(f); // Fecha o arquivo
return voo; // Retorna o ponteiro para a região da memória onde as
// informações foram guardadas
}

// Função que salva a estrutura novamente no arquivo data.dat. Para que ela
// funcione corretamente é necessário que o campo RRN da estrutura informada
// esteja definido para uma posição válida. Caso você deseje inserir um novo
// vôo use a função abaixo inserir_voo
unsigned long atualiza_voo(struct D_Voo * voo){
FILE *f;
unsigned long RRN, acc;
unsigned char campo,len,fim;
f = fopen("data.dat","rb+"); // Abre o arquivo para leitura e atulização
// no caso, se abríssemos com wb+, o conteúdo
// já gravado no arquivo seria descartado, por
// que ele trataria como se fosse um novo
// arquivo
if(f == NULL){
f = fopen("data.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
fclose(f);
f = fopen("data.dat","rb+");
}
fseek(f,voo->RRN,SEEK_SET); // Importante ressaltar que essa função só
// funcionará corretamente se o campo RRN da
// região da memória a ser salva estiver
// definido.
RRN = voo->RRN; // Apenas copia o valor de RRN para informar para o return
// Util quando essa função é chamada na função inserir_voo
fim = 0;
campo = 0;
len = 0;
while(!fim){
switch(campo){ // Mesma ideia da função de leitura, só que ao contrário
// Foi utilizado o fputc e não o fputs para garantir que
// todos os bytes da cadeia de caracteres seriam
// copiados e não somente até o '{TTEXTO}'.
case 0: // Código de vôo
fputc(voo->codigo[len],f);
len++;
if(len == 17){
len = 0;
campo++;
}
break;
case 1: // Código de aeroporto de partida
fputc(voo->partida[len],f);
len++;
if(len == 4){
len = 0;
campo++;
}
break;
case 2: // Código de aeroporto de chegada
fputc(voo->chegada[len],f);
len++;
if(len == 4){
len = 0;
campo++;
}
break;
case 3: // Horário em BCD em sistema Little Endian
if(len == 0){
acc = voo->horario;
}
fputc((acc&0xFF00)>>8,f);
acc = (acc&0x00FF) << 8;
len++;
if(len == 2){
len = 0;
campo++;
}
break;
case 4: // Código da companhia aéria
fputc(voo->cia[len],f);
len++;
if(len == 3){
len = 0;
campo++;
}
break;
case 5: // Offset da árvore de passageiros correspondente no arquivo
// passa.txt em sistema Little Endian
if(len == 0){
acc = voo->passageiros;
}
fputc((acc&0xFF000000)>>24,f);
acc = (acc&0x00FFFFFF) << 8;
len++;
if(len == 4){
fim = 1;
}
break;
}
}
fclose(f);
return RRN;
}

// Caso específico da função atualiza_voo, em que o campo RRN da região da
// memória é preenchido automáticamente com a última posição ocupada do
// arquivo data.dat
unsigned long inserir_voo(struct D_Voo * voo){
FILE *f;
f = fopen("data.dat","rb+");
if(f == NULL){
f = fopen("data.dat","wb");
if(f == NULL){
printf("Erro de leitura de arquivo.");
fclose(f);
return -1;
}
fclose(f);
f = fopen("data.dat","rb+");
}
fseek(f,0,SEEK_END); // Desloca para a última posição do arquivo
voo->RRN = ftell(f);
fclose(f);
return atualiza_voo(voo);
}




B_VOO.C

// ORDEM define a ordem da árvore B
#define ORDEM 2
#include "index_voo.c" //manipulação do arquivo index.dat



// Pilha para navegar EM ORDEM pela árvore recursivamente
struct B_Pilha{
struct Arvore_B* arvore;
struct B_Pilha *anterior;
};

// Função interessante que informa qual é o próximo vôo em relação ao vôo
// informado EM ORDEM, sem precisar repercorrer a árvore.
// Além do elemento informado, é necessário informar o endereço do ponteiro (&&)
// para a pilha, para que a função possa saber em qual página se parou e
// indicar qual deverá ser a próxima página acessada. Esse ponteiro deve começar
// apontando incialmente para a raiz da árvore B.
// Essa função trás comodidade para trabalhar, pois não precisamos criar
// uma função recursiva para cada vez que precisarmos percorrer a árvore
// EM ORDEM.
struct I_Voo proximo_b(struct I_Voo atual, struct B_Pilha **pilha){
int i,j; // registradores auxiliares para for e while
char pos,achado; // registrador identificador de posição, e flag se a
// posição foi encontrada
struct Arvore_B *pai, *avo; // ponteiros para páginas auxiliares
struct B_Pilha *push; // ponteiro auxliar para trabalhar com a pilha
/*
* A busca pelo próximo elemento é feita da seguinte maneira, respeitando
* a ordem de prioridades:
* => procura por um voo irmão posterior válido na mesma árvore
* => procura por uma página filha, respeitando a ordem dos links,
* se alguma delas tiver algum vôo
* => procura se alguma página de hereditariedade n tem algum irmão
* posterior de em relação a uma página de hereditariedade n-1
* - filha da página n - que é pai/avo em algum grau do voo atual
*
*/
if(*pilha != NULL){ // se a pilha for nula, não tem como a função descobrir
// o próximo elemento, já que a struct I_Voo não guarda
// nem o pai nem os irmãos, tão pouco os filhos.
pai = (*pilha)->arvore; // carrega a página pai
if(pai->entradas > 0){ // apenas para assegurar que a arvore tem
// um elemento (atual != NULL) e evitar o
// uso não previsto da função
// Prioridade 1
for(pos=0;pos<pai->entradas-1;pos++){ //percorre todos os filhos
// do pai para descobrir
// a posição do voo atual
// na página
if(strcmp(pai->voo[pos].chave, atual.chave) == 0){
for(j=pos+1;j<pai->entradas;j++){ // se encontrou,
// continua percorrendo
// a página para
// procurar se existe
// um próximo irmão
// válido
if(pai->voo[j].chave[0] != '#'){
return pai->voo[pos+1]; // retorna o próximo se
// encontrado
}
}
}
}
// Prioridade 2
for(i=0;i<pai->entradas+1;i++){ // Percorre todos os links da página
// pai
if(pai->link[i] != -1){ // Se o link for válido, busca se tem
// algum filho válido.
for(j=0;j<carrega_indice(pai->link[i])->entradas;j++){
if(carrega_indice(pai->link[i])->voo[j].chave[0] != '#'){
// Como vamos acessar uma página filha em relação a
// página pai do vôo atual, precisamos registrar
// na pilha, para podermos voltar futuramente
push = (struct B_Pilha*) malloc(sizeof(struct B_Pilha));
push->arvore = carrega_indice(pai->link[i]);
push->anterior = (*pilha);
(*pilha) = push;
// retorna o primeiro filho de uma página filha
// válida encontrada
return carrega_indice(pai->link[i])->voo[j];
}
}
}
}
// Prioridade 3
if((*pilha)->anterior != NULL){ // Verifica se o pai do voo atual
// tem outro pai (avo)
// Em caso positivo, carrega o avo para memória e exclui o pai,
// já que a essa altura do algoritmo, temos certeza que todos
// os elementos do pai do atual (inclusive todos os seus filhos
// e netos de qualquer grau) já foram retornados em outra
// oportunidade. O ponteiro pai, porém, ainda nos é útil para
// determinar qual filho o pai é do avô.
push = *pilha;
*pilha = push->anterior;
free(push);
avo = (*pilha)->arvore;
while(avo != NULL){ // enquanto tiver avôs...
// busca qual filho o pai é do avô (1º, 2º, ..., etc)
for(pos=0;pos<avo->entradas+1;pos++){
if(avo->link[pos] == pai->RRN)
break;
}
// busca o próximo irmão válido, se existir
for(i=pos+1;i<(avo->entradas+1);i++){
if(avo->link[i] != -1){
for(j=0;j<push->arvore->entradas;j++){
if(push->arvore->voo[j].chave[0] != '#'){
push = (struct B_Pilha*) malloc(sizeof(struct B_Pilha));
push->arvore = carrega_indice(avo->link[i]);
push->anterior = *pilha;
*pilha = push;
return push->arvore->voo[j];
}
}
}
}
// Se a pilha ainda não chegou no fim, descarta o avô e
// pega o bisavô... e assim por diante
if(*pilha != NULL && (*pilha)->anterior != NULL){
pai = (*pilha)->arvore;
push = *pilha;
*pilha = push->anterior;
free(push);
avo = (*pilha)->arvore;
}
else
break;
}
}
// se não foi encontrado um próximo elemento, então retorna um
// elemento com chave vazia.
strcpy(atual.chave,"");
return atual;
}
}
}

// busca optimizada na árvore B a partir do código de voo (chave)
// É necessário informar o endereço do ponteiro pilha (&&) pois
// essa função permite encontrarmos o voo bem como também em que árvore
// o vôo está, a partir do estado final da pilha.
struct I_Voo busca_b(char chave[17], struct B_Pilha ** pilha){
unsigned long RRN;
struct I_Voo atual;
struct Arvore_B * arvore;
int i;
RRN = carrega_raiz();
while(RRN != -1){
arvore = carrega_indice(RRN); // carrega árvore referida pelo RRN
// coloca na pilha a árvore
*pilha = (struct B_Pilha *) malloc(sizeof(struct B_Pilha));
(*pilha)->anterior = NULL;
(*pilha)->arvore = arvore;
// varre a pagina para encontrar uma chave coincidente
for (i=0;i<arvore->entradas;i++){
atual = arvore->voo[i];
if(strcmp(chave,atual.chave) == 0){
return atual;
}
// se encontrar uma chave "maior" segundo a ordem ASCII,
if(strcmp(chave,atual.chave) < 0){
RRN = arvore->link[i];
break;
}
}
// se não encontrar nenhuma chave "maior", usa o último link
if(i==arvore->entradas){
RRN = arvore->link[i];
}
}
// se a chave não for encontrada, retorna uma chave vazia
strcpy(atual.chave,"");
return atual;
}

// A função maior e mais complexa do programa.
// insere um vôo na árvore B a paritr do RRN no arquivo data.dat e da chave.
unsigned long inserir_b(unsigned long raiz, char chave[17], unsigned long RRN){
struct Arvore_B *atual, *mitose; // ponteiro para percorrer a árvore,
// ponteiro uma nova página, no caso
// de overflow
int i, pos; // registrador auxiliar e de posição
unsigned long prox_RRN, link, prox_link, ret; // valor do proximo RRN,
// valor do link, valor do
// proximo link, valor de
// retorno, RRN temporário
char inser[17],prox[17];
char achado, fim, overflow, mediana, fator; // flags de fim, overflow,
// elemento medio, fator de
// deslocamento na cópia de
// elementos da página
struct B_Pilha *pilha, *push;
ret = raiz;
if(raiz != -1){
// ETAPA 1 - BUSCA A FOLHA EM QUE O ELEMENTO DEVE SER INSERIDO
push = pilha = NULL;
atual = carrega_indice(raiz); // carrega a raiz da árvore
fim = 0;
while(atual->entradas > 0){ // percorre a árvore até chegar nas folhas
achado = 0;
for(pos=0;pos<atual->entradas;pos++){ // escolhe o galho trilhar
// se a chave já existir, então não adiciona nada e simplesmente
// retorna a raiz
if(strcmp(atual->voo[pos].chave, chave) == 0){
return raiz;
}
// quando encontrar a primeira chave maior que a que será
// inserida
if(strcmp(atual->voo[pos].chave, chave) > 0){
achado = 1;
// Verifica se o link é válido
if(atual->link[pos] != -1 && carrega_indice(atual->link[pos])->entradas > 0){
// Carrega na pilha
push = (struct B_Pilha*) malloc(sizeof(struct B_Pilha));
push->anterior = pilha;
push->arvore = atual;
pilha = push;
// Carrega o pagina do link para atual
atual = carrega_indice(atual->link[pos]);
}
else // A pagina do link está vazia
fim = 1;
break;
}
}
if(!achado){ // se a chave for maior que todas, então usa o último
// link
if(atual->link[pos] != -1 && carrega_indice(atual->link[pos])->entradas > 0){
push = (struct B_Pilha*) malloc(sizeof(struct B_Pilha));
push->anterior = pilha;
push->arvore = atual;
pilha = push;
atual = carrega_indice(atual->link[pos]);
}
else
fim = 1;
}
if(fim){
break;
}
}
// ETAPA 2 - INSERE O ELEMNTO DE FORMA INTERATIVA PARA GARANTIR O BALANCEAMENTO
strcpy(prox,chave); //informa que o elemento a ser inserido é a chave
prox_link = -1; // informa que o link do elemento a ser inserido é
// nulo
prox_RRN = RRN; // informa que o RRN (do arquivo data.dat) a ser
// inserido é o chamado no argumento da função
while(atual != NULL){
overflow = atual->entradas == 2*ORDEM; // Se a página a ser inserido
// estiver cheia
mediana = pos == ORDEM; // Se a posição em que deve ser inserido
// o elemento vai deixá-lo no meio
// da página caso ocorra overflow
strcpy(inser,prox); // Recupera o valor a ser inserido
link = prox_link; // Recupera o link a ser inserido
RRN = prox_RRN; // Recupera o RRN a ser inserido
if(overflow){
if(!mediana){ // Se ocorreu overflow, mas não é mediana,
// significa que o elemento será inserido,
// e outro será removido para ser inserido
// na página pai
if(pos > ORDEM){ // Se o elemento for inserido depois do
// meio, copia o ORDEM+1
strcpy(prox,atual->voo[ORDEM].chave);
prox_link = atual->link[ORDEM+1];
prox_RRN = atual->voo[ORDEM].RRN;
}
else{ // Se for antes do meio, copia o ORDEM
// não pode ser "igual ao meio", porque não é
// mediana
strcpy(prox,atual->voo[ORDEM-1].chave);
prox_link = atual->link[ORDEM];
prox_RRN = atual->voo[ORDEM-1].RRN;
}
}
else{ // Se não for mediana, então o elemento não deve ser
// inserido na árvore, já que vai acontecer overflow
// e ele precisará ser removido.
// Nesse caso, coloca ele para ser inserrido na árvore
// pai. Note que esse processo pode se repetir várias
// vezes até que seja necessário criar uma nova raiz.
strcpy(prox,inser);
prox_link = -1;
prox_RRN = RRN;
}
// Se ocorreu overflow, obrigatoriamente teremos que dividir
// a página em duas (mitose). A mitose vai guardar o endereço
// da região da memória onde está a nova página criada.
mitose = (struct Arvore_B *) malloc(sizeof(struct Arvore_B));
// Como a página será dividida ao meio, cada lado ficará com
// ORDEM elementos
mitose->entradas = ORDEM;
// Informa que os links estão nulos, a princípio
for(i=0;i<(2*ORDEM)+1;i++){
mitose->link[i] = -1;
}
// Copia a metade maior dos elementos da página que sofreu
// overflow
for(i=0;i<ORDEM;i++){
fator = 0;
if(pos > ORDEM+1) // Se o elemento a ser inserido estiver
// na metade copiada, deve deixar
// um espaço vago.
fator++;
if(i+fator < ORDEM+1){ // copia os elmentos com o translado
// necessário se for preciso
strcpy(mitose->voo[i].chave,atual->voo[ORDEM+i+fator].chave);
mitose->link[i+1] = atual->link[i+ORDEM+fator+1];
mitose->voo[i].RRN = atual->voo[i+ORDEM+fator].RRN;
}
}
if(!mediana){
// passa o último link órfão para o primeiro link da mitose
mitose->link[0] = atual->link[ORDEM+1];
if(pos>ORDEM+1){
// se o item a ser inserido estiver depois da metade,
// copia ele para a mitose
strcpy(mitose->voo[pos-ORDEM-1].chave,inser);
mitose->link[pos-ORDEM] = link;
mitose->voo[pos-ORDEM-1].RRN = RRN;
}
}
else // se o item a ser inserido estiver na mediana,
// copia o link dele para a primeira posição da
// mitose
mitose->link[0] = link;
aloca_indice(mitose); // salva a pagina mitose no arquivo
//index.dat
}
if(!(overflow && mediana)){ // Caso o elemento a ser inserido
// não seja o mesmo a ser removido
// ele insere o novo elemento
for(i=atual->entradas-1;i>=0;i--){
fator = 0;
if(i >= pos){
fator++;
}
if(fator != 0 && (i+fator < atual->entradas || !overflow)){
strcpy(atual->voo[i+fator].chave, atual->voo[i].chave);
atual->link[i+fator+1] = atual->link[i+1];
atual->voo[i+fator].RRN = atual->voo[i+1].RRN;
}
}
if(overflow) // descarta os elementos já copiados para mitose
atual->entradas = ORDEM;
else
atual->entradas++;
if(pos <= ORDEM || !overflow){ // se for o caso, copia o
// elemento a ser inserido
strcpy(atual->voo[pos].chave, inser);
atual->link[pos+1] = link;
atual->voo[pos].RRN = RRN;
}
}
atualiza_indice(atual); // salva as alterações no arquivo index.dat
// ETAPA 3 - Se ocorreu overflow, coloca o elemento que sobrou na página pai,
// de forma interativa (voltando para etapa 2)
if(overflow){
prox_link = mitose->RRN; // é importante notar que o valor
// prox_link já foi utilizado, como
// sendo o link[0] da mitose, por isso
// pode ser sobreescrito
if(pilha == NULL){ // Se chegou ao topo da árvore
// adiciona uma nova página como raiz
pos = 0;
push = (struct B_Pilha*) malloc(sizeof(struct B_Pilha));
push->anterior = pilha;
push->arvore = (struct Arvore_B*) malloc(sizeof(struct Arvore_B));
push->arvore->entradas = 0;
push->arvore->link[0] = atual->RRN;
for(i=0;i<(2*ORDEM);i++){
push->arvore->voo[i].chave[0] = '{TTEXTO}';
}
for(i=1;i<(2*ORDEM)+1;i++){
push->arvore->link[i] = -1;
}
ret = aloca_indice(push->arvore);
salva_raiz(ret);
pilha = push;
free(mitose);
free(atual);
atual = push->arvore;
pilha = push->anterior;
free(push);
}
else{ // se não chegou ao topo, carrega a próxima página pai
push = pilha;
free(mitose);
free(atual);
atual = push->arvore;
pilha = push->anterior;
free(push);
for(pos=0;pos<atual->entradas;pos++){
if(strcmp(atual->voo[pos].chave,prox) > 0){
break;
}
}
}

}
else{
break;
}
}
}
else{ // Caso a raiz da árvore esteja NULL, simplesmente insere o elemento
atual = (struct Arvore_B *) malloc(sizeof(struct Arvore_B));
atual->entradas = 1;
strcpy(atual->voo[0].chave, chave);
atual->voo[0].RRN = RRN;
for(i=0;i<(2*ORDEM)+1;i++){
atual->link[i] = -1;
}
ret = aloca_indice(atual);
salva_raiz(ret);
}
return ret;
}
// Ufa!

//Função simples que insere o voo, atualizando o index.dat e o data.dat
int inserir_voo_b(unsigned long raiz, char codigo[17], char partida[4], char chegada[4], short horario, char cia[3]){
struct D_Voo *voo;
struct P_Voo *voo_atual;
unsigned long RRN;
voo = (struct D_Voo*) malloc(sizeof(struct D_Voo));
strcpy(voo->codigo, codigo);
strcpy(voo->partida, partida);
strcpy(voo->chegada, chegada);
voo->horario = horario;
strcpy(voo->cia, cia);
voo->passageiros = -1;
RRN = inserir_voo(voo);
inserir_b(raiz,voo->codigo,RRN);
}

// Função simples que apenas inutiliza o registro no arquivo index.dat,
// tornando o voo removido para o usuário
int remover_b(unsigned long raiz, char codigo[17]){
struct Arvore_B *arvore;
struct B_Pilha *pilha;
int i;
char temp[17];
arvore = carrega_indice(raiz);
busca_b(codigo,&pilha);
arvore = pilha->arvore;
for(i=0;i<arvore->entradas;i++){
if(strcmp(arvore->voo[i].chave,codigo) == 0){
strcpy(temp,arvore->voo[i].chave);
sprintf(arvore->voo[i].chave,"#%s",temp);
}
}
atualiza_indice(arvore);
}

// Busca optmizada na árvore B e retorna as informações do arquivo data.dat
int busca_voo_b(char codigo[17]){
struct B_Pilha *pilha;
struct I_Voo voo_indice;
struct D_Voo *voo;
voo_indice = busca_b(codigo,&pilha);
if(strcmp(voo_indice.chave,"") != 0){
voo = carrega_voo(voo_indice.RRN);
if(voo != NULL)
printf("%s %s %s %x:%x %s\n", voo->codigo, voo->partida, voo->chegada, (voo->horario & 0xFF00) >> 8, voo->horario & 0xFF, voo->cia);
else
printf("ERRO\n");
}
else{
printf("ERRO\n");
}
}

// Imprime o arquivo index.dat formatado
int imprime_b(unsigned long raiz){
struct Arvore_B *arvore;
unsigned RRN;
int i;
RRN = 4;
if(raiz != -1){
printf("%lu\n",raiz);
arvore = carrega_indice(RRN);
while(arvore != NULL){
printf("%lx|%d",RRN,arvore->entradas);
for(i=0;i<ORDEM*2;i++){
printf("|%lx|%s,%lx",arvore->link[i],arvore->voo[i].chave,arvore->voo[i].RRN);
}
printf("|%lx|\n",arvore->link[i]);
RRN += 0x6A; // Corrigir para ordem
arvore = carrega_indice(RRN);
}
}
}




AVL_PASSAGEIROS.C


// Pilha de passageiros
struct P_Pilha{
struct Passageiro* passageiro;
struct P_Pilha *anterior;
};

// Calcula o coeficiente da balanço
char balanco_avl(struct Passageiro *raiz){
char balanco;
char altura_esquerda;
char altura_direita;
altura_esquerda = altura_direita = 0;
if(raiz->esquerda != NULL)
altura_esquerda = 1+ raiz->esquerda->coeficiente;
if(raiz->direita != NULL)
altura_direita = 1+ raiz->direita->coeficiente;
balanco = altura_esquerda - altura_direita;
return balanco;
}

// Calcula o coeficiente de altura
char altura_avl(struct Passageiro *raiz){
char balanco;
char altura_esquerda;
char altura_direita;
balanco = 0;
if(raiz != NULL){
altura_esquerda = altura_direita = 0;
if(raiz->esquerda != NULL)
altura_esquerda = 1+ raiz->esquerda->coeficiente;
if(raiz->direita != NULL)
altura_direita = 1+ raiz->direita->coeficiente;
balanco = altura_esquerda > altura_direita ? altura_esquerda : altura_direita;
}
return balanco;
}

// Balança a árvore AVL
struct Passageiro* balanca_avl(struct Passageiro *raiz){
struct Passageiro *temp;
struct Passageiro *nova_raiz;
nova_raiz = raiz;
if(balanco_avl(raiz) > 1){ // Se o lado esquerdo for maior
// Se a sub-arvore tiver sinal contrário
if(raiz->esquerda != NULL && balanco_avl(raiz->esquerda) < 0){
// Rotação para direita (rotação dupla)
temp = raiz->esquerda;
raiz->esquerda = temp->direita;
temp->direita = raiz->esquerda->esquerda;
raiz->esquerda->esquerda = temp;
temp->coeficiente = altura_avl(temp);
raiz->esquerda->coeficiente = altura_avl(raiz->esquerda);
}
// Rotação para esquerda
if(raiz->esquerda != NULL){
nova_raiz = raiz->esquerda;
raiz->esquerda = nova_raiz->direita;
nova_raiz->direita = raiz;
if(raiz->esquerda != NULL)
raiz->esquerda->coeficiente = altura_avl(raiz->esquerda);
raiz->coeficiente = altura_avl(raiz);
nova_raiz->coeficiente = altura_avl(nova_raiz);
}
else{
nova_raiz = raiz;
}
}
else if(balanco_avl(raiz) < 1){// Se o lado direito for maior
if(raiz->direita != NULL && balanco_avl(raiz->direita) > 0){
// Rotação para esquerda (rotação dupla)
temp = raiz->direita;
raiz->direita = temp->esquerda;
temp->esquerda = raiz->direita->direita;
raiz->direita->direita = temp;
temp->coeficiente = altura_avl(temp);
raiz->direita->coeficiente = altura_avl(raiz->direita);
}
if(raiz->direita != NULL){
// Rotação para direita
nova_raiz = raiz->direita;
raiz->direita = nova_raiz->esquerda;
nova_raiz->esquerda = raiz;
if(raiz->direita != NULL)
raiz->direita->coeficiente = altura_avl(raiz->direita);
raiz->coeficiente = altura_avl(raiz);
nova_raiz->coeficiente = altura_avl(nova_raiz);
}
else{
nova_raiz = raiz;
}
}
return nova_raiz;
}


// Simples busca interativa optmizada
struct Passageiro* busca_avl(struct Passageiro *raiz, char passaporte[10], struct P_Pilha **pilha){
struct Passageiro* atual;
char cmp;
struct P_Pilha *push;
atual = raiz;
while(atual != NULL){
cmp = strcmp(atual->passaporte,passaporte);
if(cmp == 0){
return atual;
}
else{
if(cmp < 0){
if(atual->esquerda != NULL){
push = (struct P_Pilha*) malloc(sizeof(struct P_Pilha));
push->anterior = *pilha;
push->passageiro = atual;
*pilha = push;
atual = atual->esquerda;
}
else
return atual;
}
else{
if(atual->direita != NULL){
push = (struct P_Pilha*) malloc(sizeof(struct P_Pilha));
push->anterior = *pilha;
push->passageiro = atual;
*pilha = push;
atual = atual->direita;
}
else
return atual;
}
}
}
}

// Função complexa, porém análoga a função inserir_b, pois a árvore B é uma
// generalização da árvore AVL
struct Passageiro* inserir_avl(struct Passageiro *raiz, char passaporte[10], char nome[40], char poltrona[5], char balanceamento){
struct Passageiro* atual;
struct Passageiro* pai;
struct P_Pilha *pilha,*push;
char balanco;
char cmp;
if(raiz != NULL){
// ETAPA 1 - Busca em qual folha da árvore será inserido
pilha = NULL;
push = pilha;
pai = atual = busca_avl(raiz,passaporte,&pilha);
push = (struct P_Pilha*) malloc(sizeof(struct P_Pilha));
push->anterior = pilha;
push->passageiro = atual;
pilha = push;
if(atual->passaporte == passaporte){
//printf("Passaporte duplicado!\n");
return raiz;
}
cmp = strcmp(atual->passaporte,passaporte);
if(cmp < 0){
atual->esquerda = (struct Passageiro *) malloc(sizeof(struct Passageiro));
atual = atual->esquerda;
}
else{
atual->direita = (struct Passageiro *) malloc(sizeof(struct Passageiro));
atual = atual->direita;
}
// ETAPA 2 - Insere o Elemento
strcpy(atual->passaporte,passaporte);
strcpy(atual->nome,nome);
strcpy(atual->poltrona,poltrona);
atual->esquerda = NULL;
atual->direita = NULL;
atual->coeficiente = 0;
// ETAPA 3 - Balanceamento interativo
pai = raiz;
while(atual != NULL){
atual->coeficiente = altura_avl(atual);
balanco = balanco_avl(atual);
if((balanco > 1 || balanco < -1) && balanceamento){
if(pilha != NULL){
if(pilha->passageiro->esquerda == atual){
pilha->passageiro->esquerda = balanca_avl(atual);
}
else{
pilha->passageiro->direita = balanca_avl(atual);
}
}
else{
pai = atual = balanca_avl(atual);
}
}
if(pilha != NULL){
atual = pilha->passageiro;
push = pilha;
pilha = push->anterior;
free(push);
}
else
break;
}
}
else{
// Se não tiver nenhum elemento, simplesmente adiciona
atual = (struct Passageiro *) malloc(sizeof(struct Passageiro));
strcpy(atual->passaporte,passaporte);
strcpy(atual->nome,nome);
strcpy(atual->poltrona,poltrona);
atual->esquerda = NULL;
atual->direita = NULL;
atual->coeficiente = 0;
pai = atual;
}
return pai;
}

// Função análoga a função proximo_b, mas simplificado
struct Passageiro * proximo_avl(struct Passageiro *raiz, struct P_Pilha **pilha){
struct Passageiro *atual;
struct P_Pilha *push;
if(raiz->esquerda != NULL){
push = (struct P_Pilha*) malloc(sizeof(struct P_Pilha));
push->passageiro = raiz;
push->anterior = *pilha;
*pilha = push;
return raiz->esquerda;
}
if(raiz->direita != NULL){
push = (struct P_Pilha*) malloc(sizeof(struct P_Pilha));
push->passageiro = raiz;
push->anterior = *pilha;
*pilha = push;
return raiz->direita;
}
atual = raiz;
while(1){
if((*pilha) == NULL){
break;
}
if((*pilha)->passageiro->esquerda == atual && (*pilha)->passageiro->direita == NULL){
atual = (*pilha)->passageiro;
push = *pilha;
*pilha = push->anterior;
free(push);

}
else if((*pilha)->passageiro->direita == atual){
atual = (*pilha)->passageiro;
push = *pilha;
*pilha = push->anterior;
free(push);
}
else
break;
}
if((*pilha) == NULL)
return NULL;
return (*pilha)->passageiro->direita;
}

// Função que realmente remove, ao contrário da árvore B
struct Passageiro* remove_avl(struct Passageiro *raiz, char passaporte[10]){
struct P_Pilha *pilha;
struct Passageiro *atual, *swap;
pilha = NULL;
atual = busca_avl(raiz,passaporte,&pilha);
if(strcmp(atual->passaporte,passaporte) == 0){
// Busca o elemento para substituir o elemento a ser removido
if(atual->direita != NULL){
swap = atual->direita;
while(swap->esquerda != NULL || swap->direita != NULL){
if(swap->esquerda != NULL){
swap = swap->esquerda;
}
else{
swap = swap->direita;
}
}
// Faz as substituições
swap->esquerda = atual->esquerda;
if(swap != atual->direita)
swap->direita = atual->direita;
else
swap->direita = NULL;
if(pilha != NULL){
if(pilha->passageiro->esquerda == atual){
pilha->passageiro->esquerda = swap;
}
else{
pilha->passageiro->direita = swap;
}
}
else{
raiz = swap;
}
}
else{ // Caso não exista uma folha do lado direito, simplemente
// remove o elemento e no lugar dele coloca o seu galho
// esquerdo.
if(pilha != NULL){
if(pilha->passageiro->esquerda == atual){
pilha->passageiro->esquerda = atual->esquerda;
}
else{
pilha->passageiro->direita = atual->esquerda;
}
}
else{
raiz = atual->esquerda;
}
}
}
raiz = balanca_avl(raiz);
return raiz;
}

Thihup
(usa Manjaro Linux)

Enviado em 29/07/2014 - 21:22h

Amigo para visualizar melhor e manter a identação faça isso

digite
["code"]
Aqui Vai todo o codigo
[/"code"]

Sem Aspas

Te +

igormorais
(usa Gentoo)

Enviado em 30/07/2014 - 08:32h

Pois é cara, não li o código porque ficou bem cansativo de ler. Mas se tá dando Falha de Segmentação é porque você tá tentando usar algum local que não foi alocado ou tá desalocando errado, enfim: revise seus ponteiros. Eu tô fazendo uma AVL agora, mas em Java.

paulo1205
(usa Ubuntu)

Enviado em 30/07/2014 - 11:28h

Edite sua postagem original e coloque o código de cada arquivo cercado pelas tags “[code]” e “[/code]”.

O programa como um todo é relativamente grande, especialmente para nós que não estamos com ele “na pele”. Por isso, será mais fácil ajudarmos você a encontrar o bug do que nós mesmos o encontrarmos.

Você mencionou que usou o GDB, o que é um bom sinal. Compilando com a opção “-g” do gcc, ele vai incluir símbolos de depuração no código executável, de modo que você vai poder, no momento da falha, examinar os valores das variáveis. Como você indicou a linha 157 do arquivo b_voo.c, que, se você nem eu tivermos errado na hora do copy-and-paste, parece ser a linha abaixo.

for (i=0;i<arvore->entradas;i++){ 

A única chance de falha de segmentação nessa linha é o valor do ponteiro arvore ter um valor inválido. Para chegar nessa situação, o programa vai depender muito de tudo o que aconteceu antes, até chegar nessa linha de código.

Eu achei a sua divisão do programa em módulos um tanto estranha. Em particular, incluir arquivos ".c" não é muito usual. Mais correto seria você separar declarações em arquivos de cabeçalho (headers, donde vem a extensão usual ".h"), e deixar as definições em arquivos ".c".

Outra coisa estranha: você abre e fecha o mesmo arquivo de dados várias vezes ao longo do programa, o que não é muito usual -- nem desejável, por causa de desempenho. Tipicamente, um programa abre o arquivo de dados no início da execução, e permanece com ele aberto ao longo da vida inteira do programa. Mesmo se o arquivo for compartilhado com outros processos, o usual seria usar locks para evitar acessos simultâneos a regiões críticas do arquivo.