How to sort a link list alphabetically? ( C Programming thru Linux gcc)?

Question

Generally, my link list will store a list of files and sub directories' name in a folder.

But now I'm having problem of sorting them alphabetically since I only learned how to sort a link list based on Integer ( ex. code / ID ).

I was thinking can I generate a number based on the file or sub directory name. Of cause this number should produced by every alphabets in the string and length of string as well. So I can sort them perfectly later. But i was non-stop thinking for almost a day I still cannot figure out how can I do it.

Anyone can advice ? or is there any other better way instead of this one?

Answer 1

The obvious answer to this is to use strcmp (from the standard string library) on the directory entry names. If you have a string a and a string b, strcmp(a, b) will return 0 if a and b are equal, an integer less than zero if a comes alphabetically before b and an integer greater than zero if a comes alphabetically after b.



This way you can most likely reuse the code you've written for sorting a linked list by integers. Just read the directory entry names (file names and subdirectory names) from the current directory.



Assuming you're either using a Linux system or programming through cygwin, you could always type 'man strcmp' in a shell to get information about the strcmp function.

Answer 2

1

Answer 3

Depending on how long your linked list is, you might have an option to do this:



Buffer a list of pointers which address at least some of the entries in the list, using a 'page table' structure that you could apply quicksort or a B+ tree sort to. That way you can pass buffer addresses to the sort rather than having to build a special sort routine which has a built-in linked list traversal to cover the whole linked list. The buffer addresses could be treated to a certain extent like binary sort index entries, at least as far as page insertion points goes; and if you partition the way quicksort does, you wouldn't need to worry about the pointers themselves as long as your compare routine dereferences them. Passing only the pointers to the data records requires an additional level of pointer indirection, because the pointers are in buffers rather than being encountered directly during a traversal, but it also frees the pre-sort ordering from the sort itself and no links in the list need be modified until you retrieve the sorted list from your sort routine.

Answer 4

Forget the integer sort. Won't work here. But you can compare two character strings using the strcmp() function, and on that basis, you can tell which one is "bigger" and order them accordingly.



Hope that helps.

Answer 5

Use the STL. Standard template library.



Containers:

http://www.cplusplus.com/reference/stl/



Algorithms (including sort):

http://www.cplusplus.com/reference/algorithm/



Here's the sort function:

http://www.cplusplus.com/reference/algorithm/sort/