Akinase

Maio 15, 2018

Tenho um trabalho do qual esta me dando trabalho, ashuahsha

a descrição é a seguinte:
Este trabalho consiste em implementar um protótipo de rede social utilizando a estrutura de dados árvore binária de busca. O sistema permitirá o cadastramento de pessoas e suas amizades. Cada pessoa possuirá um nome, um id e um conjunto de amizades. O id é um identificador inteiro único. O nome é o nome da pessoa. O conjunto de amizades é constituído dos ids das pessoas com as quais a pessoa possui algum tipo de relação de amizade. Pessoas serão armazenadas em uma árvore binária de busca em que a chave de cada nó será o id da pessoa correspondente. O conjunto de amizades de uma pessoa será representado por uma outra árvore binária de busca. Os nós desta árvore armazenam apenas o id de cada amigo, que também é usado como chave para a organização da árvore. Em resumo, o sistema armazenará uma árvore binária de busca de pessoas. Cada pessoa possuirá uma árvore binária de busca com suas amizades. O sistema deverá suportar as seguintes operações:

1. Inserção. Permite cadastrar uma nova pessoa no sistema.

2. Remoção. Permite remover uma pessoa do sistema, dado seu id.

3. Busca. Recebe o id de uma pessoa e caso a pessoa esteja no sistema, exibe suas informações e também suas amizades.

4. Cadastrar amizade. Recebe o id de duas pessoas e, caso ambas estejam cadastradadas no sistema e já não sejam amigas, cadastra uma nova amizade entre estas pessoas.

5. Remover amizade. Recebe o id de duas pessoas e, caso ambas estejam cadastradas no sistema e sejam amigas, desfaz a amizade entre as duas pessoas.

6. Consultar amizade. Recebe o id de duas pessoas e diz se existe amizade entre as duas.

7. Caminho de amizade (Bônus). Recebe o id de duas pessoas, P e Q, e, caso as duas estejam no sistema, mostra um possível caminho de amizade entre as duas. Isto é, mostra uma sequência de pessoas p1, p2, …, pn, em que p1 = P e pn = Q e existe uma relação de amizade entre pi e pi-1, para 2 <= i <= n.

segue o que eu já fiz:

#include <iostream>
#include <string>
//#include "Dicionario.h"
#include "ABB.h"
using namespace std;

class Pessoa
{
public:
   string nome;
   int idade;
   Pessoa();
   Pessoa(string n, int i);
   void Imprime();

};

Pessoa::Pessoa()
{
nome = "vazio";
idade = 0;
}

Pessoa::Pessoa(string n, int i)
{
nome = n;
idade = i;
}

void Pessoa::Imprime()
{
cout << nome << "-" << idade << "-" << endl;
}

class Amigos
{
public:
   string nome;
   int idade;
   Amigos();
   Amigos(string n, int i);
   void Imprime();
};

Amigos::Amigos()
{
nome = "vazio";
idade = 0;
}

Amigos::Amigos(string n, int i)
{
   nome = n;
   idade = i;
}
int main()
{
   string opcao;
   cin >> opcao;

Dicionario<int, Pessoa> D;

   while(opcao != "SAIR")
   {
       if(opcao == "INSERIR")
       {
           string nome, lixo;
           int chave;
           int idade;
           cin >> chave;
           getline(cin, lixo);
           getline(cin, nome);
           cin >> idade;


           Pessoa p(nome, idade);

           D.Inserir(chave, p);
       }
else if(opcao == "INSERIRAMIGO")
       {
string nome, lixo;
int chave;
cout << "DIGITE O ID do amigo RAIZ";
cin >> chave;
           int chavemigs;
           cout << "DIGITE O ID DO AMIGO A SER INSERIDO";
           cin >> chavemigs;

       }
       else if(opcao == "BUSCAR")
       {
           int chave;
           cin >> chave;
           Pessoa p = D.Buscar(chave);
           p.Imprime();
       }
       else if(opcao == "REMOVER")
       {
           int chave;
           cin >> chave;
           Pessoa p = D.Remover(chave);
       }
       else if(opcao == "IMPRIMIR")
       {
           D.Imprime();
       }

       cin >> opcao;
   }
}

#include <iostream>

using namespace std;

template <class T, class U>
class Dicionario;

template <class T, class U>
class No
{
public:
   No(T ch, U co);
   T chave;
   U conteudo;
   No * esquerda, * direita;
//Dicionario apontando para Amigos();
};

template <class T, class U>
No<T, U>::No(T ch, U co)
{
chave = ch;
   conteudo = co;
   esquerda = NULL;
   direita = NULL;
//Criar novo noh migs
}

template <class T, class U>
class Nomigs
{
public:
   Nomigs(T ch, U co);
   T chave;
   U conteudo;
   Nomigs * esquerda, * direita;
};

template <class T, class U>
Nomigs<T, U>::Nomigs(T ch, U co)
{
chave = ch;
   conteudo = co;
   esquerda = NULL;
   direita = NULL;
}

template <class T, class U>
class Dicionario
{
public:
   No<T, U> * raiz;

   Dicionario();
   void Inserir(T chave, U conteudo);
   void InserirRecursivo(No<T, U> * & anda, T chave, U conteudo);
void InserirAmigo(T chave, U conteudo);
   void InserirAmizade(Nomigs<T, U> * & anda, T chave, U conteudo);

   U Remover(T chave);
   U RemoverRecursivo(No<T, U> * & anda, T chave);
   U Buscar(T chave);
   U BuscarRecursivo(No<T, U> * anda, T chave);

   int NumNos(No<T, U> * x);
   int NumFolhas(No<T, U> * x);
   int NosCaminho(No<T, U> * anda, T chave);
   int NumNiveis(No<T, U> * x);

void Imprime();
void ImprimeRec(No<T, U> * x);
};

template <class T, class U>
void Dicionario<T, U>::InserirAmigo(T chave, U conteudo)
{
InserirAmizade(raiz, chave, conteudo);
}

/*template <class T, class U>
void Dicionario<T, U>::InserirAmizade(NoMigs<T, U> * & anda, T chave, U conteudo)
*
* NO1 = Arvore->Buscar(chave1)
No2 = Arvore->Buscar(chave2)
No1->Arvore->Inserir(chave2)
NO2->Arvore->Inseir(chave1)
*/

template <class T, class U>
Dicionario<T, U>::Dicionario()
{
raiz = NULL;
}

template <class T, class U>
void Dicionario<T, U>::Inserir(T chave, U conteudo)
{
InserirRecursivo(raiz, chave, conteudo);
}

template <class T, class U>
void Dicionario<T, U>::InserirRecursivo(No<T, U> * & anda, T chave, U conteudo)
{
   if(anda == NULL)
   {
       No<T, U> * novo = new No<T, U>(chave, conteudo);

anda = novo;
}

if(chave == anda->chave)
return;

if(chave < anda->chave)
InserirRecursivo(anda->esquerda, chave, conteudo);

if(chave > anda->chave)
InserirRecursivo(anda->direita, chave, conteudo);
}

template <class T, class U>
U Dicionario<T, U>::Buscar(T chave)
{
return BuscarRecursivo(raiz, chave);
}

template <class T, class U>
U Dicionario<T, U>::BuscarRecursivo(No<T, U> * anda, T chave)
{
if(anda == NULL)
return U();

if(chave == anda->chave)
return anda->conteudo;

if(chave < anda->chave)
return BuscarRecursivo(anda->esquerda, chave);

if(chave > anda->chave)
return BuscarRecursivo(anda->direita, chave);
}

template <class T, class U>
U Dicionario<T, U>::Remover(T chave)
{
return RemoverRecursivo(raiz, chave);
}

template <class T, class U>
U Dicionario<T, U>::RemoverRecursivo(No<T, U> * & anda, T chave)
{
if(anda == NULL)
return U();

   if(chave == anda->chave)
   {
       U conteudo = anda->conteudo;
       //Caso 3: 2 Filhos
       if(anda->esquerda != NULL && anda->direita != NULL)
       {
           //Encontrar maior da esquerda de anda
           No<T, U> * ME = anda->esquerda;
           while(ME->direita != NULL)
               ME = ME->direita;

           T chaveME = ME->chave;
           anda->conteudo = RemoverRecursivo(anda->esquerda, ME->chave);
           anda->chave = chaveME;
       }
       else
       {
           No<T, U> * novoanda;
           //Caso 1: NÃ³ Folha
           if(anda->esquerda == NULL && anda->direita == NULL)
           {
               novoanda = NULL;
           }
           //Caso 2: 1 Filho (direita)
           else if(anda->esquerda == NULL && anda->direita != NULL)
           {
               cout << "achou caso" << endl;
               novoanda = anda->direita;
           }
           //Caso 2: 1 Filho (esquerda)
           else if(anda->direita == NULL && anda->esquerda != NULL)
           {
               novoanda = anda->esquerda;
           }

           delete anda;
           anda = novoanda;
       }

       return conteudo;
   }
   if(chave < anda->chave)
       return RemoverRecursivo(anda->esquerda, chave);
   else if(chave > anda->chave)
       return RemoverRecursivo(anda->direita, chave);
}

template <class T, class U>
void Dicionario<T, U>::Imprime()
{
   ImprimeRec(raiz);
   cout << "Numero de noh: " << NumNos(raiz) << endl;
   cout << "Numero de niveis: " << NumNiveis(raiz) << endl;
   cout << "Numero de folhas: " << NumFolhas(raiz) << endl;
}

template <class T, class U>
void Dicionario<T, U>::ImprimeRec(No<T, U> * x)
{
if(x == NULL)
return;

   ImprimeRec(x->esquerda);
   cout << x->chave << " ";
   x->conteudo.Imprime();
   ImprimeRec(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NumNos(No<T, U> * x)
{
if(x == NULL)
return 0;

return 1 + NumNos(x->esquerda) + NumNos(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NumFolhas(No<T, U> * x)
{
   if(x == NULL)
       return 0;
   if(x->esquerda == NULL && x->direita == NULL)
       return 1;
   return NumFolhas(x->esquerda) + NumFolhas(x->direita);
}

template <class T, class U>
int Dicionario<T, U>::NosCaminho(No<T, U> * anda, T chave)
{
if(anda == NULL)
return 0;

if(chave == anda->chave)
return 1;

   if(chave < anda->chave)
       //o nÃ³ atual contribui em uma unidade
       //+ o nÃºmero de nÃ³s na esquerda
       return 1 + NosCaminho(anda->esquerda, chave);

if(chave > anda->chave)
return 1 + NosCaminho(anda->direita, chave);
}

template <class T, class U>
int Dicionario<T, U>::NumNiveis(No<T, U> * x)
{
if(x == NULL)
return 0;

   int ne = NumNiveis(x->esquerda);
   int nd = NumNiveis(x->direita);
   int max;
   if(ne > nd)
       max = ne;
   else
       max = nd;

return 1 + max;
}

Maio 15, 2018

Tenho um trabalho do qual esta me dando trabalho, ashuahsha

a descrição é a seguinte:

Definição do trabalho Este trabalho consiste em implementar um protótipo de rede social utilizando a estrutura de dados árvore binária de busca. O sistema permitirá o cadastramento de pessoas e suas amizades. Cada pessoa possuirá um nome, um id e um conjunto de amizades. O id é um identificador inteiro único. O nome é o nome da pessoa. O conjunto de amizades é constituído dos ids das pessoas com as quais a pessoa possui algum tipo de relação de amizade. Pessoas serão armazenadas em uma árvore binária de busca em que a chave de cada nó será o id da pessoa correspondente. O conjunto de amizades de uma pessoa será representado por uma outra árvore binária de busca. Os nós desta árvore armazenam apenas o id de cada amigo, que também é usado como chave para a organização da árvore. Em resumo, o sistema armazenará uma árvore binária de busca de pessoas. Cada pessoa possuirá uma árvore binária de busca com suas amizades. O sistema deverá suportar as seguintes operações: