Tạo trong C#, C++ và Java một phiên bản đánh máy mạnh mẽ của một con trăn cấu trúc gõ yếu

Question

Trong python Tôi đã điều sau đây:

graph = {} 

graph[1] = {} 
graph[2] = {} 
graph[3] = {} 

graph[1][3] = graph[3] 

graph[2][1] = graph[1] 
graph[2][3] = graph[3] 

graph[3][2] = graph[2] 

này là một cấu trúc để đại diện cho một đồ thị và mà tôi tìm thấy thoải mái bởi vì cấu trúc của nó giống như một trong các nút của nó vì vậy tôi có thể sử dụng nó trực tiếp để bắt đầu tìm kiếm (như trong chiều sâu đầu tiên). Phiên bản in của nó là:

{1: {3: {2: {1: {...}, 3: {...}}}}, 2: {1: {3: {2: {...}}}, 3: {2: {...}}}, 3: { 
2: {1: {3: {...}}, 3: {...}}}} 

Và nó có thể được sử dụng như:

graph[1][3][2][3][2][1][3][2][1][3][2].keys() 

Bây giờ, tôi tò mò muốn biết làm thế nào người ta sẽ thực hiện nó trong C++, C# và Java mà không cần đến "Đối tượng" thủ thuật sẽ điền mã với các phôi xấu xí. Đối với C++ Tôi đã suy nghĩ trong templatemeta lập trình nhưng điều đó sẽ tạo ra "các kiểu dữ liệu hữu hạn" khi những gì cần thiết là một cái gì đó giống như

map<int,map<int,...>> or map<int,...> 

Answer 1

Dưới đây là một hack đơn giản:

#include <map> 
#include <memory> 

struct GraphNode 
{ 
    std::map<std::size_t, std::unique_ptr<GraphNode>> m; 

    GraphNode & operator[](std::size_t i) 
    { 
    if (!m[i]) { m[i].reset(new GraphNode); } 
    return *m[i]; 
    } 
}; 

Chúng tôi thêm một số quá tải ostream để in:

#include <prettyprint.hpp> 

std::ostream & operator<<(std::ostream & o, GraphNode const & g) 
{ 
    if (g.m.empty()) return o << "*"; 
    return o << g.m; 
} 
std::ostream & operator<<(std::ostream & o, std::unique_ptr<GraphNode> const & p) 
{ 
    if (!p) return o << "*"; 
    return o << *p; 
} 

E sử dụng xample:

#include <iostream> 

int main() 
{ 
    GraphNode n; 

    n[2] = GraphNode(); 
    n[4] = GraphNode(); 

    n[2][3] = GraphNode(); 
    n[2][8] = GraphNode(); 
    n[2][1] = GraphNode(); 

    std::cout << n << std::endl; 
} 

Prints: [(2, [(1, *), (3, *), (8, *)]), (4, *)]

đặc điểm khác có thể dễ dàng bổ sung; tại thời điểm này không rõ ràng cho dù bạn muốn tất cả các nút cũng hỗ trợ dữ liệu vệ tinh ("giá trị") hay chỉ có nút lá có thể có giá trị hoặc nếu không có bất kỳ dữ liệu bổ sung nào.

Answer 2

Để lưu trữ một trong hai đồ thị thêm hoặc giá trị "thiết bị đầu cuối" (trên thực tế, cả hai cách tiếp cận khái quát để arbitarily nhiều loại với bất kỳ giải thích, miễn là chúng có thể được liệt kê tại compiletime), bạn sử dụng một trong hai:

• Unions (có thể discriminated), hoặc
• polymorphism (đặc biệt là kiểu phụ polymorphism)

Trong cả hai trường hợp, bạn có loại Graph sau đó bạn có thể ẩn cả biểu đồ lồng nhau và giá trị được lưu trữ.

Trong C++ cụ thể, bạn có thể sử dụng trước đây là union hoặc Boost::Variant (an toàn hơn và thuận tiện hơn để xử lý). Bạn có thể cần phải chuyển tiếp khai báo lớp để nó hiển thị tại thời điểm bạn xác định nó. Một công đoàn cung cấp đủ chỗ để lưu trữ một giá trị của một trong hai loại, và (hoặc ngầm trong Boost::Variant hoặc rõ ràng với đồng bằng cũ union) một "thẻ" cho biết đó là một trong những trường hợp. Sau đó, bạn có thể xem xét bất kỳ giá trị được lưu trữ nào và cho biết đó là một đồ thị hay giá trị đầu cuối khác và trích xuất giá trị được liên kết.

Trong Java và C#, bạn không có nhiều hỗ trợ cho các loại liên kết thẳng về phía trước, vì vậy bạn sẽ sử dụng tùy chọn thứ hai. Có một giao diện (hoặc trừu tượng) lớp IGraph, với một triển khai cho biểu đồ (tham chiếu đến IGraph s) và một cho gói các giá trị không phải đồ thị trong một loại phụ khác là IGraph. Về cơ bản bạn sử dụng đa hình subtype. Điều này cũng có thể xảy ra trong C++, nhưng tôi nhận được ấn tượng rằng một liên minh là một ý tưởng tốt hơn nếu các kiểu có thể được biết trước, không bao giờ thay đổi và nhỏ về số lượng. Nó cũng cho phép bạn tránh một số con trỏ/tài liệu tham khảo - cả hai union s và Boost::Variant s có thể được lưu trữ trên ngăn xếp, trong khi đa hình đòi hỏi indirection.

Answer 3

Trong Java, tôi sẽ đi với một lớp Node đại diện cho bất kỳ nút nào của biểu đồ.

public class Node<T> { 
    private List<Node<T>> children = new ArrayList<Node<T>>(); 
    private T value; 

    public Node(T value) { 
     this.value = value; 
    } 

    public void addChild(Node<T> child) { 
     this.children.add(child); 
    } 

    public Node<T> getChild(int index) { 
     return this.children.get(index); 
    } 

    public List<Node<T>> getChildren() { 
     return this.children; 
    } 

    public T getValue() { 
     return this.value; 
    } 
} 

Nếu bạn muốn có một đồ thị mà sẽ chứa các giá trị int bạn có thể nhanh chóng nó và sử dụng nó với:

Node<Integer> graph = new Node<Integer>(10); //value of the first node is 10 
graph.addChild(new Node<Integer>(-3)); 
graph.getChild(0).addChild(new Node<Integer>(5)); 
System.out.println(graph.getChild(0).getChild(0).getValue()); //prints 5