Hello.

I'm having quite major difficulties implementing a linked list in a C program. The problem is to scan through a text file containing the lyrics of a song (Bob Dylan's "Blowin' in the Wind) & count the number of words that begin with each particular letter.

I'm thinking that the program should have a while loop that reads in each word from the file & takes it's first letter as a character & add one to the integer variable held in the node corresponding to that letter. A printed table of the contents of the list is then printed to screen for the benefit of the user.

The problem is, I cannot find any method of implementing this. Nor can I conceive of a method of comparing the characters without making a linked list of 26 nodes OUTSIDE the loop, assigning a letter to each individual node. But that seems horridly inefficient & I'd prefer to do it inside the loop somehow.

Can any of the experienced programming gurus here shed a but of light on this for me? I've been able to easily master all the prior C material, but Linked Lists are driving me insane. I have run a search for materials both on this site & the wider Internet, but 90% of results seem to deal with situations far more complex & involved than mine which is probably extremely simple.

Thanks in advance.

Is it a requirement that a linked list be used?? If I'm understanding the requirements correctly, a linked list is overkill for this situation.

An array is better for this situation for a number of reasons.

If all you are doing is counting the number of words that start with each letter, then you know there is a finite number of "counters" that you'll need. Ie., if you ignore case and numbers, you'll need only 26 counters (a thru z). An array is great for when the size is known beforehand, a linked list is good when you don't know the size beforehand.

When you determine the letter that a word starts with, you can easily know exactly which array element to increment. With a linked list, you'll have to search thru the list to find the correct node to increment.

Assuming that a linked list is required, I think that the idea that you don't like is most efficient. Create the linked list with 26 nodes before processing the file, then as you process each word, you just find the appropriate node to increment.

To create the linked list while processing the file (inside the loop as you say), you'd have to process a word, determine the first letter, search the linked list to see if the letter's node exists, if it does you increment, if it doesn't you have to insert an new node in the correct position.

The first option is much cleaner and will take less code and even tho you may create a few nodes that you don't use, it'll still be faster. Plus it'll make output easier. What if you have no words that start with 'x'? If that node is not in the list, it'll take special code to notice that and output a 0 as the count (if that's what you want).

The reason that the option that you don't like seems to inefficient is that a linked list is not really appropriate. But if a linked list is required, I think that your outside/inside idea is the best.

Good luck

Be sure to come back and let us know if our suggestions helped!

Yes, it is a requirement that linked lists be used. Most likely as an assessment of abilities to use pointers,linked lists & structures more than anything else. I also think that the assigment wants me to use the second of the linked list methods you've described.

So far I've managed to implement the loop algorithm as follows;

-A word is scanned in as a string & it's first letter assigned to a character variable. The scanning continues until EOF is reached.
-Because the song lyrics contain numerous instances of words beginning with "'" (the song must have been chosen to try & trip me up :) ), code to shift the letter written in will be written
-Because the song lyrics contains both upper & lower case letters, I'll make a function call to change the character to lower-case.

But this is the point at which things become unstuck. I know I've got to deal with a previously initialised linked list, but I don't know how to compare letters to a baseline when the baseline doesn't yet exist.

As I said before, you search the linked list for the node that contains the letter that you are looking for. If you find the node, then you increment the counter. If you do not find the node, then you have to insert a new node.

Your 'baseline' will be an empty list to start with, and you'll be adding to it as you go.

Be sure to come back and let us know if our suggestions helped!

So for the first line of the song;

"How many roads must a man walk down"

How exactly do I build up the list without a pre-defined list of 26 nodes? Is there a function to go to the nth node of a list? I had thought that that wasn't possible with linked lists, but maybe I was wrong.

First, to clarify. What I am understanding that you want to do is not to build the linked listed with 26 nodes ahead of time, but to build the list as you process the words in the file. If I've got that wrong, then let me know.

If that is what you want to do, then when you process the first word (how), you will search the linked list for an 'h' node. You won't find an 'h' node, so you need to insert an 'h' node into the list. So, now your list has one node.

When you process "many", again you'll find that the search returns no match, so you'll insert an 'm' node. Then you'll insert a 'r' node for "roads".

Then, on the fourth word (must), you'll search the list for the 'm' node and find a match, so you just increment the counter of the 'm' node.

So, you'll start with an empty list, then add nodes as you need them.

How you add nodes, depends upon the requirements of the instructor and/or how much work you want to do. The easy way would be to always add the new node to the end of the list. But then when you search, you have to search all the way to the end of the list every time (because the list is not sorted).

The more appropriate way would be to insert the nodes in alphbetical order. So then when you search, you can quit searching earlier (if you know the nodes are alphabetical and are searching for 'm', then if you come to the 'n' node, you know that 'm' must not exist).

Be sure to come back and let us know if our suggestions helped!

Yes, you are right. It's required that the list is built up dynamically rather than being pre-defined.

I'll be adding/removing nodes with custom functions that insert a new node either one before or one after the node that is pointed to as the current node.

What I can't seem to figure out, however, is the searching aspect of this. When you say I'll search the linked list for a 'h' node, what do you mean? At the loop inception, there is only one node in the list (that created when the list is initialised) but the variables in the node (letter; for storing letter for that node & count; count of instances of word beginning with that letter) will both be null. How do you search the nodes?

Assuming that I just allow the first scanned letter to be the head node, the next letter I'll be scanning in is 'm'. Again, how do I get the program to tell whether 'm' is greater or lesser than 'h'?

Linked lists are tieing me up in knots. Apologies if this is very simple, I'm very new at C programming.

I'm not sure if you are misusing some of the terminology or if your instructor is teaching non-standard linked lists.

Let's define a node for your program. It would probably be a structure with three member variables:

- a char to hold the letter
- an int to hold the count
- a pointer to point to the next node in the list (if the node is the last node in the list, then the pointer would be set to null)

You mention a 'head' node. This is one place where I think that you are confusing the terminology.

You don't have a head node, you have a 'head' pointer. This is a pointer to the first node in the list. This pointer is not an actual node, just a pointer to the first node.

Let's assume that your node structure is defined as:

struct nodestruct {
char letter;
int count;
struct nodestruct *next;
}

You'd declare the head pointer as:

struct nodestruct *head = NULL;

So 'head' is pointing at nothing. The list is empty.

The first time that you create a node (for 'h'), you'll add the new node so that it is first on the list.

struct nodestruct *node;

node = calloc(1,sizeof(struct nodestruct));

node->letter = 'h';
node->count = 1;
node->next = NULL;

When you go to search the list, you'll start at 'head'. If head == NULL, then you know that the list is empty, so it is a special case in the code to add the first node.

head = node;

head now points to the first node and the node's next value is NULL.

Now, with the second word, you'll create a new node:

node = calloc(1,sizeof(struct nodestruct));

node->letter = 'm';
node->count = 1;
node->next = NULL;

To verify that there is a non-empty list to search, do (as before):

if (head == NULL) {

..add first node code here

} else {

.. search list code here...

}

To search the list, you start with the first node:

struct nodestruct *ptr;

ptr = head; /* ptr now points to the first node on the list */

/* Does this node contain the letter that you want? */
if (ptr->letter == 'm') {

.. got a match, so can increment the count and exit the search loop

}

/* if didn't match, move on to the next node */

ptr = ptr->next;

Remember, ptr is pointing to a node and ptr->next contains the address of the next node in the list. So the above line, copies the address of the next node in the list into the variable 'ptr'. So now 'ptr' points to the next node in the list. If 'ptr' is now null, then that means that you've reached the end of the list.

I'm walking the line between explaining how this works and not writing the code for you. So I've included some parts, but not always in the exact way you'll need to use them.

Let's see how much this helps.

Be sure to come back and let us know if our suggestions helped!

But I don't see how you can implement that in a single while loop which
is incrementing until EOF is reached. I don't get how you can create new nodes inside of the loop for a specific letter. In fact, I just don't get linked lists
very well at all I'm beginning to realise.

I don't have my code with me at the moment,
it's stored on my workstation. But it's half-nine in my timezone at the moment, so I'll have to get back to this tomorrow.

But here is what I was implementing so far.

Structure definition in a seperate library module.

typedef struct _node
{
char letter;
//Letter associated with node.
int count;
//Current count of occurences of a particular letter
struct _node* next;
//Pointer to next node
} node;

Variable declarations in main()

node* current;
//Pointer to current node
LinkedList* list;
//Linked list of nodes
FILE testsong_ptr;
//Pointer to input file testsong.txt
char word[50];
//Variable to store scanned word
char letter;
//Variable to store first letter of scanned word

I then open the file for reading, making a check first to see if it can actually be read.

Initialisation of linked list

//Allocate memory & initialise linked list
list = (LinkedList*) malloc(sizeof(LinkedList));
InitLinkedList (list);

Where the function InitLinkedList creates a singly linked list with a single node.

Loop for scanning through file

//While loop to scan through song text
while (fscanf(testsong_ptr, "%s", word)!= EOF)
{
//If the first word is not a letter, correct
if (word[0] == ' \' ')
{
letter = word[1];
}
else
{
letter = word[0];
}

//Make scanned letter lower case
letter = tolowre(letter);

That, however, is where the wheels fall off. Even with all that help you gave me in your previous post, I can't wrap my head around getting this stuff into the loop. Perhaps I'll fare better tomorrow.

Thanks anyway.