Thread: Arrays of linked lists

  1. #1
    Registered User
    Join Date
    Apr 2012

    Arrays of linked lists

    First post here.

    The goal of my program is to read a binary file, that consists of 'Vehicle Data'. I read the data in, calculate a centroid (average of 4 points) for x,y,z of a car.

    This data will be part of a structure called Car - Car will contain floats x,y,z and int timeslice, and struct Car *next.
    In final, each Car in the linked list will be the same car but its positions and what time slice it is at.

    Back to the main

    I need to have an array of nodes (node structure - short int id (car id) and struct car *head (pointer to start of linked list)

    #include <stdio.h>
    #include <stdlib.h>
    struct fileHeader
            int netChkSum, STVersion;
            double nUsed;
            int startTime, slicesStored;
            double BackgroundOffset, OtherOffset;
            int histState, x1, x2, y1, y2, metric;
    struct BlockHeaderData
            short int type, size;
    struct Point
            int x[4], y[4], z[4];
    struct Node
        struct Car *head;
        struct Car *tail;
            short int id;
    struct Car
            float x,y,z;
            int timeslice;
            struct Car *next;
    struct VehicleData
            short int id;
            char vType, driverType, payment;
            short int node;
            short int upNode;
            short int speed;
            short int accel10;
            short int width;
            short int length;
            char lane, destLane;
            int flag;
            int color;
            /*struct Point points [4];*/
            int x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4;
    /* Functions */
    void readBlock(FILE *fp, struct Node*, int);
    struct Car readVehicle(struct Point);
    void writeCar(struct Node*, struct Car*, short int);
    void readBlock(FILE *fp, struct Node *cars, int i)
            struct BlockHeaderData block;
            struct VehicleData v;
            struct Point p;
            struct Car c;
            short int id;
            while((feof(fp)) == 0)
                    fread(&block, sizeof(struct BlockHeaderData), 1, fp);
                    /*      print out block data    */
                    /*printf("Type %c\n", block.type);*/
                    if (block.type == 'V')
                            /*      Get Vechicle Coords
                                    send coords to vertex list for car structure    */
                            fread(&id, 2, 1, fp);
                            fseek(fp, 25, SEEK_CUR);
                            fread(&p, 48, 1, fp);
                            c = readVehicle(p);
                            c.timeslice  = i;
                   = NULL;
                            writeCar(cars, &c, id);
                    }else if (block.type == 'X')
                            fseek(fp, (long int) block.size, SEEK_CUR);   /* Skips the current block, if not V or X */
            printf("-------NEW BLOCK!\n");
    /*      Computes the centroid of the car, and gives the cars ID and timeslice   */
    struct Car readVehicle(struct Point p)
            struct Car c;
            int x, y, z, i;
            float x1, y1, z1;
            x = y = z = 0;
            for (i = 0; i < 4; i++)
                    x += p.x[i];
                    y += p.y[i];
                    z += p.z[i];
            x /= 4;
            y /= 4;
            z /= 4;
            /* Move Decimal 2 points        */
            x1 = (float) x / 100;
            y1 = (float) y / 100;
            z1 = (float) z / 100;
            /*printf("\tx = %.2f\ty = %.2f\tz = %.2f\n", x1, y1, z1);*/
            c.x = x1;
            c.y = y1;
            c.z = z1;
            return c;
    void writeCar(struct Node *cars, struct Car *c, short int id)
            /*      Find hash ID, check to see if location empty
                    If empty add node, if not, check to see if same ID's, same ID's add to linked list
                    If not same ID's, find a new hash table value and repeat step 2 */
            struct Car *temp;
            int hashVal = (id*509) % 1000;
            temp =  (struct Car*) malloc(sizeof(struct Car));
            if (temp == NULL)
                    if(cars[hashVal].id == 0)
                            cars[hashVal].id = id;
                            cars[hashVal].head = c;
                            cars[hashVal].tail = c;
                            printf("CAR %d at [%d]\t%d\n", cars[hashVal].id, hashVal, cars[hashVal].head->timeslice);
                            printf("\t%f\t%f\t%f\n", cars[hashVal].head->x, cars[hashVal].head->y, cars[hashVal].head->z);
                    }else if(cars[hashVal].id == id)
                            if(cars[hashVal].head == NULL)
                                    cars[hashVal].head = c;
                            temp = cars[hashVal].tail;
                            temp->next = c;
                            while (temp->next != NULL)
                                    temp = temp->next;
                            temp->next = &c;*/
                            /*printf("CAR %d at [%d]\t%d\n", cars[hashVal].id, hashVal, cars[hashVal].head->timeslice);
                            printf("\t%f\t%f\t%f\n", cars[hashVal].head->x, cars[hashVal].head->y, cars[hashVal].head->z);*/
                    }else if(cars[hashVal].id != id)
                            hashVal = (hashVal + (id * 683)) % 1000;
                            /*printf("New Hash %d\n", hashVal);*/
            /*printf("CAR %d at [%d]\n",, hashVal);
            printf("Added car %d at [%d]\n", cars[hashVal].id, hashVal);
            printf("%d\t[%d]\t",, hashVal);
            printf("New %d\t[%d]\n",, hashVal);*/
    int main()
            struct fileHeader head;
            struct BlockHeaderData block;
            struct Node cars[1000];
            int i;
            int co = 0;
            long int fileOffset, fileLoc;
            FILE *fp;
            /* test vars*/
            struct Car *temp;
            if (!fp)
                    printf("Unable to open file!");
                    return 1;
            fread(&head,sizeof(struct fileHeader),1,fp);
            /* Print out data       */
            printf("netChkSum = %d\n", head.netChkSum);
            printf("STVersion = %d\n", head.STVersion);
            printf("nUsed = %d\n", head.nUsed);
            printf("startTime = %d\n", head.startTime);
            printf("slicesStored = %d\n", head.slicesStored);
            printf("Background Offset = %d\n", head.BackgroundOffset);
            printf("OtherOffset = %d\n", head.OtherOffset);
            printf("HistState = %d\n", head.histState);
            printf("Extents: x1 = %d, y1 = %d, x2 = %d, y2 = %d\n", head.x1, head.y1, head.x2, head.y2);
            printf("metric = %d\n\n\n", head.metric);
            for(i = 0; i < 1000; i++)
                     cars[i].id = 0;
            /*for (i = 0; i <= head.slicesStored; i++)*/ testing, so only running through 4 timeslices instead of 3000++
            for (i = 0; i <= 4; i++)
                    /*      Read Offset, Remember file location using ftell */
                    fread(&fileOffset, 8, 1, fp);
                    fileLoc = ftell(fp);
                    /*      Print        * /
                    printf("Offset to: %d\t", fileOffset);
                    printf("\tfp loc = %d\n", fileLoc);     */
                    /*      Move to offset, read the block header   */
                    fseek(fp, fileOffset, SEEK_SET);
                    readBlock(fp, cars, i);
                    fseek(fp, fileLoc, SEEK_SET);
      This part outputs the correct car ID, but the x,y,z floats are giving me a 0??
            for(i = 0; i < 1000; i++)
                    if (cars[i].id != 0)
                            printf("i:%d\tID:%d\t", i, cars[i].id);
                            printf("%.2f\t%.2f\t%.2f\n", cars[i].tail->y, cars[i].head->y, cars[i].head->z);
    Just wondering if this is a correct way of implementing an array of nodes, and nodes have a pointer to a car structure which then has its own linked list of the cars positions.

    Ill be checking this thread frequently, so if you need clarity let me know.


  2. #2
    Registered User
    Join Date
    Jan 2009
    Are you asking if this:

    struct Node cars[1000];
    is the way to declare an array of struct nodes? It's a way to do it.

  3. #3
    Registered User
    Join Date
    Apr 2012
    Well i did read earlier that the better way was to
    #define size 1000
    struct Node cars[size];
    but when i tried that the define line was giving me errors.

    Overall, im trying to figure out why the last for loop in my code wont output the correct coords for the car structure. Currently it has been outputting 0's or huge numbers? I think there is a problem with my else statement in my writeCars function.

    Or the car structure doesnt even see anything thats why im getting 0 outputs

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginner- fgetc, arrays, and singly linked lists
    By timg123 in forum C Programming
    Replies: 5
    Last Post: 07-15-2010, 09:02 AM
  2. pointers and linked lists in place of arrays
    By kordric in forum C++ Programming
    Replies: 8
    Last Post: 05-14-2008, 10:59 AM
  3. Arrays Vs Linked Lists
    By ianbd in forum C++ Programming
    Replies: 3
    Last Post: 08-31-2005, 08:41 AM
  4. From Python's Linked Lists to Dynamic Arrays
    By hexbox in forum C Programming
    Replies: 3
    Last Post: 01-26-2005, 03:14 PM
  5. linked lists / arrays
    By akira in forum C++ Programming
    Replies: 0
    Last Post: 11-27-2001, 01:01 AM