-
Linked Lists
Hi,
I'm writing 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 got a start on the lists, but am still unsure where to proceed from there.
Below is the code:
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
//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>
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
-
And your question is what, exactly?
Maybe:
http://cslibrary.stanford.edu/103/
-
I'm not sure how and what to malloc for the linked lists. Also, if anyone could critique my code for walking the list that would let me know if I at least did that right. Lastly, for the main parts of the program (the word counting), would I use a loop? I'm pretty sure that strcmp will be used, but not sure what strings to compare.
Thanks,
James
-
First of all i feel lazy just looking at your code. I suggest that you indent it properly so itll be readable.
-
Indented code below, sorry about that. I also made some progress from my initial post.
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
head->word = malloc(strlen(word_buff)+1);
//MAKE NEW ELEMENTS FOR BRAND NEW WORDS
//HELP HERE
//WHAT I'VE GOTTEN SO FAR
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
//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);
}
-
free anything that you *alloc.
-
Here's an update. It'll compile now, but when I try to count the words, I get a segmentation fault. I'm really unsure where to go from here. Any help would benefit me greatly.
Thanks,
James
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);
}
-
For a start, you declare head as a pointer, and it's initialised to NULL because it's declared outside any functions. Then, in add_to_list, you dereference it with head->word before malloc'ing any space for it.
-
Hi again,
Made a few changes. Any more input? I've got the program set up with the variables to print the wordcounts, I just don't know how to actually perform them.
Thanks again,
James
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();
//the below printf's are just wrapped around so they'd fit on
//the message board, they're correct in my actually code
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
//CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS
if(!head)
head = malloc(sizeof(struct list_elem));
else
{
struct list_elem* tmp = head;
head = malloc(sizeof(struct list_elem));
head->next = tmp;
}
head->word = malloc(strlen(word_buff)+1);
strcpy(head->word,word_buff);
}
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);
}
-
>>number of unique words, total words, and the most frequent word from a text file.
In order to meet these requirements, you need to change your link list processing.
When you add a new node to the list, start by searching the list to determine if a node already exists that contains the same word as the one you're entering. If you find a match, don't allocate a new node; instead, simply increment a counter variable on the existing node, noting that another occurence of this word has been applied. If you don't find a matching node (meaning this is the first time the word is being put into the list), allocate the node, copy in the word, and set the counter variable to 1.
Now, having done that, you can meet the requirements as follows:
>>number of unique words
This is the count of nodes.
>>total words
This is the sum of the counter variables from each and every node.
>>the most frequent word
The word from the node with the highest counter value.
-
Hi,
Can anyone comment my code between the brackets below? My friend helped me and I'm kind of unsure what's really going on.
Thanks,
James
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);
}
////////////////////comment here to next set of brackets
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
if(!head)
head = malloc(sizeof(struct list_elem));
else
{
struct list_elem* tmp = head;
head = malloc(sizeof(struct list_elem));
head->next = tmp;
}
head->word = malloc(strlen(word_buff)+1);
strcpy(head->word,word_buff);
}
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++;
}
////////////////////////don't need commenting below
#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);
}
-
Code:
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++;
}
This justs counts all the elemts in the array. It starts at the beginning and goes to the end, ++ing n along the way.
-
Hi everyone,
Thanks for the help so far. I've made a lot of progress, but I'm getting incorrect word counts. Can anyone check this over and see what's wrong?
Thanks,
James
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
struct list_elem *tmp = head;
for(tmp=head; tmp!=NULL; tmp=tmp->next)
{
if(!strcmp(word_buff, tmp->word))
tmp->count++;
return;
}
//CODE TO MAKE NEW ELEMENTS FOR BRAND NEW WORDS
tmp=head;
head = malloc(sizeof(struct list_elem));
head->next = tmp;
head->word = malloc(strlen(word_buff)+1);
strcpy(head->word,word_buff);
}
void list_walk() {
//CODE TO WALK THE LIST AND GATHER THE STATS
most_frequent_elem=head;
struct list_elem *lp;
for(lp=head; lp!=NULL; lp=lp->next)
{
unique_words++;
total_words += lp->count;
if(lp->count > most_frequent_elem->count)
most_frequent_elem=lp;
}
}
#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);
}