Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Steve Thompson <stevet810@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: primitive instruction for programming |
| Date | 2015-04-19 16:28 +0000 |
| Organization | Friends of the Galactic Collective |
| Message-ID | <XeFN08.NCX.yvonB@gmail.com> (permalink) |
| References | (3 earlier) <mgg66h$u4r$1@dont-email.me> <hLTsJW.t1p.ffTNE@gmail.com> <kfnr3rkys8d.fsf@x-alumni2.alumni.caltech.edu> <263NCi.tYn.6s7aE@gmail.com> <kfn618sx4i5.fsf@x-alumni2.alumni.caltech.edu> |
On Sat, Apr 18, 2015 at 06:59:14PM -0700, Tim Rentsch wrote:
> Steve Thompson <stevet810@gmail.com> writes:
> > On Thu, Apr 16, 2015 at 09:04:34AM -0700, Tim Rentsch wrote:
> >> Steve Thompson <stevet810@gmail.com> writes:
> >>
> >>> On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote:
> >>>> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote:
> >>>>> Bartc wrote:
> >>>>> [code example that uses labels and goto's]
> >>>>
> >>>> This style of code is more error-prone. It's not even obvious
> >>>> where l1 needs to go; I can put it in several places and it
> >>>> would still compile, but the program won't work.
> >>>>
> >>>> This is something that just isn't a problem when using
> >>>> conventional control structures; why do you want to introduce
> >>>> a new source of bugs?
> >>>
> >>> One of the things I've been trying to do is an inorder traversal
> >>> of a binary tree without using recursion. With normal control
> >>> structures it doesn't seem possible without using goto.
> >>
> >> This is an interesting problem. It has a solution that is
> >> fairly simple but not immediately obvious. The key idea is
> >> to keep track of two different kinds of state - a (pointer to
> >> a) tree which represents a completely unprocessed subtree,
> >> and a stack of (pointers to) trees which represent subtrees
> >> that have had their left sides taken care of but still need
> >> their value processed and their right side done; loop over
> >> processing those as long as the unprocessed subtree is
> >> non-empty or the stack is non-empty, always processing an
> >> unprocessed subtree first. Here is a function to illustrate
> >> that does inorder printing (the Index type is just an
> >> ordinary integer type; note that the type Tree is a pointer
> >> type, so the 'stack' variable is a pointer to an array of
> >> pointers):
> >
> > That is a succint description. As I wrote in a followup I should
> > have clarified that I found an algorithm, but it is rather goto
> > oriented.
>
> I saw that. I find code like that very difficult to understand.
> Perhaps not completely impenetrable, but enough so to raise at
> least a couple of red flags in a code review.
It is one of those examples that straddles the line. Some programmers
will understand what it does without much difficulty, wheras
intermediate/beginners may be instantly confused. Fortunately it is
my project and coding standard, and not subject to third-party
constraints.
> >> void
> >> inorder_print( Tree root ){
> >> Tree *stack = malloc( 100 * sizeof *stack );
> >
> > A balanced binary tree with a depth of 90 will easily exceed the
> > number of nodes one might hope to address with a 64-bit address
> > space.
>
> That depends on how good the balancing is. In any case, the
> number chosen was meant only to be sufficient, not minimal.
I understood that the number was somewhat arbitrary, but I wanted to
point out the potential risk since we are not discussing a particular
C implementation of a known binary tree algorithm.
> > If the tree is unbalanced you should guard against stack overflow
> > or make sure that your insert/delete functions catch this.
>
> Of course. I didn't think it was important to mention this,
> since any decent binary tree package will do some sort of
> balancing.
>
> >> Index next = 0;
> >> Tree tree = root;
> >>
> >> while( tree || next > 0 ){
> >> if( tree ){
> >> stack[ next++ ] = tree;
> >> tree = tree->left;
> >> } else {
> >> tree = stack[ --next ];
> >> printf( " %d", tree->value );
> >> tree = tree->right;
> >> }
> >> }
> >> printf( "\n" );
> >>
> >> free( stack );
> >> }
> >
> > I think one of the lessons here is that parent pointers are pretty
> > much superfluous to binary tree algorithms, and that recursion is
> > mostly avoidable.
>
> Whether parent pointers are useful depends I think on what
> operations need to be supported. As for recursion, I think
> that's the wrong takeaway - binary trees are one area where
> recursion is an excellent fit in terms of both ease of coding
> and performance.
I think you are probably correct. My binary tree package suffers from
the defect that it depends on a descriptor which identifies the tree
root (and describes tree properties), and therfore treating a subtree
as a tree introduces additional complexity.
> I'm wondering why you didn't have any comments on the function
> shown, after your earlier comments about finding a solution
> without goto.
Ah, but I did not find a solution without goto, only the one I posted.
Actually, nearly all loops use 'goto' but it is hidden by the
C compiler.
At any rate, I will concede that your algorithm is clearer and more
compact.
Regards,
Steve Thompson
--
"If I had a nickel for every time some idiot called me about a
computer problem that turned out to be user error, I would be able to
retire and spend the rest of my days cultivating clues in my backyard
hillside garden." -- MysteryDog in 24hoursupport.helpdesk.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 00:56 -0700
Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 09:24 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 01:59 -0700
Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 10:32 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 02:53 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 11:04 +0100
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 14:10 +0200
Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 14:27 -0700
Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-20 15:12 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 00:17 +0100
Re: primitive instruction for programming Emiliano Gomes Padilha <egpadilha@gmail.com> - 2015-04-22 11:07 -0700
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 09:04 +0200
Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-21 03:02 -0500
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-21 01:34 -0700
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 11:34 +0200
Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-21 11:48 +0100
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-21 13:10 +0200
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-21 10:53 +0100
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 20:09 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 12:48 -0700
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 09:40 +0200
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-14 11:24 +0100
Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-14 05:39 -0500
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 13:29 +0200
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 10:59 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:28 -0700
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:33 -0700
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 03:59 -0700
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 04:23 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 11:36 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 04:26 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 12:41 +0100
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 06:26 -0700
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 15:33 +0200
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 06:44 -0700
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-13 16:30 +0200
Re: primitive instruction for programming Ian Collins <ian-news@hotmail.com> - 2015-04-14 07:52 +1200
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 09:47 +0200
Re: primitive instruction for programming raltbos@xs4all.nl (Richard Bos) - 2015-04-14 08:10 +0000
Re: primitive instruction for programming David Brown <david.brown@hesbynett.no> - 2015-04-14 10:40 +0200
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-13 17:52 +0000
Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:20 -0500
Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:33 -0500
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-14 19:51 +0000
Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-16 09:04 -0700
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-17 02:25 +0000
Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-17 08:34 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-17 17:49 +0100
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-17 19:06 +0000
Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-17 20:45 -0700
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-18 16:43 +0000
Re: primitive instruction for programming Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-18 09:56 -0700
Re: primitive instruction for programming Stephen Sprunk <stephen@sprunk.org> - 2015-04-17 17:52 -0500
Re: primitive instruction for programming Morris Dovey <mrdovey@iedu.com> - 2015-04-17 18:02 -0500
Re: primitive instruction for programming Stephen Sprunk <stephen@sprunk.org> - 2015-04-17 19:26 -0500
Re: primitive instruction for programming Morris Dovey <mrdovey@iedu.com> - 2015-04-17 20:04 -0500
Re: primitive instruction for programming Michael Angelo Ravera <maravera@prodigy.net> - 2015-04-19 14:59 -0700
Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-20 00:19 +0100
Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-20 02:06 +0100
Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-20 02:26 +0100
Re: primitive instruction for programming Richard Heathfield <rjh@cpax.org.uk> - 2015-04-20 02:18 +0100
Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-18 18:59 -0700
Re: primitive instruction for programming Steve Thompson <stevet810@gmail.com> - 2015-04-19 16:28 +0000
Re: primitive instruction for programming Richard Damon <Richard@Damon-Family.org> - 2015-04-19 17:16 -0400
Re: primitive instruction for programming Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-22 15:28 -0700
Re: primitive instruction for programming John Bode <jfbode1029@gmail.com> - 2015-04-23 07:20 -0700
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 03:07 -0700
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 09:47 -0700
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 11:09 -0700
Re: primitive instruction for programming Noob <root@127.0.0.1> - 2015-04-13 20:43 +0200
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 12:09 -0700
Re: primitive instruction for programming Xcott Craver <xcottcraver@gmail.com> - 2015-04-14 07:11 -0700
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-14 07:28 -0700
Re: primitive instruction for programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 15:57 +0100
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-14 08:13 -0700
Re: primitive instruction for programming fir <profesor.fir@gmail.com> - 2015-04-13 14:02 -0700
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 14:28 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 22:51 +0100
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 14:58 -0700
Re: primitive instruction for programming Bartc <bc@freeuk.com> - 2015-04-13 23:25 +0100
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 15:37 -0700
Re: primitive instruction for programming James Kuyper <jameskuyper@verizon.net> - 2015-04-13 19:09 -0400
Re: primitive instruction for programming fmassei@gmail.com - 2015-04-13 16:20 -0700
Re: primitive instruction for programming Robert Wessel <robertwessel2@yahoo.com> - 2015-04-13 18:03 -0500
Re: primitive instruction for programming asetofsymbols@gmail.com - 2015-04-13 20:58 -0700
Re: primitive instruction for programming fir <profesor.fir@gmail.com> - 2015-04-13 15:02 -0700
csiph-web