PlanoDeAula_420054 - Listas Lineares Sequenciais e Encadeadas (Parte II)

Prévia do material em texto

Plano	de	Aula:	Listas	Lineares	Sequenciais	e	Encadeadas	(Parte
II)
ESTRUTURA	DE	DADOS	-	CCT0637
Título
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	II)
Número	de	Aulas	por	Semana
Número	de	Semana	de	Aula
9
Tema
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	II)
Objetivos
Possibilitar	ao	aluno:
-	Reconhecer	e	manipular	Listas	Duplamente	Encadeadas
-	Reconhecer	e	manipular	Listas	Circulares	Simples
-	Desenvolver	no	laboratório	os	conceitos	sobre	Listas	Simplesmente
Encadeadas,	Listas	Duplamente	Encadeadas	e	Listas	Circulares	Simples	por
meio	de	exercícios	guiados	que	criem	situações	de	uso	dessas	estruturas.
Estrutura	do	Conteúdo
CONTEÚDOS:
Lista
Listas	Encadeadas
Listas	Duplamente	Encadeadas
Listas	Circulares	Simples
RESUMO	DE	CONCEITOS:
Listas	Lineares	Encadeadas
Em	listas	lineares	encadeadas,	diferentemente	das	listas	lineares	sequenciais
(ou	contíguas),	os	elementos	não	estão	necessariamente	armazenados
sequencialmente	na	memória.	Assim,	para	manter	a	ordem	lógica	entre	os
elementos,	as	listas	lineares	encadeadas	podem	ser	implementadas	de	duas
formas:
	Duplamente	encadeada
Numa	lista	linear	duplamente	encadeada	cada	elemento	possui,	além	do
espaço	para	armazenamento	da	informação,	um	espaço	para	armazenar
a	referencia	da	localização	de	memória	onde	se	encontra	o	próximo
elemento	da	lista	e	outro	espaço	para	armazenar	a	referencia	da
localização	de	memória	onde	se	encontra	o	elemento	anterior.
A	representação	simbólica	para	a	lista	linear	duplamente	encadeada	é
apresentada	a	seguir:
	
Na	figura	acima	note	que,	na	lista	duplamente	encadeada,	o
campo	próximo	de	um	nó	faz	referência	ao	próximo	nó	da	lista,	e	o
campo	anterior	faz	referência	ao	nó	anterior	ao	nó	em	questão.
	
Uma	primeira	vantagem	da	utilização	de	lista	duplamente	encadeada	sobre	a
lista	simplesmente	encadeada	é	a	maior	facilidade	para	navegação,	que	na
lista	duplamente	encadeada	pode	ser	feita	nos	dois	sentidos,	ou	seja,	do	início
para	o	fim	e	do	fim	para	o	início.	Isso	facilita	a	realização	de	operações	tais
como	inclusão	e	remoção	de	nós,	pois	diminui	a	quantidade	de	variáveis
auxiliares	necessárias.
A	principal	vantagem	da	utilização	de	listas	encadeadas	sobre	listas
sequenciais	é	o	ganho	em	desempenho	em	termos	de	velocidade	nas
inclusões	e	remoções	de	elementos.	Em	uma	lista	contígua	é	necessário	mover
todos	os	elementos	da	lista	para	uma	nova	lista	para	realizar	essas	operações.
Com	estruturas	encadeadas,	como	não	existe	a	obrigatoriedade	dos
elementos	estarem	em	posições	contíguas	da	memória,	basta	realizar
alterações	nas	referências	dos	nós,	sendo	um	novo	nó	rapidamente	inserido
ou	removido.	Esta	estrutura	é	mais	adequada	para	listas	com	centenas	ou
milhares	de	nós,	onde	uma	inserção	ou	remoção	em	uma	lista	contígua
representará	uma	perda	notável	no	desempenho	do	processamento.
Rotinas	de	Manipulação	Lista	Duplamente	Encadeada
As	rotinas	inserção	e	remoção	de	elementos	numa	lista	são	realizadas
manipulando-se	a	referência	ao	próximo	nó	da	lista.	Observe	a	ilustração	a
seguir:
Inserção:
	
	
Remoção:
	
	
	
Veja	o	algoritmo	a	seguir:	
	
#include	<iostream>
using	namespace	std;
//	elemento	da	lista	-	nó	ou	nodo
struct	Nodo	{
	int	info;
	struct	Nodo	*ant;
	struct	Nodo	*prox;
}no;
int	main	()	{
	struct	Nodo	*inicio	=	NULL,	*tmp,	*p;
	int	v;
	while(	1	){
	cout	<<	endl	<<	"Valor?	"	;
	cin	>>	v	;
	if	(	v	==	0	)	break;
	//	cria	um	novo	nodo	para	ser	inserido	na	lista
	tmp	=	(struct	Nodo*	)	new	Nodo;
	tmp	->	info	=	v;	
	tmp	->	prox	=	NULL;
	if	(inicio	==	NULL)	{	//	lista	vazia
	inicio	=	tmp;
	tmp->ant	=	tmp->prox	=	NULL;
	}
	else	{
	//	p	irá	percorrer	a	lista	
	p	=	inicio;
	
	while	(	p->prox	!=	NULL	&&	p->info	!=	v)	{
	p	=	p->prox;
	}
	if	(	p->info	!=	v	){
	
	p->prox	=	tmp;
	tmp->ant	=	p;
	}
	}
	}
	
	//	mostrando	a	lista
	p	=	inicio;
	while	(	p	!=	NULL	)	{
	cout	<<	p->info;
	p	=	p->prox;
	}
	cout	<<	endl;
}
Listas	Circulares	Simples
O	algoritmo	de	busca	em	uma	lista	encadeada	pode	ser	melhorado	se
modificarmos	a	lista	de	modo	que	ela	passe	a	ser	circular	como	está	mostrado
na	figura	abaixo.	
lista	circular	encadeada
	
Neste	caso	o	algoritmo	não	tem	como	testar	o	final	da	lista.	A	solução	é
armazenar	o	dado	que	se	está	procurando	no	nó	cabeça.	Ao	término	do
algoritmo	a	chave	é	sempre	encontrada,	e	pode-se	descobrir	se	ela	pertencia
ou	não	a	lista	pelo	ponteiro	que	foi	dado	como	resposta.	Caso	o	ponteiro
termine	apontando	para	o	nó	cabeça,	podemos	afirmar	que	o	elemento	não	se
encontra	na	lista.
Os	algoritmos	de	procura,	inserção	e	remoção	em	uma	lista	circular	encadeada
estão	mostrados	no	programa	abaixo.	O	algoritmo	de	busca	aparece	como
parte	das	rotinas	de	inserção	e	remoção.	Neste	algoritmos	primeiro	se	procura
o	elemento	depois	se	decide	o	que	fazer.	No	algoritmo	de	busca,	caso	o
elemento	já	exista	na	lista,	não	há	nada	a	fazer,	caso	contrário	o
ponteiro	ant	aponta	para	o	elemento	após	o	qual	o	novo	elemento	será
inserido.	No	algoritmo	de	remoção,	a	busca	termina	apontando	para	o
elemento	a	ser	removido	(ponteiro	pont)	ou	com	a	indicação	que	o	elemento
não	se	encontra	na	lista	(pont	apontando	para	o	nó	cabeça).	
	
#include	<iostream>
#include	<ctype.h>	
#include	<stdlib.h>
using	namespace	std;
struct	tElemento	{	
								int	info;	
								struct	tElemento	*prox;	
};
char	tela();	
struct	tElemento	*cria_no();	
void	insere	(struct	tElemento	*,	int	);	
void	meu_remove	(struct	tElemento	*,	int);	
void	listar(struct	tElemento	*);
int	main()	
{	
				struct	tElemento	*ptlista;	
				char	linha[80];	
				char	opcao;	
				int	sair	=	0,	valor;
				ptlista	=	cria_no();	
				ptlista->prox=ptlista;	
	
				do	{	
											opcao	=	tela();	
											switch	(opcao)	{	
																		case	'i':	
																							puts("Qual	dado	a	inserir?");	gets(linha);	
																							cin	>>	linha	>>	valor;	
																							insere(ptlista,	valor);	
																							break;	
																		case	'r':	
																							puts("Qual	dado	a	remover?");	gets(linha);	
																							cin	>>	linha	>>	valor;
																							meu_remove(ptlista,	valor);	
																							break;	
																		case	'l':	
																							listar(ptlista);	
																							break;	
																		case	's':	
																							sair	=	1;	
																							break;	
																		default:	
																										puts("Opcao	invalida.");	
																										break;	
											}	
				}	while	(!sair);	
}	
	
char	tela	()	{
					char	opcao,	linha[80];
					puts("Qual	a	sua	opcao?");	
					puts("[L]istar,	[I]nserir,	[R]emover,	[S]air");	
					gets(linha);	
					cin	>>	linha	>>	&opcao;	
					return	tolower(opcao);	
}	
		
		
	
void	listar	(struct	tElemento	*ptlista)	{
					int	i=0;	
					struct	tElemento	*pont;
					pont	=	ptlista->prox;	
					while	(pont	!=	ptlista)	{	
											cout	<<	"Elemento	"	<<	i++	<<	"	=	"	<<	pont->info	<<	endl;	
											pont	=	pont->prox;	
					}	
}	
	
void	insere	(struct	tElemento	*ptlista,	int	valor)	{
					struct	tElemento	*pont,	*ant,	*pt;
/*	Aqui	esta	o	algoritmo	de	busca	em	uma	lista	circular	*/
			ant	=	ptlista;	pont	=	ptlista->prox;	
				ptlista->info	=	valor;
				while	(pont->info	<	valor)	{	
													ant	=	pont;	
													pont	=	pont->prox;	
				}
				if	(pont->info	==	valor	&&	pont	!=	ptlista)	
							puts("Elemento	ja	existe	na	tabela.");	
				else	{	
									pt	=	cria_no();	
									pt->info	=	valor;	
									pt->prox	=	pont;	
									ant->prox	=	pt;	
					}	
}
void	meu_remove	(struct	tElemento	*ptlista,	int	valor)	{	
					struct	tElemento	*pont,	*ant;
				ant	=	ptlista;	pont	=	ptlista->prox;	
				ptlista->info	=	valor;
				while	(pont->info	<	valor)	{	
										if	(pont->info<	valor)	{	
													ant	=	pont;	
													pont	=	pont->prox;	
										}	
				}
				if	(pont->info	==	valor	&&	pont	!=	ptlista)	{	
							ant->prox	=	pont->prox;	
							free(pont);	
				}	
				else	puts("Elemento	nao	existe	na	tabela.");	
}
struct	tElemento	*cria_no()	{
							struct	tElemento	*pt;
							if	((	pt	=	(struct	tElemento	*)	new	tElemento	)	==	NULL	)		
							{	
												puts("Nao	há	espaço.");	
												exit(1);	
							}	
							pt->info	=	-1;	
							pt->prox	=	NULL;	
							return	pt;	
}
	
Aplicação	Prática	Teórica
SUGESTÃO	DE	EXERCÍCIOS	PARA	SEMANA	09
TEÓRICOS
1.	 Ano:	2012	 /	Banca:	CESPE	 /	Órgão:	Banco	da	Amazônia	 /	Prova:	Técnico
Científico	-	Administração	de	Dados
	
Em	 algumas	 implementações,	 uma	 lista	 vazia	 pode	 ter	 um	 único	 nó,
chamado	 de	 sentinela,	 nó	 cabeça	 ou	 header.	 Entre	 suas	 possíveis
funções,	 inclui-se	 simplificar	 a	 implementação	 de	 algumas	 operações
realizadas	 sobre	 a	 lista,	 como	 inserir	 novos	 dados,	 recuperar	 o
tamanho	da	lista,	entre	outras.
(					)	Certo					(					)	Errado
	
1.	 Ano:	2012	 /	Banca:	CESPE	 /	Órgão:	Banco	da	Amazônia	 /	Prova:	Técnico
Científico	-	Administração	de	Dados
	
Estruturas	 ligadas	 como	 listas	 encadeadas	 superam	 a	 limitação	 das
matrizes	que	não	podem	alterar	seu	tamanho	inicial.
(					)	Certo					(					)	Errado
	
1.	 Ano:	2012	 /	Banca:	CESPE	 /	Órgão:	Banco	da	Amazônia	 /	Prova:	Técnico
Científico	-	Administração	de	Dados
	
As	 listas	 duplamente	 encadeadas	 diferenciam-se	 das	 listas
simplesmente	 encadeadas	 pelo	 fato	 de,	 na	 primeira,	 os	 nós	 da	 lista
formarem	um	anel	com	o	último	elemento	ligado	ao	primeiro	da	lista.
(					)	Certo					(					)	Errado
	
1.	 Ano:	2011	/	Banca:	CESPE	/	Órgão:	FUB	/	Prova:	Analista	de	Tecnologia	da
Informação
	
O	uso	de	 listas	encadeadas	na	representação	de	matrizes	 justifica-se,
entre	 outros	 motivos,	 quando	 a	 matriz	 é	 esparsamente	 povoada	 por
dados.	Em	uma	possível	implementação	para	esse	caso,	os	valores	dos
índices	 de	 cada	 dimensão	 da	 matriz	 são	 armazenados	 em	 listas
encadeadas,	e	cada	elemento	da	matriz	com	valor	diferente	de	zero	é
um	 nó	 (ou	 célula)	 em	 outra	 lista	 encadeada,	 acessível	 a	 partir	 das
listas	dos	índices	da	matriz.
(					)	Certo					(					)	Errado
	
1.	 Ano:	 2009	 /	 Banca:	 FCC	 /	 Órgão:	 TJ-PI	 /	 Prova:	 Analista	 Judiciário	 -
Tecnologia	da	Informação
	
Uma	 lista	 ligada	 é	 uma	 estrutura	 que	 corresponde	 a	 uma	 sequência
lógica	de	entradas	ou	nós.	Cada	nó	armazena	a	localização	do	próximo
elemento	na	sequência,	ou	seja,	de	seu	nó	sucessor.	Nessa	estrutura,
a)	 para	 estabelecer	 a	 ligação	 entre	 um	 nó	 já	 pertencente	 a
uma	 lista	 e	 um	 novo	 nó,	 basta	 fazer	 com	 que	 o	 novo	 nó
referencie	 no,	 campo	 next,	 o	 nó	 que	 anteriormente	 era
referenciado	pelo	nó	original,	desde	que	esse	campo	não	tenha
o	valor	nulo.
b)	a	existência	de	um	ponteiro	apontando	para	o	1º	elemento	e
outro	para	o	fim	da	lista	permite	que	a	inserção	ou	deleção	de
dados	de	um	nó	que	esteja	no	meio	da	 lista	seja	 rapidamente
executada.
c)	enquanto	a	entrada	que	determina	o	topo	da	lista	é	mantida
em	um	nó	descritor	dessa	 lista,	a	entrada	que	marca	o	 fim	da
lista	é	mantida	fora	do	descritor.
d)	o	armazenamento	de	uma	lista	requer	uma	área	contígua	de
memória	 para	 permitir	 a	 otimização	 no	 processamento	 de
criação	e	remoção	de	nós	da	lista.
e)	 o	 armazenamento	 de	 uma	 lista	 não	 requer	 uma	 área
contígua	 de	 memória.	 Como	 listas	 são	 estruturas	 dinâmicas,
normalmente	são	definidos	procedimentos	que	permitem	criar	e
remover	nós	na	memória.
	
PRÁTICOS
1.	 Descreva,	 em	 linguagem	 C++,	 a	 estrutura	 de	 uma	 das	 célula	 de	 uma
lista	duplamente	encadeada.
2.	 Escreva	uma	função	que	remova	de	uma	lista	duplamente	encadeada	a
célula	 apontada	 por	 p.	 (Que	 dados	 sua	 função	 recebe?	 Que	 coisa
devolve?)
3.	 Escreva	 uma	 função	 que	 insira	 em	 uma	 lista	 duplamente	 encadeada,
logo	 após	 a	 célula	 apontada	 por	 p,	 uma	 nova	 célula	 com	 conteúdo	 y.
(Que	dados	sua	função	recebe?	Que	coisa	devolve?)
4.	 Problema	 de	 Josephus.	 	 Imagine	 que	 temos	 n	 pessoas	 dispostas	 em
círculo.	 Suponha	 que	 as	 pessoas	 estão	 numeradas	 1	 a	 n	 no	 sentido
horário.	 Começando	 com	a	 pessoa	de	 número	1,	 percorra	 o	 círculo	 no
sentido	horário	e	elimine	cada	m-ésima	pessoa	enquanto	o	círculo	tiver
duas	ou	mais	pessoas.	Qual	o	número	do	sobrevivente?