#### Archived

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

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

## 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 on other sites
This should work (not tested, it''s written off the top of my head):
  void remove(int *array, unsigned int item, unsigned int max) { --max; while(item < max) { array[item] = array[item+1]; ++item; }}

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

##### 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 on other sites
but....is their anything wrong with mine?

##### 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 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 on other sites
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 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 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 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

1. 1
Rutin
21
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 13
• 38
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631715
• Total Posts
3001868
×