时间戳

首页 > 解决方案 > 重新排列双向链表时偶尔会出现段错误

c - 重新排列双向链表时偶尔会出现段错误

问题描述

如果这对某些人来说似乎微不足道，我很抱歉，但在过去的一天里，我一生都无法弄清楚为什么会发生这种段错误。我有一个双向链表数组，我在其中保持一定的顺序。每次访问或更新列表中的节点时，它都会移动到列表的头部，这发生在数组中的每个链表中。我将提供如何初始化链表数组以及如何排列顺序的代码。任何帮助表示赞赏。如果有帮助，则双向链表数组是为了模拟缓存。我只是希望它是显而易见的，因为我对 malloc 和 C 有点陌生。第一次使用这个网站，所以请让我知道我是否不遵守约定或在我的帖子中做错了什么

我试过打印出链表数组的结构，它似乎在结构上总是合理的。段错误仅在我重新排列节点时发生，特别是当我尝试访问 Node->prev->next 时。不仅如此，当我专门更新尾节点时也会发生这种情况

void maintainLRU(cacheBlock* ptr, int index)//rearranges a list with node passed in to be head
{
    if(ptr->next == NULL)//Tail
    {
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        cache[index].tail = ptr->prev;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
    else
    {
        ptr->prev->next = ptr->next;
        ptr->next = cache[index].head;
        cache[index].head = ptr;
        ptr->prev->next = NULL;
        ptr->prev = NULL;
    }
}

//following code exists within main and is how i initialize the'cache'
numLines = cacheSize/(blockSize*assocType); //determines number of linked lists in my array. 
cache = malloc(sizeof(cacheLine)*numLines);
for(int i = 0; i < numLines; i++)
{
        cacheBlock* temp = malloc(sizeof(cacheBlock));
        temp->valid = 0; //whether the node holds data yet or not
        cache[i].head = temp;
        for(int j = 1; j < assocType; j++)//assoctype is just how many nodes in the list
        {
            temp->next = malloc(sizeof(cacheBlock));
            temp->next->prev = temp;
            temp->next->valid = 0;
            temp = temp->next;
        }
        cache[i].tail = temp;
}//cacheblock is just a node with next, prev, and a valid bit
//cacheLine is just a struct with a pointer to a headnode
//the maintain order function is explicitly called only if the node updated or accessed is not the head.```

标签： csegmentation-faultdoubly-linked-list

解决方案

案例1：ptr在列表的末尾你正确地删除了自己，把自己放在列表的开头，但不要让列表prev的“旧”头指向你；所以你的名单是腐败的。

案例 2：ptr 不在列表末尾，您将 prev 指向下一个，但不要将下一个指向您的 prev，因此您的列表已损坏。

所有情况：您应该提供足够的程序，以便有人可以编译并尝试它。在某种程度上，这会导致你分析你的工作足以注意到明显的错误。微妙的是这个论坛的目的。

3 十年前，紧密优化链表操作非常重要；在那个时候，编译器的书呆子们已经把他们的游戏升级到了足够的程度，你应该能够将maintainLRU写成：

void maintainLRU(cacheBlock* ptr, int index) {
    list_remove(&cache[index], ptr);
    list_insert_before(&cache[index], cache[index].head, ptr);
}

所以你不会成为简单错误的牺牲品。

推荐阅读