EX-LDE

Prévia do material em texto

1	
 
UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL 
INSTITUTO DE INFORMÁTICA 
Bacharelado em Ciência da Computação e 
Engenharia da Computação 
INF 01203 – Estruturas de Dados 
Profa. Renata Galante (galante@inf.ufrgs.br ) 
Exercícios sobre Lista Duplamente Encadeada (LDE ) 
 
Nomes: ____________________________________________________ 
 ____________________________________________________ 
 ____________________________________________________ 
 
01. Complete as atualizações de ponteiros que estão faltando nos código 
abaixo. Considere a estrutura de dados a seguir que é uma lista duplamente 
encadeada: 
struct TipoPtNo{ 
 int codigo; 
 char nome[20]; 
 float preco; 
 struct TipoPtNo* ant; 
 struct TipoPtNo* prox; 
 }; 
typedef struct TipoPtNo PtNo; 
01.a) Lista todos os nós do início para o fim.		
void imprime(PtNo* PtLista) 
{ 
 PtNo* PtAux=PtLista; 
 if (PtLista == NULL) 
 puts("lista vazia"); 
 else 
 do { 
 printf("Codigo = %d Nome = %s Preco = %f\n", 
 PtAux->codigo, 
 PtAux->nome, 
 PtAux->preco); 
 
 _______________________ 
 
 } while (_______________________); 
} 
	
 
 
 
	 2	
01.b) Lista todos os nós do fim para o início.		
void imprimeInvertida(PtNo *PtLista){ 
 PtNo *PtAux; 
 if (PtLista==NULL){ 
 printf("Lista vazia ! "); 
 }else 
 { PtAux=PtLista; 
 while (PtAux->prox!=NULL) 
 
 ____________________; 
 
 while (_________________) { 
 printf("Codigo = %d Nome = %s Preco = %f\n", 
 PtAux->codigo, 
 PtAux->nome, 
 PtAux->preco); 
 
 _____________________; } } } 
 
01.c) Destrói a lista. 
PtNo* destroi(PtNo* ptLista) 
{ PtNo *PtAux; 
 while (ptLista != NULL) 
 { 
 PtAux = ________________; 
 
 ptLista = ______________; 
 free(PtAux);} 
 
return ________; 
} 
 
01.d) Insere um nó no início da lista. 
PtNo* insereInicio(PtNo *PtLista, InfoNo Dado) 
{ 
 PtNo *Pt; 
 Pt = (PtNo*) malloc(sizeof(PtNo)); 
 Pt->info = Dado; 
 
 Pt->ant = _____________________; 
 Pt->prox = ____________________; 
 if (PtLista != NULL) 
 PtLista->ant = ______________; 
 PtLista = ______________________; 
 return PtLista; 
} 
 
	 3	
01.e) Insere um nó no final da lista. 
PtNo* insereFinal(PtNo *PtLista, InfoNo Dado) 
{ 
 PtNo *Pt, *PtAux; 
 Pt = (PtNo*) malloc(sizeof(PtNo)); 
 Pt->info = Dado; 
 if ((PtLista) == NULL) 
 { 
 PtLista = _________________; 
 Pt->ant = _________________; 
 Pt->prox = ________________; 
 } 
 else { 
 PtAux = PtLista; 
 while (PtAux->prox != NULL) 
 PtAux=_______________________; 
 PtAux->prox = ____________________; 
 Pt->ant = ________________________; 
 Pt->prox = _______________________; 
 } 
 return PtLista; 
} 
 
02.	Considere	o	código	abaixo	para	responder	esta	questão.		
struct Aluno{ 
 int cartao; 
 struct Aluno* Ant; 
 struct Aluno* Prox; 
 }; 
typedef struct Aluno TipoPtNo; 
 
TipoPtNo* FazAlgumaCoisa(TipoPtNo *PtLista){ 
 TipoPtNo *PtAux; 
 
 if (PtLista==NULL){ 
 printf("Lista vazia ! "); 
 } else 
 { 
 PtAux=PtLista; 
 while (PtAux->Prox!=NULL) 
 PtAux=PtAux->Prox; 
 
 PtLista=PtAux; 
 
 do{ 
 PtAux->Prox = PtAux->Ant; 
 PtAux=PtAux->Ant; 
 
 } while (PtAux!=NULL); 
 } 
 return PtLista;} 
	 4	
02.(a)		–	O	que	faz	o	procedimento	FazAlgumaCoisa()?	Atenção:	NÃO	descreva	a	
função	 linha	 por	 linha	 e	 SIM	 explique,	 com	 suas	 palavras,	 qual	 o	 problema	 que	 a	
função	resolve.	
	
	
	
	
	
	
	
	
02.(b)	–	Considerando	que	a	função	FazAlgumaCoisa()recebe	como	entrada	o	
ponteiro	PtLista	que	aponta	para	o	primeiro	elemento	da	 lista	do	desenho	abaixo,	
mostre	(desenhe)	a	lista	resultante	após	a	execução	da	função.		
	
	
	
	
	
	
	
	
	
02.(c)	 	 –	 Liste	 a	 ordem	 em	 que	 os	 elementos	 da	 lista	 do	 enunciado	 02(b)	 serão	
exibidos	 se	 executarmos	 a	 função	imprime()	 abaixo	 após	 a	 execução	 da	 função	
FazAlgumaCoisa().	
	
void imprime(TipoPtNo *PtLista) 
{ 
 PtNo* PtAux=PtLista; 
 if (PtLista == NULL) 
 puts("lista vazia"); 
 else 
 while (PtAux != NULL){ 
 printf("Cartão = %d \n", PtAux->cartao); 
 PtAux = PtAux->prox; 
 } 
} 
	
	
Lista	Resultante:		____________,			____________,				____________,				____________,	
	 5	
03.	 Jogo	 dos	 7	 erros.	 Marque	 (circule)	 no	 código	 da	 página	 a	 seguir	 os	 7	 erros	
encontrados	 no	 código	 e	 assinale	 abaixo	 a	 alternativa	 que	 contém	 a	 correção	 do	
código	(as	alternativas	contem	as	correções	na	ordem	em	que	aparecem	no	código)	
	
	(A)						*aux != ptr; 
valor == ptr->info 
ptr->ant=novo; 
while 
aux->prox != NULL 
valor > aux->info 
return (ptr); 
	
(B)							valor < ptr->info 
*aux=ptr; 
while 
ptr->ant==novo; 
aux->prox != NULL 
return free(ptr); 
valor > aux->info 
 
(C)						*aux=ptr; 
valor < ptr->info 
ptr->ant=novo; 
while 
aux->prox != NULL 
valor > aux->info 
return (ptr); 
 
(D)							aux=*ptr; 
valor < ptr->info 
ptr->ant=novo; 
while 
aux->prox != NULL 
valor > aux->info 
return free(ptr); 
	
03(b)	–	Explique	o	que	faz	a	função	Misterio().	Atenção:	NÃO	descreva	a	função	linha	
a	linha	e	SIM	explique,	com	suas	palavras,	qual	é	o	problema	que	a	função	resolve.	
 
	
	
	
	
	
 
 
	 6	
struct TipoPtNo{ 
 int info; 
 TipoPtNo* prox; 
 TipoPtNo* ant; 
}; 
 
TipoPtNo* Misterio(TipoPtNo *ptr, int valor) 
{ TipoPtNo *novo, *aux=&ptr; 
if (novo=( TipoPtNo *)malloc(sizeof(TipoPtNo))) 
 { if (ptr==NULL) 
 { novo->info=valor; 
 novo->prox = NULL; 
 novo->ant = NULL; 
 ptr=novo; 
 } 
 else if (valor > ptr->info) 
 { novo->info=valor; 
 novo->prox=ptr; 
 novo->ant=NULL; 
 ptr->ant=novo->prox; 
 ptr=novo; 
 } 
 else 
 { for(valor > aux->info && aux->prox != ptr) 
 aux=aux->prox; 
 if(valor != aux->info) 
 { novo->info = valor; 
 novo ->prox = NULL; 
 novo->ant = aux; 
 aux->prox = novo; } 
 else 
 { novo->info = valor; 
 novo->prox = aux; 
 novo->ant = aux->ant; 
 aux->ant = novo; 
 (novo->ant)->prox = novo; 
 } 
 } 
 return (novo); 
 } 
 else{ printf(“Erro ao alocar memoria!”); 
 } 
 } 
 
	 7	
04.	Os	elementos	em	uma	lista	duplamente	encadeada	com	20	elementos	possuem	
cada	um	três	campos:	
• proximo	–	um	ponteiro	para	o	próximo	elemento	da	lista;	
• valor	–	informação	armazenada	pelo	elemento	da	lista;	
• anterior	–	um	ponteiro	para	o	elemento	anterior	da	lista.	
	
Sendo	"Z"	o	décimo	elemento	desta	lista	e	"X"	e	"Y"	dois	outros	elementos	que	não	
pertencem	à	lista,	com	seus	respectivos	ponteiros	"ptZ",	"ptX"	e	"ptY",	considere	o	
trecho	de	código	abaixo.	
 
ptY->proximo = ptX; 
ptX->anterior = ptY; 
ptX->proximo = ptZ->proximo; 
ptZ->proximo->anterior=ptX; 
ptZ->proximo = ptY; 
ptY->anterior = ptZ; 
	
Este	trecho	de	código	é	usado	para	inserir	na	lista	os	elementos:	
a)	Y,	logo	após	o	Z,	e	X,	logo	após	o	Y.	
b)	Y,	antes	do	Z,	e	X,	logo	após	o	Z.	
c)	Y,	antes	do	Z,	e	X,	antes	do	Y.	
d)	X,	logo	após	o	Z,	e	Y,	logo	após	o	X.	
e)	X,	antes	do	Z,	e	Y,	logo	após	o	Z.	
	 	
	 8	
05.	 Escreva	 uma	 função	 em	 C	 que	 encontra	 o	 elemento	 do	 meio	 de	 uma	 lista	
duplamente	encadeada	sem	utilizar	contadores.	Caso	a	lista	tenha	um	número	par	
de	 elementos,	 qualquer	 dos	 dois	 elementos	 do	meio	 podem	 ser	 retornados.	 Se	 a	
lista	for	vazia,	retornar	0.	Note	que	a	lista	possui	apenas	um	ponteiro	ptLista	que	
apontapara	 o	 primeiro	 elemento	 da	 lista.	 A	 função	 deve	 retornar	 o	 conteúdo	 do	
campo	de	informação	do	nó.		
Exemplos:		 Entrada:	5	2	7	4	8		 	 Saída	esperada:	7	
Entradas:	1	6	3	4	6	1	 	 Saída	esperada:	3	ou	4	
	
A	 resposta	 desta	 questão	 deve	 conter	 (i)	 a	 definição	 da	 estrutura	 de	 dados;	 (ii)	 o	
protótipo	da	função;	e	(iii)	a	implementação	em	C	da	função.