Printable View
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.
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 :cool: .
but i don't want to reorder the actual list. Only print whatever(1st) comes in alphabetical order and then go as normal
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.
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.
thanks for the suggestions.
lemnisca,
i tried what you suggested:
in my list i have B,C,,A,D,E.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;
}
it prints one "found a smaller character" as expected. I'm having trouble swapping them.
I tried
it just gives me the same order.Code:temp /* (B) */ = start->next; /* (A)*/
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.
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:
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.Code:Node *node;
for(node = start, node != NULL, node = node->next)
{
/* do stuff */
}
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:
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.Code:Node *first = start;
Node *current;
for(current = start, current != NULL, current = current->next)
{
if(/*current element comes before first*/)
first = current;
}
As i said, to prevent the linklist falling off the last element and giving me a segmentation fault.Quote:
Originally Posted by lemnisca
it's declared as a normal char char cityname in the struct.Quote:
What is cityname declared as? If it's a char *, you should be using strncmp to compare, not <.
If i don't swap them then how will the new re-ordered list be printed?Quote:
I'm not sure what you mean by 'swapping them'.
swapping the first alphabetical char that i find to the first element.Quote:
What exactly are you swapping?
Quote:
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.
do you see what i mean?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;
original list
BDCAE
after the above function is run i get:
BDCAE
should be
ADCBE
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.
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:
if (current->next->cityname < start->cityname)
{
printf("%s %s %s", "\nFound a smaller character", start->next->cityname, "\n");
}
printf argument mismatch for format d. Expected int got pointer to charCode:
printf("%d", current->next->cityname);
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.");
}
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.
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.Quote:
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.
like...?Quote:
if you want to compare strings, you must use something else.
thanks for the tip, i have to know how to find whever comes alphabetically first. I have no idea where to start :|Quote:
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.
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.
yep i forgot to mention tried both. strings.h gives me 'cannot find library'.Quote:
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.
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.Quote:
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
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)
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:
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.Code:strncmp(a, b, LENGTH)
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.
Quote:
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).
b = a;Code:charNode *current = start;
charNode *first = start;
charNode *b = start;
charNode *c = current->next->next->next;
charNode *a = current->next;
;
makes
BDA
Quote:
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:
ADC, b is missing.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;
I tried c->next = b; at the end but it gives me an endless loop
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:Quote:
Originally Posted by lemnisca
i get A,B,D,C.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 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:
We now haveCode: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) */
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:
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:last_node->next = first_node;
second_last_node->next = NULL;
prints NSW.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;
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?
The last element doesn't get sorted.Code:while (current != NULL && current->next != NULL)
You have two pointers to the same node.Code:charNode *W = start->next->next;
charNode* E = start->next->next;
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?
still isn't what i expected :|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;
}
by the way i'm certain that none of the nodes are being skipped this time.
prints NSWE as soon as i put the "if" statement, i'm only getting NSW.Code:
while (current != NULL)
{
printf("%c", current->cityname);
current = current->next;
}
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)
i guess i could hard code another temporary node, but then it won't work with lists that are less than 5. There's gotta be an easier way?