Linked Lists / Structures / Memory Allocation

MetallicaX · #1 17-Mar-2009, 21:52

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:

CPP / C++ / C 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

Kimmo · #2 19-Mar-2009, 00:06

I'm not a C person and I cannot make this program for you (not saying you'd want that...), but since Dave and Bob are on holiday, let me say something in general.

First of all, it's not a good idea to write a thousand lines before trying to compile. You didn't try to compile it even once, did you? I tried and I got

Code:

main.c: In function `main':
main.c:21: error: `cptr' undeclared (first use in this function)
main.c:21: error: (Each undeclared identifier is reported only once
main.c:21: error: for each function it appears in.)
main.c:21: error: syntax error before "car_t"
main.c:22: error: syntax error before '{' token
main.c: In function `location':
main.c:39: error: parameter name omitted
main.c:41: error: invalid initializer
main.c:45: error: `i' undeclared (first use in this function)
main.c:47: warning: comparison between pointer and integer
main.c:48: error: `car' undeclared (first use in this function)
main.c:48: error: `X' undeclared (first use in this function)
main.c:49: warning: comparison between pointer and integer
main.c:51: warning: comparison between pointer and integer
main.c:52: error: `Y' undeclared (first use in this function)
main.c:53: warning: comparison between pointer and integer
main.c:56: warning: return makes integer from pointer without a cast
main.c:56: warning: function returns address of local variable
main.c: In function `check':
main.c:60: error: parameter name omitted
main.c:66: error: `i' undeclared (first use in this function)
main.c:74: error: `car' undeclared (first use in this function)
main.c:75: error: syntax error before "car"
main.c:76: error: syntax error before '}' token
main.c:83:2: warning: no newline at end of file

Now many of those are warning, some are even pretty harmless (like the last warning). But do you really want to return an address to a local variable? Or compare an int to a pointer?

Based on this compiler output I'd say getting linked lists to work are your least worries.

CPP / C++ / C Code:

//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;

What do you think car_s is here? Where in your program is the definition for car_s?

CPP / C++ / C Code:

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};

This puzzles me. I think this is what you think you're doing:

Randomize X, Y, Weight. Create an array of 500 cars (why, since you were supposed to make linked list?) and assign X, Y and Weight to the first car in the list. Then create a pointer to point at the just created array of cars and assign to it the address of the first car in the array. Then assign to the first car in the list values of X, Y and Weight (Why do this twice?).

This is what I think you're doing:

Randomize X, Y and Weight. Create an array of 500 floats and assign X, Y and Weight to the first three elements in the array, respectively. Then the next line already generates an error, since there's not a type 'car' in your program. car_t is a struct you have just defined. Later in your loop you use

CPP / C++ / C Code:

cptr->x=rand() % 500;

to access the members of that struct. Why did you think writing something like car_t[i] would make sense?

CPP / C++ / C Code:

//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;

Cannot say about this part, since I don't know much about malloc. But your loop would probably generate an access violation error, since you're trying to write to the 501th element in the array, which doesn't exist. Use

CPP / C++ / C Code:

 for(i=0; i<500; i++)

instead.

I'm also not sure about the way you randomize the locations of the cars. While it's unlikely, given 250000 possibilities, it's still possible that two cars would get the same location. Your assignment didn't mention it, but I'm assuming you cannot have two cars in the same location?

You could create an array of 250000 bools or bits and set a bool or a bit each time you create a new location. Then, when you generate another location, you could easily check if that location is already in use (bool is true or a bit is set). Maybe...

CPP / C++ / C Code:

 return;
}

Since main is supposed to return an int, you should probably return an int. Generally 0 for success and anything else for different failures.

CPP / C++ / C Code:

//Function for the location of the cars. 
int location(int)
  {

Suppose you passed an argument to this function. How would you access it? You can omit the name in the declarations, since it's not necessary, but in the definitions.

CPP / C++ / C Code:

     int m[5] = rand() % 4;
     int g = 5;

I think I got "invalid initializer" for the first line here. What exactly are you trying to do? m here is an array of 5 ints. If you're somehow trying to tell the compiler that m can only hold values up to 4, it won't do. You probably want

CPP / C++ / C Code:

int m = rand() % 4;

or something.

CPP / C++ / C Code:

//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;
}

The loop has the same problem as the previous for loop. Also, what exactly is supposed to be going on in this loop? Why is g 5? What are (X+1) etc? You already randomize the locations once in your main(), so what is this function for? What does the return value mean? Also, the variables X, Y and car are local to main(), you cannot see them in this function.

CPP / C++ / C Code:

//Function to check for collisions

To check for collisions, you probably need the locations of cars? Where in your function do you think that happens?

As for the actual check if two cars are on the same location, I have no idea what would the best way to go about it. A primitive way would be to check the locations of all cars against the locations of all the other cars.

A little more sophisticated way would be to use your (would-be) array of bools or bits to check if there actually IS a car in the same location (you would of course update that array each time the cars move) and if there is, THEN go through all the cars and find the one(s) in the same location.

Perhaps again a little more sophisticated way would be to turn your (would-be) array of bools or bits into an array of pointers to cars. So, the pointers would point to the car currently at a given location. Then (I think) you could easily check which of the cars has more mass and delete the approriate one and assign the pointer to point at the new car.

(In fact, at the moment it seems to me that the last way would make using the linked list obsolete, since you would already have pointers keeping track of all the cars.)

The last way, of course, would only work if your cars move one by one. Probably not overly complicated to make it work even if they all move at once, but...

I think a bottom line is justified:
Get the basics of C handled first.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
Singly linked to doubly linked	wbaker01	C++ Forum	2	22-Jan-2007 13:23
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
Memory de-allocation during debugging	gaoanyu	C Programming Language	12	19-Dec-2005 04:50
Linked List	silicon	C++ Forum	2	22-Jul-2004 03:29

Linked Lists / Structures / Memory Allocation

Re: Linked Lists / Structures / Memory Allocation