GABARITO_Lista9 ESTRUTURA DE DADOS

Prévia do material em texto

Lista 9 – Listas Duplamente Encadeadas 
 
 
 Para os exercícios a seguir, considere : 
 
 struct nodupla { 
 int dado; 
 struct nodupla *dlink; // link p/ o nó à direita 
 struct nodupla *elink; // link p/ o nó à esquerda 
 }; 
 
 
 
1) Faça um programa (aplicação) em C++ para ler a quantidade n de nós de uma lista 
duplamente encadeada de reais, sendo n ≥ 0. A lista deverá ser construída com n 
nós, através de sucessivas inserções no início. Após sua criação, a lista deverá 
ser impressa, se possível. Emita mensagem de erro em caso de lista vazia. 
 Defina o tipo nodupla para reais. 
 
Nesta questão, implemente 2 funções (operações) : 
 
a) nodupla *insereFrente(nodupla *p, int valor); 
 
p aponta para o primeiro nó da lista e valor é o elemento a ser 
inserido no início da lista. 
 
b) void imprime(nodupla *p); 
 
 onde p aponta para o 1º. nó da lista (i.e., nó mais à esquerda na lista). 
 
A lista deverá ser impressa da esquerda para a direita. 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
struct nodupla { 
 float dado; 
 struct nodupla *dlink; // link p/ o nó à direita 
 struct nodupla *elink; // link p/ o nó à esquerda 
 }; 
 
 
 
//Protótipos 
nodupla *insereFrente(nodupla *, float ); 
void imprime(nodupla *); 
 
 
int main() 
{ 
 nodupla *primeiro = NULL; //inicializa a lista duplamente encadeada 
 
 int n; 
 float valor; 
 
 do { 
 
 cout << "Digite a quantidade de nos (n >= 0) : "; 
 cin >> n; 
 if (n < 0) 
 cout << "ERRO: quantidade invalida." << endl; 
 } while (n < 0); 
 
 cout << "Construindo uma lista duplamente encadeada com " 
 << n << " nos... " << endl; 
 for (int conta = 1; conta <= n; conta++) 
 { 
 cout << "Digite um valor p/inserir na frente da lista: "; 
 cin >> valor; 
 primeiro = insereFrente(primeiro,valor); 
 } 
 
 if (primeiro != NULL) 
 { 
 cout << "Lista resultante : " << endl; 
 imprime(primeiro); 
 } 
 else 
 cout << "Lista vazia. " << endl; 
 
 cout << endl; 
 system("pause"); 
 
 
} 
 
 
//Definições das funções 
 
nodupla *insereFrente(nodupla *p, float valor) 
{ 
 
 nodupla *novo; 
 
 novo = new nodupla; 
 novo->dado = valor; 
 novo->dlink = p; 
 novo->elink = NULL; 
 if (p != NULL) 
 p->elink = novo; 
 p = novo; 
 
 return p; 
} 
 
void imprime(nodupla *p) 
{ 
 while (p != NULL) 
 { 
 cout << " " << p->dado; 
 p = p->dlink; 
 } 
} 
 
 
 
 
 
2) Faça um programa (aplicação) em C++ para construir uma lista duplamente 
encadeada (não circular) de inteiros positivos, através de sucessivas inserções no 
fim da lista. Após sua criação, a lista deverá ser impressa e ter sua quantidade de 
nós também impressa. Emita mensagem de erro em caso de lista vazia. 
Nesta questão, implemente 3 funções (operações) : 
 
a) nodupla *insereFim(nodupla *p, int valor); 
 
p aponta para o primeiro nó da lista e valor é o elemento a ser 
inserido no início da lista. 
 
b) void imprime(nodupla *p); 
c) int contaNos(nodupla *p); 
 
 
Solução : 
 
 
#include <iostream> 
 
using namespace std; 
 
struct nodupla { 
 int dado; 
 struct nodupla *dlink; // link p/ o nó à direita 
 struct nodupla *elink; // link p/ o nó à esquerda 
 }; 
 
//Protótipos 
nodupla *insereFim(nodupla *, int ); 
void imprime(nodupla *); 
int contaNos(nodupla *); 
 
//Programa principal 
int main() 
{ 
 //inicializa a lista duplamente encadeada 
 nodupla *primeiro = NULL; 
 int valor; 
 
 for ( ; ; ) 
 { 
 cout << "Digite um valor positivo p/inserir : "; 
 cin >> valor; 
 if (valor <= 0) 
 break; 
 primeiro = insereFim(primeiro,valor); 
 } 
 
 
 
 
 if (primeiro != NULL) 
 { 
 cout << "Lista resultante : " << endl; 
 imprime(primeiro); 
 } 
 else 
 cout << "Lista vazia. " << endl; 
 
 cout << "Quantidade de nos : " << contaNos(primeiro) 
 << endl; 
 
 cout << endl; 
 
 system("pause"); 
 
} 
 
 
//Definições das funções 
 
nodupla *insereFim(nodupla *p, int valor) 
{ 
 
 nodupla *novo, *aux; 
 
 novo = new nodupla; 
 novo->dado = valor; 
 novo->dlink = NULL; 
 
 if (p == NULL) 
 { 
 novo->elink = p; 
 p = novo; 
 } 
 else 
 { 
 aux = p; 
 while (aux->dlink != NULL) 
 aux = aux->dlink; 
 aux->dlink = novo; 
 novo->elink = aux; 
 } 
 return p; 
} 
 
 
 
 
 
 
 
 
 
void imprime(nodupla *p) 
{ 
 while (p != NULL) 
 { 
 cout << " " << p->dado; 
 p = p->dlink; 
 } 
} 
 
 
int contaNos(nodupla *p) 
{ 
 int contador = 0; 
 while (p != NULL) 
 { 
 contador++; 
 p = p->dlink; //aponta para o nó à direita 
 } 
 return contador; 
}