missing pointer information

[spongefreddie]

Okay, there's no way I'm posting three big files of code from a textbook (for all the obvious reasons). This is not a class I'm taking; I'm trying to learn C programming on my own.

I've spent over five days working on ONE FREAKING EXERCISE. I'm a stubborn person, but I'm getting close to quitting the whole process due to some apparent genetic disability that prevents me from understanding this particular exercise. I feel like I'm missing one piece of vital information regarding pointers that I never properly learned from the textbook (my fault, not the textbook's). It's pushing me past the edge of patience because I can't even figure out the proper way to frame the question for this forum. I'll try one more time...

The exercise includes an already working program that identifies two structures:

struct film
{
   char title[TSIZE];
   int rating;
};

typedef struct film Item;

typedef struct node
{
   Item item;
   struct node * next;
}  Node;

typedef Node * List;

Then, the point of the exercise is for me to rewrite a bunch of functions that have been referencing List, but AFTER the definition of List is changed to this:

// typedef Node * List;   // removed for redefinition

typedef struct list
{
    Node * head;    /* points to head of list */
    Node * end;     /* points to end of list  */
}  List;

What I'm running up against seems to be a basic misunderstanding of levels of pointers. I acknowledge that the new definition of List changes what was once a 'pointer to a structure' to a 'structure with two pointers to a structure'. I understand (or thought I did) the difference between a pointer and a non-pointer structure member.

No matter how many times I start over again, and try to re-write the functions that utilize List, I come up with crap. I've used print statements to follow my progress line by line. The closest I could come was a list of node members that were always off by two. And forget about the memory freeing function... at this point I can't even dream of making that work.

As there seems to be no formal question in this post, and a lot of whiny blathering, I'm not sure if anyone will be able to help. I don't want an "answer" to the exercise from the forum, I want to fully understand the concept in this program's scenario. I just wish I could figure out how I could properly frame the question to gain the missing information I need, in order to not feel like a complete moron.

[quzah]

Typedef: A way of calling something, something else.

typedef struct something SomethingElse;

Now, anywhere you normally would have done:

struct something asomthing;

You instead do:

SomethingElse asomething;

That's all there is to it.


Quzah.

[spongefreddie]

Thank you, quzah, but I already understand how typedef allows the programmer to avoid longer statements.

I'm not having any problem understanding structures and typedefs as they are used in the program. I'm having difficulty mentally processing the difference in relationships that is created when what was once a pointer-to-a-structure is now a structure-of-two-pointers-to-a-structure.

The functions that were once dealing with a pointer to a function, are now of course not working properly with an additional level of pointers added on. The function declarations are as follows (to give you an idea of the kind of data manipulations occurring):

void InitializeList(List * plist);
void EmptyTheList(List * plist);
void Traverse (List l, void (* pfun)(Item item) );
int AddItem(Item item, List * plist);
int ListIsFull(List l);
int ListIsEmpty(List l);
unsigned int ListItemCount(List l);

[quzah]

Read pointers right to left.

type * ptr;

The variable 'ptr' is a * (pointer) to a 'type'. That just means that the value that 'ptr' stores, is an address of a variable of 'type' type.

type ** ptr;

The variable 'ptr' is a * (pointer) to a * (pointer) to a type. This means that the value of 'ptr' is an address of a variable of 'type *'. (It stores the address of a pointer which stores the address of a 'type'.)

int x; // as its value, stores an int
int *y; // as its value, stores the address of an int
int **z; // as its value, stores the address of an int*

Quzah.

[itsme86]

I've always viewed pointers as the most difficult aspect of C programming, so don't give up hope. It looks like the new struct is just there to keep track of the start and end nodes of the list. So instead of just passing around a pointer to the start of a linked list, you're passing around a pointer to a struct with some metadata about the list.

void InitializeList(List * plist)
{
  plist->head = plist->end = NULL;
}

void EmptyTheList(List * plist)
{
  Node *n, *nnext;
  for(n = plist->head;n;n = nnext)
  {
    nnext = n->next;
    free(n);
  }
  plist->head = plist->end = NULL;
}

int AddItem(Item item, List * plist)
{
  Node *newnode = malloc(sizeof(*newnode));
  newnode->item = item;
  newnode->next = NULL;

  if(plist->end)
    plist->end->next = newnode;
  else
    plist->head = newnode;

  plist->end = newnode;
  return 1; // Why is this returning an int? The number of items in the list? I don't know
}

That should give you a start on the rest of the functions you need to implement.

[spongefreddie]

Thank you both for your answers.

Answer to itsme86's astute question regarding the strange int return value of AddItem(): the program in the book is returning a boolean value, and due to my dusty IDE, I had to write my own simple stdbool.h file, using the integer values 0 and 1 for false and true, then change bool to int in the function declaration and definition.

After looking at itsme86's code, I already see major flaws in my logic (of course) in both AddItem() and InitializeList(). EmptyTheList() is doing something completely different than the book's approach (in the initial example of the program), so that was also revelatory.

I'm going to go "Once more unto the breach, dear friends, once more."

Thanks again! If you don't hear from me again, it will be due to my application of a 100% concentration of hydrochloric acid to my compiler, albeit metaphorically.

[CommonTater]

Thank you both for your answers.

Answer to itsme86's astute question regarding the strange int return value of AddItem(): the program in the book is returning a boolean value, and due to my dusty IDE, I had to write my own simple stdbool.h file, using the integer values 0 and 1 for false and true, then change bool to int in the function declaration and definition.

Actually you could have defined a bool type in the header as well.

#ifndef BOOL_H
#define BOOL_H


#define true 1
#define false 0

typedef int bool;

#endif //BOOL_H

[spongefreddie]

Almost there... one aha! moment achieved, one more to go. The program now compiles and works properly after the exercise's requested alterations, so technically the exercise is done! But, there's one thing I need to understand before I can feel like I actually succeeded.

After the very helpful posts from everyone, I was able to figure out that I was over-complicating the difference between the new structure pointers and the old pointer-to-Node. As itsme86 reminded me, all pointers are the same under the hood.

So, for all but two of the function definitions, I was able to change the code successfully with a simple substitution of 'List->head' for 'List'. The InitializeList() was a bit different, in that I had to include the 'end' pointer along with the 'head' pointer in the NULL assignment (revelation thanks to itsme86's code).

The part keeping me from completely understanding what's going on is a single line from itsme86's code. The following is my version of his code, altered to fit with the framework of the rest of the program. I have numbered the lines for my comments and question afterward.

int AddItem(Item item, List * plist)   // haven't changed it back to 'bool' type yet
{
   Node * pnew = (Node *) malloc(sizeof(Node));

   if (pnew == NULL)
      return false;   // quit function on failure, hence the boolean return value

   CopyToNode(item, pnew);

   pnew->next = NULL;

   if (plist->head == NULL)    // LINE 1
      plist->head = pnew;      // LINE 2
   else
      plist->end->next = pnew; // LINE 3

   plist->end = pnew;          // LINE 4

   return true;
}

LINE 1 and LINE 2: I was already using this logic, so I understand the process of putting the first node with user data at the head of the list.

LINE 3: I wasn't handling this properly, and once I saw this line, it finally made sense how I was going to place the current node in the next successive position in the list.

LINE 4: Here's where I can't seem to completely absorb the concept. I am confused about why assigning the previous pointer to the new node after assigning the node's 'next' pointer to the new node (LINE 3) is necessary (but testing certainly verifies that it is absolutely necessary!). In effect, once the program exits the function, then both 'end' and 'end->next' point to the same place, or at least that's how it seems to me at this point.

If someone would take a second and make it clear to me, that would be most cool. I apologize in advance for having trouble picking up what is likely second nature for most of you.

[anduril462]

So plist->end should always point to the last element of the list. Your code appends pnew onto the end of the list (plist->end->next = pnew). But up to line 3, plist-> still points to the old end. You need to update it to point to the new end of the list, pnew. That's what line 4 does, reset the end pointer to the new end.

[itsme86]

For simplicity sake let's assume you have 3 nodes at memory addresses 1, 2, and 3.

The first time you add a node, head and end are both NULL, so head is set to 1 (the new node). Then end is set to 1 as well.

The second time you add a node, the else condition runs setting end->next (basically 1's next pointer) to 2, the new node. So now 1->next points to 2. Then the list's end pointer is set to 2.

So far we have list->head point to 1, 1's next pointer pointing to 2, and list->end pointing to 2.

The next time you add a node, the else condition runs setting end->next (2's next pointer) to 3, the new node. Then the list's end pointer is set to 3.

So you end up with list->head set to 1, list->head->next set to 2, list->head->next->next set to 3. And of course, list->end points to 3.

Hopefully that clears it up a tiny bit.

[spongefreddie]

AHA!!!

Line 3 will not attach the new node to the end of the list during a successive iteration of AddItem() if Line 4 isn't allowed to adjust the last node's 'base' value (which is actually the previous node's 'next' pointer). If Line 4 isn't present, then when Line 3 comes up during the next call to the function, the new node will copy over the one previously stored, instead of attaching an additional node to the end.

Thank You!!!