链接列表，但每个“下一个”指针指向下一个节点的“下一个”指针

Question

我试图写一个链接列表，其限制是节点内的指针必须指向下一个节点的指针。有了这个限制，我将如何访问节点内的变量？ 说出节点被定义

struct Node { 
    int val; 
    void *next; 
} 

但对于每一个节点，假设我们有currentNode和nextNode，我们提出void *的下一个值

currentNode.next = &(nextNode.next); 

你会如何去创造这一点，并有效地访问各节点？

Answer 1

通过使用offsetof运算符减去next的偏移量，可以获得指向Node的指针。

struct Node *nextNode = (struct Node *)((char *)currentNode.next - offsetof(Node, next)); 
int nextVal = nextNode->val; 

如果你使用的C99，不具有offsetof()内置的，你可以用这个传统的宏：

#define offsetof(st, m) ((size_t)&(((st *)0)->m)) 

这在技术上是未定义的行为（见Does &((struct name *)NULL -> b) cause undefined behaviour in C11?），但它通常工作。

Answer 2

使用适当的结构，这样的限制本质上是满意：

struct Node { 
    void *next; 
    int val; 
} 

需要显式指针运算。

Answer 3

我按照您的要求实施链接列表。希望这会帮助你。在这个链接列表中，节点内的每个指针指向下一个节点指针。

请在你的程序stdio.h中，memory.h的顶部添加这3头文件和STDLIB.H这一计划的

struct Node { 
    int val; 
    void *next; 
}; 


void main(void) 
{ 
    typedef struct Node NODE; 
    NODE *f,*p,*q = NULL; 
    int i = 1; 
    /* First create your first node here */ 
    f = (NODE *)malloc(sizeof(NODE)); 
    f->next = f; 
    f->val = 0; 
    p = f; 

/* now lets create link list with 10 nodes */ 
    while(i < 10) 
    { 
    q = (NODE *)malloc(sizeof(NODE)); 
    q->next = q; 
    q->val = i++; 
    p->next = q->next; /* first node is pointing to the next node pointer */ 
    p = q; 
    } 

    /* search the link list and print its value */ 
    p = f; /* now p is pointing to the first node of the link list */ 
    i = 0; 
    /* first print the value of first node here */ 
    printf("Node :%d and val = %d\n", i, p->val); 
    while(p->next != p) 
    { 
     printf("Node :%d and val = %d\n", i++, ((NODE *)(p->next))->val); 
     p = p->next; 
    } 
} 

输出;

节点：0和val = 0

节点：1和val = 1

节点：2和val = 2

节点：3和val = 3

节点： 4和val = 4

节点：5和val = 5

节点：6和val = 6

节点：7和val = 7

节点：8和val = 8

节点：9和Val = 9