指向队列节点的双指针 [英] Double pointer to a queue node

问题描述

我的疑问只针对指针，如果我们使用 * head 而不是我们访问里面的位置（或传递的地址），那么 head 是队列的双倍精灵main但当我们使用 head 而不是我们在当前函数中使用 head 时，它将保存指向 Queue 的指针的地址我们这样做 head =&（* head） - > next 因为（* head） - > next 本身就是一个地址，当我们使用& 在此之前，将创建一个单独的块将存储块并保存（* head） - > next 的地址，我们将该地址分配给头部I有这个疑问，因为它像一个两步过程，我们不能直接把（* head） - > next 在头部内部疼痛我们需要传递地址的地址，因为我们需要一个额外的块并且当循环执行n次时会有n个中间块？请告诉我是否正确并告诉我正确的逻辑谢谢

 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; 
} 

怀疑2号



在函数中

图* G = malloc（sizeof（* G））; 

他正在为一个块分配内存块，它将把指针保存到G

结构中的其他元素怎么样没有为它们的指针结构内部分配内存（我考虑的是结构图）

代码来自一本好书

请帮帮我



我有什么试过：

 #include< stdio.h> 
 #include< stdlib.h> 
 #include< assert.h> 
 
 typedef struct Queue Queue; 
 
 struct Queue {
 int data; 
 int priority; 
队列*下一个; 
}; 
 
 Queue * queue_new（int d，int p）
 {
 Queue * n = malloc（sizeof（* n））; 
 
 n-> data = d; 
 n-> priority = p; 
 n-> next = NULL; 
 
返回n; 
} 
 
 int queue_pop（Queue ** head）
 {
 assert（* head）; 
 
队列* old = * head; 
 int res = old-> data; 
 
 * head =（* head） - > next; 
免费（旧）; 
 
返回res; 
} 
 
 void queue_remove（队列**头，int数据）
 {
 while（* head&&（* head） - > 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; 
边缘*下一个; 
}; 
 
 struct Graph {
 int v; 
边缘**边缘; 
 int * dist; 
 int * path; 
}; 
 
图表* graph_new（int v）
 {
图表* 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））; 
 
返回G; 
} 
 
 void graph_delete（Graph * G）
 {
 if（G）{
 for（int i = 0; i< G- > v; i ++）{
 Edge * e = G-> edge [i]; 
 
而（e）{
 Edge * old = e; 
 
 e = e-> next; 
免费（旧）; 
} 
} 
 
免费（G->边缘）; 
免费（G-> dist）; 
免费（G->路径）; 
免费（G）; 
} 
} 
 
 Edge * edge_new（int vertex，int weight，Edge * next）
 {
 Edge * e = malloc（sizeof（* E））; 
 
 e-> vertex = vertex; 
 e->重量=重量; 
 e-> next = next; 
 
返回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]; 
 
而（e）{
 int w = e-> vertex; 
 int d = G-> dist [v] + e->重量; 
 
 if（G-> dist [w] == -1）{
 G-> dist [w] = d; 
 G->路径[w] = v; 
 
 queue_push（& queue，w，d）; 
} 
 
 if（G-> dist [w]> d）{
 G-> dist [w] = d; 
 G->路径[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）; 
} 
 
返回0; 
} 
 

解决方案

）;
}

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_new（int v）
{
图表* 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））;

返回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;
免费（旧）;
}
}

免费（G->边缘）;
免费（G-> dist）;
免费（G->路径）;
免费（G）;
}
}

Edge * edge_new（int vertex，int weight，Edge * next）
{
Edge * e = malloc（sizeof（* E））;

e-> vertex = vertex;
e->重量=重量;
e-> next = next;

返回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];

而（e）{
int w = e-> vertex;
int d = G-> dist [v] + e->重量;

if（G-> dist [w] == -1）{
G-> dist [w] = d;
G->路径[w] = v;

queue_push（& queue，w，d）;
}

if（G-> dist [w]> d）{
G-> dist [w] = d;
G->路径[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）;
}

返回0;
}

让我们尝试一些实验证据。该程序

  #include   <   stdio.h  >  
   #include   <   stdlib.h  >  
  
  struct 队列
 {
  int 数据; 
  int 优先级; 
  struct 队列*下一个; 
}; 
 
  void  dump_pointers（ struct  Queue ** phead）
 { 
 printf（   -  dump_pointers  -  \ n）; 
 printf（  phead =％p，* phead =％p&（* phead）=％p \ n，phead，* phead，&（* phead））; 
} 
 
  void  dump_sizes（ struct  Queue * p）
 {
 printf（   -  dump_sizes  -  \ n）; 
 printf（  sizeof（* p）=％lu \ n，的sizeof （* p））; 
 printf（  sizeof（p-> data）=％lu \ n ， sizeof （p-> data））; 
 printf（  sizeof（p-> priority）=％lu \ n ， sizeof （p-> priority））; 
 printf（  sizeof（p-> next）=％lu \ n ， sizeof （p-> next））; 
} 
 
  int  main（）
 {
  struct 队列* head =（ struct 队列*）malloc（ sizeof （* head）） ; 
 printf（  head =％p \ n，head）; 
 dump_pointers（& head）; 
 dump_sizes（head）; 
免费（头）; 
  return   0 ; 
} 

输出：

 head = 0x826010 
  -  dump_pointers  -  
 phead = 0x7ffc5a7e5020，* phead = 0x826010&（* phead）= 0x7ffc5a7e5020 
  -  dump_sizes  -  
 sizeof（* p）= 16 
 sizeof（p->数据）= 4 
 sizeof（p->优先级）= 4 
 sizeof（p-> next）= 8 

所以：

• phead 和之间（当然）没有区别&（* phead）。
• struct 的大小等于其成员变量大小的总和（如果某些结构变量是指针，则malloc不会分配更多内存，以使它们指向有效的内存区域。）

< pre lang =c ++> Graph * G = malloc（ sizeof （* G））;

他正在为一个块分配内存块它将指针指向G



不完全正确。它正在分配Graph结构并将G分配给该结构的地址。这当然是可读代码，但我认为它模糊了真正发生的事情，特别是对初学者而言。我认为最好写成：

 Graph * g = malloc（ sizeof （Graph））; 

I认为这可以更清楚地显示出什么。就个人而言，我更喜欢使用calloc，因为它将分配的内存归零。还有一件事，正如你在Pallini先生的解决方案中看到的那样，分配结果需要强制转换，因为它返回一个void指针。这意味着我的小例子需要写成

 Graph * g =（Graph *）malloc（ sizeof （Graph））; 

在它的价值类别下，这里有一个可以简化内存分配的小宏：

  #define AllocateMemory（count，type） （类型*）calloc（count，sizeof（type）） 

在这种情况下用于一个实例：

图* g = AllocateMemory（ 1 ，Graph）; 

如您所见，不需要进行铸造。

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;
   }

解决方案

"); } 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; }

Let's try a bit of experimental evidence. The program

#include <stdio.h>
#include <stdlib.h>

struct Queue
{
  int data;
  int priority;
  struct Queue *next;
};

void dump_pointers( struct Queue ** phead)
{
  printf("-- dump_pointers --\n");
  printf("phead=%p, *phead=%p &(*phead)=%p\n", phead, *phead, &(*phead));
}

void dump_sizes( struct Queue *p)
{
  printf("-- dump_sizes --\n");
  printf("sizeof(*p)=%lu\n", sizeof(*p));
  printf("sizeof(p->data)=%lu\n", sizeof(p->data));
  printf("sizeof(p->priority)=%lu\n", sizeof(p->priority));
  printf("sizeof(p->next)=%lu\n", sizeof(p->next));
}

int main()
{
  struct Queue * head = (struct Queue *) malloc(sizeof(*head));
  printf("head = %p\n", head);
  dump_pointers( &head);
  dump_sizes( head );
  free(head);
  return 0;
}

The output:

head = 0x826010
-- dump_pointers --
phead=0x7ffc5a7e5020, *phead=0x826010 &(*phead)=0x7ffc5a7e5020
-- dump_sizes --
sizeof(*p)=16
sizeof(p->data)=4
sizeof(p->priority)=4
sizeof(p->next)=8

So:

• There is (of course) no difference between phead and &(*phead).
• The size of a struct is equal to sum of the size of its member variables (if some of the struct variables are pointers, no further memory is allocated by malloc in order to make they point to a valid memory area).

Graph *G = malloc(sizeof(*G));

"He is allocating memory block for one block which will hold the pointer to G"

Not exactly. It is allocating a Graph structure and assigning G to the address of that structure. That is certainly readable code but I think it obscures what's really going on, especially for beginners. I think it would better written as:

Graph *g = malloc( sizeof( Graph ) );

I think that shows what's going on much more clearly. Personally, I prefer to use calloc because it zeros the allocated memory. One more thing, as you can see in Mr. Pallini's solution, a cast is required on the result of the allocation because it returns a void pointer. This means my little example needs to be written as

Graph *g = (Graph *)malloc( sizeof( Graph ) );

Under the category of for what it's worth, here's a little macro that can simplify memory allocation:

#define AllocateMemory(count,type)	(type*)calloc(count,sizeof(type))

to use it in this case for one instance :

Graph *g = AllocateMemory( 1, Graph );

As you can see, no casting is needed.

这篇关于指向队列节点的双指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！