Atividade estruturada - Estrutura de Dados

Prévia do material em texto

Questão 1.0
A )
Variável global : x 
Variáveis locais : 
1) numero e outroNumero – escopo : main. 
Veja o trecho : 
int main() 
{ 
int numero = 10, outroNumero; 
//continua 
2) numero - escopo : Teste1 
3) numero e valor – escopo : Teste2 
4) n e valor - escopo : Teste3 
B )
Função main : Não há passagem de parâmetros 
Função Teste 1 : Passagem de parâmetro por valor 
Função Teste 2: Passagem de parâmetro por referência 
FunçãoTeste 3: Passagem de parâmetro por valor
C )
Passos : 
1) Variável global x recebe 20. Ela será visível na main e nas outras funções. 
2) Na main, a variável local numero recebe 10 na declaração. 
3) Chamada para a função Teste1, passando o valor de numero, ou seja, 10. 
4) Na função Teste1 : Há uma variável local numero (cópia da variável numero da main) que recebeu o valor passado 10. A variável numero local à função Teste1 recebe 10+20, ou seja, numero (local à Teste1) recebe 30. Depois, a variável global x é incrementada para 21. Terminada a função Teste1, a variável local numero deixa de ocupar espaço na memória. Assim, terminada a execução de Teste1, a variável x está visível, com a alteração sofrida, mas a variável numero (local a Teste1) já não mais existe na memória. 
5) Volta-se para main, para a 1ª. linha de cout. Neste momento, tem-se que numero (local à main) permanece com o valor 10 e a variável global x vale 21. 
6) Chamada para a função Teste2. Neste caso, há uma passagem de parâmetro por referência usando & (ver definição e protótipo da função). 
7) Começando a execução de Teste2, vemos o parâmetro numero, a variável local valor e x (variável global). A variável local valor recebe 100 na declaração. O argumento numero (vide chamada da função Teste2) recebe 10 + 100, ou seja, 110 e depois, x é incrementado para 22. Ao terminar a execução de Teste2, tem-se que valor não mais ocupa espaço na memória, x foi de fato modificada e numero (variável local à main) sofreu a alteração realizada em Teste2, passando a valer 110. 
8) Na linha outroNumero = Teste3(numero); temos que a variável outroNumero, que é local à main, receberá o retorno da função Teste3. O argumento de Teste3 é numero, que neste momento vale 110. Assim comoTeste1, a função Teste3 trabalha com passagem de parâmetro por referência. 
9) Começando a executar Teste3 temos o parâmetro n, que é uma variável local à função Teste3. O parâmetro n armazena o valor do argumento numero, usado na chamada da função. Como numero (local à main) vale 110, o parâmetro n vale também 110. Dentro de Teste3 há uma variável local valor que recebe 200 na declaração. Em seguida, a variável local n (local à função Teste3) recebe 310 (n recebe 200 + 110). Em seguida, x (variável global) é decrementada para 21. O valor da variável local n é retornado para o ponto de chamada na função main. Ao término da execução de Teste3, tanto a variável n, quanto a variável valor, não mais ocupam espaço em memória. 
10)O valor retornado pela função Teste3 é atribuído à variável outroNumero, que recebe 310. A variável global x vale 21. 
11)Somente ao término da execução da função main, as variáveis x, numero e outronumero são liberadas da memória. 
D) 
Questão 2 : Pilha 
2.1 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
 
typedef struct queue
{
 int value;
 struct queue *prev,*next;
}q;
 
q *topo = NULL,*base = NULL; 
 
void push(int value)
{
 q *aux;
 if(topo == NULL)
 {
 base = (q *) malloc(sizeof(q));
 base->value = value;
 base->next = NULL;
 base->prev = NULL;
 topo = base;
 }
 else
 {
 aux = (q *) malloc(sizeof(q));
 aux->value = value;
 aux->prev = topo;
 aux->next = NULL;
 topo->next = aux;
 topo = aux;
 }
}
 
int pop()
{
int value;
 if(topo == NULL)
 return -1;
 else
 {
 value= topo->value;
 topo = topo->prev;
 }
 return value;
}
 
void convertDecBin(int dec)
{
 int r;
 while(dec != 0)
 {
 r = dec%2;
 push(r);
 dec = dec/2;
 
 }
}
 
void show()
{
 int flag = 0,b;
 printf("\n O numero binario e : ");
 while(flag != 1)
 {
 
 b = pop();
 if(b == -1)
 flag = 1;
 else
 printf("%d",b);
 }
}
 
main()
{
 int dec;
 int ch;
 do
 {
 
 printf("Informe o numero DECIMAL para ser convertido \n");
 scanf("%d",&dec);
 convertDecBin(dec);
 show();
 
 puts("\n-1 for finish");
 scanf("%d",&ch);
 }while(ch != -1);
}
2.2
#include <iostream> 
#include <stack> 
using namespace std; 
int main () { 
 
stack<char> pilha; 
int cont=0; 
char car=' '; 
cout << "Informe os caracteres da pilha [# indica o final]" << endl; 
while (car != '#') { 
cin >> car; 
pilha.push(car); 
} 
cout << "Exibindo a pilha"; 
while (!pilha.empty()) { 
cout << " " << pilha.top(); 
if (pilha.top() == '(') 
cont++; 
else 
if (pilha.top() == ')') 
cont--; 
pilha.pop(); 
} 
cout << endl; 
if (cont == 0) 
cout << "Parênteses balanceados" << endl; 
else 
cout << "Parênteses desbalanceados" << endl; 
return 0; 
}
2.3
#include<stdio.h>
#include<stdlib.h>
 
main(){
 
 char original [256];
 char invertida [256];
 int tamanho, palindromo=1, i, j;
 
 puts ("Digite uma palavra : ");
 
 gets(original);
 
 for (tamanho=0; original[tamanho] != '\0'; tamanho++);{
 
 } 
 for (i=0, j=tamanho-1; j>0; i++, j--){
 invertida[ i ] = original[ j ];
 
 
 if (invertida[ i ] != original[ i ]) // AQUI ELE COMPARA SE O INVERSO DA PALAVRA É 
 palindromo=0; // IGUAL A PALAVRA ORIGINAL
 break;
 
 }
 
 
 if (palindromo)
 puts("a palavra e um palindromo");
 
 else
 puts("a palavra nao e um palindromo");
 
 system("pause>nul");
}
2.4
#include<stdio.h>
#include<stdlib.h>
 
main(){
 
 char original [256];
 char invertida [256];
 int tamanho, palindromo=1, i, j;
 
 gets(original);
 
 for (tamanho=0; original[tamanho] != '\0'; tamanho++);{
 
 } 
 for (i=0, j=tamanho-1; j>0; i++, j--){
 invertida[ i ] = original[ j ];
 
 if (invertida[ i ] != original[ i ]) // AQUI ELE COMPARA SE O INVERSO DA PALAVRA É 
 palindromo=0; // IGUAL A PALAVRA ORIGINAL
 break;
 }
 
 if (palindromo)
 puts("a string eh um palindromo");
 
 else
 puts("a string NAO eh um palindromo");
 
 system("pause>nul");
}
2.5
#include <iostream> // cout, cin
#include <string> // string
#include <stack> // stack
#include <vector> // vector
#include <string.h> // strtok
#include <cstdlib> // atoi (string to int)
 
#include <sstream>
// int to string
#define SSTR( x ) dynamic_cast< std::ostringstream & >( \
 ( std::ostringstream() << std::dec << x ) ).str()
 
using namespace std;
 
// check if string is a number
bool is_operand(string& str)
{
	int size_str = str.size();
 
	for(int i = 0; i < size_str; i++)
	{
		if (str[i] < '0' || str[i] > '9')
			return false;
	}
	return true;
}
 
int main(int argc, char *argv[])
{
	string expr;
	stack<string> my_stack;
	vector<string> my_tokens;
 
	cout << "Expression in polish notation (example: 5 1 3 * +): ";
	getline(cin, expr);
 
	// split expr into tokens, delimiters: one blank space
	char * pch = strtok((char*)expr.c_str(), " ");
	while (pch != NULL)
	{
		my_tokens.push_back(pch);
		pch =strtok(NULL, " ");
	}
 
	int size_vec = (int)my_tokens.size();
 
	// expression evaluated from left to right
	for(int i = 0; i < size_vec; i++)
	{
		// check if is a operand
		if (is_operand(my_tokens[i]))
		{
			// push on stack
			my_stack.push(my_tokens[i]);
		}
		else
		{
			// is operator (+ - * or /)
 
			string my_operator = my_tokens[i];
 
			// pop operands
			// atoi: string to int
			int op1 = atoi(my_stack.top().c_str());;
			my_stack.pop();
			int op2 = atoi(my_stack.top().c_str());;
			my_stack.pop();
 
			// define SSTR: int to string
			if(my_operator == "+")
				my_stack.push(SSTR(op2 + op1));
			else if(my_operator == "-")
				my_stack.push(SSTR(op2 - op1));
			else if(my_operator == "*")
				my_stack.push(SSTR(op2 * op1));
			else
				my_stack.push(SSTR(op2 / op1));
		}
	}
 
	cout << "Result: " << my_stack.top() << endl;
	return 0;
}
Questão 3 : Filas Sequenciais Simples e Circular
3.1
#include <stdio.h> 
 
 #include <stdlib.h> 
 
 #define LIM 7 
 
 #define FALSE 0 
 
 
 
 #define TRUE 1 
 
 
 
 #define UM 1 
 
 #define DOIS 2 
 
 #define TRES 3 
 
 
 
 
 
 
 
 int obterOpcao(void) 
 
 { 
 
 int opcao; 
 
 printf("MENU\n"); 
 
 printf("%2d - Enfileirar um numero inteiro positivo\n", UM); 
 
 printf("%2d - Desenfileirar tudo e imprimir apenas os valores que sao multiplos de 5 \n", DOIS); 
 
 printf("%2d - Terminar o programa\n", TRES); 
 
 printf("Opcao: "); 
 
 scanf("%d", &opcao); 
 
 return opcao; 
 
 } 
 
 
 
 int main(void) 
 
 { 
 
 int x,inicio, fim, fila[LIM], opcao, valor; 
 
 inicio = 0; // fila vazia 
 
 fim = 0; 
 
 
 
 while ((opcao = obterOpcao()) != TRES) 
 
 { 
 
 switch (opcao) 
 
 { 
 
 case UM: 
 
 printf("Valor a ser inserido na fila: "); 
 
 scanf("%d", &valor); 
 
 if (fim - inicio == LIM) { 
 
 printf("Operacao frustrada - fila esgotada...\n"); 
 
 } 
 
 else{ 
 
 if(inicio == fim){ 
 
 fila[inicio] = valor; 
 
 fim = fim + 1; 
 
 } 
 
 else{ 
 
 fim = fim + 1; 
 
 for(x = fim;x<=inicio;x--){ 
 
 fila[x+1] = fila[x]; 
 
 } 
 
 fila[inicio] = valor; 
 
 } 
 
 
 
 } 
 
 break; 
 
 case DOIS: 
 
 
 
 if (fim == LIM){ 
 
 printf("Operacao frustrada - fila vazia...\n"); 
 
 } 
 
 else{ 
 
 printf("Retirado \n%d\n", fim %5); 
 
 fim = fim -1; 
 
 printf("Operacao concluida com sucesso\n"); 
 
 } 
 
 break; 
 
 } 
 
 putchar('\n'); 
 
 } 
 
 return 0; 
 
 } 
 
3.2
#include <stdio.h> 
 
 #include <stdlib.h> 
 
 #include <string.h> 
 
 #include <ctype.h> 
 
 
 
 int main(void) 
 
 { 
 
 int x,y; 
 
 char fila[10],pilha[10], temp[1]; 
printf("Entre com o nome:"); 
 
 scanf("%s", fila); 
 
 y = 0; 
 
 for(x=0;x<=9;x++){ 
 
 if (isalpha(fila[x])){ 
 
 pilha[y] = toupper(fila[x]); 
 
 } 
 
 else{ 
 
 pilha[y] = fila[x]; 
 
 } 
 
 y = y + 1; 
 
 } 
for(x=0;x<=9;x++){ 
 
 printf("%c", pilha[x]); 
 
 } 
 printf("\n"); 
 
 system("pause"); 
 
 return 0; 
 
 }
3.3
#include <stdio.h> 
 
 #include <stdlib.h> 
 
 #define LIM 7 
 
 #define FALSE 0 
 
 #define TRUE 1 
#define UM 1 
 
 #define DOIS 2 
 
 #define TRES 3 
 
 #define QUATRO 4 
 
int obterOpcao(void) 
 
 { 
 
 int opcao; 
 
 printf("MENU\n"); 
 
 printf("%2d - Enfileirar um numero inteiro positivo\n", UM); 
 
 printf("%2d - Desenfileirar um valor, exibindo na tela o seu dobro\n", DOIS); 
 
 printf("%2d - Desenfileirar tudo, exibindo os valores desenfileirados sem alteracoes\n", TRES); 
 
 printf("%2d - Terminar o programa\n", QUATRO); 
 
 printf("Opcao: "); 
 
 scanf("%d", &opcao); 
 
 return opcao; 
 
 } 
 
 
 
 int main(void) 
 
 
 
 { 
 
 int x,inicio, fim, fila[LIM], opcao, valor; 
 
 inicio = 0; // fila vazia 
 
 fim = 0; 
 
 while ((opcao = obterOpcao()) != QUATRO) 
 
 { 
 
 switch (opcao) 
 
 { 
 
 case UM: 
 
 printf("Valor a ser inserido na fila: "); 
 
 scanf("%d", &valor); 
 
 if (fim - inicio == LIM) { 
 
 printf("Operacao frustrada - fila esgotada...\n"); 
 
 } 
 
 else{ 
 
 if(inicio == fim){ 
 
 fila[inicio] = valor; 
 
 fim = fim + 1; 
 
 } 
 
 else{ 
 
 fim = fim + 1; 
 
 for(x = fim;x<=inicio;x--){ 
 
 fila[x+1] = fila[x]; 
 
 } 
 
 fila[inicio] = valor; 
 
 } 
} 
 
 break; 
 
 case DOIS: 
 
 if (fim == 0){ 
 
 printf("Operacao frustrada - fila vazia...\n"); 
 
 } 
 
 else{ 
 
 printf("Retirado \n%d", fim * 2); 
 
 fim = fim -1; 
 
 printf("Operacao concluida com sucesso\n"); 
 
 } 
 
 break; 
 
 case TRES: 
 
 if (fim == 0){ 
 
 printf("Operacao frustrada - fila vazia...\n"); 
 
 } 
 
 else{ 
 
 printf("Retirado \n%d", fim); 
 
 fim = fim -1; 
 
 printf("Operacao concluida com sucesso\n"); 
 
 } 
 
 break; 
 
 } 
 
 putchar('\n'); 
 
 } 
 
 
 
 return 0; 
 
 }
3.4
 #include <stdio.h> 
 
 #include <stdlib.h> 
 
 #include <string.h> 
 
 #include <ctype.h> 
 
 int main(void) 
 
 { 
 
 char fila[10], filaA[10]; 
 
 int filaB[10]; 
 
 int i, x; 
 
 int indexA = 0, indexB = 0; 
 
 printf("Entre com o nome:");
 scanf("%s", fila); 
 
 for(i=0 ; fila[i]!='\0'; i++){ 
 
 if (isalpha(fila[i])){ 
 
 filaA[indexA++] = fila[i]; 
 
 }else if (isalnum(fila[i])){ 
 
 x = fila[i] - '0'; 
 
 filaB[indexB++] = x; 
 
 } 
 
 } 
 
 printf("Fila B\n"); 
 
 for(i=0 ; i<indexB ; i++){ 
 
 printf("%d ", filaB[i]); 
 
 } 
printf("\nFila A\n"); 
 
 for(i=0 ; i<indexA ; i++){ 
 
 printf("%c ", filaA[i]); 
 
 } 
 
 system("pause"); 
 
 return 0; 
 
 } 
Questão 4