Brook Renzi Brook Renzi - 3 months ago 30
C Question

Alphabetically sorting linked list

I am trying to make an alphabetically sorted linked list. For the code if any two names are the same their ages are compared. It is assumed their ages will not be the same.

I have made a function which compares two students for their name and age as shown by comesBefore. This works fine.

The problem I'm having is when linking the four names together I get a segmentation fault. If anyone can give me some pointers on where I am going wrong or on debugging in c that would be great.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

typedef struct name_s Name;

//Struct name_s contains a character pointer to a name, an age, and a
// pointer to the next name in a linked list

struct name_s{
char* name;
int age;
Name* next;
};

//comesBefore takes a pointer to student1 and student2.
//The two students are compared to see which one comes first in
//alphabetical order.
//If both names are the same then their ages are compared.
//The function returns true if student1 should come first else false

bool comesBefore(const Name* student1, const Name* student2)
{
int i = 0;
if (student2 == NULL){
return true;
}
while (student1->name[i]!= '\0' && student2->name[i] != '\0'){
if (student1->name[i] < student2->name[i]){
return true;
}
i++;
}

if (student1->name == student2->name){
if (student1->age < student2->age){
return true;
}
}

return false;
}

//creates a linked list in alphabetical order of the names
//if any two names are the same the one with the lowest age comes first

Name* linkedList(Name names[], int n)
{
Name* head = NULL;
Name* previous = NULL;
Name* last = NULL;
Name* current = &names[0];
int i = 0;
while (i < n) {
if (head == NULL){
head = current;
} else {
if (comesBefore(current, head)){
current->next = head;
head = current;
} else {
previous = head;
while(comesBefore(current, previous->next) == false
&& previous->next != NULL){
previous = previous->next;
}

current->next = previous->next;
previous->next = current;
}

}
last = head;
int k = 0;
while (k <= i){
last = last->next;
k++;
}

last->next = NULL;
i++;
current = &names[i];
}


return head;
}


int main(void)
{

Name a;
Name b;
Name c;
Name d;
Name* s1 = &a;
Name* s2 = &b;
Name* s3 = &c;
Name* s4 = &d;

s1->name = "Zaphod Beeblebrox";
s1->age = 250;
s2->name = "Albert Einstein";
s2->age = 133;
s3->name = "Albert Einstein";
s3->age = 7;
s4->name = "Brook Fleming";
s4->age = 20;

Name names[4];
names[0] = a;
names[1] = b;
names[2] = c;
names[3] = d;

Name* list = linkedList(names, 4);
while (list!=NULL){
printf("Name: %s\nAge: %d\n--------\n",
list->name,
list->age
);
list = list->next;
}



return 0;
}

Answer

The problem is that the "next" pointers are not initialized. You need to nullify them.

Name a = {};
Name b = {};
Name c = {};
Name d = {};

Another thing, is that your sorting function is not handling well the string comparison. You should change it to:

bool comesBefore(const Name* student1, const Name* student2)
{
    int i  = 0;
    if (student2 == NULL)
    {
        return true;
    }
    while (student1->name[i]!= '\0' && student2->name[i] != '\0')
    {
        if (student1->name[i] < student2->name[i]){
            return true;
        }
        else if (student1->name[i] > student2->name[i]){
            return false;
        }

    i++;
}
...

or even better, use strcmp()

also note that the whole "k" and "last" part in your code is not required at all

Comments