Fila Pilha Lista Deque

Estruturas de dados clássicas Vetores ou arrays Vetores, ou arrays, são estruturas de dados lineares e estáticas, isto é, são compostas por um número fixo (finito) de elementos de um determinado tipo de dados. O espaço de memória utilizado é alocado em tempo de compilação (declaração das variáveis), ou seja, quando o programa começa a ser executado, as variáveis do tipo vetor já estão alocadas na memória com o número total de elementos. O tempo de acesso aos elementos de um vetor é muito rápido, sendo considerado constante: os elementos são acessados pelo seu índice no vetor. Porém, a remoção de elementos pode ser custosa se não for desejável que haja espaços "vazios" no meio do vetor, pois nesse caso é necessário "arrastar" de uma posição todos os elementos depois do elemento removido. Essa é uma estrutura muito recomendada para casos em que os dados armazenados não mudarão, ou pouco mudarão, através do tempo.

Lista A Lista é uma estrutura de dados linear, composta por uma sequência de nós ou nodos. Existem duas formas de representar as listas: - Alocação sequencial: os nós ocupam posições sequenciais contíguas. - Alocação dinâmica (encadeada): os nós (celulas) apontam para o próximo elemento da lista. Diferentemente dos vetores, na alocação dinâmica a reserva de memória para cada célula (nó) ocorre em tempo de execução do programa. Neste caso, a quantidade máxima de nós em uma lista será determinada pelo tamanho de memória disponível no computador. Outra vantagem da alocação dinâmica sobre a seqüencial é que o gasto de memória é proporcional ao número de nós da lista. Por exemplo, se a lista tiver apenas dois nós, serão gastos bytes de memórias referentes a estes dois nós. Para trabalhar com uma lista dinâmica (ligada), devemos guardar o primeiro elemento da lista. Lista simplesmente encadeada (LSE): cada nó da lista ponta para o próximo nó. A LSE só pode ser percorrida em um único sentido Lista duplamente encadeada (LDE): cada nó da lista aponta para o nó anterior e posterior. A LDE pode ser percorrida em ambos os sentidos Lista Circular: O primeiro nó aponta para o último e o último aponta para o primeiro.

Noções da Linguagem C

pág 1

Pilha . É uma lista linear em que todas as inserções, as remoções e os acessos são feitos em uma única extremidade, chamada topo. São baseadas no princípio LIFO (last in, first out) ou UEPS (Último a entrar, primeiro a sair) onde os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha. Exemplos de pilhas são as pilhas de pratos, pilhas de livros, etc.

Exemplo: Considere a pilha abaixo: 13 19 14 10 Qual será seu o estado final, após executar as seguintes instruções: Pop x Pop y Pop z Push y Push x Push z

14 13 19 10

Noções da Linguagem C

Resposta:

pág 2

Qual será o estado final das pilhas abaixo, após executar as seguintes instruções: 4 3 2 1 A

B

C

Push(B,pop(A)) Push(C,pop(A)) Push(B,pop(A)) Push(C,pop(A)) Push(A,pop(B)) Push(C,pop(B)) Push(C,pop(A)) 2 4 1 3 A

B

C

Resposta:

Noções da Linguagem C

pág 3

Fila As filas são estruturas baseadas no princípio FIFO (first in, first out) ou PEPS (Primeiro a entrar, primeiro a Sair) em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE (incluir - INC), que adiciona um elemento ao final da fila, e DEQUEUE (retirar - DEL), que remove o elemento no início da fila. Ex: fila de bancos, A política de inserção e remoção em filas é conhecida como: A) B) C) D) E)

FILO LIFO UEPS LILO FIFO Resposta: E

A política de inserção e remoção em pilhas é conhecida como: A) B) C) D) E)

LIFO FILO PEPS LILO FIFO Resposta: A

Qual será o estado final da Fila abaixo após executar as instruções:

inicio

Y

INC “X” INC “T” DEL DEL INC “R” INC “J” DEL

F

C

Resposta: C–X–T–R-J

Deque de entrada restrita: A remoção poder ser feita por qualquer extremidade, porém as inclusões podem ser feitas apenas por uma. Deque de saída restrita: A inclusão poder ser feita por qualquer extremidade, porém as remoções podem ser feitas apenas por uma.

Noções da Linguagem C

pág 4

Noções da Linguagem C

pág 5

Estruturas de Dados Encadeadas Dinâmicas - Implementação Física Listas Simplesmente Encadeadas (LSE) A grande diferença da lista para as outras estruturas de dados, é que as listas não possuem critério de inclusão e remoção de dados. Uma lista encadeada tem necessariamente uma variável ponteiro apontando para o seu primeiro elemento. Essa variável será utilizada sempre, mesmo que a lista esteja vazia, e deverá apontar sempre para o início da lista (primeiro elemento). Caso esta primeira variável não seja atualizada corretamente (no caso da inclusão de um elemento na primeira posição), a lista poderá se perder na memória e não ser mais acessível. Um elemento da lista é composto de duas partes: a informação propriamente dita e uma conexão com o próximo elemento. São chamadas de simplesmente encadeadas porque possuem somente o endereço do seu próximo (próximo elemento).

typedef struct celula { int dados; struct celula *proximaCelula; }tipoCelula;

/* campo para os dados */ /* ponteiro para a proxima celula */ /* nome do novo tipo de estrutura */

Uma lista encadeada é toda alocada dinamicamente. Sabemos que a memória alocada dinamicamente não possui um nome como acontece nas variáveis comuns, portanto, todas as listas devem possuir uma variável padrão, do tipo ponteiro, que vai apontar para o seu inicio. Uma vez que o primeiro elemento será uma célula, e cada célula é uma estrutura, então a variável que apontará para o início da lista será um ponteiro de estrutura. A variável início mostrada na figura acima será então definida como: TipoCelula * inicio;

/* ponteiro para uma estrutura tipoCelula */

Uma vez que a lista não possui elementos ainda, então: inicio = NULL; Para uma lista vazia (sem células), a variável inicio possui valor NULL:

Noções da Linguagem C

pág 6

Incluindo o primeiro elemento (primeira célula): TipoCelula aux;

/* variavel auxiliar: ponteiro para uma estrutura tipoCelula

Para reservar memória para nova célula, utilizamos o comando malloc aux = malloc (sizeof (tipoCelula)); Temos então:

e precisamos atualizar os ponteiros para que a lista receba seu primeiro elemento. Sendo assim: 1) aux->proximaCelula = NULL; // atribui NULL ao campo proximacelula da célula apontada por aux 2) inicio = aux; // copia o endereco de aux em inicio

2

Para inserir dados nesta primeira célula, podemos utilizar o ponteiro aux, que permanece apontando para a célula. aux->dados = 10;

/*atribui o valor 10 ao campo dados da célula pontada por aux

Obs: Cada célula de uma lista também é chamada de nó ou nodo O programa a seguir cria uma lista com três nós, conforme exibida a abaixo

inicio matricula proximo

11

2

3

1

Noções da L inguagem C

7

pá

#include <stdio.h> #include <stdlib.h> main( ) { typedef struct no {int matricula; stuct no *proximo; } tipoNo; tipoNo

*inicio,

*novo,

*atual;

/* cria o primeiro registro (nodo 1) */ novo = malloc(sizeof (tipoNo)); /* aloca o nó na memória */ novo->matricula = 1; /* atribui 1 para amatrícula */ novo->proximo = NULL; /* NULL = Fim */ inicio = novo; /* inicio aponta para o primeiro nó */ atual = novo; /* cria o segundo registro (nodo 2) */ novo = malloc(sizeof (tipoNo)); /* instancia o segundo nó */ novo->matricula = 2; novo->Proximo = NULL; /* NULL = Fim */ atual->proximo = novo; /* nó anterior aponta para o segundo lista */ atual = novo; /* cria o terceiro registro (nó 3) */ novo = malloc(sizeof (tipoNo)); /* instancia o terceiro nó */ novo->matricula = 3; novo->Proximo = NULL; /* NULL = Fim */ atual->proximo = novo; /* nó anterior aponta para o segundo lista */ atual = novo; /* exibe os nós da lista */ atual = inicio; while (atual != NULL) { printf("\n matricula = %d ",atual->matricula); atual=atual->proximo; } getchar();

}

Noções da L inguagem C

8

pá

O programa abaixo cria uma lista dinâmica (FILA) com 5 nós, contendo as matrículas: 1, 2, 3, 4, e 5, respectivamente. #include "stdio.h" #include <stdlib.h> main() { typedef struct no {int matricula; struct no *proximo; }tipoNo; tipoNo *inicio, int i; clrscr();

*novo,

*atual;

inicio = atual = NULL; for (i=1;i<6;i++) { novo = malloc(sizeof(tipoNo)); novo->matricula = i; novo->proximo=NULL; if (inicio == NULL) inicio = novo; else atual->proximo = novo; atual = novo; }

/* exibe a lista */ atual = inicio; while (atual != NULL) { printf("\n matricula = %d ",atual->matricula); atual=atual->proximo; } getch(); }

 

Inicio   matricula prox

11

2

3

Noções da L inguagem C

4

5

9

pá

O programa abaixo cria uma lista dinâmica (tipo Pilha) com 3 nós, contendo as matrículas: 1, 2, e 3. topo

matriculaaprox

#include <stdio.h>

3

main() {

2

1

typedef struct no {int matricula; struct no *proximo; }tipoNo; tipoNo

*topo,

*novo,

*atual;

clrscr(); /* inclui primeiro registro na pilha */ novo = malloc(sizeof(tipoNo)); novo->matricula = 1; novo->proximo = NULL; topo = novo; /* inclui segundo registro na pilha */ novo = malloc(sizeof(tipoNo)); novo->matricula = 2; novo->proximo = topo; topo = novo; /* inclui terceiro registro na pilha */ novo = malloc(sizeof(tipoNo)); novo->matricula = 3; novo->proximo = topo; topo = novo; /* exibe os registros da pilha */ atual = topo; while (atual != NULL) { printf("\n matricula = %d ",atual->matricula); atual=atual->proximo; } getch(); }

Será exibido:

matricula = 3 matricula = 2 matricula = 1

Noções da L inguagem C

10

pág

O programa abaixo cria uma lista encadeada do tipo Pilha, com as matrículas, 1, 2,3,4 e 5. #include "stdio.h" main() { typedef struct no {int matricula; struct no *proximo; }tipoNo; tipoNo int i;

*topo,

*novo,

*atual;

clrscr(); topo = atual = NULL; for (i=1;i<6;i++) { novo = malloc(sizeof(tipoNo)); novo->matricula = i; if (topo == NULL) novo->proximo = NULL; else novo->proximo = topo; topo = novo; } /* exibe os registros da pilha */ atual = topo; while (atual != NULL) { printf("\n matricula = %d ",atual->matricula); atual=atual->proximo; } getch(); } Será exibido:

matricula matricula matricula matricula matricula

= = = = =

5 4 3 2 1

topo matricula proximo

15

4

3

Noções da L inguagem C

2

1

11

pág

Percorrendo a lista Para percorrer uma lista (fila ou pilha) temos que utilizar uma variável auxiliar (ponteiro auxiliar). Inicialmente, aux deverá apontar para o início da fila (ou para o topo, no caso das pilhas). Depois, aux receberá o endereço contido no campo proximo, ou seja, receberá o endereço da próxima célula (próximo nó). Enquanto aux for diferente de NULL, repete-se o processo acima. Observe o trecho de programa a seguir que exibirá todos os nós da lista. aux = inicio; while (aux != NULL) { printf("\n matricula = %d ",aux->matricula); aux = aux->proximo; } getchar(); }

Inicio

matricula proximo

11

2

3

Noções da L inguagem C

4

5

12

pág

Incluindo um nó no final da lista (Fila) O último nó da lista não apontava para nenhum outro, agora, este deverá apontar para o novo nó.

Início

27

10 valor

valor

Próximo

Proximo

- se a lista não é vazia, percorrer a lista até a última célula (aux apontará para o último nó) - alocar memória para o novo nó (malloc) - atribuir dados aos campos de dados - atribuir NULL ao campo ponteiro da nova célula incluída - atribuir ao campo ponteiro da última célula o endereço da nova célula

TipoNo

*aux, *inicio, *novo;

if (inicio != NULL) { aux = inicio; while(aux->proximo != NULL) aux = aux->proximo;

}

novo = malloc(sizeof(tipoNo)) novo->valor = 55; novo->proximo = NULL; aux->proximo = novo;

Desta forma, a lista ficará assim:

Início

10 valor

55

27 Proximo

valor

Proximo

Noções da L inguagem C

Valor

Proximo

13

pág

Excluindo o primeiro nó da lista

Início

2

7

Dado

Dado

Prox

3 Prox

apontar aux para o inicio da fila (aux = inicio) início recebe o endereço do segundo nó (inicio = aux-prox retirar o primeiro nó da memória ( free(aux) );

tipoNo *aux, *inicio; aux = inicio; inicio = aux->prox; free(aux);

Dado

Prox

ou inicio = inicio->prox)

/* aux aponta para o início da fila */ /* inicio aponta para o segundo nó */ /* libera da memória do primeiro nó */

A lista ficará da seguinte forma: inicio

Dado

17

prox

3

Noções da L inguagem C

14

pág

Excluindo um nó qualquer da lista Observe a lista: Início

2 Dado

7 Dado

Prox

3 Prox

Dado

Prox

Desejamos fazer a exclusão do nó com valor 7 (segundo nó) - percorrer a lista até o nó anterior ao de valor 7 (primeiro nó) - atribuir o endereço do nó de valor 7 a um ponteiro auxiliar (para poder liberar a memória) - alterar o endereço apontado pelo nó 1, para que ela aponte para onde o nó de valor 7 aponta atualmente (nó 3). - liberar a memória do nó de valor 7 ( free(aux) ) A lista ficará da seguinte forma:

Início

7

2 Dado

Prox

Dado

3 Prox

Dado

Prox

tipoNo aux, apaga; aux = inicio; while(aux->prox->valor != 7) aux = aux->prox; apaga = aux->prox; /* apaga recebe o endereço do nó 2 */ aux->prox = apaga->prox; /* nó 1 aponta para o nó 3 */ free(apaga); /* libera área do nó 2 */

Noções da L inguagem C

15

pág

Listas Duplamente Encadeadas (LDE) As listas duplamente encadeadas são aquelas em que cada nó possui não só o endereço do nó anterior mas também o endereço do próximo nó. Observe o gráfico e a declaração abaixo:

typedef struct celula { struct celula *anterior; int indice; char nome[15]; struct no *proxima; } tipoCelula;

/* ponteiro da celula anterior */ /* campo de dado */ /* campo de dado */ /* ponteiro da proxima célula */

tipoCelula *cabeca, *cauda;

Noções da L inguagem C

16

pág

Exercícios 1) Cite duas características das LSE (listas simplesmente encadeadas)

Resposta: Cada nó aponta para o nó posterior Só pode ser percorrida em um único sentido

2) Cite duas características das LDE (listas duplamente encadeadas)

Resposta: Cada nó aponta para o nó posterior e para o nó anterior Pode ser percorrida nos dois sentidos

3) Cite duas características das estruturas com alocação estática de memória

Resposta: A quantidade de memória a ser alocada para as variáveis é definida em tempo de compilação (na declaração das variávies) A alocação de memória é feita pela quantidade máxima de elementos definida no vetor. Não podemos alterar a quantidade máxima de elementos declarados (e alocados) ao longo da execução do programa.

4) Cite duas características das estruturas com alocação dinâmica de memória

Resposta: A quantidade de memória a ser alocada para as variáveis é definida em tempo de execução. A alocação de memória é feita para cada célula (nó) individualmente. A quantidade máxima de elementos depende exclusivamente da memória total disponível no computador.

5) Sobre o trecho de programa abaixo, pode-se afirmar que: typedef struct no { int char struct no } tipoNo; tipoNo *inicio; A) B) C) D) E) F)

matricula; nome[30]; *proximo;

A) Pode ser a estrutura de uma fila estática B) Pode ser a estrutura de um registro de vetor C) Pode ser a estrutura de uma lista duplamente encadeada D) Pode ser a estrutura de uma lista encadeada dinâmica E) Pode ser a estrutura de uma lista estática

Noções da L inguagem C

17

pág

6) Sobre o trecho de programa abaixo, pode-se afirmar que:

G) H) I) J) K)

typedef struct no { int matricula; char nome[30]; int proximo; } tipoNo; tipoNo x[50]; A) Pode ser a estrutura de uma lista simplesmente encadeada estática B) Pode ser a estrutura de um PILHA dinâmica C) Pode ser a estrutura de uma lista duplamente encadeada D) Pode ser a estrutura de uma lista encadeada dinâmica E) Pode ser a estrutura de uma FILA dinâmica

7) Sobre o trecho de programa abaixo, pode-se afirmar que:

a) b) c) d) e)

Typedef struct no {struct no *anterior ; int matricula; char nome[30]; struct no *proximo; } tipoNo; tipoNo *inicio; A) Pode ser a estrutura de uma fila estática B) Pode ser a estrutura de um registro de vetor C) Pode ser a estrutura de uma lista duplamente encadeada D) Pode ser a estrutura de uma lista encadeada E) Pode ser a estrutura de uma lista estática

8) Sobre o trecho de programa abaixo, pode-se afirmar que: Typedef struct no { int anterior ; int matricula; char nome[30]; int proximo; } tipoNo; tipoNo x[50]; f) A) Pode ser a estrutura de uma Fila dinâmica g) B) Pode ser a estrutura de uma lista duplamente encadeada estática h) C) Pode ser a estrutura de uma lista duplamente encadeada dinâmica i) D) Pode ser a estrutura de uma lista simplesmente encadeada j) E) Pode ser a estrutura de uma Pilha dinâmica

9) A política de inserção e remoção em filas é conhecida como: F) G) H) I) J)

A) FILO B) LIFO C) UEPS D) LILO E) FIFO

Noções da L inguagem C

18

pág

10) A política de inserção e remoção em pilhas é conhecida como: F) G) H) I) J)

A) LIFO B) FILO C) PEPS D) LILO E) FIFO

11) Sobre o deque de saída restrita podemos afirmar que: A) B) C) D) E)

A) Podemos excluir em ambas as extremidades B) Podemos incluir em apenas uma extremidade C) Podemos excluir em apenas uma extremidade D) Não é permitido excluir elementos E) Não é permitido incluir elementos

12) Sobre o deque de entrada restrita podemos afirmar que: A) B) C) D)

A) Podemos incluir em ambas as extremidades B) Podemos incluir em apenas uma extremidade C) Podemos excluir em apenas uma extremidade D) Não é permitido excluir elementos E) Não é permitido incluir elementos

13) Qual será o estado final da fila, após executar as instruções abaixo:

inicio

Y

INC INC INC DEL DEL INC

T

F

“C” “D” “H” “B”

Noções da L inguagem C

19

pág

14) Considerando a pilha ao lado, qual será o seu estado final após executar as seguintes instruções:

22 45 17 5

Pop x Pop y Pop z Pop w Push y Push x Push w Push z

Resposta:

15) Qual será o estado final das pilhas ao lado, após executar as seguintes instruções:

40 31 27 15

Push(B,pop(A)) Push(C,pop(A)) Push(B,pop(A)) Push(C,pop(A)) Push(A,pop(B)) Push(C,pop(B)) Push(C,pop(A))

A

A

B

B

C

C

Resposta:

Noções da L inguagem C

20

pág

16) Percorrendo a lista abaixo, qual a seqüência obtida ? 1

S

2

7

O

4

R

A) B) C) D) E)

A

5

9

B

8

4

5 6

1

7

O

3

3

2 9

E

T

8

BOASORTE BOA SORTE SORTEBOA SORTE BOA SOR TEBOA

17) Percorrendo a lista abaixo, qual a seqüência obtida ? 1

X

2

8

Y

4

R

Z

5

3

T

7

A

3

6 1

C

8

5

9 6

4 9

G

M

7

18) Considerando a lista abaixo que implementa uma PILHA qual será o primeiro e o último valor a ser excluído desta lista? Endereço

Valor proximo

00 K 03

01 W NULL

02 I 06

03 A 05

04 H 02

05 Z 04

06 B 01

19) Suponha que a tabela abaixo represente uma lista encadeada de nomes, organizada sobre os 5 elementos de um vetor. Qual o primeiro elemento desta lista? Elemento Nome Próximo 1 Maria 0 2 Antonio 4 3 João 5 4 Carlos 3 5 Josefina 1

Noções da L inguagem C

21

pág

20) Suponha que a tabela deva representar uma lista duplamente encadeada de cores, organizada sobre os 5 elementos de um vetor: Elemento 1 2 3 4 5

Cor ? ? ? ? ?

Anterior 4 1 2 5 0

Próximo 2 3 0 1 4

Sabendo-se que a ordem das cores na lista é BEGE – VERDE – AZUL – VERMELHO – AMARELO, a coluna intitulada cor, na tabela acima, deveria apresentar, de cima para baixo, o seguinte preenchimento: A) BEGE- VERMELHO-AMARELO-AZUL-VERDE B) AZUL-BEGE-VERDE-VERMELHO-AMARELO C) AMARELO-AZUL-BEGE-VERMELHO-VERDE D) VERMELHO-AZUL-AMARELO-BEGE-VERDE E) AZUL-VERMELHO-AMARELO-VERDE-BEGE

21) Considerando que a lista abaixo encontra-se instanciada na memória, o que será exibido pelo trecho de programa a seguir: aux = inicio; while (aux->proximo != NULL) aux = aux -> proximo; novo = malloc(sizeof(tipoNo)); novo->valor = “F”; novo->proximo = NULL; aux->proximo = novo; aux = inicio; while (aux != NULL) { printf(“\n %c “,aux->valor); aux = aux->próximo; }

inicio proxim o

letr

H

K

Noções da L inguagem C

M

22

pág

Noções da L inguagem C

23

pág