Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Advanced data structures

Reply
Thread Tools

Advanced data structures

 
 
Bruce Cook
Guest
Posts: n/a
 
      12-12-2009
bartc wrote:

>
> "Richard Heathfield" <(E-Mail Removed)> wrote in message

[...]
> There might be more apt languages than C (not everyone is comfortable with
> zero-based indexing for example), but if it's a choice between 'MIX' and
> C, then C wins.


I'm interested in why you'd pick zero-based indexing as something people
would specifically have problems with in C.

I personally find zero-based indexing fairly natural, other languages which
1 based indexing such as Fortran and Cobol used to bug me, especially after
I had started programming in C and "knew there was a better way"

zero based indexing certainly makes more sense mathematically.

Bruce

 
Reply With Quote
 
 
 
 
Frank
Guest
Posts: n/a
 
      12-12-2009
On Sat, 12 Dec 2009 09:06:25 +0100, jacob navia wrote:

> Frank a écrit :
>>
>> Sounds great. How much is it? Does it come with a companion disc?

>
> I paid 50.62$ at Amazon.com (new) but maybe you can find it for less. There is
> a used version (at amazon) starting at 45$, other sites may have better offers.
>
> The code of the book is available at the author's web site. Just cut/paste
> from there.
>
> jacob


Sounds good. If anyone in the beehive state wants to ask me what I want
for Christmas, I can be precise.

Cheers,
--
 
Reply With Quote
 
 
 
 
Nick
Guest
Posts: n/a
 
      12-12-2009
Bruce Cook <(E-Mail Removed)> writes:

> bartc wrote:
>
>>
>> "Richard Heathfield" <(E-Mail Removed)> wrote in message

> [...]
>> There might be more apt languages than C (not everyone is comfortable with
>> zero-based indexing for example), but if it's a choice between 'MIX' and
>> C, then C wins.

>
> I'm interested in why you'd pick zero-based indexing as something people
> would specifically have problems with in C.
>
> I personally find zero-based indexing fairly natural, other languages which
> 1 based indexing such as Fortran and Cobol used to bug me, especially after
> I had started programming in C and "knew there was a better way"
>
> zero based indexing certainly makes more sense mathematically.


Once you get into "friendly" string manipulation, there are a few arguments
for 1-based indexing, particularly when combined with "zero is false,
everything else is true". For example, it would be "nicer" in
Javascript to be able to write »if(somestring.indexOf("test"))« rather
than having to add »!=-1« at the end. Of course, C using pointers for
this manages to do it quite well with the NULL return from strstr.
--
Online waterways route planner: http://canalplan.org.uk
development version: http://canalplan.eu
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
jacob navia <(E-Mail Removed)> writes:
>I find this book excellent. Everything is written in C, it


It seems to allocate a stack entry

st = (stack_t *) malloc( ...

and then, in the next line

st->base = ...

it seems to use »st« without ever taking account for the
possibility that »st« might be 0?

This might be fine when a program is used by the programmer
himself, who can cope with segment violations or other
strange runtime-behavior. But it might not be appropriate
when software is intended to be delievered as a product to a
customer who needs to depend on it.

 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
Richard Heathfield <(E-Mail Removed)> writes:
>Anyone who is not comfortable with 0-based indexing needs to buy a new
>mattress. The contortions you have to go through to use other bases just
>melt away when you switch to 0.


See also (English language page):

http://www.purl.org/stefan_ram/pub/zero

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-12-2009
James Dow Allen a écrit :
> On Dec 12, 4:03 pm, jacob navia <(E-Mail Removed)> eut ecrit:
>
>> [Check out Peter Brass's book. Source code on-line.]

>
> I looked at the source for tries (digital search trees) and was
> disappointed to see that he didn't use "traversor structures."
> I know Ben Pfaff uses such things, and it seems excellent idea.
> Do others use them? Can Brass' examples be recommended if he
> *doesn't* use them?
>


I do not know but the tries subject is treated very extensively
in that book, sorry. Pages 335 to 356 are about tries, and he
shows several implementations.

Maybe you didn't look at the correct one?

Because in many examples he shows a first "trivial" implementation that
he later refines more and more. If you would explain what do you
mean by "traversor structures" we could go further.

jacob
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-12-2009
Stefan Ram a écrit :
> jacob navia <(E-Mail Removed)> writes:
>> I find this book excellent. Everything is written in C, it

>
> It seems to allocate a stack entry
>
> st = (stack_t *) malloc( ...
>
> and then, in the next line
>
> st->base = ...
>
> it seems to use »st« without ever taking account for the
> possibility that »st« might be 0?
>
> This might be fine when a program is used by the programmer
> himself, who can cope with segment violations or other
> strange runtime-behavior. But it might not be appropriate
> when software is intended to be delievered as a product to a
> customer who needs to depend on it.
>

He does that, as he explains in the text, because they are replaced
in the next section by a heap implementation where he builds an
intermediate layer (as I did for the list container) that allocates
nodes from a linked list of blocks.

The book is not a fool proof receipt book, it is a book about
advanced data structures. The code is just to illustrate the text!
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-12-2009
jacob navia a écrit :
>
> The book is not a fool proof receipt book, it is a book about
> advanced data structures. The code is just to illustrate the text!


What I mean with this sentence is that when reading code about an
algorithm, it is easier to read if the error handling code is not
shown.

What I am interested in with this book is to learn about the
data structures themselves, not about good software practices,
testing the return value of malloc, writing int main(void) or
similar problems.

In my implementation of the heap I did test for NULL return,
and I issue the corresponding error. In a book about advanced
data structures that is just a distracting detail.

 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
jacob navia <(E-Mail Removed)> writes:
>What I mean with this sentence is that when reading code about an
>algorithm, it is easier to read if the error handling code is not
>shown.


I have another definition of »algorithm«: An algorithm is
the implementation of some feature using the means of a
specific target language. That is, for example, an algorithm
for a tree search in Prolog differs from the same algorithm
in Assembler. The algorithm depends on the elementary
operations available. It can not be abstracted away from the
target language too much. There is no such thing as a
»language-independent algorithm«. For example, in a language
with an operator »¤« for a tree search of x in the tree T,
the algorithm for a tree-search just ist »x ¤ T«.

>What I am interested in with this book is to learn about the
>data structures themselves, not about good software practices,
>testing the return value of malloc, writing int main(void) or
>similar problems.


To me, when programming in C, handling malloc in the correct
way is an integral part of the algorithm. It can not be
abstracted away. Otherwise, I'd use a language with more
automated memory management.

>In my implementation of the heap I did test for NULL return,
>and I issue the corresponding error. In a book about advanced
>data structures that is just a distracting detail.


I would not actually issue from a library function in the
sense of a side-effect with access to external files or
consoles or so, but just return 0. For example, I »quote«
some code, which actually was simplified by me:

node_t *get_node() /* version simplified by Stefan Ram */
{ ...
currentblock = malloc( BLOCKSIZE * sizeof(node_t) );
return( currentblock ); }

http://www-cs.ccny.cuny.edu/~peter/dstest/li_stack.c

This still is ok, as it returns 0 in case malloc returns 0.

.-------------------------------------------------------.
| We do not need extra means to »signal« a failure, |
| but we must not hide it from the caller. |
'-------------------------------------------------------'

But then, later:

st = get_node();
st->next = NULL;

http://www-cs.ccny.cuny.edu/~peter/dstest/li_stack.c

Here »st« is used as if it was known at runtime that it was
not 0. Such code is appropriate for some other languages,
but IMHO not for C.

 
Reply With Quote
 
James Dow Allen
Guest
Posts: n/a
 
      12-12-2009
On Dec 12, 7:50*pm, jacob navia <(E-Mail Removed)> eût écrit :
> James Dow Allen a écrit :
> > On Dec 12, 4:03 pm, jacob navia <(E-Mail Removed)> eût écrit :
> >> [Check out Peter Brass's book. *Source code on-line.]

>
> > I looked at the source for tries (digital search trees) and was
> > disappointed to see that he didn't use "traversor structures."
> > I know Ben Pfaff uses such things, and it seems excellent idea.
> > Do others use them? *Can Brass' examples be recommended if he
> > *doesn't* use them?

>
> Because in many examples he shows a first "trivial" implementation that
> he later refines more and more. If you would explain what do you
> mean by "traversor structures" we could go further.


I examined several modules linked from
http://www-cs.ccny.cuny.edu/~peter/dstest.html
all with the same unfortunate result. Let us admit,
however, that much or most other tree-traversing code also
does *not* use such "traversor structures". Ben Pfaff's
code does and, whether or not he claims it as original
invention, can doubtless do better than I at lucid
discussion thereof.

Not counting the rather trivial
typedef char object_t;
Brass's code declares a single object type
(node), where I'd use at least another two.
Add a table or table descriptor type more than
just a certain node (the root) becoming all
there is to a "tree." The other type I'd
surely introduce for all but the most trivial
search tree is "traversor", which holds the
state of a search in progress (or search completed).

To understand the need, consider that we operate
the tree searcher as a co-routine, returning the
entire tree in pre- or post-order. Brass's
code can't do that: it has create(), find(), insert()
and delete() but no treewalker(). When you write
treewalker() you'll see the need for the traversor
object; once you implement it you find it convenient
to use during find(), delete(), etc. as well.

James Dow Allen
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Advanced Python Programming Oxford Lectures [was: Re: *Advanced*Python book?] Michele Simionato Python 1 03-27-2010 06:10 AM
Help with Repeater control and advanced data manipulation Mike Cain ASP .Net 2 10-22-2006 09:31 AM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
ADVANCED data matching? HotRod ASP .Net 2 04-12-2005 01:13 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM



Advertisments