Listas ligadas, filas e pilhas

Relatório 2 – Listas Ligadas

Alocação de Memória - Nada mais é que reservar um espaço em memória antes que um programa inicie suas funções, mas nem sempre é possível determinar exatamente o espaço em memória que um programa ou uma função especifica necessitará para armazenamento de dados. Desse modo pode se utilizar da Alocação Dinâmica de Memória que reserva espaço em memória no período em que um programa permanece em execução, ou seja, o espaço reservado para armazenamento de dados é ampliado conforme a necessidade do programa. Se não há espaço suficiente para um dado a mais o próprio programa (através de funções especificas “malloc e free” existentes em uma biblioteca denominada “stdlib.h”) reserva um espalho em memória a mais para armazenar novos dados assim sempre haverá espaço disponível para armazenamento de dados enquanto um programa estiver em execução.

A função malloc aloca um bloco de bytes consecutivos na memória do computador, enquanto a função free libera a memória ocupada por uma variável já que na alocação dinâmica as variáveis continuam a existir mesmo depois que a execução da função termina.

Exemplo da utilização de malloc e free:

#include<stdio.h>

#include<stdlib.h>

main(){

int *v, i, j;

printf("Informe um valor: ");

scanf ("%i",&j);

v = malloc(j * sizeof(int));

for(I = 0; i < j; i + +){

printf("\nInforme o numero %i: ", i+1);

scanf("%i",&v[i]);

}

for(i = j -1; i > = 0; i - -){

printf("\nNumero: %i",v[i]);

}

free (v);

v = NULL;

getch();

}

Filas

São conjuntos de elementos, objetos ou qualquer coisa que possa ser numerado e formar um conjunto ordenado como, por exemplo, filas de banco, compras ao serem passadas pelo caixa, listas telefônicas, o alfabeto, linha de produção de veículos, fila de aviões para decolagem, entre outros. Então se diz que filas são estruturas de dados do tipo FIFO (first in, first out), ou seja, primeiro a entrar primeiro a sair, pois o primeiro elemento a entrar sempre será o primeiro a sair sendo que, listas podem ser de tamanho fixo ou variado (flexível).

Listas e Listas Simples Encadeadas

Listas são uma serie de elementos encadeados e em ordem onde o primeiro elemento não só esta ligada ao segundo, mas também indica o segundo elemento como o próximo da lista e assim por diante.

Em linguagem de programação utilizando-se de ponteiros – variáveis que indicam endereços de outras variáveis já que diferentemente de uma lista de compras ou telefônica, as variáveis que precisam ser encontradas ficam armazenadas em espaços de memória que estejam livres no momento tornando-os, aleatórios.

Deste modo o tipo de alocação, para cada novo elemento inserido na estrutura alocamos um novo espaço de memoria para armazena-las, no entanto não temos como acessar essas informações se não continuamente, temos de ir de uma em uma na lista para chegar à informação para consulta, fazendo assim uma demora um pouco maior no processamento, mas ainda sim guarda o espaço estritamente necessário na memoria sem desperdícios.

Através do conhecimento adquirido até o momento, foram gerados os seguintes programas para a empresa aérea Voebem:

Estrutura para Voo

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct Voo{

int num_voo, pass_bordo;

char data_voo[11], hora_voo[6];

char porto_saida[20], porto_chegada[20];

char rota[20], temp_voo[9];

};

void cadastrarVoo();

void consultarVoo();

void removerVoo();

struct Voo *pont;

struct Voo limpa;

int i, j, opc;

main(){

system("cls");

printf("\n=== Empresa Aerea Voebem ===\n");

printf("\n PRINCIPAL \n");

printf("\n| 1 - Cadastrar Voo |");

printf("\n| 2 - Consultar Voo |");

printf("\n| 3 - Remover Voo |");

printf("\n| 4 - Sair |\n");

printf("\nEscolha uma das opcoes: ");

scanf ("%i", &opc);

switch (opc){

case 1:

if(pont == NULL){

pont = (struct Voo *)malloc(100* sizeof(struct Voo));

}

cadastrarVoo();

break;

case 2:

consultarVoo();

break;

case 3:

removerVoo();

break;

case 4:

exit(0);

break;

default: