sort a linked list ???

This is a discussion on sort a linked list ??? within the C Programming forums, part of the General Programming Boards category; hi, the structure of my linked list looks like this : typedef struct tag{ char name[100]; int emp_id; float hrs_wkd; ...

  1. #1
    Registered User goran's Avatar
    Join Date
    Sep 2001
    Posts
    68

    Unhappy sort a linked list ???

    hi,

    the structure of my linked list looks like this :

    typedef struct tag{
    char name[100];
    int emp_id;
    float hrs_wkd;
    struct tag *next;
    }node;

    Now, while inserting, i insert it based on the employee id. I need to print the list based on the employee name. For this, i have to sort the linked list based on the employee name first. Does anybody have a function for the sorting a linked list ?

    thanks.
    I don't wait for the future; it comes soon enough.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    well how far have you got on your own? dont just ask for code until you have made an attempt at it yourself.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Sayeh
    Guest
    If your instructor wants you to actually rearrange your tree and replay it via traversal, this answer won't help you.

    In the "real world", where performance is a factor, you don't rearrange the data. That is cumbersome and slow. A professional would create a dynamic list of 'node*' to go with the tree. This is called an 'index' or 'hashing table'.

    Each time you create a new node, you would increase the node* list by one. Each time you eliminate a node you would eliminate the corresponding node* entry.

    This hashing table, in order to be useful, yet generic enough to be manipulated, quickly, is simply a list of pointers (node*). Each entry in the hash table contains a pointer to a node in the tree.

    You can then use qsort() and the hash table to sort the data by any field in the data, and then you simply rearrange your hash table. You can then zip through the hash table, replay nodes in the order they appear in the hash table, and voila! sorted.

    enjoy.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  3. Linked List Merge Sort
    By LostNotFound in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2003, 10:34 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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