Thread: printing first linklist element in alphabetical order?

  1. #16
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    ok, thanks. i was working on getting the linked list in order with single chars before i move onto strings.


    Code:
    
    
       charNode *current = start;
       charNode *b = start;
       charNode *c = current->next->next->next;
    
       while (current != NULL && current->next != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
                       b = current;
                       b->next = c;
    
    
           }
    
            current = current->next;
        }
    
        return start;
    
    }

    returns B,D,C. i can't figure out how to put back A at the start.

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

    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).
    Code:
     charNode *current = start;
       charNode *first = start;
       charNode *b = start;
       charNode *c = current->next->next->next;
       charNode *a = current->next;
       ;
    b = a;

    makes

    BDA

    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.

    after the following line

    b->next = c;

    'A' is overwritten by C.
    makes
    BDC

    I can't figure out to put 'A' at the start.


    [EDIT]

    and also:
    Code:
     charNode *current = start;
       charNode *first = start;
       charNode *b = start;
       charNode *c = current->next->next->next;
       charNode *a = current->next->next;
       charNode *d = start->next;
    
     b = a;
     d->next = c;
     b->next = d;
                      d = b;
    ADC, b is missing.

    I tried c->next = b; at the end but it gives me an endless loop
    Last edited by Axel; 10-27-2005 at 11:23 PM.

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

    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.
    .
    Ok after numerous amounts of drawing and comparing the nodes, and following what you've suggested i can't get the correct answer. I have come close to the solution:
    Code:
    charNode *current = start;
       charNode *b = start;
       charNode *c = current->next->next->next;
       charNode *a = current->next->next;
       charNode *d = start->next;
    
       while (current != NULL && current->next != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
    
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
    
    
                d->next = c;
                a->next = b;
    
           }
    
            current = current->next;
        }
    
        return a;
    i get A,B,D,C.

    i expected A,D,B,C. I simply want to "swap" A and B. Any hints?

  4. #19
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    To swap two elements of a linked list, it's just a matter of changing pointers around.

    Suppose I have:

    A B C D

    in a linked list, and I wish to swap B and C. Currently A points to B, B points to C, and C points to D. What we want is for A to point to C, then C to point to B and then B to point to D. All you need to do is reassign the pointers, and make sure you don't lose any in the process.

    For instance, you could do something like:
    Code:
    B->next = C->next;
    /* B now points to where C used to, i.e. D */
    C->next = B;
    /* C now points to B */
    A->next = C;
    /* A now points to C (A used to point to B and B to C) */
    We now have

    A C B D

    as required. In order to swap two nodes, you need the two nodes to swap as well as the two nodes preceding them. In this example B was one of the nodes to swap as well as the node preceding C, so we only needed three nodes - in general you will need four. This is because not only do you need to swap the next elements of the nodes you are swapping, you also need to attach them to the previous node in the list correctly.

    If you write down what you have and what you want, you should be able to figure out how to get there. It is just a matter of working out which pointers need to be reassigned where, and then doing it in such a way that you don't lose any pointers - the easiest way to do this is using temporary variables.
    Last edited by lemnisca; 10-28-2005 at 07:20 AM.

  5. #20
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    in otherwords say if i had the following:

    N,S,W,E

    is there a simple way of putting "e" at the start with effecting the other nodes? i.e. i just want "E" to go at the start because it comes alphabetically first than the rest i.e. E,N,S,W

    another example

    C,B,A,D

    A,C,B,D
    Last edited by Axel; 10-28-2005 at 07:36 AM.

  6. #21
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    sorry lemnisca, i'll try that. But i was just intrested, is there an easy way to do (my previous post) i just want to place the lowest alphabetical character at the start without effecting anything else rather than walking through the whole thing

  7. #22
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    If you want the last node to go to the front, all you have to do is:
    Code:
    last_node->next = first_node;
    second_last_node->next = NULL;
    The last node now points to the start of the list, so it i the new start node. The second last node gets its 'next' element set to NULL to terminate the list (otherwise it would turn into a ring).

  8. #23
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
      charNode *current = start;
       charNode *N = start;
       charNode *S = start->next;
       charNode *W = start->next->next;
       charNode* E = start->next->next;
    
    
       while (current != NULL && current->next != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
    
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
    
              E->next = N;
              W->next = NULL;
              //  d->next = c;
              // a->next = b;
           }
    
            current = current->next;
        }
    
        return start;
    prints NSW.

    and

    last_node->next = first_node;

    say my list contained NSWE

    the last node is E so i put the first node after E

    now the list reads S,W,E,N

    second_last_node->next = NULL;
    second last node is E we place N to null as follows:

    S,W,E

    what happened to the swap of E?

  9. #24
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    while (current != NULL && current->next != NULL)
    The last element doesn't get sorted.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #25
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Code:
       charNode *W = start->next->next;
       charNode* E = start->next->next;
    You have two pointers to the same node.

  11. #26
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    still prints NSW

    Code:
      charNode *current = start;
       charNode *N = start;
       charNode *S = start->next;
       charNode *W = start->next->next;
       charNode* E = start->next->next->next;
    
    
       while (current != NULL && current->next != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
    
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
    
              E->next = N;
             W->next = NULL;
              //  d->next = c;
              // a->next = b;
           }
    
            current = current->next;
        }
    
        return start;

  12. #27
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Did you read dwks' post?

  13. #28
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Code:
    
    charNode *test(charNode *start)
    {
    
       charNode *current = start;
       charNode *N = start;
       charNode *S = start->next;
       charNode *W = start->next->next;
       charNode* E = start->next->next->next;
    
    
       while (current != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
    
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
    
              E->next = N;
             W->next = NULL;
              //  d->next = c;
              // a->next = b;
           }
    
            current = current->next;
        }
    
        return start;
    
    }
    still isn't what i expected :|

  14. #29
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    by the way i'm certain that none of the nodes are being skipped this time.

    Code:
    while (current != NULL)
        {
         
    
           printf("%c", current->cityname);
    
            current = current->next;
        }
    prints NSWE as soon as i put the "if" statement, i'm only getting NSW.

  15. #30
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    ok i figured it out:

    Code:
    if (current->next->cityname < start->cityname )
          {
    
             printf("%s %c %s", "\nFound a smaller character", current->next->cityname, "\n");
              E->next = N;
             W->next = NULL;
             start = E;
           }
    
        printf("\n%c\n", current->cityname);
    
            current = current->next;
        }
    
        return start;

    it only works with hard coded values :|

    in my if statement, it finds the shortest alphabetical character. I can't use that start = current->next; it just gives me a segmentation fault.
    Is there any way to do that will work on any data? i.e. it wont work with 2 nodes and not more than 5.

    Here's the complete code btw:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <string.h>
    
    struct charNode
    {
       char cityname[15];
       struct charNode *next;
    };
    
    typedef struct charNode charNode;
    
     void addElement(charNode **start, char city[], double numberone, double numbertwo);
    void printList(charNode *start, charNode *temp);
    charNode* newNode(char city[], double numberone, double numbertwo);
    charNode* getString(charNode *start);
    charNode *sort(charNode *start);
    
    int main()
    {
       charNode *start = NULL;
    
       start = getString(start);
       printList(start, start);
       start = sort(start);
       printList(start, start);
       return 0;
    }
    
    
    charNode* getString(charNode *start)
    {
    
            char *city1, *city2, *city3, *city4, *city5;
    
    
            if ((city1 = malloc(sizeof(char) * 15)) == NULL) {
            }
    
            strcpy(city1, "Carrot");
    
    
            if ((city2 = malloc(sizeof(char) * 15)) == NULL) {
            }
    
            strcpy(city2, "Apricot");
    
            if ((city3 = malloc(sizeof(char) * 15)) == NULL) {
            }
    
            strcpy(city3, "Bananna ");
    
            if ((city4 = malloc(sizeof(char) * 15)) == NULL) {
            }
    
            strcpy(city4, "Apple");
    
    
            if ((city5 = malloc(sizeof(char) * 15)) == NULL) {
            }
    
            strcpy(city5, "Pear");
    
    
            addElement(&start, city1,  28.8, 17.6);
            addElement(&start, city2, 5.6, 79.12);
            addElement(&start, city3, 55.3, 49.9);
            addElement(&start, city4, 22.22, 11.11);
            addElement(&start, city5, 22.22, 11.11);
    
    
        return start;
    }
    
     void addElement(charNode **start, char city[], double numberone, double numbertwo)
    {
    
       charNode *temp,*prev, *loc;
    
       temp = newNode(city, numberone, numbertwo);
    
    
       if (*start == NULL)
       {
          *start = temp;
       }
    
       else
       {
          loc = *start;
          prev = NULL;
    
          while (loc != NULL)
          {
             prev = loc;
             loc = loc->next;
          }
    
    
          temp->next = loc;
          if (prev == NULL)
          {
             *start = temp;
          }
          else
          {
             prev->next = temp;
          }
       }
    
    }
    
    
    charNode* newNode(char city[], double numberone, double numbertwo)
    
    {
    
       charNode *temp;
    
       temp = (charNode *) malloc(sizeof(charNode));
       if (temp == NULL)
       {
          printf("WARNING - Memory allocation error\n");
          exit(EXIT_FAILURE);
       }
    
    
       strcpy(temp->cityname, city);
    
    
       temp->next = NULL;
    
       return temp;
    }
    
    
    void printList(charNode *start, charNode *temp)
    {
    
       while (start != NULL )
       {
          printf("\n%s", start->cityname);
    
    
          start = start->next;
       }
           printf("\n");
    
    }
    
    
    
    charNode *sort(charNode *start)
    {
    
       charNode *current = start;
       charNode *N = start;
       charNode *S = start->next;
       charNode *W = start->next->next;
       charNode* E = start->next->next->next;
    
    
       while (current != NULL)
        {
          if (current->next->cityname < start->cityname )
          {
    
             printf("%s %s %s", "\nFound a smaller character", current->next->cityname, "\n");
    
              E->next = N;
              W->next = NULL;
              start = E;
           }
            current = current->next;
        }
    
        return start;
    
    }

    Carrot
    Apricot
    Bananna
    Apple
    Pear

    Found a smaller character (null)

    Apple
    Carrot
    Apricot
    Bananna


    notice how 'pear is skipped out' it only works with 4 nodes. any hints? (the same thing happens with single chars btw)
    Last edited by Axel; 10-29-2005 at 09:20 AM.

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