ATPS_Estrutura_de_dados

1 Introdução 3

2 Relatório 1 – Estrutura de Dados 4

2.1 Relatório e implementação (Etapa 1 – Passo 2) 4

2.1.1 Alocação de memoria 4

2.1.2 Ponteiros em C. 4

2.1.3 Estrutura de dados e C 5

2.1.4 Vetores em C 5

2.1.5 Implementado valores unidimensionais 6

2.1.6 Operações com Strings de caracteres 7

2.1.7 Estrutura em C 9

2.1.8 Implementando estruturas 13

2.2 Atividades (Etapa 1 – Passo 3) 16

2.2.1 Alocação estática de memoria 16

2.2.2 Programa em C – Estrutura avião(struct aviao) 16

3 Relatório 2 – Listas ligadas 24

3.1 Programa em C (Etapa 2 – Passo 2) 24

3.2 Programa em C (Etapa 2 – Passo 3) 29

4 Relatório 3 – Filas e Pilhas 35

4.1 Programa em C (Etapa 3 – Passo 2) 35

4.2 Programa em C (Etapa 3 – Passo 3) 38

5 Relatório 4 – Grafos 43

5.1 Estrutura Grafo (Etapa 4 – Passo 2) 43

5.1.1 Representação de grafos em C 43

5.1.2 Algoritmo de menor caminho 43

5.1.3 Representação por meio de matriz de adjacência 43

5.1.4 Caminho em amplitude 45

5.1.5 Caminho em profundidade 45

5.2 Programa em C (Etapa 4 – Passo 3) 46

6 Conclusão 62

7 Bibliografia 63

 

1 Introdução

Esta ATPS tem como objetivo fixar o conhecimento em alocação de memória, ponteiros estrutura de dado, vetores, pilhas, listas e filas na linguagem C. Realizando pesquisas e desenvolvendo os programas solicitados em cada etapa, assim aplicando o conceito aprendindo.

 

2 Relatório 1 – Estrutura de Dados

2.1 Relatório e implementação (Etapa 1 – Passo 2)

2.1.1 Alocação de memoria

A alocação de memória nas diversas linguagens está relacionada à maneira como estas linguagens tratam a memória e ao momento das amarrações dos nomes (variáveis) às localizações de memória. Linguagens estáticas determinam a utilização da memória em tempo de compilação. Já as linguagens dinâmicas o fazem durante a execução do programa. A seguir são apresentadas as técnicas utilizadas por estes tipos de linguagensPonteiros em C

2.1.2 Ponteiros em C.

Um ponteiro (= apontador = pointer) é um tipo especial de variável que armazena endereços. Um ponteiro pode ter o valor especial

NULL

que não é o endereço de lugar algum. A constante NULL está definida no arquivo-interface stdlib e seu valor é 0 na maioria dos computadores.

Se um ponteiro p armazena o endereço de uma variável i, podemos dizer "p aponta para i" ou "p é o endereço de i" (querendo dizer "o ponteiro p aponta para i" no primeiro caso e "o valor de p é o endereço de i" no segundo). Se um ponteiro p tem valor diferente de NULL então

*p

é o valor do objeto apontado por p. (Não confunda esse uso de "*" com o operador de multiplicação!) Por exemplo, se i é uma variável e p é igual a &i então dizer "*p" é o mesmo que dizer "i".

Há vários tipos de ponteiros: ponteiros para caracteres, ponteiros para inteiros, ponteiros para ponteiros para inteiros, ponteiros para registros etc. O computador faz questão de saber de que tipo de ponteiro você está falando. Para declarar um ponteiro p para um inteiro, diga

int *p;

Para declarar um ponteiro p para um registro cel, diga

struct cel *p;

Um ponteiro r para um ponteiro que apontará um inteiro é declarado assim:

int **r;

2.1.3 Estrutura de dados e C

Estrutura de dados: estudar, manipular, organizar, salvar e extrair informações de uma grande quantidade de dados. Automatizar esse processo para que não precisemos declarar, inicializar e fazer outras operações em nossas variáveis de um modo manual.

2.1.4 Vetores em C

Vetores, também chamados arrays (do inglês) ou arranjo ou ainda matrizes, são uma maneira de armazenar vários dados num mesmo nome de variável através do uso de índices numéricos. Em C, vetores devem sempre conter dados do mesmo tipo de variável.

Declaramos vetores de maneira muito semelhante à declaração de variáveis normais. A única diferença é que depois do nome da variável deve ser informada a quantidade de elementos do vetor. Para declarar um vetor chamado vetor, com cinco elementos inteiros, escrevemos:

int vetor[5];

Note que a quantidade de elementos de um vetor não pode ser alterada depois que o vetor for declarado. Para criar vetores de tamanho dinâmico, podemos usar ponteiros, que serão abordados mais adiante.

Da mesma maneira que podemos inicializar uma variável junto com sua declaração, podemos usar as chaves ({}) para inicializar um array.

int vetor[5] = {17, 42, 9, 33, 12};

Para fazer referência a um valor de um elemento contido em um vetor, usamos a notação vetor[índice], que serve tanto para obter quanto para definir o valor de um elemento específico, dada sua posição. Note que os elementos são numerados a começar do zero, e, portanto, se o número de elementos é N, o índice ou posição do último elemento será N - 1.

vetor[0] = 3;

int x = vetor[2];

int