Estruturas de Dados: Pilha, fila e Lista

Prévia do material em texto

Estruturas de Dados 1
🌑
Estruturas de Dados 
Biblioteca
Para poder estudar essa parte da materia foi necessário baixar uma biblioteca 
chamada cdslib
Implementação Conceitual
Pilha
Na pilha o último elemento que entra é o primeiro que sai
Operações Básicas:
Empilhar: que vai colocando um objeto em cima do outro
Desempilhar: que vai tirando os objetos
Legenda da imagem:
Verde: Está mostrando a quantidade de elementos dentro da pilha e onde sera 
colocado o próximo elemento
Vermelho: Está mostrando o local onde os elementos ficam
Amarelo: Indica a enumeração das "casas" dos elementos
Seta: Mostra a direção em que os elementos vão sendo colocados
Documentação
Pilha
Fila
Na fila o primeiro elemento que entra é sempre o primeiro que sai.
https://iuricardoso.github.io/cdslib/stack_8h.html
Estruturas de Dados 2
Operações Básicas:
Insersação: Adicionar um elemento no final da fila
Remoção: Retirar o primeiro elemento da fila
A fila é baseada em:
Posição Inicial
Tem a função de mostrar onde começa a fila
Muda quando um elemento é tirado, pois sempre é retirado o primeiro 
elemento
Posição Final
Mostra onde termina a fila
Muda quando se adiciona um elemento
Observações
As duas posições ficam iguais quando: A fila está vazia ou cheia
O que define se é um o outro é a quantidade de elementos que tem dentro da 
fila
A fila inicia com lixo, e quando se tira um elemento ele se torna lixo, pois não 
tem como apagar um elemento
Documentação
Fila
Lista
Qualquer momento pode ser adicionado e removido um elemento em qualquer 
posição.
Outras caracteristica da lista é a existencia de diversas operações.
A utilização ideal da lista é usar locação dinâmica, pois se usar vetor não funciona 
muito bem. Porem a biblioteca usada usa uam forma estática.
https://iuricardoso.github.io/cdslib/queue_8h.html
Estruturas de Dados 3
Legenda da imagem:
Vermelho: Esse é o espaço inicial que se tem
Amarelo: É onde indica a quantidade de elementos dentro da lista
Verde: É onde se encontra o primeiro vetor
Exemplo de campo em Azul: Na esquerda temos onde fica o elemento e na direita 
temos onde fica o vetor que vai apontar para o proximo elemento.
Documentação
Lista
Observação
O primeiro campo é nulo e quando se coloca o primeiro elemento esse vetor 
apento para o elemento.
Quando se tira um elemento ou se coloca um elemento, o que vai se alterando 
é os locais onde estava ou vai estar o elemento e para onde os ponteiros 
estão apontando
Exemplo: Se tirar o elemento X, o primeiro vetor vai apontar agora para o 
elemento A, e a "caixa" que antes continha o elemento X e o ponteiro que 
está ao lado dele sumiria.
UTILIZANDO NA LINGUAGEM C
Pilha
Precisar usar a biblioteca stack
#include "stack.h"
Exemplo 1
https://iuricardoso.github.io/cdslib/list_8h.html
Estruturas de Dados 4
#include <stdlib.h>#include <stdio.h>#include "stack.h"void exemploA(void); 
 
int main()
{ 
 exemploA() 
 system("PAUSE"); 
 system("CLS"); 
 
 return 0;
}
void exemploA(void)
{ 
 
 STACK s = stackCreate(3,sizeof(int)); //criando uma pilha de 3 elementos 
 
//por mais que esteja sendo criado um vetor, ele aloca esse vetor 
 
 if (s== NULL) //testando se vai ser possível alocar 
 { 
 printf("ERRO: nao ha memoria suficiente. '\n"); 
 exit(1); 
 } 
 
 
 int e; //vai ser usado para enviar os elementos para empilhar e desempilhar 
 
 
 printf("Pilha tem capacidade para %d elementos. \n", stackCapacity(s)); //passa a pilha
 como parametro 
 
 
 
 e = 10; // primeiro valor 
 
//ao mesmo tempo que a função abaixo empilha ela também testa se da ou não através do if 
 
 if(!stackPush(s, &e)) // se usa o &e pois se consegue empilhar qualquer tipo de dado, en
tão precisa especifica que pode ser um endereço para qual quer coisa 
 
 { 
 printf("Nao foi possivel empilhar %d. Pilha esta cheia!",e); 
 } 
 else 
 { 
 printf("Empilhado: %d\n",e); 
 } 
 
 e = 20; //segundo valor 
 stackPush(s, &e); 
 printf("Empilhado: %d \n", e); 
 
 e = 30; //terçeiro valor 
 stackPush(s, &e); 
 printf("Empilhado: %d \n", e); 
 
 printf("Quantidade de elementos epilhados: %d \n", stackSize(s)); //mostra a quantidad
e de elementos que é 3 nesse caso
if(stackPeekTop(s, &e)) //mostra qual o elemento no topo da pilha 
 { 
 printf("Elemento do topo: %d \n", e); //vai mostrar 30 
Estruturas de Dados 5
 } 
 else 
 { 
 //erro: pilha vazia 
 } 
 
 printf("Tamanho da pilha: %d \n", stackSize(s)); //vai da 3
 e = 100; 
 
 if(!stackPush(s, &e)) 
 { 
 printf("Impossivel empilhar %d. Pilha esta cheia!\n") 
 printf("tamanho da pilha: %d \n \n", stackSize(s)); 
 } 
 else 
 { 
 //empilhou 
 } 
 
 printf("Desempilhando"); 
 while(stackPop(s, &e)) //Aqui temos que enquanto tiver elementos vai desempilhar 
 { 
 printf("%d", e); 
 } 
 
 printf("\n Tamanho da pilha: %d \n", stackSize(s)); 
 
 stackFree(s); //liberando a memória
} 
 
 
Exemplo 2
#include <stdlib.h>#include <stdio.h>#include "stack.h"void exemploB(void); 
 
 
int main()
{ 
 exemploB() 
 system("PAUSE"); 
 system("CLS"); 
 
 
 return 0;
}
struct Livro
{ 
 char titulo[50] 
 int paginas;
}
void exemploB(void)
{ 
 STACK pilha = stackCreate(5, sizeof(struct Livro)); 
Estruturas de Dados 6
 
 struct Livro livro; //criação da váriavel
// É possivel iniciar uma struct dessa forma 
 
 const struct Livro estrut_dad_descomp = 
 { 
 .titulo = "Estrutura de Dados complicada", 
 .paginas = 411 
 }; 
 
 const struct Livro intro_estru_dad = 
 { 
 .titulo = "Introducao a Estruturas de Dados", 
 .paginas = 411 
 }; 
 
 const struct Livro linguagem_c = 
 { 
 .titulo = "Linguagem C Completa e Descomplicada", 
 .paginas = 411 
 }; 
 
 stackPush(pilha, &estrut_dad_descomp); 
 printf("Empilhado: %s, %d pag \n", estrut_dad_descomp.titulo, estrut_dad_descomp.paginas
); 
 
 stackPush(pilha, &intro_estru_dad); 
 printf("Empilhado: %s, %d pag \n", intro_estru_dad.titulo, intro_estru_dad.paginas); 
 
 stackPush(pilha, &linguagem_c); 
 printf("Empilhado: %s, %d pag \n", linguagem_c.titulo, linguagem_c.paginas); 
 
 livro = (struct Livro) 
 { 
 .titulo = "treinamento em Linguagem C", 
 . paginas = 405 
 }; 
 stackPush(pilha, &livro); 
 printf("Empilhado: %s, %d pag \n", livro.titulo, livro.paginas); 
 stackPeekTop(pilha, &livro); 
 
 printf("\n Topo: %s, %d pag \n", livro.titulo, livro.paginas); 
 printf("Quantidade de livros na pilha: %d \n\n", stackSize(pilha));
 StackPop(pilha,%livro); 
 printf("Desempilhando: %s, %d pag \n", livro.titulo, livro.paginas); 
 
 StackPop(pilha,%livro); 
 printf("Desempilhando: %s, %d pag \n", livro.titulo, livro.paginas); 
 
 StackPop(pilha,%livro); 
 printf("Desempilhando: %s, %d pag \n", livro.titulo, livro.paginas); 
 
 StackPop(pilha,%livro); 
 printf("Desempilhando: %s, %d pag \n", livro.titulo, livro.paginas); 
 
 printf("Quantidade de livros na pilha: %d \n\n", stackSize(pilha)); 
 
 stackFree(pilha); 
Estruturas de Dados 7
 
}
Fila
Usa a biblioteca queue
#include "queue.h"
Exemplo
#include <stdio.h>#include "queue" 
 
void imprimeDadosFila(QUEUE f); //funções criadas para auxiliar
void adicionaBoneco(QUEUE f, char boneco[]);
int main()
{ 
 
 QUEUE f = queueCreate(4, sizeof(char *)); // cria uma fila de capacidade máxima para 4 
strings. 
 
 char * boneco; //cria um ponteiro 
 
 
 if (f == NULL) //testando se funciona a alocação 
 { 
 printf("ERRO: não conseguiu alocar a fila.\n"); 
 return 1; 
 }
//Adicionando primeiro elemento 
 
 boneco = "Luke Skywalker"; 
 if (! queueAdd(f, &boneco)) //função para adicionar 
 { 
 printf("ERRO: fila cheia. Não adicionou: '%s'.\n", boneco); 
 } 
 else 
 { 
 printf("Boneco adicionado na fila: %s\n", boneco); 
 
 char * primeiro; //criando um ponteiro para receber uma copia do primeiro elemento 
 if (queuePeek(f, &primeiro)) //função para pegar o primeiro elemento{ 
 printf("Primeiro da fila: %s\n", primeiro); 
 } 
 } 
 
 printf("Tamanho da fila: %d\n\n", queueSize(f)); //testando o tamanho 
 
 // Adiciona segundo elemento 
 
 adicionaBoneco(f, "Axl Rose"); //aqui está sendo usado uma função auxiliar 
 imprimeDadosFila(f); 
 
 // Adiciona terceiro elemento 
 
 adicionaBoneco(f, "Vegeta"); 
Estruturas de Dados 8
 
 imprimeDadosFila(f); //função auxiliar
 // Remove primeiro elemento 
 if (queueRemove(f, &boneco)) //função de remover 
 { 
 printf("Removido: '%s'\n", boneco); 
 } 
 else 
 { 
 printf("Não conseguiu remover boneco da fila\n"); //isso só vai acontecer se a fi
la tiver cheia 
 } 
 imprimeDadosFila(f); //função auxiliar
 // Adiciona Goku na fila 
 adicionaBoneco(f, "Goku"); 
 imprimeDadosFila(f); 
 
 // Adiciona Luke Skywalker na fila 
 adicionaBoneco(f, "Luke Skywalker"); 
 imprimeDadosFila(f); 
 
 // Tenta adicionar Darth Vader, mas fila está cheia. 
 adicionaBoneco(f, "Darth Vader"); 
 imprimeDadosFila(f);
 // Remove todos da fila, um a um. 
 printf("\nRemovendo elementos da fila:\n"); 
 while ( queueRemove(f, &boneco) ) 
 { 
 printf("Elemento removido: '%s'\n", boneco); 
 imprimeDadosFila(f); 
 } 
 
 queueFree(f); //liberando memoria 
 return 0;
}
void imprimeDadosFila(QUEUE f) 
{ 
 char * primeiro; 
 if (queuePeek(f, &primeiro)) 
 { 
 printf("Primeiro da fila: %s\n", primeiro); 
 } 
 printf("Tamanho da fila: %d\n\n", queueSize(f));
} 
 
void adicionaBoneco(QUEUE f, char * boneco) 
{ 
 if (! queueAdd(f, &boneco)) 
 { 
 printf("ERRO: fila cheia. Nao adicionou: '%s'.\n", boneco); 
 } 
 else 
 { 
 printf("Boneco adicionado na fila: %s\n", boneco); 
 }
}
Estruturas de Dados 9
Lista
Usa a biblioteca list.h
#include "list.h"
Exemplo
#include <stdio.h>#include "list.h"void imprimirLista(LIST lista); //função auxiliar
int main() 
{ 
 LIST lista = listCreate(4, sizeof(char *)); //criação da lista, nessa biblioteca ela t
ambém é estática 
 char * e; //essa váriavel é para cada elemento inserido ou retirado 
 int tam; 
 int pos; 
 
 // Imprime a lista vazia! 
 imprimirLista(lista);
 // Adicionando primeiro elemento 
 
 e = "Arroz"; 
 if ( listAdd(lista, &e) != LIST_IS_FULL ) //função para adicionar elemento, se coloca
 o != LIST_IS_FULL para diferencia de quando não for possivel adicionar 
 { 
 printf("Elemento adicionado no final da lista: '%s'\n", e); 
 imprimirLista(lista); 
 } 
 else { 
 // erro: lista cheia! 
 } 
 
 // Adicionando segundo elemento 
 
 e = "Banana"; 
 tam = listAdd(lista, &e); //aqui é para atualizar o tamanho da lista 
 printf("Elemento adicionado no final da lista: '%s'\n", e); 
 printf("Lista agora tem %d elementos.\n", tam); 
 imprimirLista(lista);
 // Adicionando um elemento na posição 1. 
 // O elemento que estava nesta posição, foi para posição 2. 
 
 e = "Feijao"; 
 tam = listAddAtPosition(lista, &e, 1);
//se usa essa função quando se quer adicionar em uma posição especifica 
 switch(tam) //precisa fazer isso pois existe 3 opções que podem ocorrer 
 { 
 case LIST_IS_FULL: // erro: lista cheia 
 break; 
 case INVALID_POSITION: // erro: posição inválida. 
 break; 
 default: 
 printf("Elemento adicionado na posicao 1 da lista: '%s'\n", e); 
 printf("Lista agora tem %d elementos.\n", tam); 
 imprimirLista(lista); 
 break; 
Estruturas de Dados 10
 } 
 
 // Adiciona um elemento na posição 2. 
 // Banana que estava nesta posição, foi para posição 3. 
 
 e = "Macarrao"; 
 tam = listAddAtPosition(lista, &e, 2); 
 switch(tam) 
 { 
 case LIST_IS_FULL: // erro: lista cheia 
 break; 
 case INVALID_POSITION: // erro: posição inválida. 
 break; 
 default: 
 printf("Elemento adicionado na posicao 2 da lista: '%s'\n", e); 
 printf("Lista agora tem %d elementos.\n", tam); 
 imprimirLista(lista); 
 break; 
 }
 // Procura e remove o Feijão da lista 
 
 e = "Feijao"; 
 pos = listRemove(lista, &e); //função para remover elemento, ele funciona comparando o 
elemento com cada elemento da lista (byte com byte) 
 if (pos != NOT_FOUND) //serve para mostrar o elemento removido e a sua posição 
 { 
 printf("Elemento removido lista: '%s'\n", e); 
 printf("Posicao do elemento removido: %d.\n", pos); 
 imprimirLista(lista); 
 } 
 else 
 { 
 // Elemento não encontrado. 
 }
 e = "Arroz"; 
 pos = listGetPosition(lista, &e); 
 if (pos != NOT_FOUND) 
 { 
 printf("'%s' encontrado na posicao %d da lista.\n", e, pos); 
 } 
 else 
 { 
 // Elemento não encontrado. 
 }
 if (listGet(lista, &e, pos) != INVALID_POSITION) 
 { 
 printf("Elemento da posicao %d = '%s'\n", pos, e); 
 } 
 else { 
 // erro: posição definida em 'pos' é inválida! 
 }
 // Remove o elemento da posição 1. 
 tam = listRemoveAtPosition(lista, 2); 
 if (tam != INVALID_POSITION) 
 { 
 printf("\nElemento da posicao 2 foi removido!\n"); 
 } 
 else { 
Estruturas de Dados 11
 // Erro: posição inválida! 
 } 
 imprimirLista(lista); 
 
 listFree(lista); 
 return 0;
}
void imprimirLista(LIST lista) 
{ 
 int i; 
 int f = listSize(lista); //captura o tamanho da lista 
 printf("*** LISTA ***\n"); 
 for(i=0; i<f; i++) //esse for serve para percorre cada elemento da lista 
 { 
 char * e; 
 listGet(lista, &e, i); //para pegar o elemento da lista é necessário indicar a sua 
posição 
 printf("[%d]: %s\n", i, e); 
 } 
 printf("*************\n\n");
}