Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Swapping Linked List Nodes in C... YEARGGH!
Options
-
04-12-2007 5:24amI have been trying to simply swap two nodes in a linked list for fcking ages... tried so many ways and each time it hasn't worked... I really need help, this is driving me crazy!
ok so here is one of the (failed) attempts:typedef struct lnode { void *data; lnode *next; }llnode; // I understand how completely wrong this is, but it's like // my 50th attempt, i've tried the more straightforward stuff void swapNodes(lnode **n1,lnode **n2) { lnode *temp; temp = *n1; *n1 = *n2; n2 = &temp; }
so any help would be greatly appreciated!0
Comments
-
Just a quick glance, you seem to have all the right elements, but you've made things over complicated for yourself!
In your structure declaration, your data value , did you mean it to be a pointer? Typically it wouldnt be a pointer, but something like "int data".
Only the second member would be a pointer, as it points to the next list structure.
So with that in mind, some of your dereferencing has become a bit muddled, you should only need one level indirection (*) for your swap function, not two (**) . there should be no pointers to pointers needed here
your passing in **, you should only need *lnode *temp; temp = *n1;
Here, you've created a pointer of type lnode called temp, but you've set it equal to what n1 points at, rather than the address of where n1 structure is.
try simplytemp = n1;
So as a starting point, make your "void *data" an "int data", and try rethink what your trying to do,0 -
Nothing wrong with data in a linked list being a pointer, and it doesn't make any difference to what he's trying to do here.
Almost there Jimmy.. like ianhobo said, just pass in single pointers as parameters and swap them around like they were regular datatypes (ie no dereferencing).0 -
Thanks guys, i got it early this morning
See I had tried the simple swapping regular pointers before that and for some reason I lost a pointer in the operation so I rewrote it to return the new first pointer and it worked. Here is what I did, it had an element of luck about it, what do you guys think, it works but would it be what you would expect?lnode* swap(lnode *n1, lnode *n2) { lnode *temp; temp = n2->next; n2->next = n1; n1->next = temp; return n2; }
for some reason if i dont return n2 it doesn't work in my list0 -
Looks fine.
What are you doing with the returned pointer?0 -
Looks fine.
What are you doing with the returned pointer?
well it was for adjacent nodes and it wouldnt work unless i returned a pointer so i called it likefirstpointertoswap = swap(first,second)
but now I need to know something else.
If I have a Linked list where the the data fields are void pointers (so pointers to any type)
when I free each node, will that free the stuff pointed to by the void data pointers?
More importantly, when I allocate memory for a node (defined above) that doesn't allocate memory for the data does it?0 -
Advertisement
-
YEAARGH, I wrote it in what I thought was C (compiling in visual C++).
But now I have changed the name ending to .c it doesn't compile! million errors!
Can anyone have a glance at this and tell me if I have used anything that isn't C specific?!// constants used for setting the order of list #define ORDER_NONE 1 #define ORDER_ASCENDING 2 // defines one list node // internally used by linked list typedef struct lnode { void *data; struct lnode *next; }lnode; //defines what each list will have // user will see this typedef struct llist { lnode *head; int order; int (*compareFunc)(void *data1, void *data2); }llist; /* ======================= function prototypes ======================= */ void add (llist &list, void *data); void removeFirst (llist &list); void setOrder (llist &list,int order); void insertBefore (llist &list, lnode *target,lnode *prev, void *data); void freeListMemory (llist &list); void freeNodes (lnode *head); void* getFirst (llist &list); lnode* newNode (void *data); llist newList (); bool isEmpty (llist &list); int compareInts (void *x, void *y); // for comparing two ints, not used void print (llist &list); // for debugging, prints ints lnode* swap (lnode *n1, lnode *n2); //no longer used /* ===================== getFirst returns a pointer to the first data element in the list ===================== */ void* getFirst(llist &list) { if(isEmpty(list)) return NULL; else return list.head->data; } /* ===================== removeFirst Removes and deletes the first node in the list ===================== */ void removeFirst(llist &list) { if(isEmpty(list)) return; lnode *second; second = list.head->next; free(list.head); list.head = second; } /* ==================== newList Returns a new initialized list ==================== */ llist newList() { llist list; list.head = NULL; return list; } /* ================= setOrder Sets the method for adding items to the list ORDER_NONE - the data will be appended to the end of the list ORDER_ASCENDING - the data will be put in lower to higher order ================= */ void setOrder(llist &list,int order) { list.order = order; } /* =============== isEmpty Determines if the list is empty =============== */ bool isEmpty(llist &list) { if(list.head == NULL) return true; else return false; } /* ================= Add Adds a new node with the data to the list ================= */ void add(llist &list, void *data) { lnode *curr; lnode *prev; switch(list.order) { case ORDER_NONE: //list is empty if(isEmpty(list)) { list.head = newNode(data); } //list is not empty so traverse the list and add the node else { curr = list.head; while(curr->next) { curr = curr->next; } curr->next = newNode(data); }break; case ORDER_ASCENDING: if(isEmpty(list)) { list.head = newNode(data); } else { curr = list.head; prev = NULL; //therein lies da rub while((list.compareFunc(data,curr->data)) > 0 ) { prev = curr; if(curr->next) curr = curr->next; else { curr = NULL; break; } } insertBefore(list,curr,prev,data); } } } /* ================= freeListMemory Traverses a list releasing each nodes' memory ================ */ void freeListMemory(llist &list) { if(isEmpty(list)) return; freeNodes(list.head); list.head = NULL; } /* ================= freeNodes Releases the memory of all nodes starting with the head ================= */ void freeNodes(lnode *head) { if(head->next) freeNodes(head->next); free(head); } /* ================== insertBefore attempts to insert the data before the target node in the list ================== */ void insertBefore(llist &list, lnode *target,lnode *prev, void *data) { lnode *newnode; //nodes given dont exist if(!target) { target = newNode(data); prev->next = target; return; } newnode = newNode(data); if(isEmpty(list)) { list.head = newnode; } //target is the head else if(!prev) { list.head = newnode; newnode->next = target; } else { prev->next = newnode; newnode->next = target; } } /* ================== swap swaps two nodes (not used anymore) ================== */ lnode* swap(lnode *n1, lnode *n2) { lnode *temp; temp = n2->next; n2->next = n1; n1->next = temp; return n2; } /* ================ newNode Creates space for a new node and gives it data ================ */ lnode* newNode(void *data) { lnode* node = (lnode*)malloc(sizeof(lnode)); node->data = data; node->next = NULL; return node; } /* ======================= print for debugging - prints list of ints ======================= */ void print(llist &list) { lnode *curr; if(isEmpty(list)) return; curr = list.head; while(curr) { int *pInt = (int*)(curr->data); printf("%d\n",*pInt); curr = curr->next; } } int compareInts(void *x, void *y) { int a = *(int*)x; int b = *(int*)y; if(a > b) return 1; else if(a < b) return -1; else return 0; }
Thanks0 -
What are some of the errors that your getting?
And type of file was it before?
Is this for a college project or work? Did you write it all yourself?? hmmm
Because some parts of it would have some generally advanced C concepts, well beyond the complexity of understanding linked lists anyway.
Just curious
Regarding your memory question, if you declared, you delete it0 -
What are some of the errors that your getting?
And type of file was it before?
Is this for a college project or work? Did you write it all yourself?? hmmm
Because some parts of it would have some generally advanced C concepts, well beyond the complexity of understanding linked lists anyway.
Just curious
Regarding your memory question, if you declared, you delete it
I'll take it as a compliment that you question whether I wrote it! Yea I did! This is for learning btw.
Ok so the errors, I have only started getting them since I made it a .c instead of a .cpp. I get about 62 of these "error C2143: syntax error : missing ')' before '&'" argggh and have no idea why its happening!0 -
ha ha I only question mainly because of your funky function pointer in one of your structs,
ok, I don't have MSVS here, its eclipse for me, so ill copy and paste and see what happens.
I presume its just the normal includes your using. stdio.h, anything else?
But there is something questioning in my head whether the referencing might differ in c and cpp?
What happen if you pass the list node as * rather than &?
Even change it for just one of the functions, and see if the error goes away....
I'l get back to you in a while0 -
ha ha I only question mainly because of your funky function pointer in one of your structs,
ok, I don't have MSVS here, its eclipse for me, so ill copy and paste and see what happens.
I presume its just the normal includes your using. stdio.h, anything else?
But there is something questioning in my head whether the referencing might differ in c and cpp?
What happen if you pass the list node as * rather than &?
Even change it for just one of the functions, and see if the error goes away....
I'l get back to you in a while
thanks! The only includes i have are stdlib and stdio0 -
Advertisement
-
it appears that pass by reference of the form
void fnct(int &var);
is c++ only, C doesn't appear to support this passing type
http://www.techiwarehouse.com/cms/articles.php?cat=18 (half way down)
http://www.maths.cam.ac.uk/undergrad/catam//ccatsl/manual/node50.html
What you will have to do, and what works in the copy and paste of your code that I did, was to remove your '&' from your function prototpes and replace with '*'.
The consequence of this is that throughout your code you will have to change all your functions from x.y->z to x->y->z
It is a bit confusing though, the compiler that I use in work *does* suppport it, but its a custom compiler for a specific paltform, but what I've read this morning seems to suggest that in general, you can't do it in C.
Hope that helps!
Anyone else any thoughts, explanations?0 -
it appears that pass by reference of the form
void fnct(int &var);
is c++ only, C doesn't appear to support this passing type
http://www.techiwarehouse.com/cms/articles.php?cat=18 (half way down)
http://www.maths.cam.ac.uk/undergrad/catam//ccatsl/manual/node50.html
What you will have to do, and what works in the copy and paste of your code that I did, was to remove your '&' from your function prototpes and replace with '*'.
The consequence of this is that throughout your code you will have to change all your functions from x.y->z to x->y->z
It is a bit confusing though, the compiler that I use in work *does* suppport it, but its a custom compiler for a specific paltform, but what I've read this morning seems to suggest that in general, you can't do it in C.
Hope that helps!
Anyone else any thoughts, explanations?
EDIT: errors gone
thanks a lot for the help! really appreciate it! So regarding freeing nodes... if I free a node that only frees the pointers? It wont free whats pointed to by the void pointers? And unless I malloc the actual data then it wont wont be on the heap? Like if i malloc the size of an lnode, that wont provide space or accomodate the space for the stuff that will be pointed to by the void pointers?0 -
if you have a structure/node which has a pointer to a data type as a member, you would have to declare memory for that pointer member to point at.
If you then create your nodes through malloc, you will have to free both the memory for the structure/node, and for the memory that its pointer member is pointing at.
Suggestion:
Create a freeNode function responsible for freeing the memory that is used for the node.
In here, have an if statement checking if this particular nodes pointer data member is null. If it is null, dont worry about it, if its not null free the memory, then free the memory for the node
Hope that helps
Ian0 -
Call Me Jimmy wrote: »if I free a node that only frees the pointers? It wont free whats pointed to by the void pointers? And unless I malloc the actual data then it wont wont be on the heap? Like if i malloc the size of an lnode, that wont provide space or accomodate the space for the stuff that will be pointed to by the void pointers?
Didn't you say you wrote this? ha ha
Your code/linked lists doesn't seem to be concerned with the memory of the structure members void pointers.
It accepts a pointer when createing a new node, and copies this pointer, so presumably this has been allocated elsewhere, so you still have to free this memory after the lists and nodes are free'd
think about the way that your function to create a new node works, and basically reverse this process,
But careful that the data which the structures are pointing to isn't still being used my some other function, as the list didn't allocate them, they could easily be in use by other functions.
If deleting the list and nodes is part of an exit function for example, then you could use what I said in my previous post about about freeing the member memory along with the node, but again, you have to be sure that the memory won't be free'd anywhere else either, freeing the same memory more than once can cause strange things to happen!
Having had a closer look at the code, don't just include the method of deleting the memory that the member pointer is pointing when freeing the nodes without fully understanding the implications.
ok, hope that hasnt caused any confusion!
Do you get me?0 -
Didn't you say you wrote this? ha ha
Your code/linked lists doesn't seem to be concerned with the memory of the structure members void pointers.
It accepts a pointer when createing a new node, and copies this pointer, so presumably this has been allocated elsewhere, so you still have to free this memory after the lists and nodes are free'd
think about the way that your function to create a new node works, and basically reverse this process,
But careful that the data which the structures are pointing to isn't still being used my some other function, as the list didn't allocate them, they could easily be in use by other functions.
If deleting the list and nodes is part of an exit function for example, then you could use what I said in my previous post about about freeing the member memory along with the node, but again, you have to be sure that the memory won't be free'd anywhere else either, freeing the same memory more than once can cause strange things to happen!
Having had a closer look at the code, don't just include the method of deleting the memory that the member pointer is pointing when freeing the nodes without fully understanding the implications.
ok, hope that hasnt caused any confusion!
Do you get me?
I did write it but i was assuming that freeing a node just freed everything associated with it, whereas now i have more knowledge (which makes it harder funnily enough ) I found out about the heap corruption as I tried yer first suggestion though! That implies that all data added has been malloc'd. I think I'm beginning to understand properly though thanks for the time anyway0 -
ok, good. It can be very confusing at times! I still get stumped quite often, and its back to the aul pen and paper to draw out my memory!I found out about the heap corruption as I tried yer first suggestion though! That implies that all data added has been malloc'd.
Probably the same memory has been free'd twice, (the list free function, and then later on in the code somewhere else), resulting in heap corruption.
As your list functions don't malloc any memory for the data members, all memory would have either been previously malloced, or are pointers to locally declared datathanks for the time anyway
Your welcome, glad I could help, anytime0
Advertisement