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

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 . . .

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.

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.

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.