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に設定されているが、リンクされたリストにまだ表示されていることです。2 回目の削除では、最後の要素の値がガベージになるため、比較チェックでその要素が削除されることはありません。誰かが私がここで何をしているのかを明らかにできますか?

4

2 に答える 2

2

使用しているハッシュ テーブルが 7 要素幅 (つまり、インデックスの場合は 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;、違いはありません。次の要素別名を格納するには、配列を更新する必要があります(*iter)->next。

于 2012-10-09T05:46:28.420 に答える