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.
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;
};
Pergunta
Akinase
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;
}
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.