oop — Реализация объектно-ориентированных графов в Stack Overflow
Я должен реализовать симуляцию WWW на c ++ с использованием графиков, где узлы — это веб-страницы, а направленные ребра — это URL-адреса.
В школе, на нашем уровне, мы все еще начинаем в объектно-ориентированном программировании, поэтому они предложили реализовать с использованием списков смежности и матриц смежности, но они мне не нравятся, потому что они монстры памяти и очень ограничены.
Вопрос:
Можете ли вы предложить другую структуру данных (предпочтительно объектно-ориентированный материал), которая использует указатели (как ребра) на другие узлы, и где я могу динамически генерировать столько ребер, сколько мне нравится ???
Я прочитал это, но я не нашел ничего полезного:
Объектно-ориентированная реализация структур данных графа
Решение
Честно говоря, попытка представить это только в одной структуре данных окажется довольно неэффективной. В действительности у вас есть меньший список регистраторов доменов, которые обеспечивают поиск. Что-то более точное, чем один тупой график, будет:
#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <string>
#include <set>
class Webpage;
class Registrar : public std::enable_shared_from_this<Registrar> {
public:
std::shared_ptr<Webpage> resolve(const std::string &url);
private:
std::map<std::string, std::shared_ptr<Webpage>> pages;
};
class Webpage {
public:
Webpage(std::shared_ptr<Registrar> registrar, const std::string &url) :
registrar(registrar),
url(url){
}
std::shared_ptr<Webpage> addLink(const std::string &url){
links.push_back(url);
return registrar->resolve(url);
}
std::vector<std::shared_ptr<Webpage>> resolvePageLinks(){
std::vector<std::shared_ptr<Webpage>> pages;
for (auto &linkUrl : links){
pages.push_back(registrar->resolve(linkUrl));
}
return pages;
}
std::string getUrl() const{
return url;
}
private:
std::string url;
std::shared_ptr<Registrar> registrar;
std::vector<std::string> links;
};
std::shared_ptr<Webpage> Registrar::resolve(const std::string &url){
auto found = pages.find(url);
if (found != pages.end()){
return found->second;
}
else{
auto webpage = std::make_shared<Webpage>(shared_from_this(), url);
pages.insert({url, webpage});
return webpage;
}
}
void printPageHierarchy(std::shared_ptr<Webpage> current, int depth, std::set<std::shared_ptr<Webpage>> &visited){
std::cout << std::string(3*depth, ' ');
std::cout << current->getUrl() << std::endl;
if (visited.find(current) == visited.end()){
visited.insert(current);
++depth;
for (auto page : current->resolvePageLinks()){
printPageHierarchy(page, depth, visited);
}
}else{
std::cout << std::string(3*depth, ' ');
std::cout << "..." << std::endl;
}
}
void printPageHierarchy(std::shared_ptr<Webpage> current){
std::set<std::shared_ptr<Webpage>> visited;
printPageHierarchy(current, 0, visited);
}
int main(){
auto registrar = std::make_shared<Registrar>();
auto site1 = registrar->resolve("site1.com");
site1->addLink("site2.com");
site1->addLink("site3.com")->addLink("site4.com")->addLink("site1.com");
std::cout << "From site1.com:" << std::endl;
printPageHierarchy(site1);
std::cout << "_____________\nFrom site3.com:" << std::endl;
printPageHierarchy(registrar->resolve("site3.com"));
}
Это довольно упрощенно и, очевидно, минимально. Ваш вопрос делает немного неясным, что именно ваши требования на самом деле.
Другие решения
Других решений пока нет …
detector