c++ - 用 C 向量替换 C++ 向量

Question

我有以下算法：

// Prim cu coada de prioritati si graful reprezentat printr-un array de vectori(matrice)
#include <vector>
#include <queue>
#include <list>
#include <stdio.h>
using namespace std; 
# define INF 0x3f3f3f3f 

struct Edge {
    int destination;
    int weight;
};

Edge newEdge(int destination, int weight) {
    return { destination, weight };
};

// Adaugarea unei muchii
void addEdge(vector <Edge> adj[], int from, int to, int weight) 
{ 
    adj[from].push_back(newEdge(to, weight));
    adj[to].push_back(newEdge(from, weight));
};

// To compare two points 
bool cmp(const Edge& e1, const Edge& e2) { 
    return e1.weight >= e2.weight; 
};

// Printeaza cel mai scurt drum de la sursa(nodul parinte) la celelalte noduri
void primMST(vector<Edge> adj[], int V, int numberElemOp) 
{ 

    // Creaza o coada de prioritati pentru a stoca nodurile. 
    // Pentru sintaxa ca data trecuta vezi: http://geeksquiz.com/implement-min-heap-using-stl/ 
    priority_queue< Edge, vector <Edge> , decltype(&cmp) > pq{cmp}; 

    int src = 0; // Nodul 0 este nodul parinte

    // vector pentru retinerea arborelui construit
    int parent[V]; 
    // Key values used to pick minimum weight edge in cut 

    // valorile utilizate pentru a alege minimul
    int key[V]; 

    // Vector care arata ce noduri au intrat in MST
    bool inMST[V];

    for (int i = 0; i < V; i++)  {
        key[i] = INF;
        inMST[i] = false;
        parent[i] = -1;    
    }

    numberElemOp += (3 * V);

    // Insereaza nodul parinte in coada de prioritati si pune cheia pe 0
    pq.push(newEdge(src, 0));
    key[src] = 0; 

    numberElemOp += 3;

    /* Pana cand se goleste coada */
    while (!pq.empty()) 
    { 
        // Primul nod din pereche este cheia minima, extrage cheia din coada de prioritati.
        // Numele nodului este stocat in a 2 a pereche (asa trebuie facut ca sa ai nodurile sortate dupa cheie
        // cheia trebuie sa fie prima valoare din pereche)
        int u = pq.top().destination; 
        pq.pop(); 

        inMST[u] = true; // Nod inclus in MST


        numberElemOp += 3;
        // Traverseaza toti vecinii lui u
        for (auto x : adj[u]) 
        { 
            // Ia numele si costul nodului vecin cu u
            int v = x.destination; 
            int weight = x.weight; 

            numberElemOp += 3;
            // Daca v nu este in MST si costul muchiei (u,v) este mai mic decat cheia lui v
            if (inMST[v] == false && key[v] > weight) 
            { 
                // Updateaza v
                key[v] = weight; 
                pq.push(newEdge(v, key[v])); 
                parent[v] = u; 
                numberElemOp += 7;
            } 
        } 
    } 

    // Printeaza muchiile msg-ului
    for (int i = 1; i < V; ++i) 
        printf("%d - %d\n", parent[i], i);

    printf("Numar operatii elementare: %d", numberElemOp);
} 

int main() 
{ 
    int numberElemOp;
    int V = 9; 
    numberElemOp += 1;
    vector<Edge> adj[V]; 

    addEdge(adj, 0, 1, 4); 
    addEdge(adj, 0, 7, 8); 
    addEdge(adj, 1, 2, 8); 
    addEdge(adj, 1, 7, 11); 
    addEdge(adj, 2, 3, 7); 
    addEdge(adj, 2, 8, 2); 
    addEdge(adj, 2, 5, 4); 
    addEdge(adj, 3, 4, 9); 
    addEdge(adj, 3, 5, 14); 
    addEdge(adj, 4, 5, 10); 
    addEdge(adj, 5, 6, 2); 
    addEdge(adj, 6, 7, 1); 
    addEdge(adj, 6, 8, 6); 
    addEdge(adj, 7, 8, 7); 

    primMST(adj, V, numberElemOp); 

    return 0; 
}

问题是我不允许使用 C++，我必须使用 C。这有点令人失望，因为 C 没有向量和优先级队列。或任何类似的结构已经实现。

我试着玩弄我自己的 Vector 实现，但最后我无法让它工作。

有没有办法可以用 C 中的东西替换 vector 和/或 priority_queue？是否有人已经在 C 中实现了 vector/priority_queue 来实现这项工作？

标签： c++c