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?

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.

What's wrong with your previous thread?

Quote:

---

Originally Posted by orangePeel

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

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. :)

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:

Quote:

---

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;
    }


 }

---

what are you planning to achieve with the infinite loop in line 132?

Quote:

---

Originally Posted by vart

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....

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