While function pointers are important. I don’t think they’re quite as important as pointers. C would just not be C without pointers. There are so many things that you would not be able to do if the language lacked pointers. Things like most data structures (try doing a linked list without pointers!) .
However function pointers give additional flexibility. You can pass them as parameters in functions and store them in variables.
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
Allocate memory for the node using malloc.
Copy the head pointer to the node’s next pointer.
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.
In my eBook, I used only structs and arrays. In fact the commonest “structure” was an array of structs. That was used for bullets, asteroids and aliens ships.The benefits of that are it’s easy to process; I started out by using it as an array and eventually switched to using a pointer to each struct “walking” the pointer through the array, jumping it if you like from struct to struct. Very simple and ideal for a game like asteroids.
You don’t need complexity because that slows things down and the only constraint in the design was making sure I could run everything at 60 frames per second..
C doesn’t come with anything more complex, yet computer science has determined many many advanced data structures that have their uses.
If you were programming a dungeon exploration game, an array might not be the best way to store the dungeon. You’d have multiple levels where each level consist mainly of rooms and corridors. How might you store that? Also there’d be monsters, treasures, traps, transporters and so on in the dungeon. How would you traverse this structure, guaranteeing there’s a path so that every room can be reached?
You might use an array to hold each level but how would you connect levels? Thinking about it I probably wouldn’t. I’d have staircases connecting corridors, traps that let you fall through to a room or corridor below, a transporter that lets you appear in a room or corridor above.
C is flexible enough to support a structure like this but you would have to code all the storage yourself. One way round it is to find an open source library like SGLIB. One reason I chose this is because it lets you create container data structures.
Sglib is fairly low level. It includes code for sorting arrays, for manipulating singe, double and sorted linked lists, red-black trees and hashed containers. As they say “A hashed container is a table of fixed size containing another (we say base) container in each cell. Once an object is going to be inserted into the hashed container, the hash function is used to determine the cell where it belongs and then the object is inserted into the base container stored in this cell. The base container is usually a list, however it can be a sorted list, double linked list or a red-black tree as well. Sglib’s hashed container is parameterised by the name of the base container.”
There are examples provided in the documentation as how to use each type of data structure.
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?
