CODEWITHSUNDEEP
c
Joseph
Joseph

Reputation: 119837

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

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

Upvotes: 1

Views: 9360

Answers (4)

LSerni
LSerni

Reputation: 57388

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.

Upvotes: 0

Artur
Artur

Reputation: 7257

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.

Upvotes: 0

Eric Postpischil
Eric Postpischil

Reputation: 222352

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.

Upvotes: 2

WildCrustacean
WildCrustacean

Reputation: 5966

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.

Upvotes: 4

Related Questions