我试图找到一种方法来通过链表存储指向内存块的空指针,我遇到了这种表示。
//Initalization
void * list;
//Add void pointer
void add_pointer(void * p) {
*(void **)p = list;
list = p;
}
//Remove pointer with address
void remove_pointer(void * p) {
void ** iter;
iter = &list;
while ((*iter != NULL) && (*iter != p)) {
iter = (void **)*iter;
}
if (*iter == p) {
*iter = *(void **)p;
}
}
这是如何运作的?下一个 block 的地址是否存储在 void 指针指向的前一个 block 的数据中?假设列表初始化为 NULL。
此外,这是否假设每个 void 指针的 block 中都没有写入数据?如果有人能阐明这个实现的工作原理,那就太好了,它可以用作链表似乎非常深奥。
最佳答案
它假定节点中的第一个字段是链接指针的槽,它是一个void *
。而list
是一个void *
,它总是指向链表的头部。
add_pointer()
函数将一个新节点添加到列表的开头。 void *p
参数指向要添加的新节点。该函数将 void *
p 转换为 void **
以便 *(void **)p
可以容纳 void *
指针。该函数将之前的头指针存储在这个位置作为
*(void **)p = list; // list is a void * to the first element
然后它将 list
设置为 void *
到新的第一个元素,即 p。
现在 remove_pointer()
函数从列表中删除一个节点,将指向它的 void *
作为参数。 iter
用于迭代列表。它最初被分配了 list
的地址,因此 *iter
将给出链接指针,该指针始终被假定为节点中的第一个字段。 while 循环将 iter
更新到列表中的下一个节点,直到它在当前节点的链接指针字段中找到 p
(即要删除的节点)。此时,它更新当前节点的链接指针字段指向p指向的节点的链接指针字段值,这是通过语句
*iter = *(void **)p; // *iter gives the link pointer filed of the current node
// p, is the node to be removed, *(void **)p gives the value in
// the link pointer filed of p
关于c++ - 奇数链表表示,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19674044/