package pa.arvore.digital01;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author aluno
*/
public class NoArvoreDigital {
char caractere;
List<NoArvoreDigital> nos;
// construtor
public NoArvoreDigital(char a)
{
this.caractere = a;
nos = new ArrayList<NoArvoreDigital>();
}
// inserir palavra
public boolean inserirPalavra(String palavra)
{ // 1) obter a primeira letra
if (palavra.length() == 0)
return true;
char letra = palavra.charAt(0);
if (palavra.length() > 1)
palavra = palavra.substring(1);
else
palavra = "";
// 2) verificar se a letra existe na arvore
NoArvoreDigital no = obterNo(letra);
if (no != null){// 3) Se ela existir
// 3.1) obter o no correspondente
// 3.2) inserir o resto da palavra neste no
return no.inserirPalavra(palavra);
} else { // 4) Se ela nao existir
// 4.1) criar um novo nó com o caractere corrente
no = new NoArvoreDigital(letra);
nos.add(no); // 4.2) Adicionar o no na lista de nos
// 4.3) inserir o resto da palavra neste no
return no.inserirPalavra(palavra);
}
}
public NoArvoreDigital obterNo(char letra)
{
for (NoArvoreDigital no: nos)
{
if (no.caractere == letra)
return no;
}
return null;
}
@Override
public String toString() {
return "[" + caractere +"] -> " +
nos.toString();
}
// metodo que verifica se a palavra existe dentro da
// arvore digital
public boolean existe(String palavra)
{
// 1) obter o primeiro caractere
if (palavra.length() == 0)
return true;
char letra = palavra.charAt(0);
// 2) obter o restante da palavra
if (palavra.length() > 1)
palavra = palavra.substring(1);
else
palavra = "";
// 3) Se o caractere existir no nó
NoArvoreDigital no = obterNo(letra);
if (no != null){
// 3.1) buscar no nó que contem o caractere
return no.existe(palavra);
} else {// 4) Senao
// 4.1) informar que a palavra não existe
return false;
}
}
public void imprimir()
{
for (NoArvoreDigital no:nos)
{
System.out.print ("["+no.caractere+"] -> ");
no.imprimir();
System.out.println();
}
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package pa.arvore.digital01;
/**
*
* @author aluno
*/
public class PaArvoreDigital01 {
/**
* @param args the command line arguments
*/
public static void main(String [] args)
{
NoArvoreDigital no = new NoArvoreDigital('*');
no.inserirPalavra("texto");
no.inserirPalavra("teste");
no.inserirPalavra("casa");
no.inserirPalavra("tomate");
System.out.println(no);
no.imprimir();
String palavra = "teste";
System.out.println(palavra + "-> " + no.existe(palavra));
palavra = "cas";
System.out.println(palavra + "-> " + no.existe(palavra));
palavra = "teto";
System.out.println(palavra + "-> " + no.existe(palavra));
}
}
#include <cstdlib>
#include <iostream>
#include <time.h>
using namespace std;
void ordenarPorSelecao(unsigned short a[], int tam)
{
int i, j, menor, aux;
for (i = 0; i < tam; i++){
menor = i;
for (j = i + 1; j < tam; j++){
if (a[j] < a[menor])
menor = j;
}
if (menor != i){
aux = a[menor];
a[menor] = a[i];
a[i] = aux;
}
}
cout << "Depois de ordenado: " << endl;
for (int i = 0; i < tam; i++){
cout << a[i] << "\t";
}
}
// funcao que realiza a busca sequencial
// a[]: tabela de dados
// tam: tamanho da tabela de dados
// v : valor a ser buscado na tabela
// retorno int: posicao de v em a[] caso ele exista,
// -1 caso contrario
int buscaSequencial(unsigned short a[], int tam,
unsigned short v)
{
int pos = -1; // assumir que o elemento nao existe
for (int c = 0; c < tam; c++){
if (a[c] == v){
pos = c;
break;
}
}
return pos;
}
int main(int argc, char *argv[])
{
// Problema
// Entrada: Um numero digitado pelo usuário e um
// vetor/tabela com 1M de números aleatórios
// Saída: Informar se o número existe na tabela ou não
// Descrição textual
// 1) Ler do usuario um numero inteiro
int tam = 10;
unsigned short t[tam]; // tabela de dados
unsigned short n; // entrada do usuario
int c; // contador
cout << "Digite um numero inteiro: "<< endl;
cin >> n;
// 2) Gerar os numeros aleatorios e armazena-los
// no vetor
srand(time(NULL)); // inicializa o gerador
for (int i = 0; i < tam; i++){
t[i] = rand() % 65454;
}
// 3) Executar a busca sequencial sobre o vetor
int r = buscaSequencial(t, tam, n);
if (r == -1){
cout << "Resultado não encontrado." << endl;
} else {
cout << "Valor encontrado na posicao " << r << endl;
}
// 4) Exibir o vetor na tela
for (int i = 0; i < tam; i++){
cout << t[i] << "\t";
}
// 5) ordenar o vetor
ordenarPorSelecao(t, tam);
// 6) exibir o vetor ordenado
cout << "Depois de ordenado: " << endl;
for (int i = 0; i < tam; i++){
cout << t[i] << "\t";
}
system("PAUSE");
return EXIT_SUCCESS;
}
#include <iostream>
#include <cstring>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv) {
// problema
// entrada: uma palavra digitada pelo usuario
// saida: informar a palavra invertida
// descricao textual
// 1) ler uma palavra do usuario
// 2) Calcular o tamanho da palavra
// 3) Para cada letra na frase
// a partir do final ( passo -1)
// 3.1) Imprime a letra
// algoritmo estruturado
// Var
char n[50];// N: conjunto[1...20]: caractere
int c, t; // C, T: inteiro
// Inicio
cout << "Digite uma palavra: "<<endl;// Escrever "Digite uma palavra: "
cin.get(n, 51);// Ler N
t = strlen(n); // T <- Tamanho(N)
for (c = t-1; c >=0; c--){// Para C De T Até 1 Passo -1 Faça
cout << n[c];// Escrever N[C]
}// Fim Para
cout << endl;
// Fim
return 0;
}
#include <iostream>
// ProjetoTabelaDadosEx01
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv) {
// Problema
// Entrada: dez notas digitadas pelo usuario
// Saida: informar cada uma das notas digitadas
// e a media
// descricao textual
// 1) Ler as 10 notas
// 2) Para cada uma das notas digitadas
// 2.1) Acumular o valor na soma
// 3) Calcular a média
// 4) Exibir as notas informadas pelo usuario
// 5) Exibir a média
// Algoritmo estruturado
// Var
int n[10]; // N: conjunto [1...10]:inteiro
int c, s; // C, S: inteiro
float m; // M: real
// Inicio
s = 0; // S -> 0
for (c = 0; c<10; c++){ // Para C De 1 Até 10 Passo 1 Faça
cout << (c+1) << " ] - Digite uma nota: " << endl; // Escrever "Digite uma nota: "
cin >> n[c]; // Ler N[C]
s = s + n[c]; // S <- S + N[C]
} // Fim Para
m = s / 10.0; // M <- S / 10
cout << "=========================" << endl;
cout << "Exibindo as notas: " << endl;
for (c = 0; c<10; c++){ // Para C De 1 Até 10 Passo 1 Faça
cout << n[c] << endl; // Escrever N[C]
} // Fim Para
cout << "Media: " << m << endl; // Escrever "Media: " M
// Fim
return 0;
}
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <time.h>
using namespace std;
int main(int argc, char *argv[])
{
// problema
// entrada: um número inteiro digitado pelo usuário (N)
// saída: gerar N números aleatórios e escrever estes
// números em arquivo.
int n;
srand(time(NULL)); // inicializando o gerador de numeros aleatório
cout << "Digite um numero inteiro: " << endl;
// 1) Ler do usuario o numero inteiro (N)
cin >> n;
// abrir o arquivo para escrita
ofstream arquivo;
arquivo.open("dados.txt");
// testar se o arquivo foi aberto com sucesso ou nao
if (!arquivo.is_open()){
cout << "ERRO: nao foi possivel abrir o arquivo!" << endl;
return EXIT_FAILURE;
}
int numero = 0;
// 2) Para cada numero de 1 até N
for (int i = 0; i < n; i++){
// 2.1) gerar o numero aleatório
numero = rand() % 100;
// 2.2) escrever o número em arquivo
cout << i << " - Escrevendo o número " << numero << " no arquivo." << endl;
arquivo << numero << endl;
}
arquivo.close();
// parte 2: abrir o arquivo e calcular o seu tamanho em bytes e
// quantidade de números
ifstream arq;
arq.open("dados.txt");
arq.seekg(0, ifstream::end);
streampos tamanho = arq.tellg(); // obtendo o tamanho do arquivo
cout << "Arquivo gerado: " << tamanho << " Bytes." << endl;
arq.close();
system("PAUSE");
return EXIT_SUCCESS;
}
#include <stdio.h>
#include <stdlib.h>
#include "tad-lista.h"
int main(int argc, char *argv[])
{
TipoLista lista, pares, impares;
TipoItem item;
int i = 0;
int a[] = {2,5,6,7,8,9,11,12,15,16,17};
int tam = 11;
int capacidade = 10;
// 1) Criar a lista
CriarLista(&lista, capacidade);
CriarLista(&pares, capacidade);
CriarLista(&impares, capacidade);
// 2) Imprimir a lista
ImprimirLista(lista);
// 3) inserir os elementos
for (i = 0; i < tam; i++)
{ item.Chave = a[i];
InserirLista(&lista, item);
// 4) Imprimir a lista
ImprimirLista(lista);
}
// 5) Pesquisar a lista
item.Chave = 5;
i = PesquisarLista(lista, item);
printf("Resultado pesquisa %d: %d\n",
item.Chave, i);
item.Chave = 3;
i = PesquisarLista(lista, item);
printf("Resultado pesquisa %d: %d\n",
item.Chave, i);
// 6) Retirar alguns elementos da lista
for (i = 0; i < capacidade; i++)
{
RetirarLista(&lista, &item);
printf("Retirado da lista: %d\n",
item.Chave);
// 7) imprimir a lista
ImprimirLista(lista);
//8) testar se numero eh par ou impar
if (item.Chave % 2 == 0)
{ InserirLista(&pares, item);
} else {
InserirLista(&impares, item);
}
}
printf("Pares: \n");
ImprimirLista(pares);
printf("Impares: \n");
ImprimirLista(impares);
system("PAUSE");
return 0;
}
// TAD LISTA
// Tipos de dados
typedef int TipoChave;
struct T_Item{
TipoChave Chave;
};
typedef struct T_Item TipoItem;
typedef struct T_Celula * TipoApontador;
struct T_Celula{
TipoItem Item;
TipoApontador Prox;
};
typedef struct T_Celula TipoCelula;
struct T_Lista{
int Tamanho;
int Capacidade;
TipoApontador Primeiro, Ultimo;
};
typedef struct T_Lista TipoLista;
// Cabeçalho das operações
// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);
// Implementação das operações
void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
Lista->Primeiro = (TipoApontador) malloc(
sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
Lista->Tamanho = 0;
Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
Lista->Primeiro->Prox = NULL;
}
// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item)
{
//1 ) verificar se LISTA estah cheia
if (ListaCheia(*Lista) == 1){
printf("ERRO: lista cheia!\n");return;
}
//2 ) criar nova celula a partir da ultima celula
Lista->Ultimo->Prox = (TipoApontador)
malloc(sizeof(TipoCelula));
//3 ) inserir a chave na celula
Lista->Ultimo->Prox->Item = item;
//4 ) atualizar apontadores (prim e ult.)
Lista->Ultimo = Lista->Ultimo->Prox;
Lista->Ultimo->Prox = NULL;
//5 ) atualizar tamanho
Lista->Tamanho++;
}
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item)
{
TipoApontador aux, q;
//1) verificar se LISTA estah vazia
if(ListaVazia(*Lista) == 1){
printf("ERRO: lista vazia");return;
}
//2) guardar a celula anterior (aux)
aux = Lista->Primeiro;
//3) guardar a celula a ser removida (q)
q = aux->Prox;
//4) atualizar a celula anterior
aux->Prox = q->Prox;
//5) obter o item removido
*item = q->Item;
//6) liberar o espaco de memoria de q
free(q);
//7) decrementar tamanho
Lista->Tamanho--;
}
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
TipoApontador aux;
int i = 0;
//1) verificar se LISTA estah vazia
if (ListaVazia(Lista) == 1){
printf("ERRO: lista vazia!\n");return;
}
//2) inicializar o apontador aux
aux = Lista.Primeiro;
//3) enquanto houver celula apos aux
while (aux->Prox != NULL &&
aux->Prox->Item.Chave != item.Chave){
//3.1) se a chave que estiver na celula apos aux
// for igual a chave procurada
//3.2) atualizar aux
aux = aux->Prox;
i++;
}
if (aux->Prox !=NULL){
// achei
printf("Elemento encontrado!\n");
} else {
// nao achei
printf("Elemento NAO encontrado!\n");
i = -1;
}
return i;
}
// verificar se estah cheia
int ListaCheia(TipoLista Lista){
if (Lista.Tamanho == Lista.Capacidade)
{ return 1; // lista cheia
} else {
return 0; //lista nao cheia
}
}
// verificar se estah vazia
int ListaVazia(TipoLista Lista)
{
if (Lista.Primeiro == Lista.Ultimo)
{ return 1; // lista vazia
} else {
return 0; // lista nao vazia
}
}
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista){
return Lista.Tamanho;
}
// imprimir a lista
void ImprimirLista(TipoLista Lista)
{
TipoApontador aux;
printf("TAD Lista [%d/%d]\n",
Lista.Tamanho, Lista.Capacidade);
//1) verificar se LISTA estah vazia
if (ListaVazia(Lista) == 1){
printf("ERRO: lista vazia!\n");return;
}
//2) inicializar o apontador aux
aux = Lista.Primeiro;
printf(" [/]-> ");
//3) enquanto houver celula apos aux
while (aux->Prox != NULL){
//3.2) atualizar aux
printf("[%d]-> ", aux->Prox->Item.Chave);
aux = aux->Prox;
}
printf("NULL\n\n");
}
#include <stdio.h>
#include <stdlib.h>
#include "tad-lista.h"
int main(int argc, char *argv[])
{
TipoLista lista;
TipoItem item;
int i = 0;
int a[] = {2, 5, 6, 7, 8, 9, 11};
int tam = 7;
int capacidade = 10;
// 1) Criar a lista
CriarLista(&lista, capacidade);
// 2) Imprimir a lista
ImprimirLista(lista);
// 3) inserir os elementos
for (i = 0; i < tam; i++)
{ item.Chave = a[i];
InserirLista(&lista, item);
// 4) Imprimir a lista
ImprimirLista(lista);
}
// 5) Pesquisar a lista
item.Chave = 5;
i = PesquisarLista(lista, item);
printf("Resultado pesquisa %d: %d\n",
item.Chave, i);
item.Chave = 3;
i = PesquisarLista(lista, item);
printf("Resultado pesquisa %d: %d\n",
item.Chave, i);
// 6) Retirar alguns elementos da lista
for (i = 0; i < tam; i++)
{
RetirarLista(&lista, &item);
printf("Retirado da lista: %d\n",
item.Chave);
// 7) imprimir a lista
ImprimirLista(lista);
}
system("PAUSE");
return 0;
}
