ED_Fila_Simples - Adriana

Prévia do material em texto

��INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA
Câmpus de Ji-Paraná – Rondônia���Estrutura de Dados – Profª. Adriana Rigolon, Me.��
TIPOS DE DADOS
O tipo de dados de uma variável define o conjunto de valores que a variável pode assumir. Por exemplo, uma variável do tipo lógico pode assumir o valor verdadeiro ou falso.
Os tipos de dados são divididos em: Tipos Primitivos de Dados e Tipos Estruturados de Dados.
Os Tipos Primitivos de Dados são os tipos básicos, a partir dos quais podemos definir os demais tipos e estruturas de dados. Estes tipos de dados são os mais freqüentes nas linguagens de programação e tem um conjunto de valores e operações restrito. São considerados Tipos Primitivos de Dados: inteiro, real, lógico, caracter, ponteiro.
Os Tipos Estruturados de Dados são construídos a partir dos tipos primitivos. Estes tipos são previstos por muitas linguagens de programação e devem ser definidos pelo programador. Exemplos de tipos estruturados: array e registro. Estes dois tipos são formados por tipos básicos como inteiros, caracteres, reais, etc.
Uma declaração de variável em uma linguagem especifica:
O conjunto de valores que pode assumir.
O conjunto de operações que podemos efetuar.
A quantidade de bytes que deve ser reservada para ela.
Como o dado representado por esses bytes deve ser interpretado (por exemplo, uma cadeia de bits pode ser interpretada como um inteiro ou real...).
Então, tipos de dados podem ser vistos como métodos para interpretar o conteúdo da memória do computador. 
TIPOS ABSTRATOS DE DADOS
O conceito de Tipo de Dados pode ser visto de outra perspectiva: não em termos do que um computador pode fazer, mas o que os usuários desejam fazer. Este conceito de Tipo de Dados independente do hardware é chamado Tipo Abstrato de Dados - TAD.
Um tipo abstrato de dados é composto por um modelo matemático acompanhado de um conjunto de operações definidas sobre este modelo.
Uma vez que TAD é definido e as operações associadas a este tipo são especificadas, pode-se implementar este tipo de dado. 
A característica essencial de um TAD é a separação entre conceito e implementação. A descrição dos valores e o conjunto de operações do TAD são fornecidos ao usuário, mas a implementação é invisível e inacessível. A separação da definição do TAD da sua implementação permite que uma mudança de implementação não altere o programa que usa o TAD.
Exemplos de TAD:
Lineares: Listas Ordenadas, Pilhas, Filas, Deques.
Não Lineares: Árvores, Grafos.
ESTRUTURAS DE DADOS
Um algoritmo é projetado em termos de tipos abstratos de dados. Para implementá-los numa linguagem de programação é necessário encontrar uma forma de representá-los nessa linguagem, utilizando tipos e operações suportadas pelo computador. Para representar o modelo matemático do TAD, em uma linguagem de programação, emprega-se uma Estrutura de Dados.
As Estruturas de Dados diferem uma das outras pela disposição ou manipulação de seus dados. A disposição dos dados em uma estrutura obedece a condições preestabelecidas e caracteriza a estrutura.
Assim, Estrutura de Dados (ED) é um método particular de se implementar um TAD. A implementação de um TAD escolhe uma estrutura de dados (ED) para representá-lo. Cada ED pode ser construída a partir de tipos básicos (inteiro, real, caracter) ou estruturados (array, registro) de uma determinada linguagem de programação.
O estudo de Estruturas de Dados não pode ser desvinculado de seus aspectos algorítmicos. A escolha correta da estrutura adequada a cada caso depende diretamente do conhecimento de algoritmos para manipular a estrutura de maneira eficiente.
PONTEIROS
Um ponteiro é uma variável cujo conteúdo é um endereço de memória, provavelmente o endereço de outra variável.
	Todas as variáveis estão armazenadas em memória. Cada uma tem seu endereço e seu conteúdo. Quando usamos o nome de uma variável num programa, o compilador compila no código o endereço, para que, quando executado, o processador acesse o conteúdo. Isso significa que o compilador só vê o endereço e o programador só vê o conteúdo. 
	Para declarar um ponteiro, acrescenta-se * entre o tipo e o nome da variável. Para ver o endereço, usa-se o operador & na frente da variável, que significa “endereço de”, e é chamado operador de referenciação. Ao contrário, para manipular um valor armazenado em um endereço, usa-se o operador * na frente do endereço, que significa “valor apontado por”, e é chamado operador de de-referenciação. 
Exemplo
#include <stdio.h>
#include <iostream>
 
main(){
 int a = 1, b = 20, v[2] = {5,257}, *pt = &b;
 printf ("No endereco de memoria %d tem o valor %d \n", &a, a);
 printf ("No endereco de memoria %d tem o valor %d \n", &b, b);
 printf ("No endereco de memoria %d tem o valor %d \n", &v[1], v[1]);
 printf ("No endereco de memoria %d tem o valor %d \n", &v[0], v[0]);
 printf ("No endereco de memoria %d tem o endereco de b: %d \n", &pt, pt);
 printf ("Em V tem o endereco do 1o. elemento do vetor: %d \n\n", v);
 system("pause");
 } 
FILAS SIMPLES
(com alocação estática)
	Uma fila (do inglês Queue) é utilizada para armazenar dados, disponibilizando o critério de acesso FIFO – First in First out (o primeiro que entra é o primeiro que sai).
	Saídas
	
	
	
	
	
	
	Chegadas
	As principais operações com uma fila são: inserção e retirada, também chamadas de Queue e DeQueue, respectivamente. O conceito de fila formaliza essas operações. Quando se fala de uma fila dentro do contexto da computação, a operação Queue sempre coloca um novo elemento no fim da fila, e a operação DeQueue sempre retira o elemento mais antigo da fila, isto é, o elemento que está na frente ou no início da mesma.
A seguir são apresentados os algoritmos para as operações básicas de uma fila.
Algoritmo 1 - Inicializa(F)
	O algoritmo 1 disponibiliza uma fila F para o uso, armazenando 1 em Início e 0 em Fim.
	Descrição:
	Inicializa a fila F.
	Dados de entrada:
	Fila F.
	Dados de saída:
	Fila F inicializada.
	Passo 1:
	Armazene 1 em Início de F.
	Passo 2: 
	Armazene 0 em Fim de F.
Algoritmo 2 - Queue(F, D)
O algoritmo 2 insere um novo elemento (D) no final de uma fila F. A variável Fim é utilizada para controlar a posição, dentro do vetor Q, onde D será inserido. O passo 1 verifica a validade da operação, para evitar que se adicione mais um elemento na fila quando a mesma estiver cheia. O passo 2 faz com que Fim indique a posição do último elemento inserido. O passo 3 armazena um novo dado na fila na posição indicada pela variável Fim.
	Descrição:
	Armazena D no fim da fila F.
	Dados de entrada:
	Fila F e dado D.
	Dados de saída:
	Fila F após inserção de D.
	Passo 1:
	Verifique se a fila F está cheia (Fim = Max).
	Passo 1.1:
	Se afirmativo, avise overflow de fila e suspenda a operação, senão vá para o passo 2.
	Passo 2: 
	Adicione 1 em Fim de F.
	Passo 3: 
	Armazene D no elemento Q subscrito no Fim da fila F.
Algoritmo 3 - DeQueue(F, R)
O algoritmo 3 retira da fila F quem está na frente, armazenando este elemento em R. A variável Início é utilizada para controlar a frente da fila. O passo 1 verifica a validade da operação para evitar que se tente retirar um elemento da fila quando a mesma estiver vazia. O passo 2 armazena o elemento que está na frente da fila na variável R. O passo 3 faz com que a variável Início indique o próximo elemento a ocupar a frente da fila se esta não ficar vazia (o que ocorre quando Inicio > Fim).
	Descrição:
	Retira o primeiro elemento da fila F.
	Dados de entrada:
	Fila F.
	Dados de saída:
	Fila F e o elemento que estava na frente da fila, R.
	Passo 1:
	Verifique se a fila F está vazia (Inicio > Fim).
	Passo 1.1:
	Se afirmativo, avise underflow de fila e suspenda a operação, senão vá para o passo 2.Passo 2: 
	Armazene em R o elemento que está na frente da fila F.
	Passo 3: 
	Adicione 1 em Início de F.
�
PROGRAMA COMPLETO PARA CRIAÇÃO E MANIPULAÇÃO DE FILAS SIMPLES, EM C
#include <stdio.h>
#include <iostream>
#define Max 5 //define o num maximo de elementos na fila 
typedef struct{
 char Q[Max];
 int inicio;
 int fim;
 } Fila;
 
void Inicializa(Fila *F){
 F->inicio = 0;
 F->fim = -1;
}
void Queue(Fila *F, char D){
 if (F->fim == (Max -1))
 printf("\nOverflow na fila\n\n");
 else{
 F->fim=F->fim + 1;
 F->Q[F->fim] = D;
 }
}
void DeQueue(Fila *F, char *R){
 if (F->inicio > F->fim)
 printf("Underflow na fila");
 else{
 *R = F->Q[F->inicio];
 F->inicio = F->inicio + 1;
 } 
} 
main(){
 Fila F1;
Fila F2;
 char atend;
 int i;
 Inicializa(&F1); 
 Inicializa(&F2); 
 Queue(&F1, 'A');
 Queue(&F1, 'B');
 Queue(&F1, 'C');
 printf("\nElementos retirados da Fila: ");
 for (i = 0; i <= F1.fim; i++){
 DeQueue(&F1, &atend);
 printf("%c ", atend);
 }
printf("\n\n"); 
system("pause"); 
} 
Início
Fim
� PAGE \* MERGEFORMAT �5�