PlanoDeAula_420053 - Listas Lineares Sequenciais e Encadeadas (Parte I)

Prévia do material em texto

Plano	de	Aula:	Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	I)
ESTRUTURA	DE	DADOS	-	CCT0637
Título
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	I)
Número	de	Aulas	por	Semana
Número	de	Semana	de	Aula
8
Tema
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	I)
Objetivos
Possibilitar	ao	aluno:
-	Reconhecer	o	TAD	Lista,	suas	caraterísticas	principais	e	variantes
-	Reconhecer	e	manipular	Listas	Lineares	Sequenciais
-	Reconhecer	e	manipular	os	diferentes	tipos	de	Listas	Encadeadas
-	Reconhecer	e	manipular	Listas	Simplesmente	Encadeadas
Estrutura	do	Conteúdo
CONTEÚDOS:
Lista	Lineares
Listas	Sequenciais
Listas	Encadeadas
Listas	Simplesmente	Encadeadas
RESUMO	DE	CONCEITOS:
Listas	Lineares
Lista	linear	é	uma	estrutura	de	dados	na	qual	elementos	de	um	mesmo	tipo	de
dado	estão	organizados	de	maneira	sequencial.	Não	necessariamente,	estes
elementos	estão	fisicamente	em	sequência,	mas	a	ideia	é	que	exista	uma
ordem	lógica	entre	eles.	Um	exemplo	disto	seria	um	consultório	médico:	as
pessoas	na	sala	de	espera	estão	sentadas	em	qualquer	lugar,	porém	sabe-se
quem	é	o	próximo	a	ser	atendido,	e	o	seguinte,	e	assim	por	diante.	Assim,	é
importante	ressaltar	que	uma	lista	linear	permite	representar	um	conjunto	de
dados	afins	(de	um	mesmo	tipo)	de	forma	a	preservar	a	relação	de	ordem
entre	seus	elementos.	Cada	elemento	da	lista	é	chamado	de	nó,	ou	nodo.
Definição:
Conjunto	de	N	nós,	onde	N	=	0,	x1,	x2,	...,	xn,	organizados	de	forma	a	refletir	a
posição	relativa	dos	mesmos.	Se	N	=	0,	então	x1	é	o	primeiro	nó.	Para	1	<	k	<
n,	o	nó	xk	é	precedido	pelo	nó	xk-1	e	seguido	pelo	nó	xk+1	e	xn	é	o	último	nó.
Quando	N	=	0,	diz-se	que	a	lista	está	vazia.	Exemplos	de	listas	lineares:
Pessoas	na	fila	de	um	banco;
Letras	em	uma	palavra;
Relação	de	notas	dos	alunos	de	uma	turma;
Itens	em	estoque	em	uma	empresa;
Dias	da	semana;
Vagões	de	um	trem;
Pilha	de	pratos;
Cartas	de	baralho.
Alocação	de	uma	lista
Quanto	a	forma	de	alocar	memória	para	armazenamento	de	seu	elementos,
uma	lista	pode	ser:
1.	 Sequencial	ou	Contígua
Numa	lista	linear	contígua,	os	nós	além	de	estarem	em	uma	sequência
lógica,	estão	também	fisicamente	em	sequência.	A	maneira	mais	simples
de	acomodar	uma	lista	linear	em	um	computador	é	através	da	utilização
de	um	vetor.
	
A	representação	por	vetor	explora	a	sequencialidade	da	memória	de	tal
forma	que	os	nós	de	uma	lista	sejam	armazenados	em	endereços
contíguos.
	
2.	 Encadeada
Os	elementos	não	estão	necessariamente	armazenados
sequencialmente	na	memória,	porém	a	ordem	lógica	entre	os	elementos
que	compõem	a	lista	deve	ser	mantida.
Operações	com	Listas
As	operações	comumente	realizadas	com	listas	são:
Criação	de	uma	lista
Remoção	de	uma	lista
Inserção	de	um	elemento	da	lista
Remoção	de	um	elemento	da	lista
Acesso	de	um	elemento	da	lista
Alteração	de	um	elemento	da	lista
Combinação	de	duas	ou	mais	listas
Classificação	da	lista
Cópia	da	lista
Localizar	nodo	através	de	elemento
Tipos	de	Listas	Lineares
Os	tipos	mais	comuns	de	listas	lineares	são	as:
pilhas
Uma	pilha	é	uma	lista	linear	do	tipo	LIFO	-	Last	In	First	Out,	o	último
elemento	que	entrou,	é	o	primeiro	a	sair.	Ela	possui	apenas	uma
entrada,	chamada	de	topo,	a	partir	da	qual	os	dados	entram	e	saem
dela.	Exemplos	de	pilhas	são:	pilha	de	pratos,	pilha	de	livros,	pilha	de
alocação	de	variáveis	da	memória,	etc.
filas
Uma	fila	é	uma	lista	linear	do	tipo	FIFO	-	First	In	First	Out,	o	primeiro
elemento	a	entrar	será	o	primeiro	a	sair.	Na	fila	os	elementos	entram	por
um	lado	("por	trás")	e	saem	por	outro	("pela	frente").	Exemplos	de	filas
são:	a	fila	de	caixa	de	banco,	a	fila	do	INSS,	etc.
deques
Um	deque	-	Double-Ended	QUEue)	é	uma	lista	linear	na	qual	os
elementos	entram	e	saem	tanto	pela	"pela	frente"	quanto	"por	trás".
Pode	ser	considerada	uma	generalização	da	fila.
Assim	o	que	vai	distinguir	os	diferentes	tipos	de	listas	são	as	operações	que
se	podem	realizar	sobre	as	mesmas,	podendo	tanto	serem	implementadas	com
alocação	sequencial	quanto	com	alocação	encadeada.
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:
Simplesmente	encadeada
Numa	lista	linear	simplesmente	encadeada	cada	elemento	possui,	além
do	espaço	para	armazenamento	da	informação,	um	espaço	para
armazenar	uma	referência	da	localização	na	memória	onde	o	próximo
elemento	da	lista	(ou	o	anterior)	se	encontra.
	
A	representação	simbólica	para	a	lista	linear	simplesmente	encadeada	é
apresentada	a	seguir:
	
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	Simplesmente	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;
struct	Nodo	{
	int	info;
	struct	Nodo	*prox;
};
struct	ListaSimplesEnc	{
	struct	Nodo	*prim;
};
void	criarLista	(struct	ListaSimplesEnc	*pList)	{
	pList	->	prim	=	NULL;
}
void	mostrarLista	(struct	ListaSimplesEnc	*pList){
	struct	Nodo	*p;
	for	(p	=	pList	->	prim;	p	!=	NULL;	p	=	p->prox)	{
	cout	<<	p->info	<<	endl;
	}
	cout	<<	endl;
}
void	inserirIni	(struct	ListaSimplesEnc	*pList,	int	v){
	struct	Nodo	*novo;
	novo	=	(struct	Nodo*)	new	Nodo;
	novo	->	info	=	v;
	novo	->	prox	=	pList	->	prim;
	pList	->	prim	=	novo;
}
void	removerIni	(struct	ListaSimplesEnc	*pList){
	struct	Nodo	*pAux	=	pList	->	prim;
	pList	->	prim	=	pList	->	prim	->	prox;
	delete(pAux);
}
void	inserirOrd	(struct	ListaSimplesEnc	*pList,	int	v){
	struct	Nodo	*novo;
	novo	=	(struct	Nodo*)	new	Nodo;
	novo	->	info	=	v;
	
	struct	Nodo	*pAtu,	*pAnt;
	pAnt	=	NULL;
	pAtu	=	pList	->	prim;
	while	(	pAtu	!=	NULL	&&	pAtu->info	<	v){
	pAnt	=	pAtu;
	pAtu	=	pAtu	->	prox;
	}
	novo	->	prox	=	pAtu	->	prox;
	pAnt	->	prox	=	novo;
}
int	estaVazia(struct	ListaSimplesEnc	*pList)	{
	return	(pList->prim	==	NULL);
}
int	main	()	{
	struct	ListaSimplesEnc	minhaLista;
	int	valor,	op;
	criarLista(&minhaLista);
	while(	1	){
	printf(	"1	-	Inserir	elemento	no	inicio\n"	);
	printf(	"2	-	Inserir	elemento	em	ordem	(so	se	a	lista	estiver	ordenada)\n"	);
	printf(	"3	-	Remover	elemento	no	inicio\n"	);
	printf(	"4	-	Remover	elemento\n"	);
	printf(	"5	-	Mostrar	lista\n"	);
	printf(	"6	-	Sair\n"	);
	printf(	"Opcao?	"	);
	cin	>>	op	;
	switch(	op	){
	case	1:	//	inserir	elemento	no	inicio
	
	cout	<<	"Valor?	";
	cin	>>	valor	;
	inserirIni(&minhaLista,	valor);
	break;
	case	2:	//	inserir	elemento	ordenado
	cout	<<	"Valor?	"	;
	cin	>>	valor	;
	inserirOrd(&minhaLista,	valor);
	break;
	case	3:	//	remover	o	primeiro
	break;
	case	4:	//	remover	determinado	elemento
	break;
	case	5:	//		mostrar	lista
	if	(estaVazia(&minhaLista))	{
	cout	<<	"Lista	vazia";
	}
	else	{
	mostrarLista(&minhaLista);
	}
	break;
	case	6:	//	abandonar	o	programa
	exit(0);
	}
	}
}
Aplicação	Prática	TeóricaSUGESTÃO	DE	EXERCÍCIOS	PARA	SEMANA	08
PRÁTICOS
1.	 Escreva	um	programa	para	concatenar	duas	listas	-	A	e	B	gerando	uma
terceira	lista	onde	devem	estar	em	primeiro	lugar,	os	elementos	da	lista
A	e	em	seguida	os	elementos	da	lista	B.
2.	 Escreva	 um	 subrotina	 para	 comparar	 duas	 listas	 de	 caracteres.	 A
subrotina	deve	retornar	1	(verdadeiro)	se	os	elementos	das	duas	 listas
são	os	mesmos	(e	na	mesma	ordem)	ou	então	0	(falso)	caso	não	sejam
iguais.
3.	 Escreva	 uma	 subrotina	 que	 a	 partir	 de	 duas	 listas	 de	 caracteres
informadas	 como	parâmetro	 verifique	 se	 todos	os	elementos	da	 lista	A
estão	contidos	também	na	lista	B	(independentemente	da	ordem).
4.	 Dadas	 duas	 listas	 A	 e	 B,	 ambas	 com	 n	 elementos,	 escreva	 uma
subrotina	 que	 informe	 qual	 é	 o	 primeiro	 elemento	 da	 lista	 A	 que	 não
está	presente	na	lista	B.
5.	 Especifique	 um	 novo	 TAD	 para	 representar	 uma	 lista	 de	 pontos	 que
representam	um	caminho	no	plano	cartesiano	a	ser	percorrido.	Além	das
funções	 para	 inclusão,	 pesquisa	 e	 remoção	 implemente	 também	 uma
operação	 que	 calcule	 o	 tamanho	 do	 caminho	 percorrido	 se	 todos	 os
pontos	da	lista	forem	visitados.
6.	 Escreva	 uma	 subrotina	 para	 inverter	 os	 apontadores	 de	 uma	 lista.	 O
elemento	que	antes	representava	o	início	da	lista	passará	a	ser	o	último
elemento	e	o	que	atualmente	é	o	último	passará	a	ser	o	primeiro.
7.	 Escreva	 uma	 função	 que	 copie	 o	 conteúdo	 um	 vetor	 para	 uma	 lista
encadeada.
8.	 Escreva	uma	função	que	copie	o	conteúdo	de	uma	lista	encadeada	para
um	vetor.
9.	 Escreva	uma	função	que	faça	uma	cópia	de	uma	lista	dada.
10.	 Escreva	 uma	 função	 que	 concatene	 duas	 listas	 encadeadas	 (isto	 é,
engate	a	segunda	no	fim	da	primeira).
11.	 Escreva	 uma	 função	 que	 conte	 o	 número	 de	 células	 de	 uma	 lista
encadeada.	 Escreva	 uma	 função	 que	 remova	 a	 k-ésima	 célula	 de	 uma
lista	encadeada	sem	cabeça.
12.	 Escreva	uma	função	que	insira	na	lista	uma	nova	célula	com	conteúdo	x
entre	a	k-ésima	e	a	k+1-ésima	células.
13.	 Escreva	 uma	 função	 que	 verifique	 se	 duas	 listas	 dadas	 são	 iguais,	 ou
melhor,	se	têm	o	mesmo	conteúdo.
14.	 Escreva	uma	função	que	desaloque	(função	free)	todos	os	nós	de	uma
lista	 encadeada.	 	 Estamos	 supondo,	 é	 claro,	 que	 cada	 nó	 da	 lista	 foi
originalmente	alocado	por	malloc.	
15.	 Escreva	 uma	 função	 que	 inverta	 a	 ordem	 das	 células	 de	 uma	 lista
encadeada	 (a	primeira	passa	a	 ser	 a	última,	 a	 segunda	passa	a	 ser	 a
penúltima	 etc.).	 Faça	 isso	 sem	 usar	 espaço	 auxiliar,	 apenas	 alterando
ponteiros.
16.	 Projeto	de	programação:	contagem	de	palavras.		Digamos	que	um	texto
é	 um	vetor	 de	 caracteres	 que	 contém	apenas	 letras,	 espaços	 e	 sinais
de	 pontuação.	 Digamos	 que	 uma	 palavra	 é	 um	 segmento	 maximal	 de
texto	 que	 consiste	 apenas	 de	 letras.	 Escreva	 uma	 função	 que	 receba
um	 texto	e	 imprima	uma	 relação	de	 todas	as	palavras	que	ocorrem	no
texto	 juntamente	 com	 o	 número	 de	 ocorrências	 de	 cada	 palavra.	 Use
uma	lista	para	armazenar	as	palavras.