c++ - 有谁知道如何在 C++ 中的链表上运行插值搜索？

Question

void List::searchInterpolation(int id){
Node* low = head;
Node* mid;
Node* high = tail;

int lowest = 0;
int middle;
int highest = getLength()-1;
int counter = 0;

while (low->getDato()->getId() <= id && high->getData()->getId() >= id){
    middle = lowest + (id - low->getData()->getId()) * (highest - lowest) /
        (high->getData()->getId() - low->getData()->getId());
    while (middle != counter){
        mid = low->getNext();
        counter++;
        if (mid->getData()->getId() < id){
            low = mid;
        } else if (mid->getData()->getId() > id){
            high = mid;
        } else{
            cout <<"1"<<endl;
        }

        if (low->getData()->getId() == id){
            cout<<"1"<<endl;
        } else{
            cout<<"-1"<<endl;
        }
    }
}

}

嗯，这就是我想出的。我已经测试过了，似乎有一个无限循环。它开始给我 -1 和 1 无处不在。

Answer 1

首先，您必须找到列表的大小。这将需要遍历列表，除非您的比较速度很慢，否则可能会否定插值搜索的任何好处。

现在，使用插值算法找到索引。mid从那low一点前进。现在确定目标值是小于还是大于mid并相应地设置low = mid或high = mid。重复直到找到目标值。您应该能够跟踪剩余范围的大小，而无需再次遍历它。