Check if an index in a struct array is empty or not in C

Question

I'm not really a fan of C, but I did homework for this exercise though. So far, what I got is that in C, initializing an array, as far as I know, is not like JavaScript. C has fixed arrays, and not initialized by a particular value. So NULL checking won't work in this case.

I have an array of structures. How would I know if that index in an array is empty or not (filled with a struct or not)?

#define LIST_LENGTH 30

//This is the struct that is inserted in the array
typedef struct node{
    char fName[30];
    char mName[30];
    char lName[30];
    char id[8];
} NODE;

typedef struct {
    int size;   //size is the struct's total capacity (at 30)
    int length; //tracks how many elements are added, but not where
    NODE nodes[LIST_LENGTH]; //This is the array in question
} List;

//somewhere in my code, I have to insert a value to the array at a specific position.
//if that position is occupied, I have to find the nearest empty position
//to the right, and shift the values rightward for that spot to be empty

Also, we are constrained to using arrays for this exercise. If we were granted to use linked-lists, this would be a walk in the park since we already know how to use dynamic lists.

How do I go about it? Or am I looking at the problem at the wrong angle (besides having to use arrays instead of linked-lists)?

How about all indices >= length to be considered empty? Or is the array with "holes" ? — chill
– chill, Commented Dec 11, 2012 at 16:15
As for your codes, your "index of array" is always non-empty... — sleepsort
– sleepsort, Commented Dec 11, 2012 at 16:17
One thing you can do is have an array of pointers to NODE, and initialize it to zero (e.g. with memset). If a position has a null pointer, that means it's empty. — Diego Basch
– Diego Basch, Commented Dec 11, 2012 at 16:19
Yeah, was just going to say maybe the array should be an array of pointers to the struct. And how are you going to "shift" values to the right? The array is fixed size. — Bejmax
– Bejmax, Commented Dec 11, 2012 at 16:25
@BejanShemirani for example, if indexes 1-7 and 9 are filled, and the program inserts a value at 3, the values 4-7 will move to 5-8 accordingly to make way for 3. If there is no more empty spaces to the right, it will look for one on the left. I'll return an error if the array is full. Basically all I needed for now was to find an empty spot. — Joseph
– Joseph, Commented Dec 11, 2012 at 16:28

WildCrustacean · Accepted Answer · 2012-12-11 16:17:11Z

4

One option would be to use some kind of sentinel value in your struct. For example, you could check if the id field is zero length, which would indicate an unoccupied spot in the array.

The downside is that you have to initialize all the elements properly when you create the array. You would also have to reset the sentinel value if you "remove" an element from the array.

As mentioned in one of the other answers, you could also change to have an array of pointers to the structures, in which case you could directly check for NULL.

answered Dec 11, 2012 at 16:17

WildCrustacean

5,9863 gold badges36 silver badges47 bronze badges

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

Comments

Eric Postpischil · Accepted Answer · 2012-12-11 16:17:39Z

Arrays in C do not have positions that are empty. If the array exists, all the elements in it exist.

An element might not be initialized, but there is no general way to determine that, except by tracking it yourself in your program. E.g., as soon as the array is allocated, initialize everything in it. Or maintain a number N indicating that the first N elements of the array have been initialized.

If you want to know whether each individual element has been initialized or not, you must maintain that information yourself, either in a separate array or by adding a flag to the structure, so that each element has its own flag saying whether the rest of the structure in that element has been initialized. You will, of course, need to initialize these flags.

Artur · Accepted Answer · 2012-12-11 16:24:05Z

0

Add 'set/valid' field to your NODE typedef and each time you insert NODE into List just set 'set/valid' to one for example. This way you can always tell if this is valid array element etc.

answered Dec 11, 2012 at 16:24

Artur

7,3572 gold badges28 silver badges40 bronze badges

Comments

LSerni · Accepted Answer · 2012-12-11 16:39:06Z

I have an array of structures. How would I know if that index in an array is empty (not filled with a struct)?

What you can do is either add a flag to the structure, isInitialized, to store whether it has been filled or not

//This is the struct that is inserted in the array
typedef struct node{
    char fName[30];
    char mName[30];
    char lName[30];
    char id[8];
    int  isInitialized;
} NODE;

and initialize all its instances within the array to 0.

Or you can initialize the structure with an illegal or "useless" value (e.g. all strings to length zero, or a special ID).

int isInitialized(NODE *s)
{
    /* Since C strings are zero-terminated, char id[8] is at most one
       seven-char string terminated by a binary zero. It can never be
       normally a sequence of eight 0xFF. */
    return memcmp(s->id, 0xFF, 8);
}

// You still have to manually mark nodes free at the beginning.
void initialize(NODE *s)
{
    memset(s->id, 0xFF, 8);
}

if (isInitialized(&(myList->nodes[15])))
{
    ...
}

One caveat to the above code is that now "id" can not safely be taken and printed: an initialization check must be performed, otherwise printf() could fail to find the terminating zero and proceed onwards, and in the case of the last structure, maybe exceed the boundaries of accessible memory and determine a protection fault crash. One could reason, however, that since it does not make sense to print an uninitialized structure (where the saving binary zero could have been lacking anyway), such a check would have had to be performed regardless.

Or you could keep a counter of how many structures have been used so far (this assumes that you never mark as available a structure "in the middle" of the array).

If you have an array of pointers to structures, then you will be able to store NULL in the pointers to not-yet-initialized structures (i.e., the pointer array is allocated, the structures it points to are not yet necessarily so); but here you preallocate the structures, so you have to do it differently.

Sorry, I meant that you would have initialized the pointers to be NULL. I'll restate.

Collectives™ on Stack Overflow

Check if an index in a struct array is empty or not in C

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related