Algoritmos e Estrutura de Dados

Prévia do material em texto

Ponteiros
 
O ponteiro nada mais é do que uma variável que guarda o endereço de uma outra variável. A declaração de ponteiros é feita da seguinte forma:
 
 
A instrução acima indica que pa é um ponteiro do tipo int. Agora veremos como atribuir valor ao ponteiro declarado. Para isto é necessário saber que existem dois operadores unitários que são utilizados com os ponteiros. O primeiro é o operador (*) através dele é possível retornar o valor da variável que está localizada no ponteiro. E o segundo é o operador (&) que retorna o endereço de memória que está localizado o valor da variavel contida no ponteiro. Portanto para atribuirmos um valor para o ponteiro é necessário referencia o valor da variável que se encontra no ponteiro utilizando o operador (*), como será demonstrado a seguir.
 
 
Desta forma estamos atribuindo o valor 24 para a variável que está contida no ponteiro. Para entender melhor quando e como utilizar os operadores (*) e (&), veja o programa mostrado abaixo.
 
 
Saída do programa:
 
 
Quando os ponteiros são declarados, eles são inicializados com um endereço não valido, portanto antes de usa-los é necessário atribuir um endereço e isso é feito através do operador (&) como demonstra a instrução pa=&a e pb=&b que atribui aos ponteiros pa e pb o endereço das varieis a e b.
 
Uma outra novidade do programa anterior é quando queremos imprimir o endereço do próprio ponteiro isto é feito referenciando pa normalmente. Porém para imprimir o endereço contido no ponteiro é usado &pa e por ultimo para imprimir o valor do endereço contido no ponteiro usamos *pa.
Através do programa abaixo é possível verificar que se pode fazer comparações entre ponteiros.
Saída do programa:
A comparação entre ponteiros em uma expressão relacional (>=,<=,> e <) é possível quando os dois ponteiros são do mesmo tipo. Isso é feito no programa mostrado através da linha “if (px1>px2)”, Caso a instrução seja verdadeira será feita a diferença entre os dois ponteiros “px1-px2”. E caso seja falso será feito ao contrario “px2-px1”. É importante dizer que os dados de saída deste programa não são iguais em todos os computadores, depende muito da memória disponível. Mas como pode-se observar em nosso exemplo, se px1=1245064 e px2=1245060 então px1-px2 será igual a um. Isso ocorre, pois a diferença depende da unidade tipo apontado. Para entender melhor, veja alguns casos de operações com ponteiros. Se um ponteiro do tipo inteiro px1 fosse igual a 150 e que os inteiros possuem dois bytes. As operações que se podem fazer são as seguintes: Incrementar o ponteiro através da expressão:
 
 
Isso fará com que o ponteiro aponte para a posição do próximo elemento. Como estamos a considerar que o tipo inteiro é do tamanho de 2 bytes, o ponteiro está sendo incrementado de 2, ou seja, o número de incrementos depende do tamanho do tipo de dados. O mesmo acontece com o decremento, porém aponta para a posição anterior. Isso é feito pela instrução:
 
Isso fará com que o ponteiro aponte para a posição do próximo elemento. Como estamos a considerar que o tipo inteiro é do tamanho de 2 bytes, o ponteiro está sendo incrementado de 2, ou seja, o número de incrementos depende do tamanho do tipo de dados. O mesmo acontece com o decremento, porém aponta para a posição anterior. Isso é feito pela instrução:
 
 
Uma outra opção é somar ou diminuir inteiros ao ponteiro:
 
 
Dessa forma o ponteiro irá apontar para o quinto elemento do tipo px1 adiante do elemento que o ponteiro estava a apontar. É importante saber que não se pode nem multiplicar e nem dividir ponteiros.
 
Do mesmo modo que se tem um ponteiro (que é o endereço de uma variável) pode-se ter ponteiro para ponteiro, ou seja, um ponteiro aponta para um outro ponteiro que finalmente aponta para a variável com o valor a ser utilizado. O que chamamos de indireção múltipla e pode ser vista no próximo programa.
 
 
Dados de saída:
 
 
Como visto no código fonte anterior, uma variável que é ponteiro para ponteiro deve ser declarada da seguinte forma:
 
Da mesma forma para acessar o valor final é utilizado o operador “*” duas vezes, conforme visto no neste exemplo. 
STRUCT
O Struct (traduzindo, estrutura) funciona basicamente como um aglomerado de variáveis, sendo realmente, passível de gravar variáveis do tipo char, int, float e etc dentro de uma variável só. 
Exemplo 1:
Nesse exemplo mostraremos como fazer uma agenda eletrônica no DEV C++.
#include<conio.h>	
#include<string.h>Estas são as bibliotecas, onde cada uma tem um pacote de funções diferentes, elas são chamadas de “includes”.
#include<stdlib.h> 
#include<stdio.h>
#include <windows.h>Principal função do programa em C.
Main (void){Variável de um programa.
 int i,j,h;Nome da estrutura “Agenda telefônica” 
 struct AgendaTelefonica
 {
 Char nomea[25];
 Char nomeb[25];Variáveis inseridas no struct.
 int num;
 };Struct transformado em matriz para caber mais informações sobre a variável.
 struct AgendaTelefonica a[2];
 for(i=0;i<=1;i++){
 	for(j=0;j<=1;j++)
{
 		for(h=0;h<=1;h++)
 Exemplo 2:
main (void){Aqui, é o ponto de estruturação da função do struct, primeiro, deve-se dar um nome a função do struct, no caso, AgendaTelefonica, e depois, abrir uma chave para o início da codificação. Depois, entrar com os tipos de variáveis desejados para fazer o programa.
 int i,j,h;
 struct AgendaTelefonica
 {
 char nomea[25];
 char nomeb[25];
 int num;
 };
 struct AgendaTelefonica a[2];
 for(i=0;i<=1;i++){Aqui, iniciaremos a contagem do for para o armazenamento individual de cada variável para que os valores e dados das mesmas não misturem entre si.
 	for(j=0;j<=1;j++){
 		for(h=0;h<=1;h++){
 printf("Entre com o nome desejado: \n");
 fflush(stdin);
 fgets(a[i].nomea, 25, stdin); No resto da programação, entraremos com os dados normalmente a serem utilizados (seguindo as regras do struct, vide primeiro documento). Você também pode consultar um exercício de teste também disponibilizado no blog do professor.
 printf("Entre com o sobrenome desejado: \n");
 fflush(stdin);
 fgets(a[j].nomeb, 25, stdin); 
 printf("Entre com o numero do celular ou fixo: ");
 scanf("%d", &a[h].num);
 system("cls");
 }
 }
 } 
Pilhas
Em determinadas aplicações, as pilhas e filas representam estruturas de dados importantes, nas quais seus elementos são˜ organizados em função de um critério que regulamenta a entrada e a saída dos elementos. Para uma pilha, tem-se o critério LIFO: LIFO: Last In, First Out - O ultimo elemento a entrar deve ser o primeiro a ser retirado. Para uma fila, tem-se o critério LIFO: FIFO: First In, First Out - O primeiro elemento a entrar deve ser o primeiro a ser retirado.
Filas e Pilhas compartilham duas características comuns: 
- ambas têm regras muito rigorosas para acessar os dados armazenados nelas 
- as operações de recuperação são, por natureza, destrutivas. 
Em outras palavras: 
Acessar um item em uma pilha requer a sua remoção e, a menos que o item seja armazenado em outro lugar, ele é destruído. Além disso, tanto pilhas como filas usam uma região contígua de memória. 
As operações básicas a serem implementadas para uma estrutura de pilha são: Iniciar a pilha Verificar se a pilha está vazia Retornar o elemento que está no topo da pilha Inserir um elemento na pilha (no topo) Retirar um elemento da pilha (do topo).
As operações básicas a serem implementadas para uma estrutura de fila são: ˜ Iniciar a fila Verificar se a fila esta vazia Inserir um elemento na pilha (ao final) Retirar um elemento da pilha (do início).
A estrutura de dados a ser declarada parao tipo Pilha pode ser definida por meio de ponteiros, como no exemplo abaixo na linguagem C:
https://www.youtube.com/watch?v=HlsUcarJj10
#include <stdio.h>
#include<stdlib.h>
#define capacidade 30
struct stack
{
 int topo, item[capacidade];
};
/*============== Inicia Pilha ======================*/
void inic_pilha (struct stack *p)
{
 p->topo = -1;
}
/*=============== Verifica pilha Cheia ==============*/
int pilha_cheia (struct stack *p)
{
 if (p->topo == (capacidade-1))
 {
 printf ("\n\n\t\tA Pilha esta Cheia!!!");
 return 1;
 }
 else
 return 0;
}
/*=============== Verifica pilha Vazia ==============*/
int pilha_vazia (struct stack *p)
{
 if (p->topo == -1)
 {
 printf ("\n\n\t\tA Pilha esta Vazia!!!");
 return 1;
 }
 else
 return 0;
}
/*=============== Verifica pilha Vazia 2 ============*/
int pilha_vazia2 (struct stack *p)
{
 if (p->topo == -1)
 return 1;
 else
 return 0;
}
/*================== Empilha ========================*/
int push (struct stack *p, int valor)
{
 return (p->item[++(p->topo)] = valor);
}
/*================== Desempilha =====================*/
int pop (struct stack *p)
{
 int aux;
 aux = p->item[(p->topo)--];
 return aux;
}
/*================== Mostra Pilha ===================*/
int mostra (struct stack *p)
{
 int aux;
 
 if (pilha_vazia2 (p))
 return 1;
 else
 {
 aux = pop (p);
 printf ("%d,", aux);
 mostra (p);
 return 0;
 }
}
/*==================Reempilha========================*/
int reempilha (struct stack *p, struct stack *p_par, struct stack *p_impar)
{
 int aux;
 
 if (pilha_vazia (p))
 return 1;
 else
 { //seleciona os valores Impares
 if (p->item[p->topo]%2) 
 {
 aux = pop (p);
 push (p_impar, aux);
 }
 else //seleciona valores pares 
 { 
 aux = pop (p);
 push (p_par, aux);
 }
 reempilha (p, p_par, p_impar);
 return 0;
 }
}
/*================== Funcao para pegar os valores a empilhar =============*/
int empilha (struct stack *p)
{
 int valor;
 
 printf ("Informe um valor para ser empilhado ou -1 para sair ");
 scanf ("%d", &valor);
 
 if (pilha_cheia (p))
 return 1;
 else
 {
 if (valor == -1)
 return 0;
 else
 {
 push (p, valor);
 empilha (p);
 return 0; 
 }
 }
}
/*======================== MAIN ===============================*/
int main ()
{
 struct stack pilha, pilha_par, pilha_impar;
 inic_pilha (&pilha);
 inic_pilha (&pilha_impar);
 inic_pilha (&pilha_par);
 
 empilha (&pilha);
 reempilha (&pilha, &pilha_par, &pilha_impar);
 
 printf ("\nPilha Par:");
 mostra (&pilha_par);
 
 printf ("\n\nPilha Impar: ");
 mostra (&pilha_impar);
 printf("\n\n\n");
 
 
 return 0;
}
Exemplo 2
#include<stdio.h>
#include<stdlib.h>
 #define MAX 10 //MAX = Quantidade de elementos máximos na pilha 
int topo=-1; //Indica o topo da pilha 
int pilha[MAX]; //Declaração da pilha 
void insere (void); //Função que insere itens na pilha 
void remover(void); //Função que remove itens da pilha
void exibe (void); //Função que exibe os itens da pilha
int main (void)
{
int op;
for (;;)
{
system("cls"); //Limpa a tela, somente no Linux
//---------------------------------
//MENU PRINCIPAL
//---------------------------------
printf("\n-------Menu-------");
printf("\n\n1- Insere");
printf("\n2- Remover");
printf("\n3- Exibir");
printf("\n4- Sair");
printf("\n\nEntre a sua opcao:");
scanf("%d",&op);
switch(op) { 
case 1 : insere(); 
break; 
case 2 : remover();
break; 
case 3 : exibe();
break; 
case 4 : exit(0); 
default: printf("\nOpcao Errada"); getchar(); break; } } }
void insere (void)
{
int i;
topo = topo + 1;
if (topo == MAX) //Insere itens na pilha até que topo for diferente de MAX
{
printf("\nPilha Cheia");
topo = topo - 1;
getchar();
}
printf("Entre com o numero (TOPO = %d): ",topo);
scanf ("%d",&i);
pilha[topo] = i;
}
void remover (void)
{
if (topo >= 0)
{
pilha[topo] = 0;
topo = topo - 1;
}
else
{
printf("Pilha Vazia");
getchar();
}
}
void exibe (void) { 
int x; 
char s[80]; 
system("cls"); 
for (x=0;x<=topo;x++) 
printf("\n %d",pilha[x]); 
printf("\n (S)air: "); 
scanf("%s",s); }
Fila
O que define uma fila?
Para que um elemento entre na fila ele será sempre colocado em uma extremidade denominada final (término, fim);
• Para que um elemento seja retirado da fila, ele sairá de uma outra extremidade denominada começo (início, frente);
First in, first out
Os elementos da fila são retirados na mesma ordem em que foram introduzidos: o primeiro a entrar é o primeiro a sair;
Não são permitidas operações sobre quaisquer nodos, somente sobre aqueles definidos pela organização da fila. Exemplos:
Controle de acesso a recursos compartilhados (fila de impressão, por exemplo).
Política de escalonamento de processos baseada em prioridades;
Definição das prioridades em uma lista de downloads;
Agendamento de tarefas;
Troca de mensagens em um sistema distribuído;
Leitura do buffer do teclado;
Enfileiramento de pacotes no equipamento de rede, antes de submetê-los ao enlace;
Etc.
Uma fila permite basicamente duas operações: Enfileirar (inserir um elemento na fila) Desenfileirar (retirar um elemento da fila). Antes de pensar os algoritmos, precisamos: 
Pensar em uma estratégia de armazenamento da estrutura; 
Pensar na interface das operações que irão manipular os dados da estrutura;
Filas - Queue
São estruturas de dados do tipo FIFO (first-in first-out), onde o primeiro elemento a ser inserido, será o primeiro a ser retirado, ou seja, adiciona-se itens no fim e remove-se do início.
São exemplos de uso de fila em um sistema:
Controle de documentos para impressão;
Troca de mensagem entre computadores numa rede;
etc.
A implementação de filas pode ser realizada através de vetor (alocação do espaço de memória para os elementos é contígua) ou através de listas encadeadas (próxima aula).
Operações com Fila:
Todas as operações em uma fila podem ser imaginadas como as que ocorre numa fila de pessoas num banco, exceto que o elementos não se movem na fila, conforme o primeiro elemento é retirado. Isto seria muito custoso para o computador. O que se faz na realidade é indicar quem é o primeiro.
criação da fila (informar a capacidade no caso de implementação sequencial - vetor);
enfileirar (enqueue) - o elemento é o parâmetro nesta operação;
desenfileirar (dequeue);
mostrar a fila (todos os elementos);
verificar se a fila está vazia (isEmpty);
verificar se a fila está cheia (isFull - implementação sequencial - vetor).
Supondo uma fila com capacidade para 5 elementos (5 nós).
Na realidade a remoção de um elemento da fila é realizada apenas alterando-se a informação da posição do último.
Para evitar problemas de não ser capaz de inserir mais elementos na fila, mesmo quando ela não está cheia, as referências primeiro e último circundam até o inicio do vetor, resultando numa fila circular.
Desta forma a fila simula uma representação circular:
Veja o algoritmo a seguir para uma fila de números reais: 
#include 
struct Fila {
	int capacidade;
	float *dados;
	int primeiro;
	int ultimo;
	int nItens; 
};
void criarFila( struct Fila *f, int c ) { 
	f->capacidade = c;
	f->dados = (float*) malloc (f->capacidade * sizeof(float));
	f->primeiro = 0;
	f->ultimo = -1;
	f->nItens = 0; 
}
void inserir(struct Fila *f, int v) {
	if(f->ultimo == f->capacidade-1)
		f->ultimo = -1;
	f->ultimo++;
	f->dados[f->ultimo] = v; // incrementa ultimo e insere
	f->nItens++;// mais um item inserido
}
int remover( struct Fila *f ) { // pega o item do começo da fila
	int temp = f->dados[f->primeiro++]; // pega o valor e incrementa o primeiro
	if(f->primeiro == f->capacidade)
		f->primeiro = 0;
	f->nItens--; // um item retirado
	return temp;
}
int estaVazia( struct Fila *f ) { // retorna verdadeiro se a fila está vazia
	return (f->nItens==0);
}
int estaCheia( struct Fila *f ) { // retorna verdadeiro se a fila está cheia
	return (f->nItens == f->capacidade);
}
void mostrarFila(struct Fila *f){
	int cont, i;
	for ( cont=0, i= f->primeiro; cont < f->nItens; cont++){
		printf("%.2f\t",f->dados[i++]);
		if (i == f->capacidade)
			i=0;
	}
	printf("\n\n");
}
void main () {
	int opcao, capa;
	float valor;
	struct Fila umaFila;
	// cria a fila
	printf("\nCapacidade da fila? ");
	scanf("%d",&capa);
	criarFila(&umaFila, capa);
	// apresenta menu
	while( 1 ){
		printf("\n1 - Inserir elemento\n2 - Remover elemento\n3 - Mostrar Fila\n0 - Sair\n\nOpcao? ");
		scanf("%d", &opcao);
		switch(opcao){
			case 0: exit(0);
			case 1: // insere elemento
				if (estaCheia(&umaFila)){
					printf("\nFila Cheia!!!\n\n");
				}
				else {
					printf("\nValor do elemento a ser inserido? ");
					scanf("%f", &valor);
					inserir(&umaFila,valor);
				}
				break;
			case 2: // remove elemento
				if (estaVazia(&umaFila)){
					printf("\nFila vazia!!!\n\n");
				}
				else {
					valor = remover(&umaFila);
					printf("\n%1f removido com sucesso\n\n", valor) ; 
				}
				break;
				case 3: // mostrar fila
					if (estaVazia(&umaFila)){
						printf("\nFila vazia!!!\n\n");
					}
					else {
					printf("\nConteudo da fila => ");
						mostrarFila(&umaFila);
					}
					break;
				default:
					printf("\nOpcao Invalida\n\n");
		}
	}
}