PDA

View Full Version : help me pleeeez? how do i solve this programme by c++




nnose
Apr 4, 2008, 05:08 AM
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?



Eraserhead
Apr 4, 2008, 05:38 AM
Compare the strings using some sort of algorithm, like Quick Sort or Merge Sort or Insertion Sort, depending on what you've been taught.

lee1210
Apr 4, 2008, 10:58 AM
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

Eraserhead
Apr 4, 2008, 11:01 AM
^^ Isn't quicksort generally easier to implement though?

ChrisA
Apr 4, 2008, 11:11 AM
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?

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.

lee1210
Apr 4, 2008, 11:14 AM
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

nnose
Apr 11, 2008, 10:58 AM
plz i need the fun that sort a doubly linked list in c++.
plz help me

[Moderator note: threads merged]

lee1210
Apr 11, 2008, 03:10 PM
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

Sbrocket
Apr 11, 2008, 03:12 PM
Some school must have a project due soon or something. :rolleyes:

Sayer
Apr 11, 2008, 06:33 PM
Compsci classes must be so frustrating. Do they actually teach anything at all or expect you to already know unix C/C++?

nnose
Apr 12, 2008, 10:56 AM
thanks alot 4 help
realy thanks