printing first linklist element in alphabetical order?

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.

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

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?

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.

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

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

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).

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?

Code:

while (current != NULL && current->next != NULL)

The last element doesn't get sorted.

Code:

   charNode *W = start->next->next;
   charNode* E = start->next->next;

You have two pointers to the same node.

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;

Did you read dwks' post?

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 :|

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.

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)