0

我一直在用 C++ 解决一个问题，Dijkstra 算法。我已经使用邻接列表实现了它。

所以我有一个用于 anode的类、一个用于 a 的类minHeap和一个用于Graph.

class node
{
    int vertex,weight;
    node *next;
    friend class Graph;
    friend class minHeap;
public:
    node();
    node(int,int);
};
node::node(){
    vertex=weight=0;
    next=0;
}
node::node(int v,int wt){
    vertex=v;
    weight=wt;
    next=0;
}

我是否以minHeap这种方式定义类（没有友元函数）并在getDijkSP()函数中正常创建一个对象，这允许我仅在该函数中使用该对象？

class minHeap
{
    node *heap;
    int heapSize,capacity,*pos;
public:
    minHeap(int);
    void addElement(node);
    node extractMin();
    void minHeapify(int);
    void decreaseKey(int,int);
};
minHeap::minHeap(int cap){
    heap=new node[capacity=cap];
    heapSize=-1;
    pos=new int[cap]();
}                                        //eliminating other methods

class Graph
{
    node **adjList;
    int v;
    bool *visited;
public:
    Graph(int);
    void addEdge(int,int,int);
    void removeEdge(int,int);
    bool existsEdge(int,int);
    void getDijkSP();
};
Graph::Graph(int vertices){
    adjList=new node*[v=vertices];
    for(int i=0;i<v;i++)
        adjList[i]=NULL;
}
void Graph::getDijkSP(){
    minHeap hp(v);                            //here
    hp.addElement(node(0,0));
    for(int i=1;i<v;i++)
        hp.addElement(node(i,INT_MAX));
    while(!hp.isempty()){
        node temp=hp.extractMin();
        cout<<temp.vertex<<" "<<temp.weight<<endl;
        for(node *current=adjList[temp.vertex];current;current=current->next)
            hp.decreaseKey(current->vertex,current->weight+temp.weight);
    }
}

（或）我是否minHeap使用友元函数定义类，以便可以minHeap使用 new 关键字创建类的对象？（这有助于我minHeap在类的范围内定义对象Graph，以便我可以在其所有功能中使用它来实现其他功能。）

class minHeap
{
    node *heap;
    int heapSize,capacity,*pos;
    friend class Graph;                //say like this
public:
    minHeap(int);
    void addElement(node);
    node extractMin();
    void minHeapify(int);
    void decreaseKey(int,int);
};
minHeap::minHeap(int cap){
    heap=new node[capacity=cap]();
    heapSize=-1;
    pos=new int[cap]();
}

class Graph
{
    node **adjList;
    int v;
    bool *visited;
    minHeap *hp;                                //and do this
public:
    Graph(int);
    void addEdge(int,int,int);
    void removeEdge(int,int);
    bool existsEdge(int,int);
    void getDijkSP();
};
Graph::Graph(int vertices){
    adjList=new node*[v=vertices];
    for(int i=0;i<v;i++)
        adjList[i]=NULL;
    hp=new minHeap(v);                        //dynamic allocation
}
void Graph::getDijkSP(){
    hp->addElement(node(0,0));
    for(int i=1;i<v;i++)
        hp->addElement(node(i,INT_MAX));
    while(!hp->isempty()){
        node temp=hp->extractMin();
        cout<<temp.vertex<<" "<<temp.weight<<endl;
        for(node *current=adjList[temp.vertex];current;current=current->next)
            hp->decreaseKey(current->vertex,current->weight+temp.weight);
    }
}

我已经阅读了这篇文章和其他几篇文章，但特别想知道这两种方法对于此类类似问题的优缺点和适用性。

为了更清楚起见，我提供了类的构造函数。

4

1 回答 1

0

简短的回答是否定的。我建议您阅读智能指针并重写整个混乱。在 C++ 中，没有真正的理由在如此简单的项目中使用手动分配。

此外，不要将 0 或 NULL 分配给指针，而是使用 nullptr，它是 C++ 符号，仅用于空指针，不像前面提到的 C 值实际上只是一个 int 0，这可能会导致一些无意的错误。

编辑以回应您的评论：

因此，我决定使用实际的现代 C++ 重写您的代码，而不是使用简单类的 C 代码。在您的整个示例中，几乎不需要指针或动态分配。我不确定谁应该拥有实际的节点，所以从示例中我假设 MinHeap 应该拥有。此外，我没有从我所看到的情况中得到 MinHeap::pos 和 Graph::visited 的意义。我可以更详细地解释该代码的任何部分，只要问哪个。

这是代码：

class Node {
    // Only friend class required if you insist on keeping members of Node private.
    // If they aren't meant to change, consider declaring them as public and const.
    template <unsigned Size> friend class Graph;
public:
    Node(int v, int wt) : vertex(v), weight(wt) {}

private:
    // Default values written in here right after declarations
    // There is no need for a default constructor. You never call it anyway.
    int vertex;
    int weight;
    Node* next = nullptr;
};

// Template parameter because of internal use of std::array.
// If the capacity shouldn't be constant, use std::vector and remove template.
template <unsigned Capacity>
class MinHeap {
public:
    // No constructor needed
    // ---------------------

    // One small tip: write parameter names in function declarations
    // even if they aren't needed there for better readability of your code.
    void addElement(Node n) { /* impl */ }
    Node extractMin() { /* impl */ }

    unsigned capacity() { return Capacity; }
    bool isEmpty() { return heap.isEmpty(); }

private:
    // Default values written in here right after declarations
    int heapSize = -1;
    std::array<Node, Capacity> heap;
};

// Template parameter because of internal use of std::array.
// If the vertex count shouldn't be constant, use std::vector and remove template.
template <unsigned Vertices>
class Graph {
public:
    // No constructor needed
    // ---------------------

    void getDjikSP() {
        hp.addElement({0, 0});
        for (unsigned i = 1; i < hp.capacity(); ++i)
            hp.addElement({0, INT_MAX});

        while (!hp.isEmpty()) {
            Node tmp = hp.extractMin();
            std::cout << tmp.vertex << " " << tmp.weight << std::endl;

            for (Node* current = adjList[tmp.vertex]; current != nullptr; current = current->next)
                hp.decreaseKey(current->vertex, current->weight + tmp.weight);
        }
    }

private:
    // Default values written in here right after declarations
    std::array<Node*, Vertices> adjList;
    MinHeap<Vertices> hp;
};

这段代码还有很大的改进空间，例如，如果 MinHeaP::extractMin 从堆中删除，它可能应该返回 Node&&，或者如果它应该返回对顶部的引用，则应该返回 const Node&，等等。为了解决所有问题这仍然可能存在问题和效率低下我需要查看所有功能的完整代码。

于 2017-07-12T10:31:28.427 回答