Help understanding algorithm implementation

I'm writing an Linear probing remove function according to notes but my implementation seems to be off because its returning false for valid searches. I was wondering if anyone could see if my implementation doesn't reflect what the notes describe.

https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/tables/linear_probing.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <class TYPE>
bool LPTable<TYPE>::remove(const string& key){
    int keyIndex = search(key); // retrieves the location of the key in the table
    if (keyIndex == -1 || records_[keyIndex] == nullptr){ //making sure the record exists in table
        return false;
    }
    else{
        delete records_[keyIndex];
        records_[keyIndex] = nullptr;
        size_--;
        int prob = keyIndex + 1; //setting position to 1 index after the deleted record
        int deleteFlag = keyIndex; //marking the index of the deleted record
        while (records_[prob] != nullptr){ //looping through until the end of the cluster
            int key = hashedIndex(records_[prob]->key_); // getting expected hash index of record's key
            if (deleteFlag >= key && deleteFlag <= prob){ // comparing the deleted record index to the expected hash index of the record and the records actual index (making sure its within range)
                records_[deleteFlag] = new Record(records_[prob]->key_, records_[prob]->data_); // inserting record into empty spot
                delete records_[prob]; //deleting record making it the new empty spot
                records_[prob] = nullptr;
                deleteFlag = prob; //marking the location
                if (prob < max_){ //if at the end of expected records go to beginning of array
                    prob = 0;
                }
                else{
                    prob++;
                }
            }
            else{
                prob++;
            }
        }
        return true;
    }
}
Last edited on
well... if it returns false, the only way I see that is the top 4 lines.
If the top 4 lines are doing something wrong, the problem is in search() or your if statement is not correct (maybe search() returns some other value??).

Assuming the if statement is correct as it looks pretty reasonable (the -1 seems weird to me, IMHO it should be null or valid, but ok whatever) then your search routine must be the problem. Which we can't see here.

Sorry didn't update thread, the error actually lied in the way I did my wrap around to the front of the array. changing the check to prob != max_ did the trick.
Registered users can post here. Sign in or register to post.