Archived

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

omegasyphon

question on a deletion algorithm

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

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

Share this post


Link to post
Share on other sites
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);
}
}

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites