Thread: linked list

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    39

    linked list

    Hi,
    I have two problems:
    please can someone give me an algorithm that would help me to understand how to put words ( read from a file) in alphabetical order using a linked list. I just dont get it!!

    Also, The words that I need to input is a real text.
    but There is punctuation (",", "!",".") that I need to skip in order to continue inputting words.
    I know that I can do

    Code:
     fscanf(fptr,"  [^,], ", words)
    to skip the comma. but how can I do all the 3 punctuations in once?

    Thank you for your help and time
    B.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,659
    You can list whatever characters you're interested in in the scan set.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by braddy
    Hi,
    I have two problems:
    please can someone give me an algorithm that would help me to understand how to put words ( read from a file) in alphabetical order using a linked list. I just dont get it!!
    You need to be able to start by getting the words and inserting them into the list unsorted and then worry about sorting them. Can you do that?
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Jan 2006
    Posts
    39
    Quote Originally Posted by hk_mp5kpdw
    You need to be able to start by getting the words and inserting them into the list unsorted and then worry about sorting them. Can you do that?
    I try but it does not work!
    This is what I did. I have 2 main problem:
    1- in create function I have a problem read the word by word and then continue when one line is done.
    2- the way I wrote create does not work. it crashes

    this is my template and my function create that is suppose to create a likned list as I read the text.
    Code:
    typedef struct wordnode {
            char *word;
            int length;
            int freq;
            struct wordnode *next}   WORD;
    
    
    void create(WORD *record)    
      {  char temp[30]; 
          int k;
          FILE *fin;
          fin=fopen("cp50610.dat","r");
          fscanf(fin," %[^ ,.;'?!]",temp); 
          k = strlen(temp)+1; /*use for the future*/
          record->word=malloc(k*sizeof(char)); 
          strcpy(record->word,temp); 
         record->next = malloc(sizeof(WORD));
         create(record->next); 
         fclose(fin);
         } /*end of create */
    Please can someone help me?
    thank you
    B

  5. #5
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Your function might work better if you had something like:

    Code:
    void create(WORD *record, FILE *f)
    And then you don't just keep opening and opening and opening and opening the file. It never closes because it is infinite recursion. You should make a base case for it to stop.

  6. #6
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    I might be having a brain fart, but I'm drawing a blank right about here

    Code:
    record->word=malloc(k*sizeof(char)); 
          strcpy(record->word,temp); 
         record->next = malloc(sizeof(WORD));
    If you allocate memory to record->word, don't you like need to allocate memory large enough to access the structure that access record->next?

  7. #7
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    I don't think so. The function operates on an already allocated WORD node and then allocates space for the next one and calls itself recursively. This is also an issue, when you initially call the function, your head node should be previously allocated, and also in your base case you should set the end of the list making record->next = NULL;

  8. #8
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Okay. Maybe this is just personal bias, but I personally don't care for recursion in linked lists. I think recursive functions should be confined to the realm of Binary Trees. I just prefer the route of setting up a head node, pass it to the function, then doing a bunch of calls to malloc() (via the while loop) to produce the nodes on a linked list.
    Last edited by cdalten; 04-11-2006 at 07:22 PM.

  9. #9
    Registered User
    Join Date
    Jan 2006
    Posts
    39
    Quote Originally Posted by Tonto
    I don't think so. The function operates on an already allocated WORD node and then allocates space for the next one and calls itself recursively. This is also an issue, when you initially call the function, your head node should be previously allocated, and also in your base case you should set the end of the list making record->next = NULL;
    I have some issue in the display. I have made the changes but when I execute, the output file is blank, even the header output does not print.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct wordnode {
            char *word;
            int length;
            int freq;
            struct wordnode *next}   WORD;
    
    main()
    {
          FILE *fin,*fout;
         WORD *start;
    	  void create(WORD *pt,FILE *fin);
    	  void display(WORD * pt,FILE *fout ); 
          fin=fopen("cp50610.dat","r");
          fout=fopen("cp50610.out","w");
          fprintf(fout,"**********************\n");
          fprintf(fout,"       OUTPUT\n");
          fprintf(fout,"**********************\n");
          
    	start=malloc(sizeof(WORD));/* get space for first node*/
    	create(start,fin);
    	display(start,fout);
      
          fclose(fin);
          fclose(fout);
          	return 0;
    }/* end main*/
    
    
    void create(WORD *record, FILE *fin)    /*to create the list */
     /* argument points to current node; function is recursive */
     /* strings are input until string END is encountered */
      {char temp[30]; /*temporary storage for string */
       int k; /*length of current string */
       
       fscanf(fin," %[^ ,.;?\n]",temp); /*input into temp to get length */
       k = strlen(temp)+1; /*need room for null character */
       record->word=malloc(k*sizeof(char)); /*get address for permanent storage of string */
       strcpy(record->word,temp); /*put string there */ 
         record->next = malloc(sizeof(WORD));
         create(record->next,fin); 
        
         } /*end of create */
        
        void display(WORD * record,FILE *fout)  /*to print linked list */
    /*argument points to start of list */
     {      
               fprintf(fout,"%s\n",record->word); /* print this one */ 
          while(record->next != NULL)  /* & walk down list */
            { record = record->next;
               fprintf(fout,"%s\n",record->word); /* print this one */
            }   
     } /*end of display */

  10. #10
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    You should strcmp(test, "END"), and then set record->next = NULL; and return; if they're the same in create.

  11. #11
    Registered User
    Join Date
    Jan 2006
    Posts
    39
    Quote Originally Posted by Tonto
    You should strcmp(test, "END"), and then set record->next = NULL; and return; if they're the same in create.
    Oh please sorry never mind the comment about the END thing I was testing my function earlier with that..
    Sorry I forgot to remove this comment.
    This should not be the issue here!

  12. #12
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    You got to stop that recursion at some point.

  13. #13
    Registered User
    Join Date
    Jan 2006
    Posts
    39
    Quote Originally Posted by Tonto
    You got to stop that recursion at some point.
    you are right I 'll try to fix that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM