Hello there.
I have a problem regarding node deletion in singly-linked lists in C. What happens is that I can't hold the previous node efficiently. Here is the code I use. - struct lista *search (struct lista *list, int m, char *s, struct lista *previous)
-
-
.........
-
-
Not problem-related code goes here....
-
-
..........
-
-
if (choice == 'd')
-
{
-
if (previous==NULL)
-
{
-
previous=list->next;
-
return previous;
-
}
-
else if (previous!=NULL&&list->next!=NULL)
-
{
-
previous->next=list->next;
-
-
}
-
else if (previous!=NULL&&list->next==NULL)
-
{
-
previous->next=NULL;
-
-
}
-
}
-
-
else
-
{
-
previous=search(list->next,m,s,previous->next);
-
return previous;
-
}
-
The parameters: *list is a pointer to a full (or empty) list and *previous points to NULL at the beggining.
Don't mind about int m and char *s. They are used elsewhere in the function. Also the "else" on line 28 DOES NOT come from the first "if" but from a string compare of 2 strings not written on the code fragment. If it is 0 then we have found the string, otherwise the function calls itself until the 2 strings match or the list is finished.
The problem is, I can't manage to delete a node if it isn't the head one. I can't find a way to set the "previous" value to the next node once one failed string compare has passed. And if I try setting "previous->next=list" just before the function calls itself again I have a memory error. I even tried malloc but it doesn't seem to work.
Any help appreciated. :)
42 4492
Hint: keep the address of the pointer to the next element and update it in a simple
list traversal loop. At the start you can take the address of the 'head pointer'.
kind regards,
Jos
Personally, I'd decouple the 'deletion of a node' routine from the 'search for a node' routine. It makes for cleaner and more understandable code.
The search routine could return a true or false stating if it found a node that matches the search criteria and update a pointer to the previous node (you would pass a double pointer to the function). In this way you can delete any node:
In this example, you have two list elements: tail -> NODE1 -> NODE2 <- head
If the search found NODE1, it would return true and a pointer to NODE1. If the search found NODE2, it would return true and a pointer to NODE2. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).
Hope that helps.
Adrian
Thanks but I can't understand how exactly I am going to do this. What I do in simple words is save the previous node just before I call the function again. Something like: - struct list *previous;
-
previous=list;
-
function_a(parameter_a, parameter_b, ..., list, previous);
That way I have the last node transferred to the function however I don't know what to do from there. Supposing I want to delete a middle note of the list, if I just do: - previous->next=list->next;
Then I can't return "previous" cause it won't be the full list. Sorry if I am making little sense. :-/
Edit: Just saw your post Adrian. Will check it out. :)
Edit: Just saw your post Adrian. Will check it out. :)
Post back if you have any questions.
Adrian
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
You don't need two pointers, all you need is the address of a pointer to the
node to be deleted or found or whatever.
Assume 'head' is a pointer to the first element of your list; also assume that
the type of a list element is a node_t; the following will do the job: -
for (node_t** next= &head; *next; next= &((*next)->next))
-
if ((*next)->datum= wanted_datum) return next;
-
return null;
If you want to return a pointer to a wanted element simpy return *next. If you
want to delete that node do this:
kind regards,
Jos
Jos, I was thinking why the double pointer? Then I realised that you are returning a double pointer so that it can still be followed and yet you can update it. Clever. ;)
I've notice in this entire discussion, that when a node is 'deleted' it is simply unlinked. Avon, I hope you are doing cleanup as well as unlinking the node.
Adrian
Jos, I was thinking why the double pointer? Then I realised that you are returning a double pointer so that it can still be followed and yet you can update it. Clever. ;)
Adrian
I'm just a bag of old tricks ;-)
kind regards,
Jos
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
It looks like you are responding to me.
I made a mistake. It was supposed to read:
If the search found NODE1, it would return true and a pointer to NULL. If the search found NODE2, it would return true and a pointer to NODE1. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).
Sorry 'bout that chief. ;)
Adrian
It looks like you are responding to me.
I made a mistake. It was supposed to read:
If the search found NODE1, it would return true and a pointer to NULL. If the search found NODE2, it would return true and a pointer to NODE1. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).
Sorry 'bout that chief. ;)
Adrian
In the case of what Jos stated, you would instead of returning a true/false and updating a pointer, you would return a double pointer. If the pointer is NULL, then you didn't find anything. If the pointer is not NULL, then what is being pointed at is the pointer you need to update, and what that second pointer is pointing at is the node that contains the found item.
Adrian
Thanks a bunch for your time guys, though I can't seem to understand what exactly you are saying. Must be my poor English. If someone of you guys could post the method of pointing to the previous node (not code or anything like that(so as not to break the rules :-P), just the logic) I'd be really obliged. :-)
Thanks a bunch for your time guys, though I can't seem to understand what exactly you are saying. Must be my poor English. If someone of you guys could post the method of pointing to the previous node (not code or anything like that(so as not to break the rules :-P), just the logic) I'd be really obliged. :-)
Jos already did that in post 7.
Adrian
By the way Adrian, yes I'm going to free the memory too, once I find out how to unlink them first. :-/
By the way Adrian, yes I'm going to free the memory too, once I find out how to unlink them first. :-/
Draw a small singly linked list on paper and use your finger as the pointer to
a pointer to an element. Reread my reply again and move your finger to the
correct positions; you'll figure it out.
kind regards,
Jos
Ok then, I'll try that. Thanks. Although may I ask for a favor? Can you rewrite the above snip of code to something less condensed so I can follow the flow more easily? :-)
Ok then, I'll try that. Thanks. Although may I ask for a favor? Can you rewrite the above snip of code to something less condensed so I can follow the flow more easily? :-)
Yeah, I found it a little hard to read too. I use braces for all my loop and if bodies. -
for (node_t ** next = &head
-
; *next != NULL
-
; next = &((*next)->next)) {
-
/* you may require a function call here if equality cannot be determined
-
using == */
-
if ((*next)->datum == wanted_datum) {
-
return next;
-
}
-
}
-
return NULL;
There are other things that I do not like about the style Jos used (such as more than one exit point in a function), but everyone has their own and this will work.
Adrian
Ah I think I got it. You are basically pointing to a pointer that is pointing the current element. That way you can manipulate the element pointer, using the pointer pointing at the element pointer. (Heh if you read this quickly it's going to be fun :P).
Am I right about this? However when I try to put something similar in my project I get "invalid type arguments to ->". Sorry for wasting your time, and thanks again. :)
Ah I think I got it. You are basically pointing to a pointer that is pointing the current element. That way you can manipulate the element pointer, using the pointer pointing at the element pointer. (Heh if you read this quickly it's going to be fun :P).
Am I right about this? However when I try to put something similar in my project I get "invalid type arguments to ->". Sorry for wasting your time, and thanks again. :)
Yup, you got it.
Make sure that when you dereference using * and -> at the same you put parenthisis around the (*var)
(*next)->item
Adrian
Aha. I just forgot to pass the address of the ptr as a parameter when I called the function. However there is one last error remaining.
This is a simplified version of the function. -
void *search (struct lista *list, int m, char *s, struct lista **next)
-
{
-
for (**next=&list;*next!=NULL;next=&((*next)->next))
-
{if (strcmp((*next)->kodikos,s)==0)
-
printf("Found");}
-
}
And that's how I call it. -
search(proion,l,s,&(*prv));
-
It tells me that there are "incompatible types in assignment" on line 3. Maybe I've done something wrong regarding the parentheses?
-
search(proion,l,s,&(*prv));
-
It tells me that there are "incompatible types in assignment" on line 3. Maybe I've done something wrong regarding the parentheses?
Yeah, you are getting the object (*) and then getting the address again (&). Try just &prv.
Adrian
I still get many errors. Here's how I define the "search" function.
(If any of these are against the rules, just tell me. :-) ) - void search (struct lista *,int, char *, struct lista **);
I still get many errors. Here's how I define the "search" function.
(If any of these are against the rules, just tell me. :-) ) - void search (struct lista *,int, char *, struct lista **);
Send me the code via a PM (Private Message). I'll take a look.
Adrian
Yeah, I found it a little hard to read too. I use braces for all my loop and if bodies. There are other things that I do not like about the style Jos used (such as more than one exit point in a function), but everyone has their own and this will work.
Adrian
It blatantly shows that you're not a "Real Programmer (tm)" ;-)
kind regards,
Jos (<--- mother of all real programmers)
It blatantly shows that you're not a "Real Programmer (tm)" ;-)
kind regards,
Jos (<--- mother of all real programmers)
U mean Father?
Savage
U mean Father?
Savage
No, mother.
kind regards,
Jos ;-)
No, mother.
kind regards,
Jos ;-)
U are really weird sometimes.
Savage
U are really weird sometimes.
Savage
Jos is a woman. Duh. ;)
Adrian
It blatantly shows that you're not a "Real Programmer (tm)" ;-)
kind regards,
Jos (<--- mother of all real programmers)
Who owns the tm? Bad Coders of the World? :p ;)
Adrian
Who owns the tm? Bad Coders of the World? :p ;)
Adrian
Nope, as I told you so: the mother of all real programmers ;-)
kind regards,
Jos (the MOARP ;-)
Send me the code via a PM (Private Message). I'll take a look.
Adrian
What errors are you having? Sorry, reading your code without comments and with variables and strings in another language (German?) is difficult.
Adrian
It's ok. Language is greek. :P
The problem is that I can't get the function "search" to work no matter what I put in as parameter. I've taken the code you put here after understanding it first, and I tried adjusting it to my project but most of the times I get "incompatible types in assignment" error (in the "for" line). Anyway you've been most helpful guys, even if you don't manage to find the error in here. :)
Well I finally managed to solve this. Thanks a lot guys for your help and sorry for stressing you so much. ;)
Well I finally managed to solve this. Thanks a lot guys for your help and sorry for stressing you so much. ;)
That is great. If you don't get a response from use in a day or so, you should post to the thread again (with the word bump or something). I've occasionally lost threads because the system doesn't keep them marked for me as new.
Good to hear that you got it solved. Sorry about the German comment, it would explain why it didn't translate properly. ;)
Adrian
Good to hear that you got it solved. Sorry about the German comment, it would explain why it didn't translate properly. ;)
Adrian
I'm really wondering what on this earth gaved u a idea that those words are from German language.
German is ,simple said, similar to English(Well,they are from same language group)
Savage
I'm really wondering what on this earth gaved u a idea that those words are from German language.
German is ,simple said, similar to English(Well,they are from same language group)
Savage
Avon PMed me the code. I saw more than you saw here in the forum.
Adrian
Avon PMed me the code. I saw more than you saw here in the forum.
Adrian
U probably sawed something like this ,right?
If so,I'm still wondering.
;P
Savage
Haha people, I wrote a post above that the language is Greek, written with English letters. So that makes it Greeklish (a very commonly used "language" ;-) )
Thanks again. ;-)
Haha people, I wrote a post above that the language is Greek, written with English letters. So that makes it Greeklish (a very commonly used "language" ;-) )
Thanks again. ;-)
You!
Tisk,tisk,tisk,tisk,tisk
LOL
Savage
You!
Tisk,tisk,tisk,tisk,tisk
LOL
Savage
;)
:p
??????????
Savage
I'm too coherient to write anything tired. ;)
Adrian
I'm too coherient to write anything tired. ;)
Adrian
I hear ya man.
Savage
Sign in to post your reply or Sign up for a free account.
Similar topics
by: A |
last post by:
Hi,
I'm trying to solve the 3rd and final case in deleting a node from a binary
tree. That is, deleting a node that has two subtrees. If someone out there
who knows about this problem as they...
|
by: Thomas Vackier |
last post by:
Hi all,
I'm trying to delete a certain tag in an XML document using XSL, but I
can't figure out how.
Here's how my XML looks like:
<root>
<element>
<name>This is text</name>
|
by: indo3 |
last post by:
Hello,
I program an xml editor with xerces for the university of
Braunschweig, the user
dont see any xml tags, it is represented in a JTree.
Now the user shall be able to insert nodes, which...
|
by: Sumeeta. |
last post by:
Hi,
Am new to xml, using the xercess c++ DOM parser .
I want to delete a node from the xml file. Have used th removeChild()
method...but nothin happens.. not even errors..
it executes but...
|
by: Manisha |
last post by:
Hi,
I am creating a C++ dll which is used to process data passed to it
through one of its exported functions. It should be able to process
160 simultaneous requests. For this reason, I have...
|
by: melanieab |
last post by:
Hi,
I'm deleting nodes in my xml file, and it does seem to work, but then when I
later reload the file and make an xmlNodeList, the nodelist count still
includes the deleted nodes yet the file...
|
by: Newcomsas |
last post by:
Hello,
I'm trying to solve a problem with JS textbox array without success.
I have two buttons in my page: PLUS and MINUS; at every click on PLUS a new
textbox named 'dear' is generated. So, if...
|
by: pramod |
last post by:
will u suggest me how to delete child from node. i have a xml file .
There are four subnodes in the Contact element i have to delete
subnodes value from file
thank in advance
|
by: simon |
last post by:
I am having problem with an application which core dumps while deleting
a vector
here is the snippet :
Event_Node_t struct defined in the header :
+++++++++++++++++++++++++++++++++++++...
|
by: tina chatterjee |
last post by:
i have implemented binary tree insertion and deletion using my on coding.
but it was not a tough job till i got confused while deleting a node having both left and right child.I am unable to...
|
by: DolphinDB |
last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation.
Take...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: Shællîpôpï 09 |
last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
| |