Category: pointers

How to use some advanced data structures in C

How to use some advanced data structures in C

Linked Lists
From Wikimedia Commons

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?

Coirridor
Image by Rudy and Peter Skitterians from Pixabay

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.

 

A look at pointers.

A look at pointers.

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?