为什么我在洗牌链表时会丢失一个节点?
Why am I losing a node when shuffling a linked list?
我一直在做一个项目。项目的一部分需要一个混洗链表。此函数是 fisher-yates 混洗算法的实现。它将链表放入数组中。然后它洗牌。然后重新链接它。
经过一些测试,我发现有时当我打乱一个链表时,我会在某处丢失一个节点。我已经用 ubsan 和 asan 做了一些测试。他们都没有表现出来。我曾经遇到过这个函数的问题,后来导致了段错误。段错误是由于未正确重新链接链表引起的。更具体地说,链表中洗牌前的最后一个节点没有正确重新链接。我通过在打乱列表之前将列表设为圆形来解决这个问题。
下面是用于混洗以及交换和重新链接函数的代码:
linked_node* shuffle(linked_node* head) {
int count = 0;
linked_node* count_head = head;
while (count_head != NULL) {
count++;
count_head = count_head->next;
}
#ifdef DEBUG
fprintf(stderr, "count: %i\r\n", count);
#endif
linked_node** array = malloc(count * sizeof(linked_node*));
int i = 0;
linked_node* add_head = head;
for (i = 0; i < count; i++) {
array[i] = add_head;
add_head = add_head->next;
}
//made circluar to prevent segfault with the last node
array[count - 1]->next = head;
srand48(time(NULL));
for (int j = count - 1; j > 0; j--) {
int random = lrand48() % (j+1);
array_swap(&array[j], &array[random]);
}
for (int k = 0; k > count - 1; k++) {
relink(array[k], array[k + 1]);
}
linked_node* new_head = array[0];
//made circular for ease of use later
array[count - 1]->next = new_head;
free(array);
return new_head;
}
static inline void relink(linked_node* prev, linked_node* next) {
if (prev != NULL && next != NULL) {
prev->next = next;
}
}
void array_swap(linked_node** a, linked_node** b) {
linked_node* temp = *a;
*a = *b;
*b = temp;
}
这个 for 循环有错别字
for (int k = 0; k > count - 1; k++) {
^^^^^^^^^^^^^
relink(array[k], array[k + 1]);
}
你的意思好像是
for (int k = 0; k < count - 1; k++) {
^^^^^^^^^^^^^
relink(array[k], array[k + 1]);
}
还有这个说法
//made circluar to prevent segfault with the last node
array[count - 1]->next = head;
是多余的,实际上没有作用。删除它。
此声明
//made circular for ease of use later
array[count - 1]->next = new_head;
可以替代此语句
array[count - 1]->next = NULL;
我一直在做一个项目。项目的一部分需要一个混洗链表。此函数是 fisher-yates 混洗算法的实现。它将链表放入数组中。然后它洗牌。然后重新链接它。
经过一些测试,我发现有时当我打乱一个链表时,我会在某处丢失一个节点。我已经用 ubsan 和 asan 做了一些测试。他们都没有表现出来。我曾经遇到过这个函数的问题,后来导致了段错误。段错误是由于未正确重新链接链表引起的。更具体地说,链表中洗牌前的最后一个节点没有正确重新链接。我通过在打乱列表之前将列表设为圆形来解决这个问题。
下面是用于混洗以及交换和重新链接函数的代码:
linked_node* shuffle(linked_node* head) {
int count = 0;
linked_node* count_head = head;
while (count_head != NULL) {
count++;
count_head = count_head->next;
}
#ifdef DEBUG
fprintf(stderr, "count: %i\r\n", count);
#endif
linked_node** array = malloc(count * sizeof(linked_node*));
int i = 0;
linked_node* add_head = head;
for (i = 0; i < count; i++) {
array[i] = add_head;
add_head = add_head->next;
}
//made circluar to prevent segfault with the last node
array[count - 1]->next = head;
srand48(time(NULL));
for (int j = count - 1; j > 0; j--) {
int random = lrand48() % (j+1);
array_swap(&array[j], &array[random]);
}
for (int k = 0; k > count - 1; k++) {
relink(array[k], array[k + 1]);
}
linked_node* new_head = array[0];
//made circular for ease of use later
array[count - 1]->next = new_head;
free(array);
return new_head;
}
static inline void relink(linked_node* prev, linked_node* next) {
if (prev != NULL && next != NULL) {
prev->next = next;
}
}
void array_swap(linked_node** a, linked_node** b) {
linked_node* temp = *a;
*a = *b;
*b = temp;
}
这个 for 循环有错别字
for (int k = 0; k > count - 1; k++) {
^^^^^^^^^^^^^
relink(array[k], array[k + 1]);
}
你的意思好像是
for (int k = 0; k < count - 1; k++) {
^^^^^^^^^^^^^
relink(array[k], array[k + 1]);
}
还有这个说法
//made circluar to prevent segfault with the last node
array[count - 1]->next = head;
是多余的,实际上没有作用。删除它。
此声明
//made circular for ease of use later
array[count - 1]->next = new_head;
可以替代此语句
array[count - 1]->next = NULL;