K&R2, exercise 6.4

[Martin Ambuhl]

I get a compile time error. I know this has something to do with arrays
and pointers but I can't figure out what is wrong with line 56:

LINE 56: psnode++ = &root_node;

psnode++ yields a value, and does not represent an object.

I will not try to guess what you meant to say, but note that
*(psnode++) = root_node;
is legal and might be related to your intent.

Note that you also omitted
#include <ctype.h>

 

[arnuld]

I get a compile time error. I know this has something to do with arrays
and pointers but I can't figure out what is wrong with line 56:


LINE 56: psnode++ = &root_node;



/* K&R2, exercise 6.4
*
* write a program that prints the distinct words in its input sorted into
* decreasing order of frequency of occurence. Precede each word by its
count. *
*
* (1) we are going to create a linked list and store words in
it. * Each structure will have a count associated with the word it
carries. When * we will see a word which is already in the list then we
will increase the count * by 1. That way we will have a linked-list of
unique structures. *
* (2) we will save a pointer to each structure in an array of
pointers * to those structures and will sort these pointers according to
the number of * occurences of each word. This will make program efficient
as we will not be sorting * the structures in linked-list but the
pointers to those structures.
*
*/




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "getword.h"

enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

extern int getword( char * , int );

struct snode *add_to_snode( struct snode *, char * );
void print_snode( struct snode ** );
struct snode *node_alloc( void );
char *strdup( char * );





int main( void )
{
char word[WORDSIZE];
struct snode *root_node;
struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode;

psnode = arr_psnodes;
root_node = NULL;


while( getword( word, WORDSIZE ) != EOF )
{
if( isalpha(word[0]) )
{
root_node = add_to_snode( root_node, word );
psnode++ = &root_node;
}
}

print_snode( arr_psnodes );


return 0;
}



struct snode
{
char *word;
int count;
struct snode *next;
};


struct snode *add_to_snode( struct snode *p, char *w )
{
int match;

if( p == NULL )
{
p = node_alloc();
p->word = strdup( w );
p->count = 1;
p->next = NULL;
}
else if ( !(match = strcmp( p->word, w )) )
{
p->count++;
}
else if( match )
{
p->next = add_to_snode( p->next, w );
}

return p;
}


void print_snode( struct snode **pp )
{
/* yet to be done */
}


void sort_nodes( struct snode **pp )
{
/* yet to be done */
}


struct snode *node_alloc( void )
{
return malloc( sizeof(struct snode));
}



char *strdup( char *pc )
{
char *pc2;

pc2 = malloc( strlen(pc) + 1 );

if( pc )
{
strcpy( pc2, pc );
}

return pc2;
}

============== OUTPUT ============
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 6-4.c
6-4.c: In function `main':
6-4.c:56: error: invalid lvalue in assignment
6-4.c: At top level:
6-4.c:100: warning: unused parameter 'pp'
6-4.c:106: warning: unused parameter 'pp'
[arnuld@raj C]$

 

[santosh]

arnuld wrote:

<snip>

Are you aware that your address munging technique is faulty? The valid
domain <nopain.com> is likely being sent spam e-mail because of your
use of that domain in your munged address in the Sender field of your
posts' header. Read the following links (especially the first two) to
learn how to properly use munged e-mail addresses.

<http://www.2kevin.net/munging.html>
<http://www.faqs.org/faqs/net-abuse-faq/munging-address/>
<http://en.wikipedia.org/wiki/Address_munging>
<http://en.wikipedia.org/wiki/Anti-spam_techniques_(e-mail)>
<http://spam.abuse.net/>
<http://www.spamhelp.org/>

 

[arnuld]

What do you think that line does? For my own part, I can make no sense
whatsoever out of it.

some earlier lines are:

struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode;

psnode = arr_psnodes;
psnode++ = &root_node;


-- arr_psnodes is an array of pointers to structures
-- psnode is a pointer to arr_psnodes ( to its first element in reality )
-- psnodes++ will point to 1st element of arr_psnodes and then so on.

therefore,

psnodes++ = &root_node;

means, the arr_snodes's 1st element points to root_node (the first node)
and ++ will make next node to get pointed by 2nd element of arr_psnodes.

just like array indexing:

int i = 0;

arr_psnodes[0] = root_node
arr_psnodes[1] = root_node (next one in linked-list)


psnodes ++ = &root_node
psnode++ = &root_node (next one in linked-list)



since psnodes is a ** and root_node is a *, hence only a ** can take the
address of a * which is quite logical I think

 

[Barry Schwarz]

I get a compile time error. I know this has something to do with arrays
and pointers but I can't figure out what is wrong with line 56:

You are killing yourself by copying bad code from one project to
another without letting any of the lessons of the previous projects
sink in.

LINE 56: psnode++ = &root_node;



/* K&R2, exercise 6.4
*
* write a program that prints the distinct words in its input sorted into
* decreasing order of frequency of occurence. Precede each word by its
count. *
*
* (1) we are going to create a linked list and store words in
it. * Each structure will have a count associated with the word it
carries. When * we will see a word which is already in the list then we
will increase the count * by 1. That way we will have a linked-list of
unique structures. *
* (2) we will save a pointer to each structure in an array of
pointers * to those structures and will sort these pointers according to
the number of * occurences of each word. This will make program efficient
as we will not be sorting * the structures in linked-list but the
pointers to those structures.
*
*/




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "getword.h"

It would be nice if you told us what this contains. I thought it
might contain the declaration of struct node but later you prove it
cannot.

enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

extern int getword( char * , int );

The extern serves no purpose. You also don't show us this function.

struct snode *add_to_snode( struct snode *, char * );
void print_snode( struct snode ** );
struct snode *node_alloc( void );
char *strdup( char * );





int main( void )
{
char word[WORDSIZE];
struct snode *root_node;
struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode;

psnode = arr_psnodes;
root_node = NULL;


while( getword( word, WORDSIZE ) != EOF )
{
if( isalpha(word[0]) )
{
root_node = add_to_snode( root_node, word );
psnode++ = &root_node;

Other have addressed this.

}
}

print_snode( arr_psnodes );


return 0;
}



struct snode
{
char *word;
int count;
struct snode *next;
};

How does you code compile if this is so late in the source?

struct snode *add_to_snode( struct snode *p, char *w )
{
int match;

if( p == NULL )
{
p = node_alloc();

Don't you think you should check if node_alloc succeeds?

p->word = strdup( w );
p->count = 1;
p->next = NULL;
}
else if ( !(match = strcmp( p->word, w )) )
{
p->count++;
}
else if( match )
{
p->next = add_to_snode( p->next, w );
}

return p;
}


void print_snode( struct snode **pp )
{
/* yet to be done */
}


void sort_nodes( struct snode **pp )
{
/* yet to be done */
}


struct snode *node_alloc( void )
{
return malloc( sizeof(struct snode));
}

Why bother with a function when you could malloc directly instead.

char *strdup( char *pc )
{
char *pc2;

pc2 = malloc( strlen(pc) + 1 );

if( pc )

This is the wrong test.

{
strcpy( pc2, pc );
}

return pc2;
}

============== OUTPUT ============
[arnuld@raj C]$ gcc -ansi -pedantic -Wall -Wextra 6-4.c
6-4.c: In function `main':
6-4.c:56: error: invalid lvalue in assignment
6-4.c: At top level:
6-4.c:100: warning: unused parameter 'pp'
6-4.c:106: warning: unused parameter 'pp'
[arnuld@raj C]$

Remove del for email

 

[arnuld]

int i = 6;
i++ = 42;

If this meant anything at all (which it doesn't), it would mean "change the
value of i to 7 and, while you're at it, change the value of 6 to 42".
(Note: NOT the value of i, but the value of 6.) This doesn't work. What
could it mean, conceptually? If 6 now has the value 42, what is 6/7? Is it
0? Or 6? Or even 42? All are defensible.

those are values, I am talking about pointers to arrays:

int arr[3];
int* pi = arr;

then ++pi will not point to next element of the array ?




and this is what I did. The only difference is 2 levels of
indirection.

 

[arnuld]

arnuld said:

int arr[3];
int* pi = arr;
then ++pi will not point to next element of the array ?

Yes, but the expression ++pi yields as its result a VALUE, not an object.
You can't assign to values. The expression:

++pi = whatever;

is illegal. I explained this in my last reply.

pretty much complicated concept. pi++ and ++pi both never yield a
pointer as result and hence can not be used for assignment but arr[i+
+] can be used. Pointers do not have much useful connection with
arrays then .

There is no difference. You are still trying to assign to a value, and that
isn't legal in C.

pi = &i; does not yield a value
pi++ = &i; yields a value

right ?



I thought C was simpler than C++ but I think it is as complicated as C+
+

 

[arnuld]

Yes, they do. If pi is a pointer, so is pi++, and so is ++pi. But they are
pointer *values*, not pointer *objects*. You can't assign to values, only
to objects.

int i = 3;

i is variable and it has value 3

int *p = &i;

p is a pointer variable and its value is the memory address of i.

Right ?

(I never use word object for things stored in memory. That confuses me
with Classes and Objects. I simply call them variables or functions)

and hence can not be used for assignment but arr[i++] can be used.

So can pi[i++]. So what?

pi++ and pi[i++] are different ?

C++ is vastly more complicated. I'm reasonably sure that everything I've
told you in this thread applies equally to C++.

I am comparing the:

complexity of understanding arrays of pointers to structures/pointers and
pointers to pointers to arrays of pointers.

with

C++ Templates and other constructs like std::string and std::vector

you never do arrays in C unless you have memory-constraints like Embedded
Programming. Most of the time, in C++, we use strings and vectors and
Std. Lib. algorithms & as per my understanding, Templates are simpler
than handling Arrays and Pointers to Pointers to arrays of pointers to
something.


I am NOT arguing with you Richard. I know you are trying to help me and I
posted this question here because I *really* want to understand arrays
and pointers because the power of C++ Std. Lib. algorithms, strings and
Templates is, in all, originates from Arrays and Pointers. I want to
master C and contribute back to community by writing Hurd. I was just an
average student in the class, not with much IQ, hence I am takinig longer
time to understand these things:

 

[Richard Tobin]

pi++ = &i; yields a value

right ?

[/QUOTE]

Right.

Er...

-- Richard

 

[arnuld]

Yes, very much so. pi++ changes the value stored in the pi object, and
has no effect whatsoever on i. pi[i++] is equivalent to *(pi + i++),
which modifies the i object (adding 1 to it) and which yields the prior
value of i for addition to pi, giving a pointer value which can be
dereferenced to access the object being pointed at.

yes, I understand it completely. I think things are pretty much different
with pointer to arrays of pointers. I will try to post an example in some
other thread and will keep this thread specific to exercise 6.4 of K&R2.

Don't I? I thought I used them quite a lot, actually.

Oh.. I forgot to add ++ in front of C

 

[???]

I see.

You are killing yourself by copying bad code from one project to
another without letting any of the lessons of the previous projects
sink in.

..... SNIP....

okay, I have took time and did correct the mistakes you mentioned. I am
not going further to write other functions yet. First, I am posting the
corrected code for a check by you folks:


/* K&R2, exercise 6.4
*
* write a program that prints the distinct words in its input sorted into
* decreasing order of frequency of occurence. Precede each word by its
count.
*
*
* The basic 2 step design-idea:
*
* (1) we are going to create a linked list and store words in
it.
* Each structure will have a count associated with the word it carries.
When
* we will see a word which is already in the list then we will increase
the count
* by 1. That way we will have a linked-list of unique structures.
*
* (2) we will save a pointer to each element of the 1st array
( which
* are structures) in an array of pointers and will sort these pointers
according
* to the number of occurences of each word. This will make program
efficient
* as we will not be sorting the structures in linked-list but the
pointers
* to those structures.
*
*/




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

int getword( char * , int );
struct snode *add_to_snode( struct snode *, char * );
void print_snode( struct snode ** );
char *strdup( char * );


struct snode
{
char *word;
int count;
struct snode *next;
};



int main( void )
{
char word[WORDSIZE];
struct snode *root_node;
struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode, **psnode_last;

psnode = arr_psnodes;
psnode_last = psnode + (ARRSIZE - 1);

root_node = NULL;


while( getword( word, WORDSIZE ) && (psnode != psnode_last) )
{
if( isalpha(word[0]) )
{
root_node = add_to_snode( root_node, word );
*(psnode++) = root_node;
}
}

print_snode( arr_psnodes );

return 0;
}





struct snode *add_to_snode( struct snode *p, char *w )
{
int match;

if( p == NULL )
{
p = malloc( sizeof(struct snode));

if( !p )
{
fprintf( stderr, "out of memory\n" );
exit( EXIT_FAILURE );
}

p->word = strdup( w );
p->count = 1;
p->next = NULL;
}
else if ( !(match = strcmp( p->word, w )) )
{
p->count++;
}
else if( match )
{
p->next = add_to_snode( p->next, w );
}

return p;
}


void print_snode( struct snode **pp )
{
/* yet to be done */
}


void sort_nodes( struct snode **pp )
{
/* yet to be done */
}



char *strdup( char *pc )
{
char *dup;

dup = malloc( strlen(pc) + 1 );

if( dup )
{
strcpy( dup, pc );
}

return dup;
}




/* A program that takes a single word as input. It will discard
* the whole input if it contains anything other than the 26 alphabets
* of English. If the input word contains more than 30 letters then only
* the extra letters will be discarded . For general purpose usage of
* English it does not make any sense to use a word larger than this size.
* Nearly every general purpose word can be expressed in a word with less
* than or equal to 30 letters.
*
*/
int getword( char *word, int max_length )
{
int c;
char *w = word;


while( isspace( c = getchar() ) )
{
;
}

while( --max_length )
{
if( isalpha( c ) )
{
*w++ = c;
}
else if( isspace( c ) || c == EOF )
{
*w = '\0';
break;
}
else
{
return 0;
}

c = getchar();
}


*w = '\0';


return word[0];
}

 

[Barry Schwarz]

okay, I have took time and did correct the mistakes you mentioned. I am
not going further to write other functions yet. First, I am posting the
corrected code for a check by you folks:


/* K&R2, exercise 6.4
*
* write a program that prints the distinct words in its input sorted into
* decreasing order of frequency of occurence. Precede each word by its count.
*
*
* The basic 2 step design-idea:
*
* (1) we are going to create a linked list and store words in it.
* Each structure will have a count associated with the word it carries. When
* we will see a word which is already in the list then we will increase the count
* by 1. That way we will have a linked-list of unique structures.
*
* (2) we will save a pointer to each element of the 1st array ( which

It's not an array but a linked list but that's just a nit.

* are structures) in an array of pointers and will sort these pointers according
* to the number of occurences of each word. This will make program efficient
* as we will not be sorting the structures in linked-list but the pointers
* to those structures.
*
*/




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

int getword( char * , int );
struct snode *add_to_snode( struct snode *, char * );
void print_snode( struct snode ** );
char *strdup( char * );

This function name belongs to the implementation but that's also just
another nit for the time being.

struct snode
{
char *word;
int count;
struct snode *next;
};



int main( void )
{
char word[WORDSIZE];
struct snode *root_node;
struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode, **psnode_last;

psnode = arr_psnodes;
psnode_last = psnode + (ARRSIZE - 1);

This works but you could accomplish the same thing by simply keeping a
count of the number of elements of arr_psnodes that are in use.

root_node = NULL;


while( getword( word, WORDSIZE ) && (psnode != psnode_last) )

Nowhere do you prompt the user for input.

{
if( isalpha(word[0]) )
{
root_node = add_to_snode( root_node, word );
*(psnode++) = root_node;

This does not do what you want. add_to_snode always adds new nodes at
the end but returns the address of the first node.

}
}

print_snode( arr_psnodes );

return 0;
}

Consider an input sequence of "a b"

struct snode *add_to_snode( struct snode *p, char *w )
{
int match;

if( p == NULL )

For the first node (N1), this is true immediately.

On initial entry for the second node (N2a), this is false.

On the recursive entry for the second node (N2b), this is true.

{
p = malloc( sizeof(struct snode));

if( !p )
{
fprintf( stderr, "out of memory\n" );
exit( EXIT_FAILURE );
}

p->word = strdup( w );
p->count = 1;
p->next = NULL;

(N1) You build struct_1 with "a", 1, and NULL.

(N2b) You build struct_2 with "b", 1, and NULL.

}
else if ( !(match = strcmp( p->word, w )) )

(N2a) This is also false.

{
p->count++;
}
else if( match )

Is there any possibility the if could evaluate to false? If it is
always true, a simple else would work just as well.

(N2a) But this is true.

{
p->next = add_to_snode( p->next, w );

(N2a) So you call this function recursively with NULL and "b".

When N2b returns here, you change struct_1 to point to struct_2
(instead of NULL) but p still points to struct_1.

}

return p;

(N1) And you return the address of struct_1 which main will store in
root_node.

(N2b) And you return the address of struct_2 to N2a.

(N2a) And you return the address of struct_1 which main will store
again in root_node.

}


void print_snode( struct snode **pp )
{
/* yet to be done */
}


void sort_nodes( struct snode **pp )
{
/* yet to be done */
}



char *strdup( char *pc )
{
char *dup;

dup = malloc( strlen(pc) + 1 );

if( dup )
{
strcpy( dup, pc );
}

return dup;
}

The routine that calls strdup does not check if it succeeded. You
either need to check here or everywhere you try to use the member word
(especially the two functions you have not yet filled in).

/* A program that takes a single word as input. It will discard
* the whole input if it contains anything other than the 26 alphabets
* of English. If the input word contains more than 30 letters then only
* the extra letters will be discarded . For general purpose usage of

Actually, the extra letters are not discarded. They are left in the
input buffer and will be processed on the next call to getword as if
they were the start of a new word.

* English it does not make any sense to use a word larger than this size.
* Nearly every general purpose word can be expressed in a word with less
* than or equal to 30 letters.

But bullet-proofing can come later and this is not an unreasonable
assumption to start with. By isolating getword in a separate function
you have made it easier to fix this problem when you get around to it.

*
*/
int getword( char *word, int max_length )
{
int c;
char *w = word;


while( isspace( c = getchar() ) )
{
;
}

while( --max_length )
{
if( isalpha( c ) )
{
*w++ = c;
}
else if( isspace( c ) || c == EOF )
{
*w = '\0';
break;
}
else
{
return 0;
}

c = getchar();
}


*w = '\0';


return word[0];
}

Remove del for email

 

[arnuld]

You are killing yourself by copying bad code from one project to
another without letting any of the lessons of the previous projects
sink in.

..... SNIP....

okay, I have took time and did correct the mistakes you mentioned. I am
not going further to write other functions yet. First, I am posting the
corrected code for a check by you folks:


/* K&R2, exercise 6.4
*
* write a program that prints the distinct words in its input sorted into
* decreasing order of frequency of occurence. Precede each word by its count.
*
*
* The basic 2 step design-idea:
*
* (1) we are going to create a linked list and store words in it.
* Each structure will have a count associated with the word it carries. When
* we will see a word which is already in the list then we will increase the count
* by 1. That way we will have a linked-list of unique structures.
*
* (2) we will save a pointer to each element of the 1st array ( which
* are structures) in an array of pointers and will sort these pointers according
* to the number of occurences of each word. This will make program efficient
* as we will not be sorting the structures in linked-list but the pointers
* to those structures.
*
*/




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

int getword( char * , int );
struct snode *add_to_snode( struct snode *, char * );
void print_snode( struct snode ** );
char *strdup( char * );


struct snode
{
char *word;
int count;
struct snode *next;
};



int main( void )
{
char word[WORDSIZE];
struct snode *root_node;
struct snode *arr_psnodes[ARRSIZE];
struct snode **psnode, **psnode_last;

psnode = arr_psnodes;
psnode_last = psnode + (ARRSIZE - 1);

root_node = NULL;


while( getword( word, WORDSIZE ) && (psnode != psnode_last) )
{
if( isalpha(word[0]) )
{
root_node = add_to_snode( root_node, word );
*(psnode++) = root_node;
}
}

print_snode( arr_psnodes );

return 0;
}





struct snode *add_to_snode( struct snode *p, char *w )
{
int match;

if( p == NULL )
{
p = malloc( sizeof(struct snode));

if( !p )
{
fprintf( stderr, "out of memory\n" );
exit( EXIT_FAILURE );
}

p->word = strdup( w );
p->count = 1;
p->next = NULL;
}
else if ( !(match = strcmp( p->word, w )) )
{
p->count++;
}
else if( match )
{
p->next = add_to_snode( p->next, w );
}

return p;
}


void print_snode( struct snode **pp )
{
/* yet to be done */
}


void sort_nodes( struct snode **pp )
{
/* yet to be done */
}



char *strdup( char *pc )
{
char *dup;

dup = malloc( strlen(pc) + 1 );

if( dup )
{
strcpy( dup, pc );
}

return dup;
}




/* A program that takes a single word as input. It will discard
* the whole input if it contains anything other than the 26 alphabets
* of English. If the input word contains more than 30 letters then only
* the extra letters will be discarded . For general purpose usage of
* English it does not make any sense to use a word larger than this size.
* Nearly every general purpose word can be expressed in a word with less
* than or equal to 30 letters.
*
*/
int getword( char *word, int max_length )
{
int c;
char *w = word;


while( isspace( c = getchar() ) )
{
;
}

while( --max_length )
{
if( isalpha( c ) )
{
*w++ = c;
}
else if( isspace( c ) || c == EOF )
{
*w = '\0';
break;
}
else
{
return 0;
}

c = getchar();
}


*w = '\0';


return word[0];
}

 

[Keith Thompson]

okay I have edited it a little bit.

[snip]
enum MAXSIZE { ARRSIZE = 1000, WORDSIZE = 30 };

[snip]

You're using the "enum trick" (a name I just invented for it) to
declare ARRSIZE and WORDSIZE as constants. I have no objection to
that, but why give the enum type a name? You never use the identifier
MAXSIZE in the rest of your program.

I'd just do this:
enum { ARRSIZE = 1000, WORDSIZE = 30 };
or perhaps this:
enum { ARRSIZE = 1000 };
enum { WORDSIZE = 30 };

You're never going to use the type; making it anonymous makes that
clear.

(This construct, in either form, is a blatant abuse of the "enum"
construct. It's not what it was intended to be used for. It creates
a type, only to discard it and use only the constants that are created
along with it, almost as a side effect. It's limited to values of
type int. But it's a cool trick anyway.)

 

[arnuld]

I'd just do this:
enum { ARRSIZE = 1000, WORDSIZE = 30 };

You're never going to use the type; making it anonymous makes that
clear.

thanks for the tip

 

[Ben Bacarisse]

root_node = add_to_snode( root_node, word );
*(psnode++) = root_node;

To use one inappropriate data structure, Mr Arnuld, may be regarded as
a unfortunate, but to use two looks looks like carelessness.

Seriously, neither the unsorted array[1] nor a linked list is really
ideal for this job. Either *will* work, so had you used only one, I
would not comment, but it is crazy to use both (and, yes, I do know
why you are doing it -- to sort the array so you print in order -- but
that is not a good reason for such a peculiar design).

[1] You may sort it later, but that is not the point.

 

[arnuld]

To use one inappropriate data structure, Mr Arnuld, may be regarded as
a unfortunate, but to use two looks looks like carelessness.

Seriously, neither the unsorted array[1] nor a linked list is really
ideal for this job. Either *will* work, so had you used only one, I
would not comment, but it is crazy to use both

from last 2 hours I am searching comp.lang.c and comp.programming archives
on Google Groups and a few secods before I read your reply I came across
this reply from "Roger Willcocks" to someone who asked the question on
how to reverse the single-linked list:


My take on this is that if you find you need to search a linked
list from its tail, you've got your design wrong. The list
should be chained the other way, or it should be a doubly
linked list. Get the design right and the question just goes away.

One other point - scanning a linked list is inherently
inefficient; if speed is a factor some other data structure - a
(balanced) tree, or hash table for instance - would be
favourite.



original thread:

http://groups.google.com/group/comp...nk=gst&q=reverse+linked+list#6a91e1d915e179aa



why I gave you this link ?

because banging my head with the function "add_to_snode" I came to know
that it was comparing the word from last node only with the present word
but not with the the words before last node and that is why program was
giving the count of 1 for every word, unless you you enter a word in
succession , say 3 times, but still then because of the array I had, it
will print the word 3 times with count 3 on every line. So I thought I
needed to search the linked list in reverse order in order to see if the
current word was already on the list or not and then I hit that thread.

It only happened when I took a piece of paper and ran the program with my
pen . only then I came to know why the doubly-linked list example from
section 6.5 of K&R2 always returns "p" and never "p->next"

okay, I will use doubly-linked list. Is it fine ?

-- to sort the array so you print in order -- but
that is not a good reason for such a peculiar design).

[1] You may sort it later, but that is not the point.

I did not get you here.

 

[arnuld]

...SNIP...

okay, I will use doubly-linked list. Is it fine ?

...SNIP..

that takes me to the problem I had 4 days ago with the doubly-linked list
program of section 6.5 of K&R2:

struct tnode *add_node( struct tnode *p, char *w )
{
int cond;

if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond > 0 )
{
p->right = add_node( p->right, w );
}

return p;
}


if you look at it closely, you will see that it always returns "p", no
matter whether p is NULL or p->word is already on the list or which else
if clause we are using, that will make p the center-point from where
everything will start and that is the main reason it keeps words sorted
right there on-the-fly and then authors only need to print the p->left, p
and then p->right.


Now the problem is, this code will keep p at the center-point for it wants
to sort th words alphabetically. In my case, I want to sort them in order
of their occurrence, which can not determined before we have seen all of
the words. So what concept or idea to use here with a doubly-linked list ?

 

[Ben Bacarisse]

that takes me to the problem I had 4 days ago with the doubly-linked list
program of section 6.5 of K&R2:

struct tnode *add_node( struct tnode *p, char *w )
{
int cond;

if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond > 0 )
{
p->right = add_node( p->right, w );
}

return p;
}

This is not a doubly linked list. This is a binary search tree. They
have the same "shape": struct S { data d; struct S *a, *b; } but very
different constraints.

Now the problem is, this code will keep p at the center-point for it wants
to sort th words alphabetically. In my case, I want to sort them in order
of their occurrence, which can not determined before we have seen all of
the words. So what concept or idea to use here with a doubly-linked
list ?

You need to do an in-order traversal of the tree.

 

[Ben Bacarisse]

Seriously, neither the unsorted array[1] nor a linked list is really
ideal for this job. Either *will* work, so had you used only one, I
would not comment, but it is crazy to use both

It only happened when I took a piece of paper and ran the program with my
pen . only then I came to know why the doubly-linked list example from
section 6.5 of K&R2 always returns "p" and never "p->next"

okay, I will use doubly-linked list. Is it fine ?

I am going to hold off answering, because in anther post you suggest
that you are confusing a doubly linked list with a binary tree. Until
that is cleared up there is no point in discussing details.

-- to sort the array so you print in order -- but
that is not a good reason for such a peculiar design).

[1] You may sort it later, but that is not the point.

I did not get you here.

What more can I say? Let me try... You store the words in a (singly)
linked list and at the same time store every one in an array. You
waste space and at the same time have the complexity of a list with
all the disadvantages of a fixed-size array. All this mess is
presumably because you don't know how to sort a linked list. I would
accept that if your code used a malloced array in a function called
"print_list_in_order" because that would keep the code simple and you
could always re-write it later to just sort the list, but your array
is used in the main loop.