Link to home
Start Free TrialLog in
Avatar of The_Kingpin08
The_Kingpin08

asked on

Best way of creating 3 linked lists

Hi all, I'm currently working on a project about linked list. I need to create 3 linked list based on the information inside a file. I already started but really doubt my method is the easiest and best way. If anyone could help me as to how should I made it, it would really help me !

As I said, I need to use the information of a file. Each information is written on a separate line, and we don't know the number of line in the file. Now here's how is separated the information in the file: On the first line, there's the name of a model with his polygon ID number. On x lines following the model's line are the polygon's points. Each points contains his 3 coordinates (x,y,z) on the same line. Here are some line of the file:

chair 1
1.24  -1.52  3.78
2.23   1.25  2.47
4.44   2.58  0.97
table 3
5.32   1.52   8.12
0.23  -1.25  -2.47
chair 2
2.32  6.25  1.65
1.25  5.82  3.24
etc.

Now I just learned linked lists contents and still taking all the info I can find. Anyway, I thought I could use a function that would read the first line and add the model's name and polygon's ID in their respected lists. Then, it would call another function to read the following lines (until we reach another model) and also add them to their respected lists. Where I doubt is if it's going to be effective and how I'm going to read the lines and indentify them.  Here's the declaration of my items.

typedef struct point* PtrPoint;
typedef struct point
{
      float x;
      float y;
      float z;             /* cooordinates of my point */
      PtrPoint next;    /* points on the next point */
}Point;

typedef struct polygon* PtrPolygon;
typedef struct polygon
{
      int numPolygon;         /* ID number of the polygon */
      int nbPoints;              /* number of points of the polygon */
      PtrPoint headPoint;    /* head of the points' list */
      PtrPolygon next;        /* points on the next polygon */
}Polygon;

typedef struct model* PtrModel;
typedef struct model
{
      char nomModel[MAX_CAR_MODEL];      /* name of the model */
      int nbPolygons;                               /* number of polygons */
      PtrPolygon headPolygon;                     /* head of the polygon's list for the model */
      PtrPolygon next;                        /* points the next model */
}Model;

PtrModel headModele;      /* head of the models' list */


Hope I gave enough informations to get some possible solutions as to how to get this done. I can post a diagram of the linked lists and my function if needed.
Thanks a lot for your time and patience.

Frank

Avatar of Jaime Olivares
Jaime Olivares
Flag of Peru image

I think your model is OK, and according with class data structures in C. To distinguish between polygon and coordinates lines, just have to make a test of first character with isalpha() function.
Don't forget to fill last element's next pointer of each list with NULL, to know that list has terminated.

Avatar of The_Kingpin08
The_Kingpin08

ASKER

I thought I could use the fscanf function to read the coordinates. If it fails, it would mean that there is no more coordinates to read because we found a new model name.
Would it also be a good solution and how could I check the return value of the function ?

Thanks, Frank
ASKER CERTIFIED SOLUTION
Avatar of Jaime Olivares
Jaime Olivares
Flag of Peru image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Ok so if my logic is correct, everytime I read a new model I'll have to create a new linked list based on the struct (defined in my previous post) for my points and polygons ? Doesn't that seems redundant and taking too much space ?
It will take the same space as if all point of all polygons belongs a unique linked list.
One linked list or many linked list needs the same space.
What you are creating in fact is "a linked list of linked list of linked list". I have use this structure many times in many graphical projects: Object/Primitives/Coordinates.

-----------------------

But, if you want to be more efficient, and polygons won't be modified after them have been loaded, you can replace "points linked list" with an "array of points". That will be a little harder to fill when loading but will consume less space and will have a simpler and faster access.
This will need some redefinitions:
typedef struct point
{
     float x;
     float y;
     float z;             /* cooordinates of my point */
/*     PtrPoint next;    DON'T NEED THIS LINE*/
}Point;

typedef struct polygon
{
     int numPolygon;         /* ID number of the polygon */
     int nbPoints;              /* number of points of the polygon */
     PtrPoint arrayPoint;    /* CHANGE: ARRAY OF POINTS, DINAMICALLY ALLOCATED */
     PtrPolygon next;        /* points on the next polygon */
}Polygon;

Thanks Jaime, your idea is great and more efficient as you said ! However, for the needs of this project I must concentrate on linked lists, but be sure that I will remember this tips for next times :)

Thanks
Hi all, I am seeking advices once more. While working on my prooject I ran into something I haven't thought before. I have to create and handle 3 separates linked lists. The creation of the lists is going correctly (so far...) but I've found since a model can have multiple polygons, it means that maybe somewhere in the file I'll have to insert a polygon in a given given model inside his list. I'm really not sure how to do this, so any help would be really appreciate. To understand more my problem, I'll post my diagram.

[Model Head]
       |
[   Model1   ]     ---------> [ Polygon1 ] ---------> [ Polygon2 ] ---------> [ Etc. ]
       |                                     |                               |
       |                              [   Point1   ]               [   Point1   ]
       |                                     |                               |
       |                              [   Point2   ]               [   Point2   ]
       |
[   Model2   ]     ---------> [ Polygon1 ] ---------> [ Polygon2 ] ---------> [ Etc. ]
       |                                     |                               |
       |                              [   Point1   ]               [   Point1   ]
       |                                     |                               |
       |                              [   Point2   ]               [   Point2   ]
       |                                     |                               |
       |                              [    Etc.     ]                [    Etc.     ]
       |
[     Etc.      ]

And here's how I started to create my linked lists. I thought the first thing to do was to handle the model, then go with the polygon and finaly go with the points, but don't know if I'm doing it properly...

void createLists(PtrModel *p, const char* fileName)
{
      char c;
        /* Opens the file to be read */
      FILE* file = fopen(fileName, "r");
        /* Creates the links and set the model list to nothing */
      PtrModel headModel = NULL, newModel;
        /* Set the memory we'll be needing */
      int nbOct = sizeof(PtrModele);

         /* Loops tuntil the end of the file is reached */
      while (!feof(fich))
        {
                /* Resize */
            newModel = (Model *) malloc (sizeof(Model));
                /* Reads the line with fgetc until a \n is found (the fgetc is needed for the PolygonID) */
            ReadLine(file, newModel->nameModel);
                /* We extract the polygon ID from the model's line */
            PolygonID = ExtractPolygonID(newModel->nameModel);
            
                /*  We check if the line is a character; if yes, it's a model */
            if (isalpha(newModel->nomModele[0]))
                        /* Check to see if thee model is already present in the list, if yes, we don't add it */
                  if(fin(newModel->nameModel,headModel )!=1)
                  {
                                /* If not present, we assign it to the next link and print his value for testing */
                        newModel->next= headModel ;
                        headModel = newModel;
                        printf("%s",headModel ->nameModel);  
                  }
       }
         /* Once the file is read, we close it */
       fclose(file);
         /* We end the linked list */
       headModel->next= NULL;
       *p = headModel;
}

Thanks for sharing your time helping me, I appreciate a lot !

Frank
Your graphic is OK, it is the right way, about your code, I have many dudes.
Could you clarify your data example? I see just 2 entities: polygons and points.
Please post a more complete example to help you better.
typedef struct point* PtrPoint;
typedef struct point
{
     float x;
     float y;
     float z;             /* cooordinates of my point */
     PtrPoint next;    /* points on the next point */
}Point;

typedef struct polygon* PtrPolygon;
typedef struct polygon
{
     int numPolygon;         /* ID number of the polygon */
     int nbPoints;              /* number of points of the polygon */
     PtrPoint headPoint;    /* head of the points' list */
     PtrPolygon next;        /* points on the next polygon */
}Polygon;

typedef struct model* PtrModel;
typedef struct model
{
     char nomModel[MAX_CAR_MODEL];     /* name of the model */
     int nbPolygons;                           /* number of polygons */
     PtrPolygon headPolygon;                   /* head of the polygon's list for the model */
     PtrPolygon next;                     /* points the next model */
}Model;

PtrModel headModele;     /* head of the models' list */



void createLists(PtrModel *p, const char* fileName)
{
     char c;
        /* Opens the file to be read */
     FILE* file = fopen(fileName, "r");
        /* Creates the links and set the model list to nothing */
     PtrModel headModel = NULL, newModel;
        /* Set the memory we'll be needing */
     int nbOct = sizeof(PtrModele);

         /* Loops tuntil the end of the file is reached */
     while (!feof(fich))
        {
                /* Resize */
          newModel = (Model *) malloc (sizeof(Model));
                /* Reads the line with fgetc until a \n is found (the fgetc is needed for the PolygonID) */
          ReadLine(file, newModel->nameModel);
                /* We extract the polygon ID from the model's line */
          PolygonID = ExtractPolygonID(newModel->nameModel);
         
                /*  We check if the line is a character; if yes, it's a model */
          if (isalpha(newModel->nomModele[0]))
                        /* Check to see if thee model is already present in the list, if yes, we don't add it */
               if(fin(newModel->nameModel,headModel )!=1)
               {
                                /* If not present, we assign it to the next link and print his value for testing */
                    newModel->next= headModel ;
                    headModel = newModel;
                    printf("%s",headModel ->nameModel);  
               }
      }
         /* Once the file is read, we close it */
      fclose(file);
         /* We end the linked list */
      headModel->next= NULL;
      *p = headModel;
}


int readLine(FILE* file, char* line)
{
    int c;
      
    while ((c = fgetc(file)) != ' ' || c != EOF) *line++ = (char)c;
    *line= '\0';
    return c != EOF;
}



Thats all I've done so far plus some other functios but right now my goal is to try to complete the lists creation, once that is done it's gonna be a big weight off my shoulders !

LMK if you need more informations,

Thanks, Frank
What I want to have, if possible, is a bigger example of your DATA. The theory is OK, your linked list design is OK, your structures are OK, but your createLists() function looks some strange.
What I want to clarify is this:

chair 1
1.24  -1.52  3.78
2.23   1.25  2.47
4.44   2.58  0.97
table 3
5.32   1.52   8.12
0.23  -1.25  -2.47
chair 2
2.32  6.25  1.65
1.25  5.82  3.24

I guess it belongs to a unique car, so "char" is a polygon name and 1 is polygon ID, but don't see the car name, maybe a file correspond to a model (car)? so filename is modelname?

sorry about the misunderstanding, here's a a larger bit of data. The file is named model.txt and I pass it in parameter to the creatLists function. If the model has the same polygon ID, we don't insert it again.

table 2
   -204.88    -648.67    -560.46
   -214.74    -649.14    -579.16
   -203.69    -648.14    -567.96
   -202.08    -648.57    -591.16
   -207.32    -649.21    -565.35
   -215.65    -649.77    -557.22
   -203.73    -649.52    -577.87
   -204.51    -648.20    -573.75
chair 12
    117.13      61.72     704.81
    138.32      73.62     698.18
    142.89      55.52     717.65
    137.79      59.62     719.09
    139.79      74.10     701.23
ball 4
   -426.41     668.31      20.99
   -409.97     669.94      23.56
   -415.53     664.72      17.26
   -398.15     666.25      15.30
   -409.96     657.18      21.26
   -424.06     672.69      24.66
ball 1
   -686.82     194.51      98.96
   -686.18     174.35      99.50
   -682.38     194.16     107.46
   -683.65     174.56     114.63
radio 6
     93.43      -3.40    -499.20
     95.70       3.67    -489.84
    101.59       1.85    -489.29
    102.21      -2.34    -506.87
table 5
   -106.33      28.28    -259.64
   -104.26      30.79    -263.88
   -105.64      32.04    -250.99
   -106.56      33.54    -271.80
bottle 11
    181.23    -481.97     -90.84
    182.24    -487.15     -93.37
    180.49    -486.65    -105.92
    178.45    -476.67     -88.76
    180.87    -487.07     -89.91
box 4
    475.18     335.75     292.21
    492.19     357.60     292.24
    485.93     357.52     291.36
    479.33     342.31     291.10
    474.87     357.52     288.17
ball 2
   -312.61    -173.92     138.65
   -326.54    -157.05     102.27
   -318.21    -157.29     124.84


Frank
so, if  a filename belongs just to one model, there are some errors in your code
This line

         newModel = (Model *) malloc (sizeof(Model));
 
must be BEFORE the while loop, because you must create a model object once you have opened the file.

inside your while(!feof(fp)) loop, there will be some:

newPolygon = (Polygon *)malloc(sizeof(Polygon)) instead

and also many:

newPoint = (Point *)malloc(sizeof(Point))

That's why I suggested you to use gets to read entire line, then evaluate if is polygon or point and do proper action (one of 2 above), fill your new structure and attach to proper linked list.
Thanks Jaime, I'll use the fgets to test the line but I'm required to use fgetc to extract the model's name and polygon's ID that are on the same line. Using your tips, here's what I made. The way of adding a link and creating a list is still uncleared, like how to add another polygon to an existing model for example. Also, I know I'll have to put the Null valu into the last point of a polygon, but have no clue as to where do this :(

void createLists(PtrModel *p, const char* fileName)
{
      char c;
      char buffer[200];

      int nbOcts = sizeof(PtrModel);

      FILE* file = fopen(fileName, "r");
      PtrModel headModel = NULL, newModel;
      PtrPoint  headPoint = NULL, newPoint;

      newModel = (Model *) malloc (sizeof(Model));

      while (!feof(file))
       {
            fgets(buffer,200,file);
            if (isalpha(buffer[0]))
            {
                  readLine(file, newModele->nameModel);
                  
                  if(search(newModele->nameModele, headModel)!=0){
                        newModel->next = headModel;
                        headModel = newModel;
                        printf("%s", headModel->nameModel);}  
            
            }else{
                  newPoint = (Point *)malloc(sizeof(Point));
                  readPoint(fich, newPoint ->x);
                  readPoint(fich, newPoint ->y);
                  readPoint(fich, newPoint ->z);
                        newPoint->next = headPoint;
                    headPoint = newPoint;
            }
                  
      }
      fclose(file);
      headModel->next = NULL;
      *p = headModel;
}



Thanks for your time again, I really appreciate.
Frank
Ok another quick question. I have a string containing the models name and the polygon's ID. How can I convert the polyon's ID from char to int ? I tried using a function but it didnt work...

char extractPolygonID(char* buf, int ID)
{
    int i=0;
      
    while (buf[i] != ' ') {buf[i] = buf[i++];}
      
      if(!isalpha(buf[i++]))
      {
            sscanf(buf[i++], "%x", &ID);
      }

    return i != EOF;
}

Thanks, Frank
Sorry frank, I was a little bussy.
I have not noticed that you specify model and polygon id in the same number.
I have yet explained how to extract both model name and polygon id. Just use:

int id;
sscanf(buf, "%s %i", modelnamebuffer, &id);

where modelnamebuffer is a char array where to store model name (possibly inside your Model structure).
But if you want to extract only polygon id and skip model name, use:

int id;
sscanf(buf, "%*s %i", &id);