How to keep track of an array of structs inside another array of structs

Thread Starter

LewisMF

Joined Nov 15, 2014
100
I have an assignment were I have to write a program in C that ask's a user to input up to 5 vehicles and each vehicle can have up to 8 models associated to it - each model will also contain extra data.

So I thought about creating and array of MAX 5 structs (for the vehicles) and inside each vehicle structure create another array of MAX 8 structs (for each vehicle's model's).

The problem is, I don't know how to keep track of the number of models that have been created inside each vehicle. I can keep track of the number of vehicles by using a counter that increments by 1 each time the 'vehicle input' function is called. But I just can't work out how to keep track of the number of models inserted for each vehicle...

This is a prototype of how I originally declared the data structure:
Code:
/********************************
    VARIABLES AND CONSTANTS
********************************/
const int MAXVEHICLES = 5;
const int MAXMODELS = 8;

/********************************
    DATA STRUCTURES
********************************/
struct modelData{
  
    int hp;
    int weight;
    int maxSpeed;
  
};

struct modelType{  
  
    char modelName[50];
    struct modelData data;
  
};

struct vehicles{  
  
    char vehicleName[50];
    struct modelType model[MAXMODELS];
  
} vehicles[MAXVEHICLES];
What would be the best approach to designing a data structure for a program with this type of functionality?

I'm kind of new to C so please go easy on me :)

Any help would be apreciated!!
 

spinnaker

Joined Oct 29, 2009
7,830
Hint is not that difficult. You already have a vehicleName member and a member to list the various model types. So what do you think you should add to vehicles to keep track of the count of models for that vehicle? If you did it for vehicles then you should be able to do it for models within a vehicle.

Of course the right way to do this is to lave a linked list of models but that might be a bit beyond your level right now. But with a linked list you would not need to worry about keeping track of the count nor be limited on the numbers of models per vehicle.
 

Thread Starter

LewisMF

Joined Nov 15, 2014
100
Hint is not that difficult. You already have a vehicleName member and a member to list the various model types. So what do you think you should add to vehicles to keep track of the count of models for that vehicle? If you did it for vehicles then you should be able to do it for models within a vehicle.

Of course the right way to do this is to lave a linked list of models but that might be a bit beyond your level right now. But with a linked list you would not need to worry about keeping track of the count nor be limited on the numbers of models per vehicle.
I did already think about this solution, the problem is, if I put an element in the vehicle structure called 'modelCounter', where would I initiallise it to 0 for the first time? and also, how would I increment this counter? I could increment it each time the 'model input' function is called inside the 'vehicle input' function but every time the vehicle function finishes executing the model counter will be lost...

Regarding the linked list solution:
Any chance you could explain this a bit more in detail - I'm not an expert, but I am familiar with linked lists :)
 

spinnaker

Joined Oct 29, 2009
7,830
Look up constructors for C++.

To add a new model, your vehicle object would have a member function called something like addModel. If would add a model object to list and increment the counter.

Lookup linked lists. There are thousands of tutorials out there.

Also read this:
https://en.cppreference.com/w/cpp/container/list

There are already list classes that do this for you but it would mean you would need to also understand inheritance which might be beyond you right now.
 

bogosort

Joined Sep 24, 2011
696
The problem is, I don't know how to keep track of the number of models that have been created inside each vehicle. I can keep track of the number of vehicles by using a counter that increments by 1 each time the 'vehicle input' function is called. But I just can't work out how to keep track of the number of models inserted for each vehicle...
One way to do this is to use helper functions. Write your main() as if it knows nothing about the internals of the various structs. Instead, you call simple helper functions that do one and only one thing. Here are some examples that use your data structures:
C:
// returns vehicle index of matching manufacturer, or first empty slot, or -1 if no empty slots
int getVehicleIndex(const char *manufacturer)
{
  int i;

  for ( i = 0; i < MAXVEHICLES; ++i )
  {
    if ( !strcmp(vehicles[i].vehicleName, manufacturer) )
    return i; // found existing manufacturer, return its index
  }

  // didn't find match, so return first empty slot
  for ( i = 0; i < MAXVEHICLES; ++i )
  {
    if ( vehicles[i].vehicleName[0] == '\0' )
      return i;
  }

  // no empty slots, return error
  return -1;
}

// inserts new model into appropriate vehicle slot
int newModel(const char *manufacturer, const char *model, const int maxSpeed)
{
  int i, vidx, model_success = 0;

  vidx = getVehicleIndex( manufacturer );

  if ( vidx == -1 )
  {
    puts( "No empty vehicle slots, bailing out." );
    return 0;
  }

  strcpy( vehicles[vidx].vehicleName, manufacturer );

  for ( i = 0; i < MAXMODELS; ++i )
  {
    if ( vehicles[vidx].model[i].modelName[0] == '\0' )
    {
      strcpy( vehicles[vidx].model[i].modelName, model );
      vehicles[vidx].model[i].data.maxSpeed = maxSpeed;
      model_success = 1;
      break;
    }
  }

  return model_success;
}

// get model data by manufacturer and model name; returns pointer to appropriate struct
struct modelType *findModel(char *manufacturer, char *model)
{
  int i, j;
  struct modelType *m = NULL;

  for ( i = 0; i < MAXVEHICLES; ++i )
  {
    if ( !strcmp(vehicles[i].vehicleName, manufacturer) )
    {
      for ( j = 0; i < MAXMODELS; ++j )
      {
        if ( !strcmp(vehicles[i].model[j].modelName, model) )
        {
          m = &vehicles[i].model[j];
          break;
        }
      }
    }
  }
  return m;
}
Then, in main(), you'd have code like:

C:
int successful_insert = 0;
struct modelType *car = NULL;

successful_insert = newModel( "Toyota", "Corolla", 96 );

if ( !successful_insert )
  puts( "Unable to insert new model." );

car = findModel( "Toyota", "Corolla" );

if ( car )
  printf( "%s max speed: %d\n", car->modelName, car->data.maxSpeed );
else
  puts( "No such model found." );
 

spinnaker

Joined Oct 29, 2009
7,830
It is homework. The TS will learn nothing if you give the answer. Besides, there are a lot better ways to write that code in C++. My advice to the TS, igonre the post above.
 

bogosort

Joined Sep 24, 2011
696
It is homework. The TS will learn nothing if you give the answer. Besides, there are a lot better ways to write that code in C++. My advice to the TS, igonre the post above.
Ahem, the OP asked for C, not C++. And I didn't give a complete solution, just some simple examples of how to use the given data structures. I don't know about you, but I learn best when I can see how to do something.

The choice of arrays of structs is obviously not ideal for this application, but learning how to use them has value. As he gains more experience, he'll see the why, but for now I think how is good enough.
 

spinnaker

Joined Oct 29, 2009
7,830
Sorry my mistake. But you still should not give the answer.

So TS ignore my advice on constructors and the standard list library is the advice that is wrong on at least non applicable. My apologies to both of you.


So to answer your question on how to set the initial value

See this post.

https://stackoverflow.com/questions/13706809/structs-in-c-with-initial-values

But the easiest way would be to just set the value after you declare your variable. A more elegant way might be to use a function.

There are various ways to set your default counter.

You can then have an addModel function as suggested by bogo but do your own work.

There are much better ways to do all of this in C++. As well as the standard list library I recommend above. But sometimes C++ is not available. Some embedded devices for example might not have a C++ compiler or C++ might not be the best solution because of the overhead.
 

Thread Starter

LewisMF

Joined Nov 15, 2014
100
First of all I would like to thank both of you for taking the time to answer my post.

I would like to clarify that, I was only asking for indications, not a full solution, I am aware that I have to find the complete solution by myself if I want to progress and get better at writing code - even know I too learn best when I can see how to do something.

With the advice you guys have given me I think I can finish off my assignment, so thanks once again!

I still would like to learn what the best way would be to approach a problem like this, especially the part that involves storing the input data from user...

At the moment my problem only involves 5 elements with another 8 elements inside each former, but I am fully aware that in the 'real world' people deal with thousands of input data and I would like to know the best way to store all this information (apart from databases, of course...) - so the bottom line is: would structures be the best solution? arrays? linked lists?....?
 

spinnaker

Joined Oct 29, 2009
7,830
To learn the very basics, using a predefined arrays is the way to go. Linked lists are the right way to go put become more complicated, especially in C. Linked lists in C you need to worry about allocating memory as well as deallocating memory. You still do dynamic allocation type programming in C++ but the stucture of C++ makes it a lot easier to deal with. You have things like constructors to allocate the memory and destructors to dellocate the memory. When a variable using your class is created the constructor is called. When the variable goes out of scope or is deallocated the destructor is called. So you don't need to worry about calling the code that does cleanup.

In C you can create helper functions to allocate memory or deallocate memory. They might allocate / deallocate memory plus handle any house keeping tasks like changing counters etc. You just need to remember to call the clean up function when the memory is no longer needed.

Regardless if you do a preallocated array or dynamic array, certainly structures are the way to go in C when you have a an object like a vehicle or model. Classes in C++ are sort of an advanced stucture. They have variables but also can contain functions for that object. Basically everything related to the object is contained withing the class. That is called encapsulation.

If you wanted to play with linked lists I would suggest starting small. First start with dynamic allocation. Look up malloc and free. Write a program to dynamically allocated space for a string (remember to allocate space for the null terminator) .

After you get that learn linked lists. But just deal with one list write now. Learn how to add an object to the list and then iterate through the list,
 

Thread Starter

LewisMF

Joined Nov 15, 2014
100
To learn the very basics, using a predefined arrays is the way to go. Linked lists are the right way to go put become more complicated, especially in C. Linked lists in C you need to worry about allocating memory as well as deallocating memory. You still do dynamic allocation type programming in C++ but the stucture of C++ makes it a lot easier to deal with. You have things like constructors to allocate the memory and destructors to dellocate the memory. When a variable using your class is created the constructor is called. When the variable goes out of scope or is deallocated the destructor is called. So you don't need to worry about calling the code that does cleanup.

In C you can create helper functions to allocate memory or deallocate memory. They might allocate / deallocate memory plus handle any house keeping tasks like changing counters etc. You just need to remember to call the clean up function when the memory is no longer needed.

Regardless if you do a preallocated array or dynamic array, certainly structures are the way to go in C when you have a an object like a vehicle or model. Classes in C++ are sort of an advanced stucture. They have variables but also can contain functions for that object. Basically everything related to the object is contained withing the class. That is called encapsulation.

If you wanted to play with linked lists I would suggest starting small. First start with dynamic allocation. Look up malloc and free. Write a program to dynamically allocated space for a string (remember to allocate space for the null terminator) .

After you get that learn linked lists. But just deal with one list write now. Learn how to add an object to the list and then iterate through the list,
Thank you Spinnaker, this information is very useful.
It sounds like the constructor/destructor is a lot easier to deal with in C++. When trying to do this in C, it gets quite complicated for me using 'New' and 'Delete' and also worrying about memory leaks, especially when I have a lot of variables.

For now what I'm going to do is keep the structure arrays and write functions for manipulating the data stored inside them: searching the array, adding and removing 'vehicles' and 'models', etc.

I'm sure as I gain more experience I will find better and more efficient ways to do this, but for now this will have to do.
 

bogosort

Joined Sep 24, 2011
696
At the moment my problem only involves 5 elements with another 8 elements inside each former, but I am fully aware that in the 'real world' people deal with thousands of input data and I would like to know the best way to store all this information (apart from databases, of course...) - so the bottom line is: would structures be the best solution? arrays? linked lists?....?
It all depends on the application, i.e., what the users of your program expect it to do. Beginners often don't realize that code should be designed before it is written, starting from a high-level perspective: "we need the following functionality". These needs will each have various technical requirements -- some possibly conflicting -- that must be understood, prioritized, and any discrepancies resolved. As this is happening, seasoned developers will be thinking of possible implementation strategies, informed by (and informing) the evolving design spec. Once the game plan is finalized (hah!), then, and only then, do you begin coding.

In short, there is no single best approach. So, what's good about your approach? Using arrays of structures is easy to understand and reason about, easy to implement, and reasonably performant (given the constraints of your assignment). What's bad? Arrays are static structures that don't scale: if your assignment hadn't specified the maximum number of vehicles and models, you'd have to hedge by making huge arrays, each element of which is a nested struct. If you make space for a thousand vehicles but only end up using 15, that's an enormous waste of memory.

What about linked lists? They have somewhat the opposite pro/con profile. Linked lists are dynamic structures: if you don't know how many vehicles and models to expect, a linked list won't waste memory as each link is created/removed on demand. Whether you have 5 or 5,000 vehicles, you'll have exactly the right number of links. This comes at the price of increased code complexity, as you'll need to manage the list as well as the data, but not having a hard-coded maximum number of vehicles is a big win.

As for runtime performance, neither approach is a clear winner. The fastest option would be arrays using global state variables to keep track of array indices, but you really shouldn't do that. Implementation details of the data structure should be invisible to the rest of the program; that way, if you decide to change the implementation, you don't need to change the rest of the program. So, assuming you do the right thing and search the arrays every time you do a model look-up, both the array and linked list methodologies will have essentially the same insert/look-up/delete performance.

Another alternative, with much better (constant) look-up performance, is a hash map on vehicle/model names. Hash maps are in a sense a combination of the array and linked-list methodologies, and are what databases use under the hood. The big downside here is increased code complexity, but they're worth a look. In fact, I recommend you try your hand at writing three different versions of your program, one with each methodology. You'll learn a bunch and, most importantly, will start to develop a feel for how to think in terms of data structures.

One final wrinkle to think about: consider how your array-of-structs (AoS) approach differs from a struct-of-arrays (SoA) approach. That is, instead of

C:
struct modelType {
  int hp;
  int weight;
  int maxSpeed;
  char modelName[50];
} model[MAXMODELS];
we have

C:
struct modelType {
  int hp[MAXMODELS];
  int weight[MAXMODELS];
  int maxSpeed[MAXMODELS];
  char modelName[MAXMODELS][50];
} model;
In both cases, I've flattened your modelType and modelData into one struct (do they really need to be separate?). Knowing that fastest performance comes from reading from CPU cache, that processors are designed to pre-fetch "nearby" data from RAM, and that arrays are stored contiguously, consider how a search on, say, maxSpeed of every model affects the CPU cache in the AoS versus the SoA. Just some food for thought. :)
 
Top