Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > One last question on hashes

Reply
Thread Tools

One last question on hashes

 
 
Chad
Guest
Posts: n/a
 
      10-26-2007
On page 145 in second edition of the book "The C Programming Language"
by K &R, they have the following lines of code in install()

hash->next = hastab[hashval];
hashtab[hashval] = np;

I'm assuming that this is meant to insert NULL at the end of the
linked list. If that is the case, I am not seeing how NULL is actually
getting put at the end of the linked list.

 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      10-26-2007
Chad <(E-Mail Removed)> writes:

> On page 145 in second edition of the book "The C Programming Language"
> by K &R, they have the following lines of code in install()
>
> hash->next = hastab[hashval];
> hashtab[hashval] = np;
>
> I'm assuming that this is meant to insert NULL at the end of the
> linked list. If that is the case, I am not seeing how NULL is actually
> getting put at the end of the linked list.


This code inserts np at the *front* of the linked list. NULL is
already at the end of the linked list, so there's no need to add
it.
--
"A lesson for us all: Even in trivia there are traps."
--Eric Sosman
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      10-26-2007
Ben Pfaff wrote:
> Chad <(E-Mail Removed)> writes:
>
>> On page 145 in second edition of the book "The C Programming
>> Language" by K &R, they have the following lines of code in
>> install()
>>
>> hash->next = hastab[hashval];
>> hashtab[hashval] = np;
>>
>> I'm assuming that this is meant to insert NULL at the end of
>> the linked list. If that is the case, I am not seeing how NULL
>> is actually getting put at the end of the linked list.

>
> This code inserts np at the *front* of the linked list. NULL
> is already at the end of the linked list, so there's no need to
> add it.


The point of this sort of list formation is that the total work may
be much less. Even if the end result desired is a list in the
order inserted, the total work is:

a list reversal O(n) with small constants
n insertions O(1) with small constants

for a net of O(n) performance. However if each value is inserted
at the end, for i = 0 through n, the insertions require:

n insertions O(i) with larger constants.

and the work is of the form K(1 + 2 + 3 ... + n), which is easily
seen to be larger.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>



--
Posted via a free Usenet account from http://www.teranews.com

 
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
using hashes as keys in hashes Steven Arnold Ruby 3 11-23-2005 03:25 PM
Hash of hashes, of hashes, of arrays of hashes Tim O'Donovan Perl Misc 5 10-28-2005 05:59 AM
Question about hashes of hashes djacober Perl Misc 10 07-25-2005 10:01 AM
Hashes of hashes or just one hash ? Perl Learner Perl Misc 11 06-09-2005 06:55 AM
Hashes of Hashes via subs Ben Holness Perl 8 10-08-2003 06:57 AM



Advertisments