1

我正在将哈希表编写为链表数组。目前我正在尝试创建一个简单的哈希表，其中键是数组的索引，值是用于实现链接的单链表。

这是我删除节点的代码：

基本结构：

struct Node
{
 int value;
 int page;   
 struct Node *next; 
};

int searchAndDelete(int frame,int page,int delete)
{
   struct Node** iter;
   iter=&hashtable[(page-1)%7];
   struct Node** prev=iter;

   for(;*iter;iter=&(*iter)->next)
   {
      if(page==((*iter)->page))
      {
         if(frame==((*iter)->value))
         {
            if(delete)
            {
               (*prev)->next=(*iter)->next;
               free(*iter);
            }
            return 1;
         }
      }
      prev=iter;
   }
   return 0;
}

插入请看这里，AddNode

当我删除一个节点时，它的值变为 0。当我搜索节点时，它返回的节点不是预设的，也就是 0 作为函数的输出。

我的代码中是否有任何我没有想到的错误？我是否留下任何内存泄漏或任何其他问题？

编辑 将这段代码添加到删除函数中：

  int searchAndDelete(int frame,int page,int delete)
  {
   struct Node** iter;
   iter=&hashtable[(page-1)%7];
   struct Node** prev=iter;
   struct Node** curr=iter;

   for(;*curr;curr=&(*curr)->next)
   {

     if(page==((*curr)->page))
     {
        if(frame==((*curr)->value))
        {
            if(delete)
            {
                if(curr==iter)
                {

                    iter=(*curr)->next;
                    free(*curr);

                }
                else
                {

                (*prev)->next=(*curr)->next;
                free(*curr);
                }

            }

            return 1;
        }

    }
    prev=curr;

  }
    return 0;



}

我看到的问题是，当我第一次删除时，元素没有被释放，它的值设置为 0，但它仍然在链表中显示。在第二次删除中，最后一个元素的值变成了一些垃圾，因此在我的比较检查中永远不会删除该元素。有人可以阐明我可能在这里做什么吗？

4

2 回答 2

2

如果您使用的哈希表是七个元素宽（即索引为 0..6），并且从您的 AddNode 代码看来是这样，那么您使用的算术对于初始迭代器查找是可疑的。

iter=&hashtable[page-1%7];

应该是：

struct Node** iter = hashtable + (page % 7);

这将为您提供哈希表中页面位置模数 7 处元素的地址，即 [0..6]。

此外，您从哈希表头节点中删除不考虑清除表元素本身。您可能需要 (a) 将其设置为 null，或 (b) 在下一个 ptr 中链接。也这样做。你有能力因为哈希表和初始节点指针都可用。

编辑：OP 要求提供样品。这只是如何做到这一点的简要说明。我敢肯定有很多更好的方法，甚至可以编译。这假设页面和框架都必须完全匹配才能使节点被视为可删除。

void searchAndDelete(int frame, int page, int del)
{
    struct Node** head = hashtable + (page % hashtable_size);
    struct Node* curr = *head;
    struct Node* prev = NULL;

    while (curr)
    {
        // if they match, setup for delete.
        if ((curr->page == page) && (curr->value == frame) && del)
        {
            // so long as the header pointer is the active node prev
            //  will be NULL. move head along if this is the case
            if (prev == NULL)
                *head = curr->next;

            // otherwise, the previous pointer needs it next set to
            //  reference the next of our vicitm node (curr)
            else
                prev->next = curr->next;

            // victim is safe to delete now.
            free(curr);

            // set to the new head node if we just deleted the
            //  old one, otherwise the one following prev.
            curr = (prev == NULL) ? *head : prev->next;
        }
        else
        {   // no match. remember prev from here on out.
            prev = curr;
            curr = curr->next;
        }
    }
}

嗯，够近了=P

于 2012-10-09T05:50:03.847 回答
1

我看到几个问题：

  1. mod 运算符%需要括号。所以iter=&hashtable[page-1%7];改为iter=&hashtable[(page-1)%7];

  2. 处理您将删除链表中的第一个元素的情况。在这种情况下prev将相同，iter所以(*prev)->next=(*iter)->next;不会有任何不同。您需要更新数组以存储下一个元素 aka (*iter)->next。

于 2012-10-09T05:46:28.420 回答