Tag: pointers

New C tutorial on implementing linked lists with pointers

New C tutorial on implementing linked lists with pointers

Posted on by David
Links
Image by Денис Марчук from Pixabay

Once you leave the relative safety of arrays and structs, the linked list using pointers is probably the next thing to consider.  Technically it’s a liked list of structs containing pointers. It’s like an array of structs only instead of allocating contiguous memory for an array, you allocate memory for each struct as you need it.

Linked lists are easy to program. You have a head pointer (a pointer to the head of the list). It starts as null as the list is empty. There’s two types of linked lists (single and double). A single list has a pointer to the next node (or is 0 at the end of the list) and can only be processed from head to end. A node is just a fancy name for the struct in the linked list.

A double list has two pointers. One to the previous node and one to the next. As well as a head pointer you need a tail pointer and you can process the list from head to tail or tail to head (i.e. backwards).

Now the first operation you can do on a linked list is add a node to it.

To do this you

  1. Allocate memory for the node using malloc.
  2.  Copy the head pointer to the node’s next pointer.
  3. Stitch the node in by pointing the head pointer to this node.

So when you are building a list you add each node to the head, in a sense pushing it in front of the others.

Double linked lists have to do an additional operation which is set the next node’s previous pointer to point to the newly added pointer. And when you add the first node to a double linked list, you have to set the tail pointer to point to this first node. After that it never changes unless you have an Append node at the end.

Uses of Linked Lists

Anything that needs dynamic memory for example a text editor might use a double linked list to store all the text. Each line could be a different length. So each node would not only have a pointer to the next and previous nodes, it would have a pointer to the text in memory. When you insert a new line, you are just inserting a new node in the list at the current node that the cursor is on.

Or you might store a directed graph (a bit like in the picture) where each node has multiple pointers to other nodes.  Anyway I’ve published tutorial eight which looks at pointers and linked lists.

 

Tutorial six on pointers added

Tutorial six on pointers added

Posted on by David
Pointers
Image by Please Don’t sell My Artwork AS IS from Pixabay

Once you ‘get’ pointers they are very easy to use. I think I always got them easily because long ago I used to do game programming in assembly language. When you are accessing blocks of ram indirectly through registers in assembly, then the concept of a pointer in C/C++ comes fairly naturally.

But really, all a pointer is, is a variable that holds an address. That address can be one of several things. It could be to a string of characters, an int or float variable, a struct, an array. In fact it can be anything that can exist in memory.

There are some limitations. It’s not good practice to use a pointer to access the underlying binary of your program, assuming that you can locate it. Plus chances are that code will be in memory that you cannot write to. Data however will let you write to it and pointers make your program far more flexible than without.

Tutorial six on pointers has been published. I’ll publish another one to follow it.

More on pointers in C. The use of typedef

More on pointers in C. The use of typedef

Posted on by David

Asteroid about to be destroyedThis bit is slightly controversial. I find all the * makes it harder to read code so I use typedefs to hide them. Here’s an example from the game. Try replacing every pbte with byte * and see if reading it is harder for you.

typedef byte * pbyte;

// mask arrays
byte bulletmask[1][3][3];
byte plmask[24][64][64];
byte a1mask[24][280][280];
byte a2mask[24][140][140];
byte a3mask[24][70][70];
byte a4mask[24][35][35];
byte alienmask[64][64];

pbyte GetMask(int type, int rotation, int size) {
  switch (type) {
    case tAsteroid: // asteroid
      {
        switch (size)
          {
            case 280:
              return (pbyte)&a1mask[rotation];
            case 140:
              return (pbyte)&a2mask[rotation];
            case 70:
              return (pbyte)&a3mask[rotation];
            case 35:
              return (pbyte)&a4mask[rotation];
          }
      };
    case tBullet: // bullet
      return (pbyte)&bulletmask;
    case tPlayer: // player
      return (pbyte)&plmask[rotation];
    case tAlien:
      return (pbyte)&alienmask;
    } 
  return 0; // null - should never get here!
}

In my post about collision detection I mentioned getting mask bytes. This function GetMask returns a pointer to a byte (i.e. the first byte in a particular mask for a particular type of object (asteroid, bullet, player, alien) and for asteroids and the player a particular rotation. The many (pbyte) are needed because the arrays have different sizes. There are 24 player and asteroid masks.

A look at pointers.

A look at pointers.

Posted on by David

You cannot be a C programmer without using pointers. It’s the one feature of the language that makes possible much of what you can do in C. Pointers seem to scare novice programmers and it’s true that you can crash a program if you make a mistake, but otherwise they’re not that bad. Pointers as parameters in functions let you change the value of an external variable.

A pointer is just a variable that holds the address of another variable. So here’s my take on pointers.

You define a pointer as a pointer to a variable type like a pointer to an int or a char. There is also a “wildcard” where you define a pointer to a void. That has its uses when passing general pointers into functions. With types, the C compiler can verify assignments.

[perl]int * pInt; // pInt is a pointer to an int
char * pChar; // pChar is a pointer to a char
int a;

void ZeroInt(int * pInt) {
if (pInt) // Check pointer does not have a null value
*pInt = 0;
}

ZeroInt(&a); // Sets a to 0.[/perl]

That ZeroInt() function is a long-winded way of setting whatever int variable it is called with to zero. Yes you can just do a = 0; but that misses the point. What if a was a struct and the ZeroInt was a function to initialise all the fields of the struct?