Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Linked Lists

Reply
Thread Tools

Linked Lists

 
 
Foodbank
Guest
Posts: n/a
 
      10-01-2005
Hi,

I have to write a program that will use linked lists to print the
number of unique words, total words, and the most frequent word from a
text file. I've gotten a decent amount of it done except for the
linked lists. I did not paste my code that tells the machine what a
word is, it works fine and it'll be easier to read that way without it.
Below is the code:

//****code from here to next section is good, I don't need help
there****//
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct list_elem {
char *word;
int count;
struct list_elem *next;
};

struct list_elem *head; /* the head pointer is initially NULL */

int get_word(char *);
void add_to_list(char *);
void list_walk(void);

int unique_words, total_words;
struct list_elem *most_frequent_elem;

main() {
char word_buff[100];
while(get_word(word_buff))
add_to_list(word_buff);
list_walk();
printf("there are %d unique words out of %d total words\n",
unique_words, total_words);
printf("the most frequent word is <%s> which used %d times\n",
most_frequent_elem->word, most_frequent_elem->count);
}
//**************************
//***********help here and below
void add_to_list(char *word_buff) {
/* *CODE TO SEARCH THE LIST AND COUNT REPEAT WORDS
/* ** CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS


void list_walk() {
/* ****** CODE TO WALK THE LIST AND GATHER THE STATS
}

Any help is greatly appreciated.

Thanks,
James

 
Reply With Quote
 
 
 
 
Alexei A. Frounze
Guest
Posts: n/a
 
      10-01-2005
"Foodbank" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> I have to write a program that will use linked lists to print the
> number of unique words, total words, and the most frequent word from a
> text file.

....
> //***********help here and below
> void add_to_list(char *word_buff) {
> /* *CODE TO SEARCH THE LIST AND COUNT REPEAT WORDS
> /* ** CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS
>
>
> void list_walk() {
> /* ****** CODE TO WALK THE LIST AND GATHER THE STATS
> }


This problem has as much to do with C as with Pascal, Basic, Assembly
language, etc etc.
It's a homework. The simplest, I must say. Instead of asking, think over
what is a linked list. Draw it if you don't understand things unless they're
visualized. If you have no idea what a linked list is, read your book(s),
lecture note(s), ask your teacher, or search the internet, but this I
believe is something you are able to do w/o asking for any help.

Alex


 
Reply With Quote
 
 
 
 
Flash Gordon
Guest
Posts: n/a
 
      10-02-2005
Foodbank wrote:
> Hi,
>
> I have to write a program that will use linked lists to print the
> number of unique words, total words, and the most frequent word from a
> text file. I've gotten a decent amount of it done except for the
> linked lists. I did not paste my code that tells the machine what a
> word is, it works fine and it'll be easier to read that way without it.
> Below is the code:
>
> //****code from here to next section is good, I don't need help
> there****//
> #include <stdio.h>
> #include <string.h>
> #include <stdlib.h>
> struct list_elem {
> char *word;
> int count;
> struct list_elem *next;
> };
>
> struct list_elem *head; /* the head pointer is initially NULL */


I would have declared the head within main using a more explicit name
such as word_head and then passed it as a parameter.

> //**************************
> //***********help here and below
> void add_to_list(char *word_buff) {
> /* *CODE TO SEARCH THE LIST AND COUNT REPEAT WORDS
> /* ** CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS


So try writing the code and we will help you with any specific problems
in C coding you have. I'm sure your tutor has either explained linked
lists of given you suitable reference material to read. We try to avoid
actually doing peoples homework for them.

> void list_walk() {
> /* ****** CODE TO WALK THE LIST AND GATHER THE STATS


You probably need some mechanism for returning the stats.

> }
>
> Any help is greatly appreciated.


Make your best effort. Getting us to do your homework won't help you to
learn. If you can't even start then you really need to discuss it with
your tutor since obviously the class is not working for you.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
 
Reply With Quote
 
Foodbank
Guest
Posts: n/a
 
      10-02-2005
Hi guys, I've read more about linked lists and have a better idea of
what they are now. I've added some code, could you please check it out
and possibly help me with what's missing?

Thanks,
James

PS This isn't homework, I'm self-teaching myself C in order to change
job positions (more programming oriented than my current position). I
guess in one regard it is homework, but it's for my own good, not for a
grade. I do appreciate the input up to this point.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct list_elem {
char *word;
int count;
struct list_elem *next;
};

struct list_elem *head;

int get_word(char *);
void add_to_list(char *);
void list_walk(void);

int unique_words, total_words;
struct list_elem *most_frequent_elem;

main() {
char word_buff[100];
while(get_word(word_buff))
add_to_list(word_buff);
list_walk();
printf("there are %d unique words out of %d total words\n",
unique_words, total_words);
printf("the most frequent word is <%s> which used %d times\n",
most_frequent_elem->word, most_frequent_elem->count);
}

void add_to_list(char *word_buff) {

/* ***** SECTION TO SEARCH THE LINKED LIST AND COUNT ANY
REPEATED WORDS****//
//MY MEASLY START, NOT SURE IF CORRECT
count=malloc(strlen(word(buff)+1));

/* ***** MAKE NEW ELEMENTS FOR BRAND NEW WORDS *****/

//WHAT I'VE GOTTEN SO FAR
sizeof(struct list_elem);
malloc(sizeof(list_elem));
}

void list_walk() {
/* ****** CODE TO WALK THE LIST AND GATHER THE STATS ***** */

struct list_elem *lp; int n=0;
for(lp=head; lp!=NULL; lp=lp->next)
n++;


}

//CODE DOESN'T NEED MODIFIED, I USED IT FROM AN OLD PROGRAM THAT TELLS
THE COMPILER WHAT A WORD IS
#include <ctype.h>
/* Leave this routine EXACTLY as it stands */
int get_word(char *s) {
int c;
do {
c = getchar();
if(c == EOF)
return(0);
} while(!isalpha(c) && !isdigit(c));
do {
if(isupper(c))
c = tolower(c);
*s++ = c;
c = getchar();
} while(isalpha(c) || isdigit(c));
*s = 0;
return(1);
}



Any help is greatly appreciated.

Thanks,
James

 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      10-02-2005
On 2 Oct 2005 15:03:43 -0700, "Foodbank" <(E-Mail Removed)> wrote:

>Hi guys, I've read more about linked lists and have a better idea of
>what they are now. I've added some code, could you please check it out
>and possibly help me with what's missing?
>
>Thanks,
>James
>
>PS This isn't homework, I'm self-teaching myself C in order to change
>job positions (more programming oriented than my current position). I
>guess in one regard it is homework, but it's for my own good, not for a
>grade. I do appreciate the input up to this point.
>
>
>#include <stdio.h>
>#include <string.h>
>#include <stdlib.h>
>struct list_elem {


Adopt a consist style of indenting. It has one of the largest returns
on investment of any programming technique.

>char *word;
>int count;
>struct list_elem *next;
>};
>
>struct list_elem *head;
>
>int get_word(char *);
>void add_to_list(char *);
>void list_walk(void);
>
>int unique_words, total_words;
>struct list_elem *most_frequent_elem;
>
>main() {
>char word_buff[100];
>while(get_word(word_buff))
>add_to_list(word_buff);
>list_walk();
>printf("there are %d unique words out of %d total words\n",
>unique_words, total_words);
>printf("the most frequent word is <%s> which used %d times\n",
>most_frequent_elem->word, most_frequent_elem->count);


You do not handle the degenerative case where there is no input.

>}


It is considered good style to clean up your allocations when done
with them. While most OSs will probably do this for you when your
program exits, think of the case where your program later becomes part
of a larger application.

>
>void add_to_list(char *word_buff) {
>
>/* ***** SECTION TO SEARCH THE LINKED LIST AND COUNT ANY
>REPEATED WORDS****//
>//MY MEASLY START, NOT SURE IF CORRECT


How would you do this using paper and pencil. The technique is the
same.

If this is the first word, create a node and save address in head.

Else search existing nodes for same word:

If found, increment count.

Else create a node and link it to list

Each time you allocate a node, you also need to allocate space for the
word the node will point to.

>count=malloc(strlen(word(buff)+1));


Didn't your compiler produce an error message here? There is no
variable count defined in your code. There is a struct member named
count but this isn't that.

>
>/* ***** MAKE NEW ELEMENTS FOR BRAND NEW WORDS *****/
>
>//WHAT I'VE GOTTEN SO FAR
>sizeof(struct list_elem);


This expression is a compile time constant. After the expression is
evaluated, the result of that evaluation is ignored. What did you
intend to happen?

>malloc(sizeof(list_elem));


Calling malloc and discarding the return value is one of the easiest
ways to create a memory leak. You probably intended to use the area
returned by malloc to hold a new node in the list. However, at this
time, you don't even know if you need a new node. (If the word is the
same as an existing word in the list, you would not.)

list_elem is not a valid type. struct list_elem is.

>}
>
>void list_walk() {
>/* ****** CODE TO WALK THE LIST AND GATHER THE STATS ***** */
>
>struct list_elem *lp; int n=0;
>for(lp=head; lp!=NULL; lp=lp->next)
>n++;
>
>
>}
>
>//CODE DOESN'T NEED MODIFIED, I USED IT FROM AN OLD PROGRAM THAT TELLS
>THE COMPILER WHAT A WORD IS
>#include <ctype.h>
>/* Leave this routine EXACTLY as it stands */
>int get_word(char *s) {
>int c;
>do {
>c = getchar();
>if(c == EOF)
>return(0);
>} while(!isalpha(c) && !isdigit(c));
>do {
>if(isupper(c))
>c = tolower(c);
>*s++ = c;
>c = getchar();
>} while(isalpha(c) || isdigit(c));
>*s = 0;
>return(1);
>}
>
>
>
>Any help is greatly appreciated.
>
>Thanks,
>James



<<Remove the del for email>>
 
Reply With Quote
 
Foodbank
Guest
Posts: n/a
 
      10-03-2005
Hi guys,

I indented the code for easier reading. Sorry about that. Thanks
again for the help.

BTW, Barry, my program didn't compile.

Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct list_elem {
    char *word;
    int count;
    struct list_elem *next;
    };

struct list_elem *head;

int get_word(char *);
void add_to_list(char *);
void list_walk(void);

int unique_words, total_words;
struct list_elem *most_frequent_elem;

main() {
    char word_buff[100];
    while(get_word(word_buff))
    add_to_list(word_buff);
    list_walk();
    printf("there are %d unique words out of %d total words\n",
    unique_words, total_words);
    printf("the most frequent word is <%s> which used %d
    times\n",
    most_frequent_elem->word, most_frequent_elem->count);
    }

void add_to_list(char *word_buff) {

    //SECTION TO SEARCH THE LINKED LIST AND COUNT ANY
    //REPEATED WORDS
    //HELP HERE

    //NOT SURE IF RIGHT
    count=malloc(strlen(word(buff)+1));

    //MAKE NEW ELEMENTS FOR BRAND NEW WORDS
    //HELP HERE

    //WHAT I'VE GOTTEN SO FAR
    sizeof(struct list_elem);
    malloc(sizeof(list_elem));
    }

void list_walk() {
    //CODE TO WALK THE LIST AND GATHER THE STATS
    //HELP HERE

    struct list_elem *lp; int n=0;
    for(lp=head; lp!=NULL; lp=lp->next)
        n++;
    }


//CODE BELOW DOESN'T NEED MODIFIED, I USED IT FROM AN OLD PROGRAM THAT
TELLS THE COMPILER WHAT A WORD IS
#include <ctype.h>
int get_word(char *s) {
    int c;
    do {
        c = getchar();
        if(c == EOF)
        return(0);
        }
while(!isalpha(c) && !isdigit(c));
    do {
        if(isupper(c))
        c = tolower(c);
        *s++ = c;
        c  = getchar();
        }
while(isalpha(c) || isdigit(c));
    *s = 0; 
    return(1); 
}
 
Reply With Quote
 
Foodbank
Guest
Posts: n/a
 
      10-03-2005
Hi all, thanks for the replies so far.

I've made some progress. My code is below. At the end of the code are
the errors I'm receiving.

Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct list_elem {
	char *word;
	int count;
	struct list_elem *next;
        };
struct list_elem *head;

int get_word(char *);
void add_to_list(char *);
void list_walk(void);

int unique_words, total_words;
struct list_elem *most_frequent_elem;

main() {
	char word_buff[100];
	while(get_word(word_buff))
		add_to_list(word_buff);
	list_walk();
	printf("there are %d unique words out of %d total words\n",
		unique_words, total_words);
	printf("the most frequent word is <%s> which used %d times\n",
		most_frequent_elem->word, most_frequent_elem->count);
       }

void add_to_list(char *word_buff) {
	//CODE TO SEARCH THE LIST AND COUNT REPEAT WORDS

	head->word = malloc(strlen(word_buff)+1);

        //CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS

       //new list element
       if(!head)
              head = malloc(sizeof(list_elem));
           else
           {
           struct list_elem* tmp = head;
           head = malloc(sizeof(list_elem));
           head->next = head;
           }
}

void list_walk() {
	//CODE TO WALK THE LIST AND GATHER THE STATS

	struct list_elem *lp; int n=0;
	for(lp=head; lp!=NULL; lp=lp->next)
	n++;
	}

#include <ctype.h>
/* Leave this routine EXACTLY as it stands */
int get_word(char *s) {
	int c;
	do {
		c = getchar();
		if(c == EOF)
			return(0);
	} while(!isalpha(c) && !isdigit(c));
	do {
		if(isupper(c))
			c = tolower(c);
		*s++ = c;
		c = getchar();
	} while(isalpha(c) || isdigit(c));
	*s = 0;
	return(1);
}
Errors:

In function `add_to_list':
error: `list_elem' undeclared (first use in this function)
error: (Each undeclared identifier is reported only once
error: for each function it appears in.)

error: `list_elem' undeclared (first use in this function) is referring
to
head = malloc(sizeof(list_elem));

Thanks again,
James

 
Reply With Quote
 
Martin Ambuhl
Guest
Posts: n/a
 
      10-03-2005
Foodbank wrote:
> Hi all, thanks for the replies so far.
>
> I've made some progress. My code is below. At the end of the code are
> the errors I'm receiving.

[...]


> In function `add_to_list':
> error: `list_elem' undeclared (first use in this function)


You have no type list_elem. You have the type 'struct list_elem'
 
Reply With Quote
 
Default User
Guest
Posts: n/a
 
      10-03-2005
Foodbank wrote:

> Hi guys,
>
> I indented the code for easier reading. Sorry about that. Thanks
> again for the help.


Please read my .sig. There's been a long discussion about this very
point ongoing in another thread.


Brian
--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header.
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      10-04-2005
On 3 Oct 2005 06:26:46 -0700, "Foodbank" <(E-Mail Removed)> wrote:

>Hi all, thanks for the replies so far.
>
>I've made some progress. My code is below. At the end of the code are
>the errors I'm receiving.
>
>
Code:
>#include <stdio.h>
>#include <string.h>
>#include <stdlib.h>
>struct list_elem {
>	char *word;
>	int count;
>	struct list_elem *next;
>        };
>struct list_elem *head;
Code:
head is automatically initialized to NULL.

>
>int get_word(char *);
>void add_to_list(char *);
>void list_walk(void);
>
>int unique_words, total_words;
>struct list_elem *most_frequent_elem;
>
>main() {
>	char word_buff[100];
>	while(get_word(word_buff))
>		add_to_list(word_buff);
>	list_walk();
>	printf("there are %d unique words out of %d total words\n",
>		unique_words, total_words);
>	printf("the most frequent word is <%s> which used %d times\n",
>		most_frequent_elem->word, most_frequent_elem->count);
>       }
>
>void add_to_list(char *word_buff) {
>	//CODE TO SEARCH THE LIST AND COUNT REPEAT WORDS
>
>	head->word = malloc(strlen(word_buff)+1);

After getting the first word, you attempt to dereference head.  This
causes undefined behavior.  On a decent system, your program will
abort with some useful error message.  This could be inside the
following if but it would be better to have it follow your if else
since whenever you create a new node you need to create a place for it
to point to.

>
>        //CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS
>
>       //new list element
>       if(!head)
>              head = malloc(sizeof(list_elem));
>           else
>           {
>           struct list_elem* tmp = head;
>           head = malloc(sizeof(list_elem));
>           head->next = head;

Obviously you meant head->next = tmp.

This will allow you to add the new node at the beginning of the linked
list but you don't know yet if you even need it.  What happens if this
word is a duplicate of one already in the list.

>           }

You never copied the current word to the area the new node points to.
All of you nodes are useless without this.

>}
>
>void list_walk() {
>	//CODE TO WALK THE LIST AND GATHER THE STATS
>
>	struct list_elem *lp; int n=0;
>	for(lp=head; lp!=NULL; lp=lp->next)
>	n++;

What is the point of this function.  After you count the number of
nodes, n is destroyed.

>	}
>
>#include <ctype.h>
>/* Leave this routine EXACTLY as it stands */
>int get_word(char *s) {
>	int c;
>	do {
>		c = getchar();
>		if(c == EOF)
>			return(0);
>	} while(!isalpha(c) && !isdigit(c));
>	do {
>		if(isupper(c))
>			c = tolower(c);
>		*s++ = c;
>		c = getchar();
>	} while(isalpha(c) || isdigit(c));
>	*s = 0;
>	return(1);
>}
>
>

>
>Errors:
>
>In function `add_to_list':
>error: `list_elem' undeclared (first use in this function)
>error: (Each undeclared identifier is reported only once
>error: for each function it appears in.)
>
>error: `list_elem' undeclared (first use in this function) is referring
>to
>head = malloc(sizeof(list_elem));


Use sizeof *head and save yourself some aggravation.

>
>Thanks again,
>James



<<Remove the del for email>>
 
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
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
List of lists of lists of lists... =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==?= Python 5 05-15-2006 11:47 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments