Skip to main content
gamedev.net
🔒 Locked

question on a deletion algorithm

Started by omegasyphon Nov 14, 2001 at 9:22 PM 12 replies 450+ views
Original Post
omegasyphon
omegasyphon
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];
          
  }
Oluseyi
Oluseyi 

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++.
omegasyphon
omegasyphon
but....is their anything wrong with mine?
Null and Void
Null and Void
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!]
invective
invective
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;
}


Ranok
Ranok
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.

---Ranok---
Gladiator
Gladiator
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
Gladiator
Gladiator
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
omegasyphon
omegasyphon
ok heres my some what different algorithm that i got working
cause i couldnt get the other working

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

void delete(int item)
{
 int loc=0, temp=0;
    for (int x=0;x<mynum;x++)
    {
        if (ary[x]==item)
          ary[x]=0;
    }

    while (loc < mynum-1)
    {
        if (ary[loc]==0)
        {
          temp = ary[loc];
          ary[loc]=ary[loc+1];
          ary[loc+1]=temp;
        }
        loc++;
    }
    mynum--;
}


Edited by - omegasyphon on November 14, 2001 12:31:09 AM

Edited by - omegasyphon on November 14, 2001 12:31:38 AM
omegasyphon
omegasyphon
btw whats a good java programming website, non game programming
invective
invective
java.sun.com

I still like the STL way better...

  
vector <int> ary;
ary.reserve (10);
for (int i =0; i<10; i++)
   ary.push_back (1);
...
//No swapping (ineffiecent for large classes or large vectors)

void template class <T> remove_element (vector <T> &ary, T key)
{

 for (vector<T>::iterator i; i< ary.end (); i++)
   if (ary [i] == key)
      ary.erase (i);
}
//swapping

void template class <T> remove_element (vector <T> &ary, T key)
{
 vector<T>::iterator end = ary.end ();
 for (vector<T>::iterator i; i< end; i++)
   if (ary [i] == key)
   {
      swap (ary[i], ary[end-1]) //end is one past the actual last element

      ary.erase (end-1);
   }
}
Oluseyi
Oluseyi
invective's STL code is just a bit inaccurate:

    
// the 'seek' loop:

vector<int>::iterator itr = ary.begin(), stop = ary.end();
while(itr != stop)
{
  if(*itr == key)
    itr = ary.erase(itr);
  else ++itr;
}


Iterators are "glorified" pointers, so dereferencing them yields the desired value. erase() also takes an iterator (or two iterators) as parameters. The call to swap() should also be replaced with iter_swap() take iterators as arguments:

  
iter_swap(itr, (stop-1));
ary.erase(stop-1);


[Edit:] consistent names.

Edited by - Oluseyi on November 15, 2001 2:26:32 AM

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.