[LCP]linked list question
bj at gmx.net
Wed Apr 3 00:56:16 UTC 2002
On Tuesday 02 April 2002 16:20, you wrote:
> WHAT precisely do you intend. There are MULTIPLE (very different)
> problems which can properly described as "reversing a list".
> when you use the word "recursively".
Sorry for being not really clear.
Maybe I'll try to explain what my program does first.
I wrote something that is supposed to parse email messages in all sort
of formats. (MIME, UU, plain rfc822, etc ...)
Because of the many formats and ways a mail can look like, the parser
should just go over the mail trying to recognize whatever it can and
simply "accept" the rest as is.
I split the mail that I receive from the MTA into seperate structs.
Those are later on being used in case the message should be rebuilt.
Every mail will have a header and maybe a body. Every body might
contain several attachment. Since I don't know how many Attachments the
mail contains I use a linked list in order to process every message.
Now I found that when allocating new nodes it would be quickest to add
them on the head-end rather than the tail-end. Obviously with the
disadvantage, of the nodes appearing in reverse.
So I thought the quickest way to reverse the list would be recursively
reversing the pointers as it is done in this function:
rreverse_mbody(mbody_t ** mb)
if (*mb==NULL) return;
first = *mb;
last = first->bnext;
if (last==NULL) return;
first->bnext->bnext = first;
first->bnext = NULL;
*mb = last;
This should be much more efficient than reversing the last n-1 elements
of the list and then iterating all the way down to the new tail and put
the old head node there. It should get the head node in the right
place without extra iteration.
> a) Did you mean the "recursively" to refer to WHAT you intend to do or
> HOW you intend to do it? In the former case you mean something like
> "reverse a list and all its sublists" so a list (A (B C D) (E F))
> becomes ( (F E) (D C B) A) but if only reversal at the top level was
> meant becomes ((E F) (B C D) A).
Yes because the structure mbody_t may contain other linked lists
For that I wrote a reverse_sub_mbody() function that does the same as
the above but reverses lists of type sub_mbody_t instead of mbody_t
> b) Did you mean do as a "function" (ie: return a new list with the
> original list left unchanged) or was this to be a "reversal in place"?
> In the former case your "process" will involve allocating either as
> new nodes as the original list contained or as many as exist at the
> level (refer back to "a").
No. This is what I want to avaoid since I have all the information I
need to rebuild the message in the structures already. The structures
were first filled while parsing the message of course ...
> What I am really trying to say by this is that the FIRST thing you
> should always do is be absolutely clear about what your program is
> SUPPOSED to do because there is no way you can get the code right
> you have accomplished that. In other words, you might be able to code
> and test your code and everything looks all right but since it isn't
> actually doing what was intended the whole larger program (of which
> is a component) may fail to work.
> This is the Linux C Programming List
> : http://lists.linux.org.au/listinfo/linuxcprogramming List
By sending an email to ANY of my addresses you are agreeing that:
1) I am by definition, "the intended recipient"
2) All information in the email is mine to do with as I see fit and
make such financial profit, political mileage, or good joke as it lends
itself to. In particular, I may quote it on usenet.
3) I may take the contents as representing the views of your company.
4) This overrides any disclaimer or statement of confidentiality that
may be included on your message.
More information about the linuxCprogramming