# Help - Linked Lists/Structures/Memory Allocation

Printable View

• 03-17-2009
MetallicaX
Help - Linked Lists/Structures/Memory Allocation
Hello
I'm having trouble getting my program to do what it needs because i don't completely understand how linked lists work. If i could get a some help i'd greatly appreciate it. I mainly need help with making it go through the 1,000 time steps, remove cars that have crashed, and debugging a few problems.

Here's the question:

Consider a square domain partitioned into 250,000 equally spaced grid cells (500 by 500). We will randomly distribute some cars into this domain such that no more than 1 car is located in any grid cell initially. Each car has a random mass between 1-50. At each time step of the simulation, each car randomly moves one grid cell in the x or y direction (4 possible directions). If a car touches the edges of the domain then it “rebounds” 180o towards the interior. If two cars land on the same grid cell, then they have had an accident, and the smaller car is removed from the simulation.

Write a program to simulate this system. Use structures to represent the cars in the simulation. Make your program efficient by only allocating memory for active cars, and free memory for cars that are no longer active. Hint: use a linked list to represent the cars.

Show the initial distribution of cars and the final distribution of surviving cars (the
number of cars at each possible mass) after 1000 time steps if the simulation starts with 500 and 2000 cars (2 cases). Make a histogram of your results using excel. The bins on the x-axis of the histogram will be the mass of each car. The value on the y-axis will be the number of cars in each bin.

Here's my code:

Code:

```//prototype definitions #include<stdio.h>  #include<stdlib.h> //structure for x,y,and weight of an array of cars  typedef struct{   float x;   float y;   float weight;   struct car_s *next;   } car_t; int main () { //local variable definitions to randomize location and weight   int i = 0;   int X = rand() % 500;   int Y = rand() % 500;   int Weight = rand() % 50;   float car[500]={X, Y, Weight};   car *cptr = car_t[i];   car[i]={X,Y,Weight};   //loop through the linked list among the 500 possible cars     for(i=0; i<=500; i++)       {         cptr-> nextptr=malloc(sizeof(struct car_t));         cptr->x=rand() % 500;         cptr->y=rand() % 500;         cptr->weight = rand() % 50;     // printf("car %d has position %d, %d and weight %d\n", i, car_t.x, car_t.y, car_t.weight);       }     cptr->nextptr=NULL;  return; } //Function for the location of the cars. int location(int)   {     int m[5] = rand() % 4;     int g = 5;    //loop through the different randimizations   for (i=0; i<=g; i++)     {       if(m==1)         car[i].x=rand() % (X+1);       if(m==2)         car[i].x=rand() % (X-1);       if(m==3)         car[i].y=rand() % (Y+1);       if(m==4)         car[i].y=rand() % (Y-1);       }  return m; } //Function to check for collisions int check(int)  {     int ix=0;     int iy=0; //loop checking for collisions   for(i=0; i<=500; i++)     {       for(ix=0; ix<=500; ix++)       {         for(iy=0; iy<=500; iy++)           {             if(iy=ix)                       car[i].x= 0             car[i].y= 0           }         }     }    return 0;   }```

-Any help or alterations you see neccessary would be of great appreciation
Thanks
• 03-17-2009
Nightowl
First off!

Why are you assigning three floats to car, like so?
Code:

`float car[500]={X, Y, Weight};`
Makes no sense . . . at least to me ;)

Beyond that, what is the problem? What is not working?

Give us someplace to start, and we can go from there . . .
• 03-17-2009
Adak
If the cars always move one grid cell (in whichever direction), then shouldn't the data type for x and y be int's, instead of floats?

Similarly, with rand() and mod being used to get the randomized weight, shouldn't that also be an integer?

In this checking for collision function:
Code:

```int check(int)  {     int ix=0;     int iy=0; //loop checking for collisions   for(i=0; i<=500; i++)     {       for(ix=0; ix<=500; ix++)       {         for(iy=0; iy<=500; iy++)           {             if(iy=ix)                       car[i].x= 0             car[i].y= 0           }         }     }    return 0;   } That looks like in psuedo code for  every car   for every x coordinate on the grid     for every y coordinate on the grid       //check it for cars at that location Which I believe is not right. What you want is for every car   check their x coordinate with every other car   if(they have the same x value)       see if they have the same y value           if so, you have an accident```
What method were you looking to use to handle the linked list nodes that need to be removed and free'd?

I'll let others comment on the linked list stuff - I'm rusty as all get out on 'em, and would sharply steer you right into the ditch, no doubt.

It's a fine problem however.
• 03-17-2009
MetallicaX
Well... That portion was when i was just messing around with it trying to get it to work and i accidently left it in when i posted this...

I guess to start off... i need to write code that will make a domain partioned into 250,000 equally spaced grid cells (500 by 500). and distribute 1,000 cars randomly giving an X value and a Y value along with giving each car a random mass between 1-50 using linked lists/structures.

Code:

```#include<stdio.h>  #include<stdlib.h> //structure for x,y,and weight of an array of cars  typedef struct{   float x;   float y;   float weight;   struct car_s *next;   } car_t; int main () { //local variable definitions to randomize location and weight   int i = 0;   int X = rand() % 500;   int Y = rand() % 500;   int Weight = rand() % 50;   float car[500]={X, Y, Weight};   car *cptr = car_t[i];   car[i]={X,Y,Weight};   //loop through the linked list among the 500 possible cars     for(i=0; i<=500; i++)       {         cptr-> nextptr=malloc(sizeof(struct car_t));         cptr->x=rand() % 500;         cptr->y=rand() % 500;         cptr->weight = rand() % 50;         printf("car %d has position %d, %d and weight %d\n", i, car_t.x, car_t.y, car_t.weight);       }     cptr->nextptr=NULL;  return; }```
This is what i need to start with and get compiled before anything else. But i can't get it working. I guess the idea of linked lists just confuses me and no matter what code or tutorials i follow i can't figure out how to apply it to this program. Yeah, so i guess firstly i need help with this code here.
• 03-18-2009
brewbuck
Quote:

Originally Posted by MetallicaX
I guess to start off... i need to write code that will make a domain partioned into 250,000 equally spaced grid cells (500 by 500). and distribute 1,000 cars randomly giving an X value and a Y value along with giving each car a random mass between 1-50 using linked lists/structures.

You don't need the create the domain explicitly. The idea is to save memory by only keeping a record for each car. The alternative would be a 2D array of size 500 by 500, with each cell simply recording whether a car was present, and the mass of the car.

The tradeoff is that collision detection is really easy if you store the grid, but you use lots of RAM. If you keep the cars in a linked list, you use much less RAM, but collision detection is inefficient because you need to compare each car to every other car to see if they have collided.