Sort structure on names (doubly linked list)

Question

I am trying to sort my structure based on names (alphabetically). For example I have this structure:

struct person{
    char name[MAX];
    char num[MAX];
    char email[MAX];
    struct person *next;   
    struct person *previous;  
};

struct person *next, *first, *end;

and in my main function :

int main()
{
 struct person p = {{0}}
 .
 .
 .
 switch(choice)
    {
    case 1 : 
        printf("Name   : "); scanf("%s", &p.name);
        printf("Num : "); scanf("%s", &p.num);
        printf("E-Mail   : "); scanf("%s", &p.email);
        input(p); //function to input data    
        break;
    case 2 : 
        sort(p); //function to sort the data
        break;
               }
}

And in my prototype function:

void sort(struct person p)
{
    struct person *ptr, *ptr2, *temp;

    ptr=first;
    ptr2=first;

    for (ptr= first; ptr!= NULL; ptr= ptr->next)
    {
        for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)
        {
            if (strcmp(ptr->name, ptr2->name) > 0)
            {
                temp = ptr;
                ptr= ptr2;
                ptr2= temp;
            }
        }
    }

}

Okay, so I have a prototype function which sort the structure based on its element which is name. I tried sorting it using the same principle as bublesort but it didnt work out for me. Pointer ptr points to the first node in the list and ptr2 points to the second node. Is my algorithm wrong?I cant seem to find out what is wrong. Main problem is with the sorting. I Hope my question is clear.

After the sort, you're likely to have a different element at the start of the list. How are you going to know which element is the new start of the list? I don't think you will know with the current code. Your sort function should probably not be taking a direct struct person p; it is likely to need to be a struct person **p or a struct person &*p. — Jonathan Leffler
– Jonathan Leffler, Commented Nov 18, 2013 at 17:25

ensc · Accepted Answer · 2013-11-18 18:26:33Z

Inner loop

    for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)

should be

    for (ptr2= ptr->next; ptr2!= NULL; ptr2= ptr2->next)

(note the ptr2 vs. ptr).

EDIT:

Swapping pointers won't work either. You have to relink to elements which requires helper variables in the loops. Things can be made more elegant (--> dealing with head of list) when working with references:

static void swap(struct person **a, struct person **b)
{
    struct person       *tmp;

    if ((*a)->next)
        (*a)->next->prev = *b;

    if ((*b)->next)
        (*b)->next->prev = *a;

    tmp        = (*a)->prev;
    (*a)->prev = (*b)->prev;
    (*b)->prev = tmp;

    tmp        = (*a)->next;
    (*a)->next = (*b)->next;
    (*b)->next = tmp;

    tmp = *b;
    *b  = *a;
    *a  = tmp;
}

void foo()
{
    struct person **a;
    struct person *prev_a;

    for (a = &first; *a != NULL; a = &(prev_a->next)) {
        struct person **b;
        struct person *prev_b;

        prev_a = (*a)->prev;

        for (b = &(*a)->next; *b != NULL; b = &(prev_b->next)) {
            prev_b = (*b)->prev;

            if (strcmp((*a)->name, (*b)->name) > 0)
                swap(a, b);

            /* prev_b == NULL can not happen because inner loop is started
               in the middle of the list */
            prev_b = prev_b->next;
        }

        if (prev_a)
            prev_a = prev_a->next;
        else
            prev_a = first;
    }
}

EDIT:

Implementing linux kernel like linked lists (having a dummy head which is linked at front and tail of list) make things more easy in the swap method because NULL pointer checks can be omitted. E.g. list would look like

     ,------------> HEAD ------------\
    | +------------     <-----------\  \ 
    | |                              |  |
    | `-> elem_n --> ... --> elem_0 -`  |
     `---        <-- ... <--        <---'

You might clarify that with some explanation; it took me more than a second look to spot the difference (the initialization from ptr->next instead of ptr2->next). I'm also not convinced it is the only problem.

Igor Ševo · Accepted Answer · 2013-11-18 17:37:46Z

0

Do not swap pointers, swap values. Also, you need to initialize empty pointers to NULL, they are not by default.

answered Nov 18, 2013 at 17:37

Igor Ševo

5,5653 gold badges40 silver badges84 bronze badges

Collectives™ on Stack Overflow

Sort structure on names (doubly linked list)

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related