Thread: Reading a file to linked lists?!

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    12

    Reading a file to linked lists?!

    Hi. I have to write a program that reads from a text file, which contains a list of stock hourly prices and the company names. Something like this:

    78.52 82.56 75.10 71.97 Water Company
    22.40 25.68 21.37 22.96 Mega Shipping Inc

    ....etc.

    Each company data will be kept in a structure that contains: a pointer for the name, an array of the prices, and the average price for the day. The structures will be kept in a linked list. Each node structure will contain a pointer to one company data, and a pointer to the next node structure.

    This is all I have so far...

    Code:
    typedef struct    {
            char *companyName;
            double hourlyPrices[NUM_PRICES];
            double avgPrice;
        } COMPANYDATA;
    
    
    typedef struct nodeTag
    {
        COMPANYDATA *pCompanyData;
        struct nodeTag *link;
    
    } NODE;
    We have to sort the nodes alphabetically. My question is, how do I read the data from the file one line at a time, and insert them alphabetically one by one?

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    I would suggest the following

    1. read whole line into the temp buffer with fgets
    2. Allocate new COMPANYDATA
    3. parse stock data into hourlyPrices array (for example with strtod calls)
    4. Find a start of the company name and allocate buffer to store it
    5. Copy Company name to allocated buffer, set the pointer inside COMPANYDATA as well as avg price
    6. if the above is successful - create new node, set the pCompanyData pointer and insert this node in the list according to company name sorting order.
    7. do the above in the loop till all the file is read.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    What's wrong with your previous thread?

  4. #4
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by orangePeel View Post
    Each company data will be kept in a structure that contains: a pointer for the name, an array of the prices, and the average price for the day. The structures will be kept in a linked list. Each node structure will contain a pointer to one company data, and a pointer to the next node structure.
    The node structure sounds atypical. Usually you'll see the companies defined as a linked list:
    Code:
    typedef  struct company  company_t;
    struct company {
        struct company *next;  /* Next company in linked list */
        char *name;
        double price[MAXPRICES];
        double average;
    };
    Just for fun, I wrote some code using setlocale() to use the user's preferred locale (language rules) for sorting the names using strcoll(), and getline() provided by POSIX.1-2008 -compatible C libraries to read lines of any length.

    The structure I used was
    Code:
    typedef struct price price_t;
    struct price {
        struct price    *next;
        size_t           namelen;
        char            *name;
        size_t           prices;
        double          *price;   /* price[prices] is the average price */
    };
    which allows any number of prices per company. The program itself takes one or more input file names as command-line parameters, reads them all into a single linked list sorted by name (calculating the average at the same time for each company), and prints out the summary. Using
    Code:
    22.22 12.35 Üh?
    1.2 53.12 323.23 Ag€nts
    Ööps
    in C/POSIX locale (typical US English), it outputs
    Code:
    Name: Ag€nts
    	Price 1: 1.20
    	Price 2: 53.12
    	Price 3: 323.23
    	Average: 125.85
    Name: Ööps
    	No prices.
    Name: Üh?
    	Price 1: 22.22
    	Price 2: 12.35
    	Average: 17.29
    but in my preferred fi_FI.utf8 locale (Finnish, using UTF-8 character set), it outputs
    Code:
    Name: Ag€nts
    	Price 1: 1.20
    	Price 2: 53.12
    	Price 3: 323.23
    	Average: 125.85
    Name: Üh?
    	Price 1: 22.22
    	Price 2: 12.35
    	Average: 17.29
    Name: Ööps
    	No prices.
    i.e. sorting the names correctly in Finnish.

    I ended up having about 190 lines of code, not counting comments or empty lines, so it's definitely not that complicated to do.

    I was a bit lazy, and instead of sorting the list (using one of the efficient sorting algorithms for linked lists), I simply build the list by adding each new entry to the correct location by traversing the list from the start for each insertion.
    I do have a reason, though. Inserting the items into a (balanced) tree is much more efficient wall-clock-wise for this case, than sorting the list afterwards. And transforming the list into a tree requires very small changes to the structure.

    You see, in most cases, reading data from disk is the bottleneck, and doing the "insertion" work instead of waiting for disk reads to complete, is free. If you do the sort afterwards, even if the sort was lightning fast, it's still additional wall clock time taken. This applies always when disk reads are slower than insertion. Rather surprising, isn't it?

    Quote Originally Posted by orangePeel View Post
    My question is, how do I read the data from the file one line at a time, and insert them alphabetically one by one?
    Use fgets() to read each line into a buffer. (I used getline() instead, because it dynamically allocates and resizes the buffer; but only POSIX.1-2008 -compatible C libraries provide it. Microsoft does not, AFAIK; just about every other recent C library does.)

    You scan the fields from the buffer using for example sscanf(line, " %lf %lf %lf %lf %99[^\r\n]", &price1, &price2, &price3, &price4, nameof100chars), making sure the return value is 5 (at least -- five fields converted), or a bit more complicated loop to parse each field in turn.

    To sort strings properly, you should use locales. Include <locale.h>, and call setlocale(LC_COLLATE, ""); at the start of your program, and you're done. That makes strcoll() compare the two strings using rules from user's current locale. These are standard C89/C99 functions, and should work even in Windows.

    To have the list sorted according to the names, you have two options:
    1. Insert new companies into the correct position
      You can do this simply by comparing the new name and each name in the existing list in turn, advancing in the list, until the new name comes before the name in the list; you insert the new company there.
      This is very simple to implement -- all you really need to worry about is the first company (when the list is empty, or the new company is inserted in front of the existing list) --, but it is not efficient if you have a lot of data.
    2. Insert new company at the beginning of the list, and sort afterwards
      Prepending to a singly-linked list is trivial, literally just two statements.
      Sorting linked lists is an interesting question, since there are a lot of algorithms, and many algorithms that are good for sorting arrays are not that good for sorting linked lists, and vice versa. (You can work around that by using an array of pointers, and sorting the array using e.g. quicksort.)

    If the exercise is about sorting, do the latter, otherwise do the former.
    For real applications, use a tree instead, for better performance.

    Apologies for the overlong, meandering post.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    12
    Hi guys. Can you look over my program and see what I have done wrong (lots of things I'm sure....). I never thought I would post my work here for safety reasons, but I am very lost so....

    This is my text file:

    51.41 52.07 52.01 51.22 50.44 49.97 Coal Diggers
    77.26 78.33 78.29 78.12 77.09 75.74 Airplane Flyers
    31.25 31.44 31.43 31.09 31.01 30.92 Oil Fracting and Pumping
    2.03 2.02 2.04 2.00 1.98 1.97 Big Bank
    44.21 44.32 44.29 43.98 43.82 43.71 Rail Container Shipping
    93.21 93.11 93.02 93.31 92.98 92.89 Gold Bugs
    Code:
    #include <stdio.h>#include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #define NUM_PRICES 6
    
    
    typedef struct
        {
            char *companyName;
            double hourlyPrices[NUM_PRICES];
            double avgPrice;
        } COMPANYDATA;
    
    
    typedef struct nodeTag
    {
        COMPANYDATA *pCompanyData;
        struct nodeTag *link;
    } NODE;
    
    
    NODE* buildList(char* fileID);
    bool getData (FILE* fpData, COMPANYDATA* pCompanyData);
    bool searchList (NODE* pList, NODE** pPre, NODE** pCur, char* target);
    NODE* insertNode(NODE* pList, NODE* pPre, COMPANYDATA item);
    void printList(NODE* pList);
    
    
    int main()
    {
        NODE* pList;
        NODE* pPre;
        NODE* pCur;
        COMPANYDATA companyData;
    
    
        pList = buildList("HW6.txt");
        printList(pList);
    }
    
    
    NODE* buildList(char* fileID)
    {
        COMPANYDATA companyData;
        NODE* pList;
        NODE* pPre;
        NODE* pCur;
        FILE* fpData;
    
    
        pList = NULL;
    
    
        fpData = fopen(fileID, "r");
        if(!fpData)
            {
                printf("Error opening file.");
                exit (210);
            }
    
    
        while (getData (fpData, &companyData))
            {
                searchList(pList, &pPre, &pCur, companyData.companyName);
                pList = insertNode (pList, pPre, companyData);
            }
    
    
        return pList;
    }
    
    
    bool getData (FILE* fpData, COMPANYDATA* pCompanyData)
    {
        char buffer[100];
    
    
        while( (fscanf(fpData, "%lf %lf %lf %lf %lf %lf %[^\n]",
                                &pCompanyData->hourlyPrices[0], &pCompanyData->hourlyPrices[1],
                                &pCompanyData->hourlyPrices[2], &pCompanyData->hourlyPrices[3],
                                &pCompanyData->hourlyPrices[4], &pCompanyData->hourlyPrices[5],
                                buffer) != EOF ) )
        {
            pCompanyData->companyName=(char*)malloc( (strlen(buffer)+1) * sizeof(char) );
            strcpy(pCompanyData->companyName, buffer);
            return true;
        }
        return false;
    
    
    
    
    }
    
    
    bool searchList (NODE* pList, NODE** pPre, NODE** pCur, char* target)
    {
        bool found = false;
    
    
        *pPre = NULL;
        *pCur = pList;
    
    
        while (*pCur != NULL && strcmp(target, (*pCur)->pCompanyData->companyName)>0)
        {
            *pPre = *pCur;
            *pCur = (*pCur)->link;
        }
    
    
        if (*pCur && strcmp(target, (*pCur)->pCompanyData->companyName)==0)
            found = true;
    
    
        return found;
    }
    
    
    NODE* insertNode(NODE* pList, NODE* pPre, COMPANYDATA item)
    {
        NODE* pNew;
    
    
        if(!(pNew = (NODE*)malloc(sizeof(NODE))))
        {
            printf("Memory overflow in insert.\n"),
            exit(100);
        }
    
    
        while(pNew->pCompanyData = (COMPANYDATA*)malloc(sizeof(COMPANYDATA)));
        pNew->pCompanyData = &item;
    
    
        if (pPre == NULL)
        {
            pNew->link = pList;
            pList = pNew;
        }
        else
        {
            pNew->link = pPre->link;
            pPre->link = pNew;
        }
    
    
        return pList;
    }
    
    
    
    
     void printList(NODE* pList)
     {
         NODE* pWalker;
         int i;
    
    
         pWalker = pList;
    
    
         while (pWalker)
         {
             for(i=0; i<NUM_PRICES; i++)
                printf("%.2lf", pWalker->pCompanyData->hourlyPrices[i]);
             printf("%s\n", pWalker->pCompanyData->companyName);
             pWalker = pWalker->link;
         }
    
    
     }

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    what are you planning to achieve with the infinite loop in line 132?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    12
    Quote Originally Posted by vart View Post
    what are you planning to achieve with the infinite loop in line 132?
    Ooops. Didn't notice that....It's ok, though. I pretty much started all over again and now everything seems to work ok. However, my teacher wants me to use a counter to count the number of companies as I read them. How can I do that? I tried doing:

    Code:
    while(strcpy(pNew->pCompanyData->companyName, buffer))  
     
       companyCounter++;
    I'm pretty sure this isn't correct though. I want to increment the company counter by one every time I read in a new company string....

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    after calling insertNode - you can increase the counter - since successfully finishing this function means you successfully read AND inserted int eh list the company data.

    how will you store the counter - is another question
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. File I/O and linked lists
    By drbr0wn in forum C Programming
    Replies: 5
    Last Post: 12-01-2011, 10:45 PM
  3. Reading file into linked lists
    By bcianfrocca in forum C++ Programming
    Replies: 2
    Last Post: 02-28-2005, 04:12 PM
  4. reading files into linked lists
    By meeloff in forum C++ Programming
    Replies: 2
    Last Post: 10-18-2004, 05:28 AM
  5. help with linked lists and file i/o
    By Mazer in forum C++ Programming
    Replies: 1
    Last Post: 10-21-2003, 01:59 PM