Atividade Estruturada

Prévia do material em texto

TÍTULO DA ATIVIDADE ESTRUTURADA
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
Disciplina: CCT0021 - ESTRUTURA DE DADOS
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 ;
Relatório - Atividade Estruturada
 
05/09/2014 13:47
Página: 1/4
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
Relatório - Atividade Estruturada
 
05/09/2014 13:47
Página: 2/4
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 :
Relatório - Atividade Estruturada
 
05/09/2014 13:47
Página: 3/4
int contaNos (nodupla *);
sendo que a função contaNos deverá receber o ponteiro para oiní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.
Relatório - Atividade Estruturada
 
05/09/2014 13:47
Página: 4/4