TRABALHO DE ESTRUTURAS DE DADOS LISTA, FILA E PILHA

Prévia do material em texto

BACHARELADO EM SISTEMA DE INFORMAÇÃO 
TRABALHO SOBRE LISTA, FILA E PILHA 
NOME: EVALDO FARIAS FURTADO 
DISCIPLINA: ESTRUTURA DE DADOS 
PROFESSOR: ERICK JERONIMO 
 
 
1. LISTA 
Uma estrutura tipo lista representa um conjunto de dados organizados 
em ordem linear, a estrutura lista e feita pela utilização de vetores na 
representação, o uso de endereço contiguo, que em algumas situações exige 
maior esforço do computador. Possui um ponteiro para próximo elemento, ou 
seja, elementos encadeados denominadas lista dinâmica. 
Quando um elemento de uma lista contém apenas um dado primitivo, 
como um número, é chamado de lista homogênea, quando uma lista contém um 
dado composto, chama-se lista heterógena. 
1.1 LISTAS LINEARES SEQUENCIAIS 
Em listas lineares sequenciais, os dados são armazenados em 
endereços de memória sequencial ou contíguos, ou seja, um dado após o outro. 
Dessa forma temos uma estrutura estática. Em estrutura estática, a alocação de 
memória é feita durante a compilação do programa. Consequentemente, deve-
se pré-determinar a quantidade máxima de elementos da lista. 
É uma lista linear na qual a ordem lógica dos elementos (a ordem 
“vista” pelo usuário) é a mesma ordem física (em memória principal) dos 
elementos. Isto é, elementos vizinhos na lista estarão em posições vizinhas de 
memória. 
Sequencial ou Contígua 
Numa lista linear contígua, os nós além de estarem em uma 
sequência lógica, estão também fisicamente em sequência. A maneira mais 
simples de acomodar uma lista linear em um computador é através da utilização 
de um vetor. 
Imagem 1.1 lista sequencial 
 
 
A representação por vetor explora a sequencialidade da memória de 
tal forma que os nós de uma lista sejam armazenados em endereços contíguos. 
 
Código 1.1 - Lista Sequencial 
#include <stdio.h> 
#include <stdlib.h> 
struct lista 
{ 
 int a; 
 struct lista *prox; 
}; 
typedef struct lista Lista; 
void inclui(Lista**,int); 
Lista* criaTermo(void); 
void liberaMemoria(Lista **); 
int main(void) 
{ 
 Lista *lis=NULL; 
 /* programa */ 
 liberaMemoria(&lis); 
 return 0; 
} 
void inclui(Lista **lis,int valor) 
{ 
 Lista *novo, *aux; 
 novo=criaTermo(); 
 novo->a=valor; 
 aux=(*lis); 
 if(aux!=NULL) 
 { 
 while( (aux->prox)!=NULL ) 
 { 
 aux=aux->prox; 
 } 
 aux->prox=novo; 
 } 
 else 
 { 
 *lis=novo; 
 } 
} 
Lista* criaTermo(void) 
{ 
 Lista *novo; 
 novo = (Lista *)malloc(sizeof(Lista)); 
 novo->prox=NULL; 
 return novo; 
} 
void liberaMemoria(Lista **lis) 
{ 
 Lista *aux1, *aux2; 
 
 aux1=(*lis); 
 while( aux1!=NULL ) 
 { 
 aux2=aux1->prox; 
 free(aux1); 
 aux1=aux2; 
 } 
 
 *lis=NULL; 
} 
 
 
1.2 LISTAS ENCADEADAS 
Uma lista encadeada é uma sequência de objetos na memória do 
computador, onde cada elemento da sequência é armazenado em uma célula 
da lista. As células que armazenam elementos consecutivos da sequência não 
ficam necessariamente em posições consecutivas da memória. 
Uma lista encadeada é um exemplo de uma estrutura abstrata, porque 
uma lista encadeada é geral: pode ser usada para armazenar muitos tipos de 
diferentes de dados. 
Em uma lista encadeada, contanto que saiba onde a lista começa, 
você pode percorrer a lista de elos de um elo de um dado ao próximo, até chegar 
no final da lista. 
Com poucas modificações pode-se acrescentar um nova etapa. Essa 
é vantagem que as listas encadeadas têm sobre os arrays, a inserção de dados 
é muito rápida. Se quisesse inserir um valor no meio de array, teria de deslocar 
todos os dados seguintes um por um. 
 
Imagem 1.2 lista encadeada 
 
 
 
Código 1.2 - Lista Encadeada 
#include <iostream.h> 
#include <stdlib.h> 
static int total = 0; /* Numero total de unidades */ 
class unidades { 
 int numero; /* Nº Unidade */ 
public: 
 unidades(); /* Construtor padrao */ 
 unidades(int); /* Construtor sobrecarregado */ 
 void aloca_proximo(); /* Construtor da proxima unidade */ 
 void aloca_proximo(int); /* Construtor da proxima unidade sobrecarregado */ 
 unidades *proximo; /* Proxima unidade */ 
 int acessa_numero() const { return numero; } 
 void muda_numero(int num) { numero = num; } 
}; 
unidades::unidades() 
{ 
 total++; 
 numero = total; 
} 
unidades::unidades(int num) 
{ 
 total++; 
 numero = num; 
} 
void unidades::aloca_proximo() 
{ 
 proximo = (unidades *) malloc(sizeof(unidades)); 
 total++; 
 proximo->numero = total; 
} 
void unidades::aloca_proximo(int num) 
{ 
 proximo = (unidades *) malloc(sizeof(unidades)); 
 total++; 
 proximo->numero = num; 
} 
int main(void) 
{ 
 unidades principal; 
 unidades *aux; 
 cout << principal.acessa_numero() << endl; 
 principal.aloca_proximo(); 
 principal.proximo->muda_numero(2); 
 cout << principal.proximo->acessa_numero() << endl; 
 aux = &principal; 
 cout << aux->acessa_numero() << endl; 
 cout << aux->proximo->acessa_numero() << endl; 
 aux->muda_numero(10); 
 cout << principal.acessa_numero() << endl; 
 cout << aux->acessa_numero() << endl; 
 aux = aux->proximo; 
 aux->muda_numero(20); 
 cout << principal.proximo->acessa_numero() << endl; 
 cout << aux->acessa_numero() << endl; 
 aux->aloca_proximo(); 
 aux = aux->proximo; 
 aux->muda_numero(3); 
 cout << aux->acessa_numero() << endl; 
 aux = &principal; 
 cout << principal.acessa_numero() << endl; 
 cout << aux->acessa_numero() << endl; 
 aux = aux->proximo; 
 cout << principal.proximo->acessa_numero() << endl; 
 cout << aux->acessa_numero() << endl; 
 aux = aux->proximo; 
 cout << aux->acessa_numero() << endl; 
 cout << principal.proximo->proximo->acessa_numero() << endl; 
 aux->aloca_proximo(); 
 aux = aux->proximo; 
 cout << aux->acessa_numero() << endl; 
 return 0; 
 
} 
2. FILA 
Uma fila é um conjunto ordenado de itens a partir do qual se podem eliminar 
itens numa extremidade – início da fila – e no qual se podem inserir itens na outra 
extremidade – final da fila. 
Ela é uma prima próxima da pilha, pois os itens são inseridos e removidos de 
acordo com princípio de que o primeiro que entra é o primeiro que sai – first in, 
first out (FIFO). 
O conceito de fila existe no mundo real, vide exemplos como filas de banco, 
pedágios, restaurantes etc. As operações básicas de uma fila são: 
 Insert ou enqueue – insere itens numa fila (ao final). 
 Remove ou dequeue – retira itens de uma fila (primeiro item). 
 Empty – verifica se fila está vazia. 
 Size – retorna o tamanho da fila. 
 Fornt – retorna o próximo item da fila sem retirar o mesmo da fila. 
 
 
 
 
 
 
Imagem 2.1 – Fila 
 
 
2.1 – Código – Fila 
 
#include <cstdlib> 
#include <iostream> 
#define clrscr system("cls") // Definindo o comando clrscr 
using namespace std; 
 
int i; // Usado no for 
int fila[10]; 
int aux[10]; 
 
int opcao = 1; // Menu 
int novo; // adicionar item 
int atual; // Para fazer a fila andar 
 
void mostrar() { 
 clrscr; 
 cout << "#################################" << endl; 
 cout << "###### Mostrar Fila Atual #######" <<endl; 
 cout << "#################################" << endl << endl; 
 
 for(i = 0; i < 10; i++) { 
 cout << "[ "<< fila[i] << " ]" << endl; 
 } 
 cout << endl; 
 
 } 
 void inserir() { 
 clrscr; 
 cout << "#################################" << endl; 
 cout << "## Adicionar elemento da Fila ###" <<endl; 
 cout << "#################################" << endl <<endl; 
 cout << "Digite o elemento: "; 
 cin >> novo ; 
 fila[atual] = novo; 
 
 cout << endl << endl; 
 
 if (atual < 9) { atual++; } 
 else { atual = 0; } 
 } 
 /* Retirar um elemento da fila */ 
 
void retirar() { 
 /* Tirar o primeiro elemento */ 
 clrscr; 
 cout << "#################################" << endl; 
 cout << "### Retirar elemento da Fila ####" <<endl; 
 cout << "#################################" << endl << endl; 
 cout << "Retirado: " << fila[0]; 
 cout << endl << endl; 
 /* Fazendo a fila 'andar' */ 
 
 for(i=1; i<10; i++) { 
 aux[i-1] = fila[i]; 
 } 
 for(i=0; i<10; i++) { 
 fila[i] = aux[i]; 
 } 
 } 
 int main(int argc, char *argv[]) 
{ 
 cout << "#################################" << endl; 
 cout << "Codigo para demostracao de Filas" <<endl; 
 cout << "#################################" << endl << endl; 
 
 while (opcao != 0) { 
 cout << "Escolha uma opcao:" << endl; 
 cout << "[1] - Mostrar Fila" << endl; 
 cout << "[2] - Inserir elemento na fila" << endl; 
 cout << "[3] - Retirar elemento da fila" << endl; 
 cout << "[0] - Sair" << endl; 
 cin >> opcao; 
 
 if (opcao == 1) { mostrar(); } 
 if (opcao == 2) { inserir(); } 
 if (opcao == 3) { retirar(); } 
 } 
 system("PAUSE"); 
 return EXIT_SUCCESS; 
 } 
 
 
 
 
 
 
 
 
3. PILHA 
Uma pilha (stack) é uma coleção ordenada de elementos que 
somente são acessados por um único lugar, o extremo da pilha. Os elementos 
da pilha são acionados ou retirados (apagados) apenas pela parte superior. 
Uma pilha é uma estrutura de dados de entradas ordenadas de 
maneira que só é possível ser introduzidos e eliminados por um extremo 
denominado topo. 
Quando dizemos uma pilha ordenada, o que queremos dizer é que há 
um elemento que pode ser acessado primeiro (o que está em cima da pilha). 
Outro elemento pode ser acessado em segundo lugar (justamente o elemento 
que está embaixo do topo), um terceiro elemento e etc. não se requer que as 
entradas possam ser comparadas utilizando o operador, menor que (<) e podem 
ser de qualquer tipo. 
As entradas da pilha devem ser eliminadas na ordem inversa em que 
foram incluídas nela. Por exemplo, é possível criar uma pilha de livros colocando 
o primeiro um dicionário, em cima dele uma enciclopédia em cima de ambos um 
romance na parte superior. 
3.1 Imagem – Pilha de Livros 
 
Quando são retirados da pilha, o romance deve ser retirado primeiro, 
depois a enciclopédia, e por último, o dicionário. 
Por causa de sua prioridade especifica << ultimo a entrar, primeiro a 
sair>>, as pilhas são conhecidas como estrutura de dados LIFO (last-in, first-
out). 
As operações comuns como pilha são inserir e retirar. A operação 
inserir (push) adiciona um elemento no topo da pilha e a operação retirar (pop) 
elimina ou retira um elemento da pilha. 
 
 
 
 
3.2 Imagem – Pilha 
 
3.1 – Código Pilha 
#include &lt;iostream&gt; 
#define tamanho 30 
using namespace std; 
 
// estrutura PILHA 
typedef struct { 
 int topo; 
 int item [tamanho]; 
} PILHA; 
 
// inicializa PILHA 
void iniPilha (PILHA &amp;p) { 
 p.topo = -1 ; 
} 
char pilhaVazia(PILHA p) { 
 if(p.topo == -1) 
 return true; 
 else 
 return false; 
} 
char pilhaCheia(PILHA p) { 
 if (p.topo == tamanho-1) 
 return true; 
 else 
 return false; 
} 
 
// inseri elementos em PILHA 
void push(PILHA &amp;p, char x) { 
 p.item[++p.topo]=x; 
} 
 
// retira elementos de PILHA 
char pop(PILHA &amp;p) { 
 return (p.item[p.topo--]); 
} 
 
// pega o último dado inserido em PILHA 
char top(PILHA p) { 
 if(pilhaVazia(p) == 1) 
 return 0; 
 else 
 return (p.item[p.topo]); 
} 
int main() { 
 char palavra[30], p_real[30]; 
 int qtd_str, i, j, npalindromo; 
 PILHA p; 
 //cria as pilhas 
 iniPilha (p); 
 
 cout &lt;&lt; "Digite uma palavra:"; 
 cin.getline(palavra, tamanho); 
 
 // pega o total de caracteres, incluindo espaços em branco 
 qtd_str = cin.gcount(); 
 
 // irá contar os caracteres válidos 
 j = 0; 
 
 // inserindo caracteres na pilha 
 for(i=0;i &lt; qtd_str-1;i++) { 
 // caso não seja espaço vazio, ou a pilha não esteja cheia 
 if(!isspace(palavra[i]) &amp;&amp; !pilhaCheia(p)) { 
 p_real[j] = palavra[i]; 
 push(p, palavra[i]); 
 j++; 
 } 
 } 
 // mostra a palavra/frase ao contrário 
 for(i=0; !pilhaVazia(p); i++) { 
 // confere caractere por caractere, caso algum seja diferente, seta a 
 // variável npalindromo 
 if(top(p) != p_real[i]) { 
 npalindromo = 1; 
 } 
 
 cout &lt;&lt; pop(p); 
 } 
 
 if(npalindromo != 1) { 
 cout &lt;&lt;"\n Palindromo"; 
 } 
 
 cout &lt;&lt;"\n"; 
 system("pause"); // Isso não precisa no Linux 
 return 0; 
} 
 
4 – REFERENCIAS: 
 
1. Ascencio. Ana Fernanda Gomes, Estruturas de dados, algoritmos, 
analises da complexidade e implementação em JAVA, C e C++, são 
Paulo, 2010. 
2. Aguilar, Luis Joyanes. Programação em C++ [recurso eletrônico]: 
algoritmos, estruturas de dados e objetos, Porto Alegre: AMGH, 2. 
Ed, 2011. 
3. Lopes, Arthur Vagas. Estruturas de dados para a construção de 
software / Arthur Vargas Lopes – Canoas: Ed. ULBRA, 1999. 
4. Griffiths, David. Use a Cabeça: C / David Griffiths, Dawn Griffiths – 
Rio de Janeiro, RJ: Alta Books, 2013.