Estrutura de Dados - Struct e Pilha

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Bibliografia
WIRTH, Niklaus. Algoritmos e estruturas de dados.
TENEMBAUM, Aaron. Estruturas de Dados usando C.
MORAES, Celso. Estruturas de Dados e Algoritmos.
SCHILDT, Herbert. C completo e total.
SZWARCFITER, Jayme. Estruturas de dados e seus algoritmos.
VELOSO, Paulo. Estruturas de dados.
HOROWITZ, Ellis. Fundamentos de estruturas de dados.
*
*
Estruturas
*
*
Definição de Tipos
O programador pode definir seus próprios tipos de dados
os tipos complexos podem ser usados da mesma forma que os simples
novas variáveis serão declaradas utilizando estes novos tipos
Ex.:
	typedef char tipo_nome [30];
	tipo_nome nome;
*
*
Agregados Heterogêneos
Struct: conjunto de dados heterogêneos referenciados por um único nome e individualizados por campos
cada campo ocupa um número inteiro de unidades endereçáveis de memória, podendo ser referenciado pelo seu nome
normalmente os elementos em uma estrutura estão logicamente relacionados
A linguagem C permite que o programador tenha acesso a todos os campos da estrutura
*
*
Estruturas
Sintaxe:
struct nome_estrutura {
			tipo_1 dado_1;
			tipo_2 dado_2;
			...
			tipo_n dado_n;
} lista_de_variaveis;
*
*
Estruturas
Sintaxe para apenas declarar variável:
struct {
			tipo_1 dado_1;
			tipo_2 dado_2;
			...
			tipo_n dado_n;
		} lista_de_variaveis;
*
*
Estruturas
Sintaxe nomeando a estrutura e depois criando variáveis:
struct nome_estrutura {
			tipo_1 dado_1;
			tipo_2 dado_2;
			...
			tipo_n dado_n;
		};
struct nome_estrutura lista_de_variáveis;
*
*
Estruturas
Exemplo:
Criando uma variável
struct {
 int registro;
 char nome[50];
 int idade;
 float salario;
} func;
Utilização
func.idade = 31;
strcpy(func.nome,“Luiz”);
*
*
Estruturas
Exemplo:
Nomeando a estrutura
struct tipo_func {
 int registro;
 char nome[50];
 int idade;
 float salario;
} func;
struct tipo_func func2;
Utilização
func2.idade=func.idade;
*
*
Definindo um Tipo
typedef struct {
 int registro;
 char nome[50];
 int idade;
 float salario;
} TIPO_FUNC;
TIPO_FUNC func, func2;
*
*
Estruturas
Variações:
Estrutura de Estruturas
Vetor de Estruturas 
*
*
Variações de Estruturas
Contendo Estruturas
struct tipoend { 
 char endereco[40];
	char cep[9];
	char cidade[25];
};
struct tipopessoa {
	char nome[15];
	 struct tipoend end;
	float salario;
};
struct tipopessoa pessoa;
Vetor de Estruturas
struct tipoend { 
 char endereco[40];
		char cidade[25];
};
struct tipopessoa {
	char nome[15];
	struct tipoend end;
	};
struct tipopessoa pessoa[50];
/* cidade da 13a pessoa:
	 pessoa[12].end.cidade */
*
*
Ponteiros para Estruturas
Sintaxe:
struct nome_estrutura {
			tipo1 dado1;
			tipo2 dado2;
			...
			tipon dadon;
} var, *ptr;
var.dado1 
equivale a
ptr->dado1
*
*
Ponteiros para Estruturas
Exemplo:
typedef struct {
 int num;
 char nome[80];
 float saldo;
} TIPOCLI;
TIPOCLI c, *pc;
Acessando o no da conta do cliente: 
c.num=120;
pc = &c;
printf("Conta: %d\n",c.num);
printf("Conta: %d \n", pc->num);
printf("Conta: %d \n",(*pc).num);
*
*
Estruturas como Parâmetros
Exemplo:
Rendimento do Saldo
Passagem por Referência de um elemento do vetor
#include "stdio.h"
typedef struct{
 int reg;
 char nome[80];
 float saldo;
} tipocli ;
void rende(tipocli *cli);
main( ) {
tipocli cliente;
printf("Informe saldo atual: ");
scanf("%f",&cliente.saldo);
rende(&cliente);
printf("\nNovo saldo: ");
printf("%0.2f \n",cliente.saldo);
}
void rende( tipocli *cli) {
	float taxa;
	printf("\nInforme rendimento: ");
	scanf("%f",&taxa);
	cli -> saldo *= taxa;
}
*
*
Estruturas como Parâmetros
Exemplo:
Rendimento do Saldo
Passagem por Referência do vetor inteiro
#include "stdio.h"
typedef struct {
 int reg;
 char nome[80];
 float saldo;
}tipocli;
void rende(tipocli *cli);
main( ) {
	tipocli cliente[3]; int i;
	for (i=0; i<3; i++) {
		printf("Informe saldo atual: ");
		scanf("%f",&cliente[i].saldo);
	}
	rende(cliente);
	for (i=0; i<3; i++) {
		printf("\nNovo saldo: ");
		printf("%0.2f \n",cliente[i].saldo);
	}
}
void rende(tipocli *cli) {
	float taxa; int i;
	printf("\nInforme rendimento: ");
	scanf("%f",&taxa);
	for (i=0; i<3; i++)
		cli[i] . saldo *= taxa;
}
void rende(cli)
	tipocli cli[];
{
Não usa “->”
*
*
Pilhas
*
*
Listas Lineares
Uma lista linear é um conjunto de n elementos L[0], L[1], ..., L[n-1] tais que
n > 0 e L[0] é o primeiro elemento
para 0 < k < n, L[k] é precedido por L[k-1]
Agrupam informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si
Estáticas (alocação seqüencial)
Dinâmicas (alocação encadeada)
*
*
Para muitas aplicações é necessário impor restrições de acesso aos dados 
Vantagens: 
aliviar a necessidade de usar estruturas com mais detalhes
permitem implementações mais simples e flexíveis, pois menos operações são suportadas
Tipos especiais de Listas:
PILHAS
FILAS
Listas – Casos Particulares
*
*
Pilhas
Seqüência de elementos dispostos uns sobre os outros
Uma das estruturas de dados mais simples e mais utilizadas, sendo implementadas até pelo hardware das máquinas modernas
Definição: Lista Linear constituída de um conjunto ordenado de itens no qual novos itens podem ser inseridos e outros podem ser eliminados em uma única extremidade chamada topo da pilha
Pilhas
*
*
Pilhas
Ao contrário do vetor, a definição de pilha compreende a inserção e a eliminação de itens, tornando-a uma estrutura dinâmica e mutável 
Idéia fundamental: todo acesso à pilha é feito através do seu topo
Novo elemento introduzido passa a ser o elemento do topo
O único elemento que pode ser removido é o elemento do topo
Pilhas
*
*
Pilhas 
Os elementos mais recentemente inseridos ficam no topo da pilha e os menos recentes, no fundo
Devido às características das operações da pilha, o último elemento inserido será o primeiro a ser retirado
Estruturas desse tipo são conhecidas como "LIFO" (Last In, First Out)
Analogia: pilha de pratos
Pilhas
*
*
Aplicações de Pilhas
Adequadas ao processamento de estruturas aninhadas de profundidade imprevisível:
sintaxe de expressões aritméticas
controle da seqüência de chamadas de expressões aritméticas
Controle de recursividade
Percurso em árvores
Aplicações de Pilhas
*
*
Pilhas 
Pilhas- Exemplo
*
*
Pilhas
Operações Básicas: 
Empilhar ou PUSH: Acrescentar no topo da pilha
Desempilhar ou POP: Retirar do topo da pilha
*
*
Pilhas - Implementações
Sintaxe das Operações:
	Representação da pilha: p
	Elemento: e
		 Desempilhar: 
			e = pop(p); 
/* remove o elemento do topo e atribui seu valor a e */
		 Empilhar:
			push(p,e);
/* inclui o elemento e no topo */
*
*
Pilhas - Implementações
Por definição, não existe um número máximo de elementos na pilha
 Push pode ser aplicado em qualquer situação
Desempilhar um elemento em uma pilha vazia provoca erro
 Pop não pode ser aplicado em uma pilha vazia
Antes de aplicar pop, é preciso verificar se a pilha está vazia
*
*
Pilhas – Novas operações
 vazia(p)
Retorna TRUE se pilha vazia ou FALSE caso contrário
 topopilha(p)
Retorna o elemento do topo da pilha sem removê-lo (corresponde a um pop e um push)
Ex.: e = topopilha(p);
topopilha, assim como pop, não pode ser usado em uma pilha vazia
Para evitar o underflow, usar vazia antes de pop e topopilha
*
*
Pilhas – Exemplo de Aplicação
Exemplo: utilização de uma pilha para garantir o correto agrupamento de parênteses, colchetes e chaves em uma expressão matemática
Verificar se existe um número igual de símbolos abrindo e fechando de cada tipo
Verificar se todo símbolo fechando está precedido
de um abrindo do mesmo tipo
Ex.: ((A+B ou A+B(	violam o critério 1 
	 )A+B( ou (A+B))	violam o critério 2
	 (A+B] ou {A-(B]}	violam os 2 critérios
*
*
Pilhas – Exemplo de Aplicação
Percorrer toda a expressão:
A cada símbolo abrindo, empilhar
A cada símbolo fechando, desempilhar e verificar se é do mesmo tipo 
Expressão válida:
se ao final, a pilha estiver vazia
Expressão inválida:
se houver uma tentativa de desempilhar com a pilha vazia ou
se o símbolo desempilhado for diferente do atual ou
se ao final a pilha NÃO estiver vazia
*
*
Pilhas – Exemplo de Aplicação
Tentem agora fazer um algoritmo genérico!!
*
*
Pilhas - Exemplo de Aplicação
gets(exp); valida=1;
for (i=0; exp[i] && valida; i++) {
	if ( (exp[i]==“(“) || (exp[i]==“[“) || (exp[i]==“{“) )
		push(s,exp[i]);
 if ( (exp[i]==“)“) || (exp[i]==“]“) || (exp[i]==“}“) )
		if (vazia(s))
		 valida=0;
		else {
		 e=pop(s);
		 if (e != equiv(exp[i]))
			valida=0;
		}
}
if (!vazia(s))
	valida=0;
if (valida)
	printf(“Válida”);
else
	printf(“Inválida”);
*
*
Pilhas
2ª PARTE
*
*
Pilhas - Implementações
Diversas formas de implementar, que se distinguem por:
natureza dos elementos
maneira como elementos são armazenados
operações disponíveis
Duas formas clássicas: 
Listas Seqüenciais (Vetor)
Lista Encadeada
*
*
Pilhas em Listas Seqüenciais
Uma pilha é um conjunto ordenado de itens e a linguagem C já contém tal estrutura: o Vetor
Problema:
vetor tem tamanho fixo e limitado, enquanto que a pilha cresce à medida da necessidade, sem limite
Solução:
limitar o tamanho máximo da pilha ao tamanho do vetor
inclusão de um outro campo para armazenar o tamanho atual da pilha
considerar que, em nenhum momento, a pilha conterá mais elementos do que o tamanho do vetor
*
*
Pilhas em Vetor
Implementação da Pilha  estrutura com dois componentes:
um vetor para armazenar os elementos (item)
um inteiro para indicar a posição atual do topo (topo)
Detalhes:
o elemento 0 será definido como o fundo da pilha
topo é o índice da última posição ocupada na pilha
pilha vazia: topo igual a -1
restrição: tamanho máximo do vetor (MAX)
*
*
Pilhas em Vetor
2
topo
item
pilha
#define MAX 100
typedef int
	 tp_item;
typedef struct {
	int topo;
	tp_item item[MAX];
} tp_pilha;
tp_pilha pilha;
0
1
2
99
*
*
Pilhas em Vetor
Quando um elemento é empilhado, o valor de pilha.topo é incrementado em uma unidade
Quando um elemento é desempilhado, o valor de pilha.topo é decrementado de uma unidade
Pilha vazia: pilha.topo == -1
Inicialização da pilha: pilha.topo = -1
*
*
Implementação das funções
Por que modularizar?
deixar o programa mais legível
facilitar manutenção e alterações
reutilização do código
Funções:
iniciapilha(&pilha);
vazia(&pilha);
pop(&pilha);
push(e,&pilha);
topopilha(&pilha);
altura(&pilha);
*
*
Implementação das funções
iniciapilha(&pilha);
vazia(&pilha);
*
*
Implementação das funções
void iniciapilha(tp_pilha *p) {
	p->topo = -1; /* Pilha vazia */
}
int vazia(tp_pilha *p) {
	if(p->topo == -1) 
		return (1);
	else 
		return (0);
}
*
*
Implementação das funções
ok=push(e,&pilha);
*
*
Implementação das funções
int push (tp_item e, tp_pilha *p) {
	if(p->topo < MAX-1) 
	{ /* Possui espaço */ 
		p->item[++(p->topo)] = e;
 return(1);
	}
	else return(0); /* estouro da pilha */
}
*
*
Implementação das funções
e=pop(&pilha);
ok=pop(&e, &pilha);
*
*
Implementação das funções
int pop (tp_pilha *p) {
	if (vazia(p)) {
	 printf("Pilha Vazia!");
	 exit(1);
	}
	else
	 return (p->item[p->topo--]);
}
/* para chamar */
if (!vazia(&pilha))
	e = pop(&pilha);
else
	/* pilha vazia */
	
opcional
*
*
Implementação das funções
int pop (tp_item *e, tp_pilha *p){
	if (vazia(p)) {
		return (0);
	}
	else {
		*e = p->item[p->topo--];
		return (1);
	}
}
/* para chamar */
if (pop(&e,&pilha))
/* usar elemento */
else
	/* pilha vazia */
	
*
*
Implementação das funções
ok=topopilha(&pilha);
x=altura(&pilha);
*
*
Implementação das funções
int topopilha (tp_item *e; tp_pilha *p) {
	if (vazia(p))
		return (0);
	else {
		*e = p->item[p->topo];
		return (1);
	}
}
int altura (tp_pilha *p) {
	return (p->topo+1);
}
*
*
Exercícios
Exercícios
*
*
Implementação das funções
Implementar uma função que receba uma pilha como parâmetro e retire todos os elementos ímpares dessa pilha. Protótipo: 
void retira_impares(tp_pilha *p);
Implementar uma função que receba duas pilhas como parâmetro e empilhe a segunda sobre a primeira. Protótipo: 
void concat_pilhas(tp_pilha *p1,tp_pilha *p2));
*
102
*
*
146
*
156
*
156
*
156
*
156
*
155
*
155
*
155
*
156
*
157
*
157
*
155
*
155
*
155
*
278
*
102
*
102
*
102
*
102
*
102
*
104
*
104
*
104
*
104
*
104
*
104
*
104
*
104
*
104
*
104
*
105
*
105
*
105
*
105
*
105
*
105
*
106
*
105
*
106
*
105
*
107
*
107
*
105