Linked list question

This is a discussion on Linked list question within the C Programming forums, part of the General Programming Boards category; Here's the problem: First your program will ask the user how manys names will be inputed. Number of names will ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    204

    Linked list question

    Here's the problem:
    First your program will ask the user how manys names will be inputed. Number of names will not exceed 100. Then ask the user for the names. Names will be in the format of "Last,First,age" with nospaces and there will always be three fields. Assume the user will always use this format. The names string will be at most 40 characters. After the user has inputed the names, ask how are they to be sorted. They are sorted by either last, first, or age. Then print the names out in sorted order. For people who have the same last name, sort by first name. For people with the same age, sort by last name and if that is also the same sort by first name. For people with the same first name, sort by last name. No two people will have the same first and last name.
    I have almost everything done, except the data structure and sorting part. I'm trying to set up a linked list to store the information input by the user and sort them from there, so I wrote this:
    Code:
    struct person {
        char last_name[40];
        char first_name[40];
        int age;
    };
    
    struct node {
        struct person;
        struct node *next;
    };
    The question is: will that kind of linked list work and am I going to be able to do the sorting part with it? Thanks.

  2. #2
    UT2004 Addict Kleid-0's Avatar
    Join Date
    Dec 2004
    Posts
    656
    Quote Originally Posted by caduardo21
    ...will that kind of linked list work?
    Yes it shall.
    Quote Originally Posted by caduardo21
    ...am I going to be able to do the sorting part with it?
    Yes you shall, with something like this using qsort:
    Code:
    customCompare( const void *a, const void *b )
    {
        const struct person *a1 = ( const struct person * )a;
        const struct person *b1 = ( const struct person * )b;
        if( strcmp( a1->first_name, b1->first_name )  > 0 )
            return 1;
        else if( I'm too lazy to type this up )
            return sajdflkasjf blah.. lol But you get the point!
    }
    
    qsort( createAPointerThatsAnArrayOfAllOfTheStructPersons( ), 
           getSizeOfLinkedList( ), 
           sizeof( struct person ), 
           customCompare( ) );

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,442
    > am I going to be able to do the sorting part with it?
    Yes, but it is a painful process and rather slow for long lists, and on the tricky side to get right.

    If you have
    a->c->b->d
    To swap b and c, you have to do
    temp = a->next;
    a->next = c->next;
    b->next = temp;

    Then it gets extra messy when you want to change the head or tail of the list for example.

    Creating an array of pointers as per Kleid-0's suggestion is an alternative since you can then use qsort().

    Once sorted, recreating the links is just a loop which does something like this
    array[i]->next = array[i+1];
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 03:05 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21