double pointer to a node
My doubt is regarding pointer only,Here head is a double pointer 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 heading 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;
}
Full program is
#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;
}
c pointers memory-management
add a comment |
My doubt is regarding pointer only,Here head is a double pointer 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 heading 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;
}
Full program is
#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;
}
c pointers memory-management
while (*head && (*head)->priority < p) { head = &(*head)->next; }should walk the list, not changehead.
– chux
Nov 16 '18 at 18:46
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned toheadif this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block
– user10628441
Nov 16 '18 at 18:55
Nice use ofsizeof(*G)inG = malloc(sizeof(*G))rather thanmalloc(sizeof(Graph)).
– chux
Nov 16 '18 at 19:17
add a comment |
My doubt is regarding pointer only,Here head is a double pointer 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 heading 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;
}
Full program is
#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;
}
c pointers memory-management
My doubt is regarding pointer only,Here head is a double pointer 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 heading 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;
}
Full program is
#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;
}
c pointers memory-management
c pointers memory-management
asked Nov 16 '18 at 18:10
user10628441
while (*head && (*head)->priority < p) { head = &(*head)->next; }should walk the list, not changehead.
– chux
Nov 16 '18 at 18:46
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned toheadif this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block
– user10628441
Nov 16 '18 at 18:55
Nice use ofsizeof(*G)inG = malloc(sizeof(*G))rather thanmalloc(sizeof(Graph)).
– chux
Nov 16 '18 at 19:17
add a comment |
while (*head && (*head)->priority < p) { head = &(*head)->next; }should walk the list, not changehead.
– chux
Nov 16 '18 at 18:46
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned toheadif this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block
– user10628441
Nov 16 '18 at 18:55
Nice use ofsizeof(*G)inG = malloc(sizeof(*G))rather thanmalloc(sizeof(Graph)).
– chux
Nov 16 '18 at 19:17
while (*head && (*head)->priority < p) { head = &(*head)->next; } should walk the list, not change head.– chux
Nov 16 '18 at 18:46
while (*head && (*head)->priority < p) { head = &(*head)->next; } should walk the list, not change head.– chux
Nov 16 '18 at 18:46
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned to
head if this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block– user10628441
Nov 16 '18 at 18:55
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned to
head if this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block– user10628441
Nov 16 '18 at 18:55
Nice use of
sizeof(*G) in G = malloc(sizeof(*G)) rather than malloc(sizeof(Graph)).– chux
Nov 16 '18 at 19:17
Nice use of
sizeof(*G) in G = malloc(sizeof(*G)) rather than malloc(sizeof(Graph)).– chux
Nov 16 '18 at 19:17
add a comment |
1 Answer
1
active
oldest
votes
queue_push() fails to insert a new node correctly.
Only one node's .next is updated. Usually 2 nodes need their .next member updated. One in the original list (previous to the new node's location) and the new one.
I find creating a temporary node before the list, superhead, simplifies code.
void queue_push(Queue **head, int d, int p) {
Queue *q = queue_new(d, p);
Queue superhead; // Only superhead.next member important.
superhead.next = *head;
Queue *previous = &superhead;
while (previous->next && previous->next->priority < p) {
previous = previous->next;
}
q->next = previous->next;
previous->next = q;
*head = superhead.next;
}
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53343267%2fdouble-pointer-to-a-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
queue_push() fails to insert a new node correctly.
Only one node's .next is updated. Usually 2 nodes need their .next member updated. One in the original list (previous to the new node's location) and the new one.
I find creating a temporary node before the list, superhead, simplifies code.
void queue_push(Queue **head, int d, int p) {
Queue *q = queue_new(d, p);
Queue superhead; // Only superhead.next member important.
superhead.next = *head;
Queue *previous = &superhead;
while (previous->next && previous->next->priority < p) {
previous = previous->next;
}
q->next = previous->next;
previous->next = q;
*head = superhead.next;
}
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
add a comment |
queue_push() fails to insert a new node correctly.
Only one node's .next is updated. Usually 2 nodes need their .next member updated. One in the original list (previous to the new node's location) and the new one.
I find creating a temporary node before the list, superhead, simplifies code.
void queue_push(Queue **head, int d, int p) {
Queue *q = queue_new(d, p);
Queue superhead; // Only superhead.next member important.
superhead.next = *head;
Queue *previous = &superhead;
while (previous->next && previous->next->priority < p) {
previous = previous->next;
}
q->next = previous->next;
previous->next = q;
*head = superhead.next;
}
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
add a comment |
queue_push() fails to insert a new node correctly.
Only one node's .next is updated. Usually 2 nodes need their .next member updated. One in the original list (previous to the new node's location) and the new one.
I find creating a temporary node before the list, superhead, simplifies code.
void queue_push(Queue **head, int d, int p) {
Queue *q = queue_new(d, p);
Queue superhead; // Only superhead.next member important.
superhead.next = *head;
Queue *previous = &superhead;
while (previous->next && previous->next->priority < p) {
previous = previous->next;
}
q->next = previous->next;
previous->next = q;
*head = superhead.next;
}
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
queue_push() fails to insert a new node correctly.
Only one node's .next is updated. Usually 2 nodes need their .next member updated. One in the original list (previous to the new node's location) and the new one.
I find creating a temporary node before the list, superhead, simplifies code.
void queue_push(Queue **head, int d, int p) {
Queue *q = queue_new(d, p);
Queue superhead; // Only superhead.next member important.
superhead.next = *head;
Queue *previous = &superhead;
while (previous->next && previous->next->priority < p) {
previous = previous->next;
}
q->next = previous->next;
previous->next = q;
*head = superhead.next;
}
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
edited Nov 16 '18 at 19:20
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
answered Nov 16 '18 at 19:14
chuxchux
81.4k871148
81.4k871148
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53343267%2fdouble-pointer-to-a-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
while (*head && (*head)->priority < p) { head = &(*head)->next; }should walk the list, not changehead.– chux
Nov 16 '18 at 18:46
what will be the address ` &(*head)->next` how computer generate address of address without storing the (*head)->next anywhere there should be some memory block where we can store the address of (*head)->next and now the address of that memory block will be assigned to
headif this happens then whenever loop runs then computer will store the address of all intermediates in same block or different memory block– user10628441
Nov 16 '18 at 18:55
Nice use of
sizeof(*G)inG = malloc(sizeof(*G))rather thanmalloc(sizeof(Graph)).– chux
Nov 16 '18 at 19:17