Atividade Estruturada - Estrutura de Dados

Prévia do material em texto

ESTRUTURA DE DADOS - CCT0021
Título
PRÁTICA CONTEXTUALIZADA ATRAVÉS DE EXERCÍCIOS
Objetivo
Pesquisar no material indicado e no conteúdo de aula e responder o questionário 
proposto.
Competências / Habilidades
1) Escrever funções com vetores; Definir, identificar aplicações e representar 
listas lineares sequenciais; Compreender e implementar as operações básicas com 
listas lineares sequenciais não ordenadas; Compreender e implementar o método 
de pesquisa ou busca sequencial
2) Conceituar a estrutura de dados pilha; Representar a estrutura de dados pilha 
por contiguidade; Compreender, implementar e desenvolver práticas com pilhas
3) Conceituar a estrutura de dados fila; Representar a estrutura de dados fila por 
contiguidade (fila simples); Compreender, implementar e desenvolver tarefas 
práticas com fila simples
4) Conceituar, representar e realizar aplicações com listas circulares simplesmente 
e duplamente encadeadas
Desenvolvimento
1) LISTAS LINEARES SEQUENCIAIS
1.1) Considere o programa abaixo e depois dê o que se pede:
#include <iostream>
#include <cstdlib>
using namespace std;
void Teste1(int );
void Teste2(int &);
int Teste3(int);
int x = 20;
int main()
{
 int numero = 10, outroNumero;
 Teste1(numero);
 cout << "Valor de numero (após Teste1) = " << numero << endl; 
 cout << "X = " << x << endl; 
 
 Teste2(numero);
 cout << "Valor de numero (após Teste2) = " << numero << endl; 
 cout << "X = " << x << endl; 
 outroNumero = Teste3(numero);
 cout << "Valor de outro numero (após Teste3) = " << outroNumero 
 << endl; 
 cout << "X = " << x << endl;
 
 system("pause");
 
}
void Teste1(int numero)
{
 numero = numero +x ;
 x++;
}
void Teste2(int &numero)
{
 int valor = 100;
 
 numero = numero + valor;
 x++;
}
int Teste3(int n)
{
 int valor = 200;
 n = n + valor;
 x--;
 return n;
} 
Pede-se:
a) Identifique as variáveis globais e locais. Quando identificar uma variável local, 
especifique o escopo da mesma.
b) Identifique, em cada função, o tipo de passagem de parâmetros.
c) Mostre, passo a passo, o valor de todas as variáveis, indicando o momento em que as 
variáveis não mais ocupam espaço na memória.
d) Diga o que é impresso na tela.
2) PILHA
2.1) Faça um programa em C++ para ler um número inteiro maior que zero, converter 
este número de decimal para binário, usando pilha e apresentar na tela, o resultado da 
conversão.
2.2) Construa um programa em C++, que use a estrutura pilha e verifique se o número de 
abre parênteses é igual ao número de fecha parênteses.
2.3) Uma palavra é um palíndromo se a sequência de letras que a forma é a mesma, quer 
seja lida da esquerda para a direita ou da direita para a esquerda (exemplo: raiar, ovo, 
ana, mussum).
2.4) Escreva um programa em C++ que reconheça se uma dada palavra é um palíndromo.
2.5) Escreva um programa em C++ que calcule o valor de uma expressão em notação 
polonesa reversa (notação pós-fixa). Considere as 4 operações e que se está trabalhando 
apenas com dígitos (valores de 0 a 9).
Obs.: Na notação polonesa reversa o operador é posto após os operandos. Assim sendo, 
não é mais necessária a utilização de parênteses, já que não há ambiguidade, como na 
notação infixa.
Ex: Notação infixa : (2 + 3)* 5 Notação Polonesa Reversa: 23+5*
Notação infixa : 2 + 3*5 Notação Polonesa Reversa: 235*+
3) FILAS SEQUENCIAIS SIMPLES E CIRCULAR
3.1) Faça um programa em C++ para apresentar um menu várias vezes, com as 
seguintes opções :
MENU
1- Enfileirar um número inteiro positivo.
2- Desenfileirar tudo e imprimir apenas os valores que são múltiplos de 5.
3- Terminar o programa
Implemente, adequadamente, cada opção fornecida.
3.2) Faça um programa em C++ para ler uma sequência de caracteres (vetor de char) 
e enfileirá-los. Em seguida, desenfileire todos os caracteres e empilhe-os em uma pilha 
P seguindo as orientações:
Converta as letras para maiúsculas antes de empilhá-las
Qualquer outro caracter, empilhe sem alteração.
Ao final, desempilhe tudo, exibindo o resultado na saída padrão.
3.3) Faça um programa em C++ para apresentar um menu várias vezes, com as 
seguintes opções :
MENU
1- Enfileirar um valor inteiro não nulo
2- Desenfileirar um valor, exibindo na tela o seu dobro
3- Desenfileirar tudo, exibindo os valores desenfileirados sem alterações
4- Terminar o programa
Implemente, adequadamente, cada opção fornecida usando funções para enfileirar e 
desenfileirar.
3.4) Faça um programa que leia um vetor de char e enfileire seus dados em duas filas : 
fila A
(fila simples ? de char ) e fila B (fila circular com contador ? de inteiros) da seguinte 
forma:
Se o caracter for dígito, converta-o para dígito e enfileire-o em B.
Se o caracter for letra, enfileire-o em A.
Qualquer outro caracter não deverá ser enfileirado.
Ao final, desenfileire as filas B e A, nesta ordem, exibindo os seus dados.
4) LISTAS CIRCULARES SIMPLESMENTE E DUPLAMENTE ENCADEADAS
4.1) Faça um programa (aplicação) em C++ para ler a quantidade n de nós de uma lista 
circular simplesmente encadeada de inteiros, sendo n = 0. A lista deverá ser construída 
com n nós, através de sucessivas inserções no final. Após sua criação, a lista deverá 
ser impressa, se possível. Emita mensagem de erro em caso de lista vazia.
Nesta questão, implemente 2 funções/operações :
a) no *insereFim(no *p, int valor);
p aponta para o primeiro nó da lista e valor é o elemento a ser inserido no final da lista.
b) void imprime(no *p);
4.2) Considerando o programa do item 2) acima, em que o ponteiro externo aponta para 
o primeiro nó da lista (nó mais à esquerda), implemente as seguintes operações 
(funções) com a lista criada :
a) Remova o primeiro nó da lista, imprimindo-a ao final.
b) Remova o último nó da lista, imprimindo-a ao final.
c) Conte o número de nós da lista
d) Procure na lista um valor passado, realizando uma busca ou pesquisa seqüencial. A
função deverá retornar NULL ou o endereço do nó com o valor encontrado.
4.3) Considere uma lista duplamente encadeada apontada por um ponteiro x e ainda, um 
nó fora da lista, apontado por um ponteiro p.
Sabendo que x aponta para qualquer nó da lista, faça o que se pede :
a) Diga o que faz a função Eureka
b) Dê um exemplo para cada caso, usando ilustrações gráficas.
// Seja o tipo
struct nodupla {
struct nodupla *elink;
int dado;
struct nodupla *dlink;
};
// Código da função
void Eureka(nodupla *p, nodupla *x)
{
if (x dlink != NULL)
x dlink elink = p;
p dlink = x dlink;
p elink = x;
x dlink;
}
4.4) 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) nodupla 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.
4.5) Considerando o programa do item 2) acima, em que o ponteiro externo aponta para 
o primeiro nó da lista, implemente as seguintes operações (funções) com a lista criada :
a) Remova o primeiro nó da lista, imprimindo-a ao final.
b) Remova o último nó da lista, imprimindo-a ao final.
c) Conte o número de nós da lista, considerando o protótipo :
int contaNos (nodupla *);
sendo que a função contaNos deverá receber o ponteiro para o início da lista (nó mais à
esquerda).
d) Substitua um valor passado como parâmetro,por um novo valor também passado 
como
parâmetro. Note que, esta operação só será possível se a lista não estiver vazia.