Solved

# Best way of creating 3 linked lists

Posted on 2004-11-14
193 Views
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 */
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;

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

0
Question by:The_Kingpin08

LVL 55

Expert Comment

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.

0

Author Comment

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
0

LVL 55

Accepted Solution

As I suggested earlier, you can make a simple test before taking a decision. Read every line using fgets, use isalpha to evaluate first character of buffer, and then use sscanf function to read fields, sscanf returns you the number of fields read, so you can test if everything is ok.

Here is a template:

char buffer[200];         /* reserve enough space as you consider */

while (...) {      /* some kind of loop */

fgets(buffer,200,fp);

if (isalpha(buffer[0])) {    /* it is a polygon label/id */
// apply proper sscanf here
} else {    /* it is a coordinate ternary */
// apply proper sscanf here
}
}
0

Author Comment

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 ?
0

LVL 55

Expert Comment

It will take the same space as if all point of all polygons belongs a unique linked list.
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;

0

Author Comment

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
0

Author Comment

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.

|
[   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 */
/* 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) */
/* 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 not present, we assign it to the next link and print his value for testing */
}
}
/* Once the file is read, we close it */
fclose(file);
/* We end the linked list */
}

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

Frank
0

LVL 55

Expert Comment

Could you clarify your data example? I see just 2 entities: polygons and points.
0

Author Comment

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

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 */
/* 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) */
/* 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 not present, we assign it to the next link and print his value for testing */
}
}
/* Once the file is read, we close it */
fclose(file);
/* We end the linked list */
}

{
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 !

Thanks, Frank
0

LVL 55

Expert Comment

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?

0

Author Comment

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

LVL 55

Expert Comment

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:

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

Author Comment

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");

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

while (!feof(file))
{
fgets(buffer,200,file);
if (isalpha(buffer[0]))
{

}else{
newPoint = (Point *)malloc(sizeof(Point));
}

}
fclose(file);
}

Thanks for your time again, I really appreciate.
Frank
0

Author Comment

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
0

LVL 55

Expert Comment

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);
0

## Featured Post

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallā¦
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to useā¦
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.