Thread: Linked Lists

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    26

    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

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    And your question is what, exactly?

    Maybe:
    http://cslibrary.stanford.edu/103/
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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

  4. #4
    Information Crocodile
    Join Date
    Dec 2004
    Posts
    204
    First of all i feel lazy just looking at your code. I suggest that you indent it properly so itll be readable.

  5. #5
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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); 
    }
    Last edited by wvu2005; 10-03-2005 at 08:09 AM. Reason: Indented code and also included code updates.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    free anything that you *alloc.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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); 
    
    
    
    }

  8. #8
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    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.

  9. #9
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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); 
    
    
    
    }

  10. #10
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  11. #11
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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); 
    
    
    
    }

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    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); 
    
    
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM