Thread: printing first linklist element in alphabetical order?

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    printing first linklist element in alphabetical order?

    I'm not sure how to approach this problem. I want to print the node that comes first in alphabetical order(not the whole thing, but only the one that's first in alphabetical order) e.g. . In my structure i.e D,C,A,B would become ADCB. i have a name should i can compare it but since there's so many possibilties i'm kind of conused. I've tried searching and haven't found any information on what i'm trying to do. Any help would be appreciated.

  2. #2
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    Do you know any type of sorting??
    Heard of bubble,heap,quick sort etc.I think you must have in arrays.Apply the same concepts here with some pointer play .
    Long time no C. I need to learn the language again.
    Help a man when he is in trouble and he will remember you when he is in trouble again.
    You learn in life when you lose.
    Complex problems have simple, easy to understand wrong answers.
    "A ship in the harbour is safe, but that's not what ships are built
    for"

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    but i don't want to reorder the actual list. Only print whatever(1st) comes in alphabetical order and then go as normal

  4. #4
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    Thats even more easier if you can afford some space.Declare a flag variable 1 for each structure.Instead of changing pointers.find the first element of list and set a flag variable to 0.search again the next first untill all flag variables are 0.
    Long time no C. I need to learn the language again.
    Help a man when he is in trouble and he will remember you when he is in trouble again.
    You learn in life when you lose.
    Complex problems have simple, easy to understand wrong answers.
    "A ship in the harbour is safe, but that's not what ships are built
    for"

  5. #5
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Declare a char * and initialise it to point to the first string in the list. Then iterate through the list. For each node, check if the string comes before (alphabetically) the one currently pointed to. If it does, change your pointer to point to the current node. At the end of your loop, you will have a pointer pointing to the element which comes first alphabetically.

    This is exactly the same algorithm as for finding the minimum of an array. The only difference is that you are using linked lists.

    Also, it doesn't have to be a pointer, but I would recommend it unless there's some reason to copy the string, e.g. if the strings will change and you still need it.

  6. #6
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    thanks for the suggestions.
    lemnisca,

    i tried what you suggested:
    Code:
    void *test(charNode *start)
    {
       charNode *temp = start;
       int i = 0;
    
       while (start != NULL && i < 4)
        {
          if (start->next->cityname < temp->cityname )
                {
                    printf("\nFound a smaller character");
                    // temp = start->next;
                }
                i++;
    		start = start->next;
        }
    in my list i have B,C,,A,D,E.
    it prints one "found a smaller character" as expected. I'm having trouble swapping them.

    I tried

    Code:
     temp /* (B) */ = start->next; /* (A)*/
    it just gives me the same order.

    Also is there a better way of knowing when the end of the list is? I tried taking out i < 4 (it's 4 because it wont run with 5 because i have to use next->) but it just gives me an endless loop

    by the way i'm just using one char at the moement to keep things simple.
    Last edited by Axel; 10-27-2005 at 02:39 AM.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    What is cityname declared as? If it's a char *, you should be using strncmp to compare, not <.

    What exactly is the point of the variable i? You are using a linked list, you don't index it, why do you need a loop counter at all? Moreover, you are comparing i against arbitrary values. There is a very common idiom for iterating through a linked list, it goes like this:
    Code:
    Node *node;
    
    for(node = start, node != NULL, node = node->next)
    {
        /* do stuff */
    }
    This is the simplest and most logical way to iterate through a linked list. The 'next' element in the last node of your list should be a null pointer, indicating the end of the list.

    I'm not sure what you mean by 'swapping them'. What exactly are you swapping? I thought you wanted to find the lexicographically smallest element in your list? You shouldn't need to swap anything, it should just go like this:
    Code:
    Node *first = start;
    Node *current;
    
    for(current = start, current != NULL, current = current->next)
    {
        if(/*current element comes before first*/)
            first = current;
    }
    That's it, that's all it is. At the end of that loop, first points to the element which comes first alphabetically. As I said before, it's the same as finding the minimum of an array. The only difference is the way you iterate through it.

  8. #8
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by lemnisca

    What exactly is the point of the variable i? You are using a linked list, you don't index it, why do you need a loop counter at all?
    As i said, to prevent the linklist falling off the last element and giving me a segmentation fault.


    What is cityname declared as? If it's a char *, you should be using strncmp to compare, not <.
    it's declared as a normal char char cityname in the struct.

    I'm not sure what you mean by 'swapping them'.
    If i don't swap them then how will the new re-ordered list be printed?


    What exactly are you swapping?
    swapping the first alphabetical char that i find to the first element.



    if(/*current element comes before first*/)
    first = current;
    }

    Ah! i see what you mean now. Not exactly what i want.

    If i have the following:

    D,BA,C

    A is smaller then D so A should replace D and D should replace A. Do you see what i mean? Finding the first character (that comes alphabetically) and in list and put it at the start. The others should be left alone. I don't want *just* the lowest alphabetical order.


    and with my approach, you can actually say if char is less then another char. Try printf("%d", c); on a char you'll get a numerical representation which can be used to compare if a character is less than another one.
    Last edited by Axel; 10-27-2005 at 06:18 AM.

  9. #9
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
    
            charNode *first = start;
            charNode *current;
            for(current = start; current != NULL && current->next !=NULL ; current = current->next)
            {
                if (current->next->cityname < start->cityname) /* if the current citynames, next city name is less than the first one */
                {
                    printf("%s %c %s", "\nFound a smaller character", start->next->cityname, "\n");
                     first = current; /*swap them around */
    
                }
            }
    
            return first;
    do you see what i mean?


    original list
    BDCAE

    after the above function is run i get:

    BDCAE

    should be

    ADCBE
    Last edited by Axel; 10-27-2005 at 06:29 AM.

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    oh and i just tried strncmp for the sake of it. It finds the lexicographically smallest element in my list but i dont exactly want that.

    Now comparing a char to another char works (i.e. which ever ones smaller) but it doesn't work on a whole string.

    Code:
     if (current->next->cityname < start->cityname)
                    {
                        printf("%s %s %s", "\nFound a smaller character", start->next->cityname, "\n");
                    }
    and the following doesn't work (it should return a numerical value so i can compare if the string is smaller(i.e. if it comes alphabetically with the one i'm comparing to).



    Code:
    printf("%d", current->next->cityname);
    printf argument mismatch for format d. Expected int got pointer to char


    How can i compare if a whole string comes first alphabetically?

    i.e.

    Denmark 28.80 17.60
    Bahamas 5.60 79.12
    Canada 55.30 49.90
    Antarctica 22.22 11.11

    Antarctica is the smallest in this case.


    and just an example where i was comparing the current element to the next

    Code:
    
        char b = 'B';
        char a = 'A';
    
        if (b > a)
        {
            printf("It's greater in value, therefore it should be swapped.");
        }
    Last edited by Axel; 10-27-2005 at 07:13 AM.

  11. #11
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Ok, your original post asked how to print the first element alphabetically in your list. From what you're saying now, you want to move the element which comes first alphabetically to the head of the list. This is an entirely different problem, please ask questions more clearly.

    If you do not want to order your elements in the way strncmp does it, there are other functions available such as strncasecmp. If none of the standard library functions do what you want, you can write your own comparison function. Whatever you do though, < will only ever work on a single char, if you want to compare strings, you must use something else.

    Having a loop counter is not a good way to find the end of a linked list. The whole idea of a linked list is that you don't have to know how long it is. You should set the last node's 'next' element to NULL, as I said earlier, and test for this to detect that you have reached the end of the list.

    Ok, so, I've told you how to find the first element. Now what you want to do is move it to the start of the list. Supposing you have a list like this:
    B-D-A-C
    You find that A is the first element, so you wish to move it to the start of the list. To do that, all you have to do is set A's 'next' element to point to B (the current start node). However, you also need to change D, otherwise D will still point to A and you will end up with a circle, and C off on its own not doing anything useful. So you need to change D's 'next' element to point to C. It is a good idea to do this before you set A to point to B, otherwise the pointer to C will be lost. You won't know where it is and so won't be able to make D point to it.

    Edit: The reason your printf doesn't work is that you've told it you want to print an integer (%d) but you are passing it a char *. Use %s to print a string.
    Last edited by lemnisca; 10-27-2005 at 07:45 AM.

  12. #12
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    If you do not want to order your elements in the way strncmp does it, there are other functions available such as strncasecmp. If none of the standard library functions do what you want, you can write your own comparison function.
    I've tried strncasecmp but i get missing prototype. I've included string.h. Looking at the function reference it mentions, lexically greater; which isn't what i'm exactly after for.

    if you want to compare strings, you must use something else.
    like...?


    Ok, so, I've told you how to find the first element. Now what you want to do is move it to the start of the list. Supposing you have a list like this:
    B-D-A-C
    You find that A is the first element, so you wish to move it to the start of the list. To do that, all you have to do is set A's 'next' element to point to B (the current start node). However, you also need to change D, otherwise D will still point to A and you will end up with a circle, and C off on its own not doing anything useful. So you need to change D's 'next' element to point to C. It is a good idea to do this before you set A to point to B, otherwise the pointer to C will be lost. You won't know where it is and so won't be able to make D point to it.
    thanks for the tip, i have to know how to find whever comes alphabetically first. I have no idea where to start :|

  13. #13
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Look at the manpage for strncasecmp, it will tell you that you need to include strings.h. Easy to miss I suppose, but that's what you need.

    To compare strings, you will need a function. There is no operator in C to do it. You have a number of functions at your disposal. strncmp will compare strings lexicographically - this is very similar to alphabetically, except that it includes numbers and other characters. Unless you know for certain your strings won't contain anything but letters, it's probably a good idea to compare lexicographically rather than alphabetically - they are identical for letters anyway. strncasecmp will do the same thing, except that it will not distinguish between captial and lowercase letters. If you really don't want to sort lexicographically, and only wish to consider letters, then write your own function to do so. If you want to do that, however, I'd recommend you make sure to check for non-alpha characters and deal with them in a sensible manner.

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Look at the manpage for strncasecmp, it will tell you that you need to include strings.h. Easy to miss I suppose, but that's what you need.
    yep i forgot to mention tried both. strings.h gives me 'cannot find library'.


    To compare strings, you will need a function. There is no operator in C to do it. You have a number of functions at your disposal. strncmp will compare strings lexicographically
    Ok, i'm kind of confused. I don't want to go into all the trouble of writing my own function if it can be done with the functions already available. I'm not even sure if strcmp will actually do what i've asked for after playing around with it.

    You said that if the string won't contain anything but number it's a good idea to compare them lexicographically. I don't think strcmp would work in my situation because you provide it 3 parameters the string, string to compare and compares the length of the string if the compared string is greater then it returns 0. Is that right? Unless you can show me an example (the one provided in the C++ reference page doesn't seem like what i'm trying to do)
    Last edited by Axel; 10-27-2005 at 08:39 AM.

  15. #15
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    strncmp will almost certainly do what you want. I'm not sure why you are making such a distinction between lexicographic comparison and alphabetic comparison as for letters they are identical.

    If you do:
    Code:
    strncmp(a, b, LENGTH)
    strncmp will return a negative number if a comes before b, zero if they are the same, and a positive number if a comes after b.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting
    By penny_731729 in forum C Programming
    Replies: 3
    Last Post: 04-28-2003, 10:56 AM
  2. Suspicious Pointer Conversion
    By mr_spanky202 in forum C Programming
    Replies: 35
    Last Post: 04-11-2003, 12:35 PM
  3. Binary searches
    By Prezo in forum C Programming
    Replies: 4
    Last Post: 09-10-2002, 09:54 PM
  4. Quick LinkList Help!!adding at the End
    By simly01 in forum C++ Programming
    Replies: 13
    Last Post: 07-28-2002, 07:19 AM
  5. Replies: 11
    Last Post: 04-18-2002, 08:56 PM