PlanoDeAula_420041 - Listas Lineares Sequenciais e Encadeadas (Parte IV)

Prévia do material em texto

Plano	de	Aula:	Listas	Lineares	Sequenciais	e	Encadeadas	(Parte
IV)
ESTRUTURA	DE	DADOS	-	CCT0637
Título
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	IV)
Número	de	Aulas	por	Semana
Número	de	Semana	de	Aula
11
Tema
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	IV)
Objetivos
Possibilitar	ao	aluno:
-	Reconhecer	e	manipular	o	TAD	Fila
-	Desenvolver	no	laboratório	os	conceitos	sobre	o	TAD	Fila	por	meio	de
exercícios	guiados	que	criem	situações	de	uso	dessas	estruturas.
Estrutura	do	Conteúdo
CONTEÚDOS:
Fila
RESUMO	DE	CONCEITOS:
Filas
As	filas	são	listas	onde	o	primeiro	elemento	a	ser	inserido	é	sempre	o	primeiro
a	ser	removido.	Por	isso	as	filas	são	muitas	vezes	chamadas	de	FIFO	(First	In
First	Out).
	
Por	exemplo,	se	os	números	3	5	7	2	e	8	forem	inseridos	em	uma	pilha	nesta
ordem,	então	eles	deverão	ser	removidos	nesta	mesma	ordem.
Como	no	caso	de	pilhas	as	filas	também	podem	ser	implementadas	de	forma
estática	ou	dinâmica.
Especificação:	
1.	 FIL*Inicia_Fila(int	N)
Cria	uma	nova	estrutura	de	fila	com	tamanho	máximo	N.
2.	 ENQUEUE(FIL*q,	int	A)
Insere/Enfileira	um	novo	elemento	A	no	fim	da	fila	Q
3.	 int	DEQUEUE(FIL	*q)
Retira/Desenfileira	o	elemento	do	início	da	fila	Q	retornando	seu
valor
4.	 int	SIZE(FIL	*q)
retorna	o	valor	correspondente	a	quantidade	de	elementos
armazenados	na	Fila
5.	 int	IS_EMPTY(FIL	*q)
retorna	o	valor	1	se	a	Fila	estiver	vazia	e	0,	caso	contrário.
Implementação	(Estática)
Utilizando-se	array,	filas	podem	ser	facilmente	implementadas.	Para	isto,	basta
armazenarmos	as	informações	do	início	e	do	final	da	fila.	Quando	um	elemento
é	inserido	ou	removido,	incrementamos	o	marcador	de	início	ou	fim	da	fila
respectivamente.
Após	um	certo	número	de	inclusões	e	remoções,	o	marcador	de	início	da	fila
pode	alcançar	o	final	do	array	e	ainda	restar	espaço	disponível	para
armazenamento.
Existem	duas	formas	de	se	resolver	o	problema:
1.	 Deslocar	elementos
2.	 Utilizar	um	array	"circular"
A	ideia	de	deslocar	elementos	é	a	mais	simples,	por	outro	lado	envolve	tempo
computacional.	Utilizando	o	conceito	de	array	circular	descartamos	os
deslocamentos.	Um	vetor	circular	pode	ser	implementado	com	a	ajuda	da
função	modulo.
Exemplo:	
Suponha	um	array	de	tamanho	10	e	seja	"fim''	e	"ini''	as	variáveis	que	marcam
o	início	e	o	final	da	fila.	Se	implementarmos	as	operações	de	inclusão	e
remoção	como	abaixo,	não	precisaremos	de	deslocamentos:
	
typedef	struct	Fila	FL;
struct	Fila
{
	int	ini;
	int	fim;
	int	fila[10];
};
void	Insere_Elemento(FL	*F,	int	A)
{
	int	aux;
	aux	=	(F->fim+1)%10;
	if	(aux	!=	F->ini)
	{
	F->fim	=	aux;
	F->fila[aux]	=	A;
	}
	else
	cout	<<	"	Fila	Cheia"	<<	endl;
}
Implementação	(Dinâmica)
typedef	struct	Fila	FL;
typedef	struct	No_fila	NO;
struct	No_fila
{
	int	elem;
	NO	*prox;
}
struct	Fila
{
	NO	*ini;
	NO	*fim;
}
/*	Exercício:	Implementar	as	operações	de	inclusão	e	remoção	*/
Aplicação	Prática	Teórica
SUGESTÃO	DE	EXERCÍCIOS	PARA	SEMANA	11
TEÓRICOS
1.	 Ano:	 2013	 /	 Banca:	 FCC	 /	 Órgão:	 TRT	 -	 9ª	 REGIÃO	 (PR)	 /	 Prova:	 Técnico
Judiciário	-	Tecnologia	da	Informação
	
Insira	os	dados	de	entrada	numa	fila.	Em	seguida	retire	cada	dado	da
fila	e	insira	numa	pilha.	Mostre	a	pilha.	Depois	retire	os	dados	da	pilha
e	insira	na	fila.	Mostre	a	fila.
	
Dados	de	entrada:	11,	12,	23,	14,	25,	50,	8,	18,	29,	10
	
As	estruturas	mostradas	ficam
I.	Pilha:	(topo)	10	-	29	-	18	-	8	-	50	-	25	-	14	-	23	-	12	-	11
II.	Fila:	(começo)	11	-	12	-	23	-	14	-	25	-	50	-	8	-	18	-	29	-	10	(fim)
III.	Fila:	(começo)	10	-	29	-	18	-	8	-	50	-	25	-	14	-	23	-	12	-	11	(fim)
IV.	Pilha:	(topo)	11	-	12	-	23	-	14	-	25	-	50	-	8	-	18	-	29	-	10
V.	A	fila	mostrada	fica	com	os	elementos	em	ordem	invertida	dos
dados	de	entrada
	
Está	correto	o	que	se	afirma	APENAS	em
a)	III	e	IV.
b)	II	e	IV.
c)	I,	II	e	III.
d)	I,	III	e	V.
e)	I,	IV	e	V.
	
1.	 Ano:	 2012	 /	 Banca:	 ESAF	 /	 Órgão:	 Receita	 Federal	 /	 Prova:	 Analista
Tributário	da	Receita	Federal
	
Assinale	a	opção	correta.
a)	Uma	fila	é	um	tipo	de	lista	linear	em	que	todas	as	categorias
são	 inseridas	 em	 um	 extremo,	 ficando	 as	 classes	 restritas	 ao
outro	extremo.
b)	 Uma	 pilha	 é	 um	 tipo	 de	 lista	 linear	 em	 que	 todas	 as
operações	de	inserção	e	remoção	são	realizadas	numa	mesma
extremidade.
c)	 Uma	 fila	 é	 um	 tipo	 de	 lista	 colinear	 em	 que	 inserções
parametrizadas	 são	 realizadas	 no	 mesmo	 extremo	 que	 as
remoções.
d)	 Uma	 pilha	 é	 um	 tipo	 de	 lista	 encadeada	 em	 que	 todas	 as
operações	de	inserção	e	retrieve	são	realizadas	na	extremidade
mais	próxima.
e)	 Uma	 pilha	 é	 um	 fila	 linear	 em	 que	 todas	 as	 operações	 de
carry	e	stand	são	realizadas	numa	mesma	extremidade.
	
1.	 Ano:	2010	/	Banca:	ESAF	/	Órgão:	CVM	/	Prova:	Analista	de	Sistemas
	
Uma	fila	é	um	tipo	de	lista	linear	em	que
a)	as	inserções	são	realizadas	em	um	extremo	e	as	remoções
no	outro	extremo.
b)	as	inserções	e	remoções	são	realizadas	em	um	mesmo
extremo.
c)	podem	ser	realizadas	apenas	inserções.
d)	a	inserção	de	um	elemento	requer	a	remoção	de	outro
elemento.
e)	a	ordem	de	saída	não	corresponde	à	ordem	de	entrada	dos
elementos.
	
1.	 Ano:	 2010	 /	 Banca:	 FCC	 /	 Órgão:	 TRT	 -	 22ª	 Região	 (PI)	 /	 Prova:	 Analista
Judiciário	-	Tecnologia	da	Informação
	
Uma	fila	duplamente	terminada,	isto	é,	uma	estrutura	linear	que
permite	inserir	e	remover	de	ambos	os	extremos	é	chamada
a)	Árvore.
b)	Shift-and.
c)	Autômato.
d)	Deque.
e)	Boyer-Moore.
	
PRÁTICOS
1.	 Escreva	uma	função	que	devolva	o	comprimento	 (ou	seja,	o	número	de
elementos)	de	uma	fila	dada.
2.	 Escreva	funções	sai	e	entra	para	remover	e	inserir	em	uma	fila.	Lembre-
se	de	que	uma	fila	é	um	pacote	com	dois	objetos:	um	vetor	e	dois	índice.
Quais	os	parâmetros	de	suas	funções?	Não	use	variáveis	globais.
3.	 Imagine	 um	 tabuleiro	 quadriculado	 com	 m×n	 casas	 dispostas	 em	 m
linhas	 e	 n	 colunas.	 	 Algumas	 casas	 estão	 livres	 e	 outras	 estão
bloqueadas.	As	 casas	 livres	 são	marcadas	com	 -	e	as	bloqueadas	com
#.	Há	um	robô	na	casa	(1,1),	que	é	livre.	O	robô	só	pode	andar	de	uma
casa	 livre	para	outra.	Em	cada	passo,	 só	pode	andar	para	a	 casa	que
está	 ao	 norte,	 a	 leste,	 ao	 sul	 ou	 a	 oeste.	 Ajude	 o	 robô	 a	 encontrar	 a
saída,	 que	 está	 na	 posição	 (m,n).	 	 	 (Sugestão:	 Faça	 uma	 moldura	 de
casas	bloqueadas.)
4.	 Resolva	os	seguintes	problemas	a	respeito	da	implementação	circular	de
uma	fila.	(Lembre-se	de	que	uma	fila	é	um	pacote	com	três	objetos:	um
vetor	e	dois	índices.)			(a)	Escreva	uma	função	que	remova	um	elemento
da	 fila.	Quais	 são	 os	 parâmetros	 da	 função?	 	 	 (b)	 Escreva	 uma	 função
que	 insira	 um	número	 na	 fila.	 	 	 (c)	 Escreva	 uma	 função	 que	 devolva	 o
comprimento	(ou	seja,	o	número	de	elementos)	da	fila.
5.	 Redimensionamento.	 	 Se	 a	 fila	 ficar	 cheia,	 é	 uma	 boa	 ideia	 alocar	 um
novo	vetor	e	 transferir	a	 fila	para	esse	novo	vetor.	Escreva	uma	 função
que	 faça	 esse	 redimensionamento.	 É	 uma	 boa	 ideia	 fazer	 com	 que	 o
novo	vetor	tenha	o	dobro	do	tamanho	do	original.
6.	 Uma	 fila	dupla	 (=	 deque)	 permite	 saída	 e	 entrada	 em	 qualquer	 das
duas	 extremidades	 da	 fila.	 Implemente	 uma	 fila	 dupla	 e	 programe	 as
funções	de	manipulação	da	estrutura.
7.	 Implemente	uma	fila	em	uma	lista	encadeada	circular	sem	célula-cabeça.
Basta	 manter	 o	 endereço	 fim	 da	 última	 célula;	 a	 primeira	 célula	 será
apontada	por	fim->prox.	Se	a	lista	encadeada	estiver	vazia	então	fim	==
NULL.
8.	 Implemente	uma	fila	em	uma	lista	encadeada	simples	(não	circular)	com
célula-cabeça.	 Será	 preciso	 manter	 o	 endereço	 ini	 da	 célula-cabeça	 e
um	ponteiro	fim	para	a	última	célula.
9.	 Implemente	uma	fila	em	uma	lista	encadeada	simples	sem	célula-cabeça.
Será	preciso	manter	um	ponteiro	ini	para	a	primeira	célula	e	um	ponteirofim	para	a	última.
10.	 Implemente	 uma	 fila	 em	 uma	 lista	 duplamente	 encadeada	 sem	 célula-
cabeça.	 Use	 um	 ponteiro	 ini	 para	 a	 primeira	 célula	 e	 um	 ponteiro	 fim
para	a	última.
11.	 Escreva	programa	para	duplicar	o	conteúdo	de	uma	fila.	A	fila	resultado
e	a	original	devem	apresentar	os	elementos	na	mesma	ordem.
12.	 Escreva	um	programa	para	 concatenar	duas	 filas	 -	A	e	B	gerando	uma
terceira	fila	onde	devem	estar	em	primeiro	lugar,	os	elementos	da	fila	A
e	 em	 seguida	 os	 elementos	 da	 fila	 B	 (em	 ambos	 os	 casos	 deve	 ser
mantida	a	ordem	original).
13.	 Considere	 a	 existência	 de	 duas	 filas	 A	 e	 B	 onde	 os	 elementos	 estão
ordenados	da	seguinte	forma:	o	maior	deles	está	no	começo	da	fila	e	o
menor	 no	 final.	 Escreva	 um	 programa	 que	 crie	 uma	 fila	 com	 os
elementos	das	duas	filas	A	e	B	também	ordenados.
14.	 Implemente	um	programa	que	receba	três	filas:	F,	F_Impares	e	F_Pares,	e
separe	 todos	 os	 valores	 guardados	 em	 F	 de	 tal	 forma	 que	 os	 valores
pares	são	movidos	para	a	fila	F_Pares	e	os	valores	 ímpares	sãomovidos
para	F_Impares.