Beginner Removing first element from an array of structs (C)

Question

I have an array of structs (actually it's a heap array sorted by priority).

 typedef struct {
    char name[MAX_CHARACTERS+1];
    int priority;
} person;
person p[MAX_HEAPSIZE+1];

and want to remove the first element in the array. I'm not sure how or what command to use.

So far, I've been doing

void remove(){
    swap(0, heapsize-1);
    strcpy(p[heapsize-1].name, p[MAX_HEAP_SIZE+1].name);
    p[heapsize-1].priority = p[MAX_HEAP_SIZE+1].priority;
}

this swaps the first and last non-empty element in the array. Then it tries to copy the data at an empty element to the last non-empty element (element i want to remove) in the array.

but I think it only copies the memory positions. Is there something simple where I can do

p[0] = NULL?

Yes, you can simply do p[0] = NULL if empty elements are allowed in your array. Please clarify what you mean by "remove." As it stands now, your remove() function is indexing beyond the bounds of the array and copying garbage. — Carey Gregory
– Carey Gregory, Commented Aug 14, 2011 at 21:42
When I do p[0] = NULL; I get an error: incompatible types when assigning to type 'person' from type 'void *'. By remove, I basically want to get rid of the first element of my array by swapping it with the last. — coril
– coril, Commented Aug 14, 2011 at 21:47
If you're compiling with a C99 compiler, you can do p[0] = (person){"anonymous", 42}; or, maybe more to your liking: p[0] = (person){"", 0}; otherwise you need to set each structure member separately: p[0].name[0] = 0; p[0].priority = 0; — pmg
– pmg, Commented Aug 14, 2011 at 21:47

Antti · Accepted Answer · 2011-08-14 22:04:52Z

3

An array is a continuous block of memory. So if you want to remove the first element, you have to move all the following elements towards the beginning by one element:

void remove(void)
{
    memmove(&p[0], &p[1], (MAX_HEAPSIZE - 1) * sizeof(person));
}

This is pretty inefficient. Popping the first element is a common operation with a heap, so you'd usually do it the other way around - remove the last element of an array - which is very fast, because the other elements of the array aren't affected.

void remove(void)
{
    heapsize--;
}

heapsize can then be used as the index of the top element of the heap (assuming you preserve the heap property, of course).

If you want to overwrite the first element of the array with the last one and zero out the memory of the last element, which is not used anymore, you can use memcpy and memset:

void remove(void)
{
    memcpy(&p[0], &p[heapsize - 1], sizeof(person));
    memset(&p[heapsize - 1], 0x00, sizeof(person));
}

Zeroing out the memory of the last element is not strictly necessary, though, because you shouldn't be accessing it in the first place. Instead of overwriting the first element with the last using memcpy, it can also be done with strcpy and assignment of the priority (like in your remove); using memcpy is simply easier.

edited Aug 14, 2011 at 22:04

answered Aug 14, 2011 at 21:54

Antti

12.6k2 gold badges29 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

coril Over a year ago

my instructor mentioned that which is why I'm swapping the first element with the last non-empty element and then fixing the heap accordingly. But before fixing, I don't know how to 'clear' last element position so that it is 'empty'.

UncleO · Accepted Answer · 2011-08-15 00:50:34Z

It sounds like you are trying to implement a heap sort. You don't actually need to "remove" the first element of the heap, or even the last one.

Instead, the algorithm is to copy the values from the the first element (the element with the highest priority) for output, then to copy the node from the "end" of the array to the first position in preparation to bubble it down into the correct position. The "end" of the array is indicated by the current heap_size.

To "remove" the last item of the array, just reduce the heap_size by 1.

I vaguely recall that the bubbling down is accomplished by checking the priorities of the children on the moving item, and then swapping it with the one with the highest priority. Repeat this on the moved item until the item is of equal or higher priority to its children.

The trick to find the children of an item is easy: they are the nodes at 2*i and 2*i+1, where the array starts at 1 instead of 0. (Would it be 2*(i+1)-1 and 2*(1+1) for 0-based arrays? Check my math, please. Or just waste one element of the array to keep the math simple.)

Collectives™ on Stack Overflow

Beginner Removing first element from an array of structs (C)

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related