Help - Linked Lists/Structures/Memory Allocation

This is a discussion on Help - Linked Lists/Structures/Memory Allocation within the C Programming forums, part of the General Programming Boards category; Hello I'm having trouble getting my program to do what it needs because i don't completely understand how linked lists ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Location
    UC Davis, California
    Posts
    4

    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

  2. #2
    Resu Deretsiger Nightowl's Avatar
    Join Date
    Nov 2008
    Location
    /dev/null
    Posts
    186
    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 . . .
    Do as I say, not as I do . . .

    Experimentation is the essence of programming. Just remember to make a backup first.

    "I'm a firm believer that <SomeGod> gave us two ears and one mouth for a reason - we are supposed to listen, twice as much as we talk." - LEAF

    Questions posted by these guidelines are more likely to be answered.

    Debian GNU/Linux user, with the awesome window manager, the git version control system, and the cmake buildsystem generator.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Location
    UC Davis, California
    Posts
    4
    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.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by MetallicaX View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List and Dynamic Memory Allocation
    By girly_engineer in forum C Programming
    Replies: 4
    Last Post: 04-18-2009, 11:50 AM
  2. Help! -Linked Lists, Memory Allocation, Time Steps, Debugg
    By MetallicaX in forum C Programming
    Replies: 2
    Last Post: 03-14-2009, 08:50 PM
  3. Memory allocation in linked lists
    By Panserbjorn in forum C Programming
    Replies: 6
    Last Post: 10-26-2007, 11:02 PM
  4. Memory Allocation for self made Linked List
    By jsimpson in forum C Programming
    Replies: 5
    Last Post: 03-10-2006, 01:14 AM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21