Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

omegasyphon

question on a deletion algorithm

This topic is 6088 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok i have this algorithm but i have 2 variations that confuse me a bit. im trying to delete a given item in an array but not sure if my algorithm is correct if i have some array like so
  
ary[10] = {7,6,8,12,10,1,5,3,4};

void remove(int item)
{
   int loc=0;
   while (loc>=0 && item< ary[loc])
      {
          ary[loc-1] = ary[loc];
          loc++;
      }
      ary[loc+1] = ary[loc];
          
  }   
  

Share this post


Link to post
Share on other sites
Advertisement

void remove(int item)
{
int index = 0;
// assume length is initialized to array length
while(array[index] != item && item < length)
++index;
// at this point we''ve found the item
if(item >= length)
// item not found
return;
while(index < length)
{
// make sure we don''t exceed the array bounds
array[index] = (length - index > 1) ? array[index + 1] : 0;
++index;
}
}

This code handles duplications by removing the first occurrence. It''s fairly robust, but you could just use STL vector if you''re using C++.

Share this post


Link to post
Share on other sites
Yes, there is at least one thing wrong with yours. Notice how you use "loc-1"? Well, that''ll end up being -1 the first time, possibly causing a segfault. Secondly, the "loc>=0" is redundant, your loop will never fail that test. I''m not sure exactly what you were trying to do, so I won''t make any more comments (I''m not sure if my remove thingy does the same thing as what you want, I just took a guess ).

[Resist Windows XP''s Invasive Production Activation Technology!]

Share this post


Link to post
Share on other sites
If the order of elements does not matter, its usually easiest to swap the element to delete with the last element and delete the last element in the list, instead of deleting in the middle and having to copy everything over the "hole" in the middle. Also, your algorithm can''t really "delete" anything, since you are not deallocating memory or calling any destructors. Technically you should also be tracking the size of the array, unless you use a special character to signify the end of the list. Its probably best to use the STL vector class if you need random access instead of an array, or the list class if you need a sorted sequence, since STl containers can find items, delete them, and maintain the length of the list for you.

Here is how you can do it the array way. I use zero to signify end of array.

  
ary[10] = {7,6,8,12,10,1,5,3,4};

void remove(int item){

int end = 0;
int position = -1; //Negative one signifies item not found

while (ary [ end] != 0 ) // Loop until end of array

{
if ( ary[ end ] == item ) //The item has been found

position = end; //Flag the location of the item to "delete"

end++;
}
if (position == -1)
return; // the item was not found, just exit

//Swap back item

ary [position] = ary [end];
//"delete" the end

ary [end] = 0;
}


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hey invective your while loop will never end. ary[end] will never equal 0 unless 0 is a array value or you get lucky when the loop acceses a memory poisition outside the array when you go over the bound.

Share this post


Link to post
Share on other sites
Why don''t you just move the back element into its spot, effectivly deleting it:


int arySize = 10;
ary[] = {...}
void remove( int item ) {
ary[item] = ary[--arySize];
}


Unless your array needs to maintain its order (which it might, I don''t know) this will work fine.

Share this post


Link to post
Share on other sites
invective got it right (almost)...

just change

while (ary [ end] != 0 )

to

while (end < 10)...

if you pass a size parameter to the function then you can use

while (end < size)....

thats for smaller arrays... if a deleted item is denoted by 0 then you can do this..

while (end.....

hope this helps

Share this post


Link to post
Share on other sites
one more thing... there are two ways to delete an item... one is to delete by index, and the other is to delete by value... what ronak described is delete by index... which is the easiest of the two... the other one is delete by value where you search for an array entry which has the value of "item" and then delete that..

btw... usign invective''s algorithm, if there are 2 items with the same value as "item" in the array the last one is gonna get deleted but not the first one...just something to think about

lata

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!