Bifalgorithm post · Computer science one · Sorting Pointers to Elements

How should a comparator handle an array of structure pointers with NULL values?

How should a comparator handle an array of structure pointers with NULL values? (Computer science one · Sorting Pointers to Elements) — "This is essentially eq…

Ideas in this flowchart

  • Trier des tableaux de pointeurs Student avec qsort
  • Le comparateur doit gérer des pointeurs vers des pointeurs
  • Chaque argument pointe vers un élément du tableau, lui-même pointeur vers un Student
  • Les arguments sont convertis en const Student ** puis déréférencés pour obtenir un Student *
  • Les étudiants sont comparés d’abord par nom de famille, puis par prénom en cas d’égalité
  • Le roster est alloué comme Student ** et qsort reçoit la taille d’un Student *
  • Les tableaux de pointeurs peuvent contenir des éléments NULL
  • Ignorer les pointeurs NULL peut provoquer un comportement indéfini ou une erreur de segmentation
  • Le programme peut définir un ordre explicite entre les pointeurs NULL et non NULL
  • Deux pointeurs NULL sont considérés comme égaux et le comparateur renvoie 0
  • Un pointeur NULL peut être placé avant un pointeur non NULL et produire -1
  • Un pointeur non NULL peut être placé après un pointeur NULL et produire 1
  • Lorsque les deux pointeurs sont non NULL, la comparaison des noms est appliquée
Feed/

How should a comparator handle an array of structure pointers with NULL values?

No cover

Channel

Computer science one

1 page

"This is essentially equivalent to the string scenario: we have an array of pointers to be sorted, our comparator function then needs to deal with pointers to pointers. An example appears in Code Sample 25.5.\n\n/**\n\n* Orders two Student pointers according to the last name/first name\n\n*/\n\nint studentPtrLastNameCmp(const void *s1, const void *s2) {\n\n//we receive a pointer to an individual element in the array\n\n//but individual elements are POINTERS to students thus we cast\n\n//them as (const Student **) then dereference to get a pointer\n\n//to a Student!\n\nconst Student *a = *(const Student **)s1;\n\nconst Student *b = *(const Student **)s2;\n\nint result = strcmp(a->lastName, b->lastName);\n\nif(result == 0) {\n\nreturn strcmp(a->firstName, b->firstName);\n\n} else {\n\nreturn result;\n\n}\n\n}\n\nStudent **roster = (Student **) malloc(sizeof(Student *) * n);\n\n...\n\nqsort(roster, n, sizeof(Student *), studentPtrLastNameCmp);\n\nAnother issue when sorting arrays of pointers is that we may now have to deal with NULL elements. When sorting arrays of elements this is not an issue as a properly initialized array will contain non-null elements (though elements could still be uninitialized, the memory space will be valid). How we handle NULL pointers is more of a design decision. We could ignore it and any attempt to access a NULL structure will result in undefined behavior (or segmentation faults, etc.). Or we could give NULL values an explicit ordering with respect to other elements. That is, we could order all NULL pointers before non-NULL elements (and consider all NULL pointers to be equal). An example with respect to our Student structure is given in Code Sample 25.6.\n\nint studentPtrLastNameCmpWithNulls(const void *s1, const void *s2) {\n\nconst Student *a = *(const Student **)s1;\n\nconst Student *b = *(const Student **)s2;\n\nif(a == NULL && b == NULL) {\n\nreturn 0;\n\n} else if(a == NULL && b != NULL) {\n\nreturn -1;\n\n} else if (a != NULL && b == NULL) {\n\nreturn 1;\n\n}\n\nint result = strcmp(a->lastName, b->lastName);\n\nif(result == 0) {\n\nreturn strcmp(a->firstName, b->firstName);\n\n} else {\n\nreturn result;\n\n}\n\n}"

Flowchart preview
👍
0
0 comments0 shares

Sign in to view and post comments.