My doubt is regarding pointer only,Here
head is a double poiner to Queue if we are using
*head than we are accessing the location(or address passed) inside main but when we are using simply
head than we are using
head in the current function only which will hold the address of pointer to
Queue now when we are doing this
head=&(*head)->next the since
(*head)->next is itself a address and when we use
& before this ,than will a separate block will memory block will be created and hold the address of
(*head)->next and we are assigning that address to head I have this doubt because its like a two step process we cannot directly put the
(*head)->next to sore something inside head we need to pass address of address for that we would require a extra block and when the loop will executed say n times than there will be n intermediate blocks? Please tell me if i am correct or not and tell the right logic thanks
void queue_push(Queue **head, int d, int p)
{
Queue *q = queue_new(d, p);
while (*head && (*head)->priority < p) {
head = &(*head)->next;
}
q->next = *head;
*head = q;
}
doubt number 2
In the function
Graph *G = malloc(sizeof(*G));
He is allocating memory block for one block which will hold the pointer to G
what about other elements in the structure no memory allocation for them inside the structure for their pointer (I am taking with respect to structure of Graph)
Code is taken from a good book
Please help me
What I have tried:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Queue Queue;
struct Queue {
int data;
int priority;
Queue *next;
};
Queue *queue_new(int d, int p)
{
Queue *n = malloc(sizeof(*n));
n->data = d;
n->priority = p;
n->next = NULL;
return n;
}
int queue_pop(Queue **head)
{
assert(*head);
Queue *old = *head;
int res = old->data;
*head = (*head)->next;
free(old);
return res;
}
void queue_remove(Queue **head, int data)
{
while (*head && (*head)->data != data) {
head = &(*head)->next;
}
if (*head) queue_pop(head);
}
void queue_push(Queue **head, int d, int p)
{
Queue *q = queue_new(d, p);
while (*head && (*head)->priority < p) {
head = &(*head)->next;
}
q->next = *head;
*head = q;
}
int queue_empty(Queue *head)
{
return (head == NULL);
}
void queue_print(const Queue *q)
{
while (q) {
printf("%d[%d] ", q->data, q->priority);
q = q->next;
}
puts("$");
}
typedef struct Graph Graph;
typedef struct Edge Edge;
struct Edge {
int vertex;
int weight;
Edge *next;
};
struct Graph {
int v;
Edge **edge;
int *dist;
int *path;
};
Graph *graph_new(int v)
{
Graph *G = malloc(sizeof(*G));
G->v = v;
G->edge = calloc(v, sizeof(*G->edge));
G->dist = calloc(v, sizeof(*G->dist));
G->path = calloc(v, sizeof(*G->path));
return G;
}
void graph_delete(Graph *G)
{
if (G) {
for (int i = 0; i < G->v; i++) {
Edge *e = G->edge[i];
while (e) {
Edge *old = e;
e = e->next;
free(old);
}
}
free(G->edge);
free(G->dist);
free(G->path);
free(G);
}
}
Edge *edge_new(int vertex, int weight, Edge *next)
{
Edge *e = malloc(sizeof(*e));
e->vertex = vertex;
e->weight = weight;
e->next = next;
return e;
}
void graph_edge(Graph *G, int u, int v, int w)
{
G->edge[u] = edge_new(v, w, G->edge[u]);
G->edge[v] = edge_new(u, w, G->edge[v]);
}
void dijkstra(const Graph *G, int s)
{
Queue *queue = NULL;
for (int i = 0; i < G->v; i++) G->dist[i] = -1;
G->dist[s] = 0;
queue_push(&queue, s, 0);
while (!queue_empty(queue)) {
int v = queue_pop(&queue);
Edge *e = G->edge[v];
while (e) {
int w = e->vertex;
int d = G->dist[v] + e->weight;
if (G->dist[w] == -1) {
G->dist[w] = d;
G->path[w] = v;
queue_push(&queue, w, d);
}
if (G->dist[w] > d) {
G->dist[w] = d;
G->path[w] = v;
queue_remove(&queue, w);
queue_push(&queue, w, d);
}
e = e->next;
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
Graph *G;
int v, e, s;
scanf("%d %d", &v, &e);
G = graph_new(v);
for (int i = 0; i < e; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
graph_edge(G, u - 1, v - 1, w);
}
scanf("%d", &s);
dijkstra(G, s - 1);
for (int i = 0; i < G->v; i++) {
if (i != s - 1) {
printf("%d ", G->dist[i]);
}
}
puts("");
graph_delete(G);
}
return 0;
}