Req. c data structures book recomendations

http://users.powernet.co.uk/eton/clc/cbooks.html contains a number of
recommendations for C books at all levels - beginner/tutorial,
intermediate, and advanced.

Sedgewick is certainly a rock-solid data structure reference, but I would be
less than human if I did not mention in passing that in "C Unleashed" I
devoted a hundred or so pages to a discussion of linked lists, stacks, and
queues, and (in a separate chapter) Ben Pfaff contributes about 50
excellent pages on binary trees of various kinds.

Freely downloadable source code to CU's data structures chapter can be found
at http://users.powernet.co.uk/eton/unleashed/code/ch11/ch11.zip - and Ben
Pfaff developed his trees chapter into an entire Open Source(!) book, which
you can find at http://www.adtinfo.org - again freely downloadable.

--
Richard Heathfield : bin...@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[ ... ]

I have to disagree. Sedgewick provides an exceptionally weak reference
on data structures at best. In some cases he refuses to provide
anything really related to the data structure in question at all -- for
an obvious example, chapter 18 includes a section titled "B-trees", but
proceeds to say "Many people reserve the term 'B-tree' to describe the
exact data structures built by the algorithm described by Bayer and
McCeight; we'll use it as a generic term to mean 'external balaned
trees.'"

He uses this as his excuse for ignoring what may easily be the single
most important data structure in all of computing, and instead attempt
to toot his own horn by basically trying to treat B-trees as a warped
variant of his own sole claim to real fame, the red/black tree.

Worse yet, his exposition even of what he does write about is, IMO, a
LONG ways from stellar. In the cryptology section, he discusses only a
simple substitution cipher (so weak that if it was included at all, it
should be in a chapter on "toys" not "cryptology"), and RSA. In the
latter case, he discusses encrypting entire messages with RSA, even
though that's virtually _never_ done. He talks about RSA being linear
time with respect to message length, and ignores the effect of key size
-- even though in reality, RSA is essentially _always_ used only to
encrypt the key for some symmetric cipher, and the key size is almost
the sole factor affecting speed.

Finally, I'd note that at least in his book that claims to give
algorithms in C++, his use of the language is so execrable that no
beginner in the language should be allowed to see the book at all.

Offhand, the only author I'm _sure_ I'd recommend against more strongly
than Sedgewick would be Schildt -- and even that's a close call; at
least if Schildt admitted that he was writing light fiction, I could
recommend him on the basis of his writing style. Sedgewick lacks even
that -- his only saving grace is that he usually more or less admits
when he's lying to you!

--
Later,
Jerry.

The universe is a figment of its own imagination.

Schildt??? Oh my.

Doesn't the Knuth series cover these topics?

Attila

[ data structures and such ... ]

Mostly, yes. Despite the updates, his coverage is clearly stronger on
older algorithms and data structures; more recent ones get rather
sparser coverage and of course there are large areas he hasn't touched
at all. Nonetheless, what he has to say is always worth listening to --
you're just left wishing he'd get around to finishing up more of the
series and do a more complete update on the existing books to go with.

OTOH, I'm the first to admit that's asking a great deal of a man who's
already contributed far more than I'm ever likely to, so I'll quit my
whining now! <G>

<snip>

> Finally, I'd note that at least in [Sedgewick's] book that claims to give

I certainly agree with that. But by the same token, my Knuth has a void main
program in it! I don't expect C lessons from Knuth. I expect programming
lessons, and he delivers them in spades.

I'm sorry you find Sedgewick disappointing. I consider it a useful resource.
On the other hand, I agree that you wouldn't want a newbie to learn C (or
C++) from it.

I can think of plenty that fall in between the two.

;-)

<snip>

A professor of mine once recommended a book on data structures
in C. Unfortunately, the only thing I remember is that the author was
woman. Does this sound familiar to anyone? Supposidly, the book was
very "elegantly" written.

/////////////////////////////////////////////////////

REPLY-TO address is garbage, use;
aardvarks_n_ocelots AT yahoo DOT com

/////////////////////////////////////////////////////

[ ... ]

Which Knuth book is that? Unqualified, "Knuth" normally refers to
TAOCP, in which the examples are given in MIX assembly language.

TAOCP certainly has a great deal about algorithms, without knowledge of
which it's virtually impossible to program at all well. Had he written
about C in 1967 (when the first volume of TAOCP was published) that
would be quite amazing indeed (not to mention, rather opaque at least
until C was invented a decade and a half later or so).

The real question in my mind is whether a beginner should really learn
anything from it. More specifically, is there any reason to prefer it
to many of its competitors such as _Introduction to Algorithms_ (Cormen,
Lieserson and Rivest) or _Data Structures and Algorithms_ (Aho, Hopcraft
and Ullman)? For that matter, though it's probably quite a bit harder
to get anymore, I'd consider _Algorithms + Data Structures = Programs_ a
better book on algorithms and data structures. Having been written by
Niklaus Wirth, the sample code is in Pascal, but at least the code is
well enough written that it's unlikely to cause anybody any harm.

TAOCP Vol 2, third edition, page 188 (in section 3.6). (It is slated for
correction in the next edition.)

Fully agree.

Beginner to... what? C (or C++)? If so, I agree. Given the context of this
newsgroup, I haven't got any legs left to stand on! But I think it makes a
reasonable intro to data structures in general...

...and so do all these, I presume. (I have read only the last-named of
these, so I can't comment on the others from direct experience.)

[ ... ]

To much of anything. To recognize when its material is wrong (perhaps
dangerously so) you almost have to already know more about a particular
algorithm or data structure than it attempts to present in the first
place.

I'm forced to disagree. It's simply wrong in some places and glosses
far too lightly over material in too many others to be particularly
useful. If you don't know the material already, this is the wrong place
to learn it. If you do know the material and need a reminder of some
detail, chances are pretty fair that this won't cover it -- it tends to
be particularly bad at skipping over anything at all complex (I'm
tempted to say "the parts the author doesn't understand", but I don't
really know that).

No -- Cormen and company stick to pseudo-code, IIRC. It's been a long
time since I looked at Aho, Hopcraft and Ullman's book so I don't
remember what it uses.

[snip]

Hi Jerry.

I'm not sure if you have read the following book:

Data Structures And Algorithms With
Object - Oriented Design Patterns In C++.

By: Bruno R. Preiss
http://www.brpreiss.com/books/opus5/body.html

It uses the standard C++ library for it's examples.

It is the only book on data structures that I have,
so I can't compare it to any others.

For anyone wishing to have a look at it, there is a
web version of the book at the above link.

If you or anyone has a chance to browse through it, I
would appreciate your thoughts on it.

Thanks.
Chris Val

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.454 / Virus Database: 253 - Release Date: 10/02/2003

[ ... ]

Nope -- this is the first I'd heard of it directly. It's not absolutely
clear whether I've heard of it indirectly.

Several years ago now, my brother Mike was on the faculty of the
Computer Science department at the University of Waterloo (I.e. more or
less the same place as Dr. Weiss). He put together their first course
on object oriented programming.

After he left there, they modified the course quite a bit, but a couple
of years ago, they decided some of the modifications had been for the
worse, so they contacted him to see if he still had a syllabus for the
course the way he'd taught it. Knowing Mike, even though it was a
course in OOP, it undoubtedly placed a heavy emphasis on algorithms.

Given that this guy talks about teaching a course of about the right
type at about the time they converted back to what Mike taught, it
wouldn't surprise me _too_ much if this is based to at least a limited
degree on what he'd done (which, as you might guess, I already knew a
bit about).

Oops -- that's the Java version. From you comments, you intended:

http://www.brpreiss.com/books/opus4/

or somewhere nearby.

To me the writing looks quite clear, and the presentation of the
algorithms is very reasonable.

Unfortunately (at least in my mind) he has chosen to create yet another
Smalltalk-like monolithic class hierarchy (complete with Object at the
root of everything). This was quite common in the early days of C++
(e.g. see Keith Gorlen's NIH class library), but is rarely considered
the ideal way to do things in modern C++.

Generally speaking, what I (and many others) consider well-written C++
at the present time more toward a forest of small inheritance trees
rather than one huge tree containing everything. In the single tree
model, when a function has to operate on any type, it takes a reference
(or pointer) to the root class (typically, as here, called Object or
something very similar). In the forest model, you typically use a
template instead.

Given that he's written parallel books using C# and Java (where
templates have only even started to be considered quite recently) it's
understandable that he wants to maintain the same basic structure across
the range of books. For that matter, even though C++ has had templates
a lot longer, most C++ compilers still have substantial problems with
them. As such, I can understand why he's chosen to avoid templates, but
to me it still has a substantial negative effect on the presentation.

Hi Jerry.

Yes, that was my first impression too. At least(if nothing else), what
attracted me to it, was the fact that it used the standard C++ library.

I appreciate your interesting views / thoughts.

I think I can relate to your comments, and I
do see some merit in "small inheritance trees".

Thanks Jerry.