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];
}
question on a deletion algorithm
Author
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
This should work (not tested, it''s written off the top of my head):
[Resist Windows XP''s Invasive Production Activation Technology!]
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!]
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++.
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!]
). [Resist Windows XP''s Invasive Production Activation Technology!]
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.
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;}
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.
Why don''t you just move the back element into its spot, effectivly deleting it:
Unless your array needs to maintain its order (which it might, I don''t know) this will work fine.
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.
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
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
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
