asked on

Linked Lists verification (long code)

Hi all, I've been working on a linked list project for some time now and thanks to people on this forums I was able to learn and do something. I am posting my 3 functions that handle the 3 linked lists and would appreciate, if there's no football or nothing to do, if someone could take a quick look to check if everything seems ok. I just need a general opinion or tips. I've probably not done it the easiest or quickest way, but I tried doing something with what I had. BTW I know there's still many thing I haven's done yet, like incrementing the point and polygon number, etc.

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

/*==========================================================================
Declaration of the lists
==========================================================================*/

typedef struct point* PtrPoint;
typedef struct point
{
      float x;
      float y;
      float z;
      PtrPoint next;
}Point;

typedef struct polygon* PtrPolygon;
typedef struct polygon
{
      int numPolygon;            /* Polygon's ID */
      int nbPoints;                  /* Number of points of the polygon */
      PtrPoint headPoint;            /* Headlist of the polygon's points */
      PtrPolygone next;
}Polygone;

typedef struct model* PtrModel;
typedef struct model
{
      char nameModel[MAX_CAR_MODELE];
      int nbPolygons;                        /* number of polygons of the model */
      PtrPolygon headPolygon;            /* Headlist of the model's polygons */
      PtrPolygon next;
}Modele;

PtrModel headModel;                        /* Headlist of the models */

/*==========================================================================
Creation of the Model's list
==========================================================================*/
PtrModel createModelList(FILE* file
{
      /* Buffer used to store the line value */
      char buffer[200];

      /* Polygon's ID used to create the new Points linked list */
      int PolygonID = 0;

      /* Definition of the pointers */
      PtrModel PtrCur, PtrPrev;
      PtrModel PtrHead = NULL;

      /* Adjust the size of the list */
      PtrCur = (PtrModel) malloc (sizeof (PtrModel));

      /* Loop until the end of the file */
      while (!feof(file))
{
            /* Reads the line and if the first character is a char, it's a new model */
            fgets(buffer,200,file);
            if (isalpha(buffer[0]))
            {
                  /* Reads the line and return the Model's name without the Polygon's ID value */
                  ReadLine(buffer, PtrCur->nameModel);

                  /* We search the Model's linked list to check is the model (with the same Polygon's ID)
                  already exists. If not, we can add it to the list. */
                  if(searchSimilarModel(PtrCur, PtrCur->nameModel))
                  {

                        /* If the current pointer is not the first, we assign it as the list's head.
                        Else, the previous pointer's next value is set to the current pointer */
                        if (!PtrHead) PtrHead = PtrCur;
                        else PtrPrev->next = PtrCur;
                        PtrPrev = PtrCur;

                        /* We create a new Polygon's list for the current model. The current model also
                        becomes the polygons list's head. */
                        createPolygonList(buffer, PtrCur);

                        /* We remember the current polygon's ID because next line it will becomes the Points' headlist */
                        ExtractPolygonID(buffer, PolygonID);
                  }

            /* The first line character wasn't a char, so the line represent a new set of points */
            }else{

                  /* Temp polygon that represents the one created on the previous line */
                  PtrPolygon PtrCurPolygon = NULL;
                  PtrCurPolygon->numPolygon = PolygonID;
                  PtrCurPolygon->nbPoints++;
                  /* We call the function that creates the 3 points with the line value. */
                  CreatePointList(buffer, PtrCurPolygon);
            }
      }

      /* Ends the linked list and return the head */
      if (PtrHead) PtrPrev->next = NULL;
            return PtrHead;
}

/*==========================================================================
Creation of the Polygon's list
==========================================================================*/
PtrPolygon CreatePolygonList(char* buffer, PtrModel PtrHead)
{
      /* Definition of the pointers */
      PtrPolygon PtrCur;

      /* Initalizing the polygons list's head */
      PtrHead->headPolygon = NULL;

      /* Adjust the size of the list */
      PtrCur = (PtrPolygon) malloc (sizeof (PtrPolygon));

      /* Reads the line and return the Polygon's ID value */
      ExtractPolygonID(buffer, PtrCur->numPolygon);

      /* Insert the new pointer and link it to the list's head */
      PtrCur->next = PtrHead->headPolygon->next;
      PtrHead->headPolygon->next = PtrCur;

      /* Ends the linked list and return the head */
      if (PtrHead->headPolygone) PtrHead->headPolygon->next = NULL;
            return PtrHead->headPolygone;
}

/*==========================================================================
Creation of the Point's list
==========================================================================*/
PtrModel CreatePointList (char* buffer, PtrPolygon PtrHead)
{
      /* Definition of the pointers */
      PtrPoint PtrCur;

      /* Initalizing the point list's head */
      PtrHead->headPoint = NULL;

      /* Adjust the size of the list */
      PtrCur = (PtrPoint) malloc (sizeof (PtrPoint));

      /* Reads the line (which contains the 3 points separated by 1 or more spaces) and return the correct value */
      ReadPoint(buffer, &PtrCur->x);
      ReadPoint(buffer, &PtrCur->y);
      ReadPoint(buffer, &PtrCur->z);

      /* Insert the new pointer and link it to the list's head */
      PtrCur->next = PtrHead->headPoint->next;
      PtrHead->headPoint->next = PtrCur;

      /* Ends the linked list and return the head */
      if (PtrHead) PtrHead->headPoint->next = NULL;
            return PtrHead->headPoint;
}

Thank you very much for taking some of your time to help me, wish there was something I could do to give back the favor. I appreciate all the support you give me. You experts guys rock, keep up the good job.

Frank

Indrawati

Some quick comments:
1. In struct definition:
      typedef struct polygon
      {
       int numPolygon; /* Polygon's ID */
       int nbPoints; /* Number of points of the polygon */
       PtrPoint headPoint; /* Headlist of the polygon's points */
       PtrPolygone next;
      }Polygone;

next should be PtrPolygon (otherwise it won't compile).

2. In CreateModelList():

      PtrCur = (PtrModel) malloc (sizeof (PtrModel));

Shouldn't this be like this:

      PtrCur = (PtrModel) malloc (sizeof (Modele));

In the first one, you only allocate memory the size of a pointer-to-model, while in the second, you allocate memory the size of Modele, which is what you want. The same thing also needs to be modified in other functions.

Indrawati

Other things:
1. Depending on your requirements, you may want to check passed parameters for the functions. E.g.:

PtrPolygon CreatePolygonList(char* buffer, PtrModel PtrHead)
{
/* Definition of the pointers */
PtrPolygon PtrCur;

/* Initalizing the polygons list's head */
PtrHead->headPolygon = NULL; //if PtrHead is NULL, this function will most likely crash

so you check PtrHead somewhere in the function, e.g.:

if(PtrHead == NULL) return NULL;

2. You may also want to check the result of malloc, e.g:

/* Adjust the size of the list */
PtrCur = (PtrPolygon) malloc (sizeof (PtrPolygon));

If there is no available memory in the system, malloc will return NULL, so you may want to check for that.

3. Minor nitpick:

/* Ends the linked list and return the head */
if (PtrHead->headPolygone) PtrHead->headPolygon->next = NULL;
return PtrHead->headPolygone;

The indentation is deceptive here, and it may confuse other code maintainers.

The_Kingpin08

ASKER

Thanks Indrawati,

I had to translate the code, that explains the "Polygone".
As far as the malloc, I changed it as you said and it works fine. Same with the validation.

Now concerning linked lists themself, do you think the creation method looks correct ? I had a problem in some cases;

- First I read the model's line which contains the model's name and the Polygon's ID. After reading the line, I assign the name to the model and store the polygon's ID.
- Then, I create a new polygon's linked list using the stored ID and go to the next line.

When I reach the next line (which will contains the points of the polygon), I don't know how to use the polygon I just created on the previous line to set it as the Point's headlist. Thats why I created a temporary polygon with the previous value.

However, I really doubt this is efficient and will work :(

Here's the part I'm talking about:

/* Temp polygon that represents the one created on the previous line */
PtrPolygon PtrCurPolygon = NULL;
PtrCurPolygon->numPolygon = PolygonID;
PtrCurPolygon->nbPoints++;
/* We call the function that creates the 3 points with the line value. */
CreatePointList(buffer, PtrCurPolygon);

I also got many question on the linked lists comparison and search methods, but once I'll be able to create my 3 lists and insert items correctly I think I'll be ok :)

Thanks for the review and the tips,

Your friendly newb, Xziac

ASKER CERTIFIED SOLUTION

Indrawati

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Indrawati

Sorry, the code:

//add current polygon to the current model
if(!PtrCurModel->headPolygon)
{
PtrCurModel->headPolygon = ptrCurPolygon;
}
else //add polygon to the head of the linked list
{
PtrCurModel->headPolygon->next = ptrCurPolygon;
PtrCirModel->headPolygon = ptrCurPolygon;
}

should be:

       //add current polygon to the current model
if(!PtrCurModel->headPolygon)
{
PtrCurModel->headPolygon = ptrCurPolygon;
}
else //add polygon to the head of the linked list
{
       PtrCurPolygon->next = ptrCurModel->headPolygon;
       PtrCurModel->headPolygon = ptrCurPolygon;
}

And findModelID(PtrHead, CurModelID) is a function that search whether CurModelID is inside the linked list with PtrHead at its head. It returns NULL of CurModelID is not in the linked list, or pointer to the Model otherwise.

The_Kingpin08

ASKER

Thank you so much Indrawati, I understand what I'm doing so much more now (more logical at least !). I tried making the search function and here's what I came up with. A little checkup would be really appreciate :)

PtrModel* findModelID(PtrModel *head, char* val)
{
PtrModele CurPtr = head;
while(CurPtr)
{
if(CurPtr->nameModel == val)
return CurPtr;
CurPtr = CurPtr->next;
}
return NULL;
}

Thanks, Frank

Indrawati

Hi Frank

The function looks very good to me. I think it should work properly.

The_Kingpin08

ASKER

BTW why does everytime Itry to declare something directly in the code, I get a compilation error like "'PtrModel' : illegal use of this type as an expression"
For example, with these lines:

PtrModel PtrCurModel;
PtrPolygon ptrCurPolygon = (PtrPolygon) malloc (sizeof (Polygone));

Frank

Indrawati

If you have declared/defined the types correctly and there's no propagated error, it should work. Maybe you can post the smallest portion of the code that, when compiled, give that error?

The_Kingpin08

ASKER

This is the exact spot:

//read model's ID
LireLigne(buffer, CurModelID);

PtrModel PtrCurModel;

The compiler doesn't takes the "PtrModele PtrCurModele;" line and returns "error C2275: 'PtrModel' : illegal use of this type as an expression"

The same happens with the lineL

//now we have the current model, find data about current polygon
PtrPolygon PtrCurPolygon = (PtrPolygon) malloc (sizeof (Polygone));

which returns "error C2275: 'PtrPolygon' : illegal use of this type as an expression"

I'm using Visual C++ 2005, think there might be a problem with the compilator ?

Frank

Indrawati

Hmmm... I tried compiling the function I posted before, and after removing some syntax errors, the function compiled perfectly. Maybe you can post the complete function, along with the declaration of the corresponding types (PtrModel, etc.)?

The_Kingpin08

ASKER

I tried moving the 2 lines that didi the error to the beginning of the function it seems to work. Do you think it will affect the final resuult ? Here's how it looks like now:

PtrModel createModelsList(FILE* fLect)
{

/* Initializing the pointer */
PtrModele PtrPrec = NULL;
PtrModele PtrTete = NULL;

/* *** Problematic line #1*** */
PtrModele PtrCurModele;

/* *** Problematic line #2*** */
//now we have the current model, find data about current polygon
PtrPolygone PtrCurPolygone = (PtrPolygone) malloc (sizeof (Polygone));

/* Buffer used to store the line value */
char buffer[200];

/* Reads the line and if the first character is a char, it's a new model */
fgets(buffer,200,fLect);

while(!feof(fLect))
{
if(isalpha(buffer[0]))
{
....

I also have one little question: Is it possible for a struct to be NULL ? I tried using the search function written previously and when the value isn't found, it doesn't change the pointer's value to NULL...Here's the problem:

//if model's ID exists, add Polygon to model
//else create new model and add Polygon to model
PtrCurModel = findModelID(PtrHead, CurModelID);

if(PtrCurModel == NULL) //model ID does not exist <---------- Even if the current model isnn't found, it's value isn't NULL...

Besides that, your function works like a charm and the logic is perfect :) Let's not just see problem now !

Thanks again,
Frank

Indrawati

Hi

I am not 100% sure, but the 'illegal use of this type as an expression' problem may be caused because you're compiling a C program, where all variables must be declared at the top of functions, unlike C++ programs.

1. About moving the problematic lines to the beginning of the function:

      /* *** Problematic line #1*** */
      PtrModele PtrCurModele;            //this should be OK

      /* *** Problematic line #2*** */
      //now we have the current model, find data about current polygon
      PtrPolygone PtrCurPolygone = (PtrPolygone) malloc (sizeof (Polygone));

note that you have to malloc new Polygone everytime your read a new polygon from the file, So you must put the malloc part into the loop, e.g:

      //at the beginning of the function
      PtrPolygone PtrCurPolygone;
      ...
      while(!feof(file))
      {
            if(isalpha(buffer[0]))
            {
                  ...
                  if(PtrCurModel == NULL)
                  {
                        ...
                  }
                  ptrCurPolygon = (PtrPolygon) malloc (sizeof (Polygone));
                  ...
            }
      }


2. I missed this point before, but I think your findModelID function should be like this (since you are comparing strings and PtrModel is a pointer to model):

PtrModel findModelID(PtrModel head, char* val)
{
PtrModel CurPtr = head;
while(CurPtr)
{
if(strcmp(val, CurPtr->nameModel) == 0)
return CurPtr;
CurPtr = CurPtr->next;
}
return NULL;
}

Since strcmp returns other values beside 0 if the strings are not equal, logically the function should only return NULL and the NULL should be stored into PtrCurModel.

The_Kingpin08

ASKER

A thousand thanks for you Indrawati, you really help me understanding !
Thank you again, I really appreciate.

Frank