help me pleeeez? how do i solve this programme by c++

Discussion in 'Mac Programming' started by nnose, Apr 4, 2008.

  1. macrumors newbie

    Joined:
    Apr 3, 2008
    #1
    ineed help plz?

    --------------------------------------------------------------------------------

    how do i solve this programme by c++?
    struct node
    {
    int id;
    char *name;
    node *next;
    };
    class list
    {
    private:
    node *head;
    }
    how can i write a fun called sort this function sorts students records in the list in an ascending order.
    note: we load student record from a text file and store them into linked list.
    just i want the fun which sort?
    plz help me?
     
  2. macrumors G4

    Eraserhead

    Joined:
    Nov 3, 2005
    Location:
    UK
    #2
    Compare the strings using some sort of algorithm, like Quick Sort or Merge Sort or Insertion Sort, depending on what you've been taught.
     
  3. macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #3
    If you want to put the nodes into an array, then rebuild the list, there are functions to do these sorts for you on arrays already.
    man qsort
    You just need to write a comparison function that takes two nodes, and returns the proper values. It's something like -1 if A is less than B, 0 if they are equal, 1 if B is less than A. Then you'll get back a sorted array, and you can reconstruct the list quickly from that.

    Otherwise:
    http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

    This page details how to implement a mergesort on a singly linked list like the one you have.

    -Lee
     
  4. macrumors G4

    Eraserhead

    Joined:
    Nov 3, 2005
    Location:
    UK
    #4
    ^^ Isn't quicksort generally easier to implement though?
     
  5. macrumors G4

    Joined:
    Jan 5, 2006
    Location:
    Redondo Beach, California
    #5
    I'm not going to do your homework for you but I'll give a big hint: Look at just to items in your list. If they are in order do nothing. If they are out of order swap them. Continue looking until all items required that you do nothing. Now, see what I've done? I've broken the problem down into smaller problems like (1) compare to items, (2) swap and (3) get next two items from list. Continue like this, breaking the problem down into smaller parts untill each part has an ovious way to code it.

    The other solution is to realize that this is a common example in many introductory text books. Find a book on "data structures" and I bet sorting a list in in there. I can't believe this is not covered by Knuth.
     
  6. macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #6
    http://www.openasthra.com/c-tidbits/sorting-a-linked-list-with-quicksort-simple-algorithm/

    Without moving it to an array, I don't believe you can quicksort a singly-linked list like this one. The link above has a quicksort for a doubly-linked list. You should come up with a way to do this on your own, though, as this is likely an assignment. Whether or not you end up using the built in sort methods, you should write something that will compare 2 elements, and build from there. No matter what kind of algorithm you use (other than bucket sort, but I doubt that's what you'll use) you will need to do comparisons between elements.

    -Lee
     
  7. thread starter macrumors newbie

    Joined:
    Apr 3, 2008
    #7
    need help plz?

    plz i need the fun that sort a doubly linked list in c++.
    plz help me

    [Moderator note: threads merged]
     
  8. macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #8
    http://forums.macrumors.com/showthread.php?t=465601

    In the thread above you asked almost the exact same question. The list being doubly-linked rather than singly-linked doesn't change things much in terms of sorting algorithms, as most don't need to move backwards in the list. Refer to the original thread, and the suggestions and links provided.

    -Lee
     
  9. macrumors 65816

    Sbrocket

    Joined:
    Jun 3, 2007
    Location:
    /dev/null
    #9
    Some school must have a project due soon or something. :rolleyes:
     
  10. macrumors 6502a

    Sayer

    Joined:
    Jan 4, 2002
    Location:
    Austin, TX
    #10
    Epic Fail

    Compsci classes must be so frustrating. Do they actually teach anything at all or expect you to already know unix C/C++?
     
  11. thread starter macrumors newbie

    Joined:
    Apr 3, 2008
    #11
    thanks alot 4 help
    realy thanks
     

Share This Page