### 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

 ``123456789101112131415161718192021222324252627282930313233`` ``````template bool LPTable::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.
Topic archived. No new replies allowed.