Category: tutorials

New C tutorial on implementing linked lists with pointers

New C tutorial on implementing linked lists with pointers

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

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.

How to measure how shuffled a deck of cards is

How to measure how shuffled a deck of cards is

Opened deck plus new deck of cardsI first thought about this when I wrote the program to shuffle  deck of cards using a riffle shuffle. If you are given a deck of cards (or pack of cards as us Brits say), how do you discern just how shuffled the pack is? Can you calculate a numeric value for it say a % ranging from 0 to 100?

I believe it’s possible.  Here’s how.

  1. Start with a default pack of cards in perfect sorted order. Out of curiosity I found an unopened deck oif Waddington’s cards and opened it as the photos show. The cards in the pack were arranged in order King, Queen, Jack down to Ace in each of the four suits Heart, Clubs, Diamonds and Spades in that order. Let’s reverse the card rank ordering so a full deck starts with Ace Hearts through to King Hearts, Ace of Clubs to King of Clubs and so on with the last card being the King of Spades.
  2. Instead of referring to cards by their rank and suite lets just number them 0-51. 0= Ace of Hearts, 51 = King of Spades.
  3. When a deck is shuffled, each card can move to any other position. So a measure of shuffledness is calculating how far the cards moved in aggregate.
  4. However the card movements have to be “normalized”. Cards 0 and 51 can move to any of 51 positions while cards 26 (King of Clubs) and 27 (Ace of Diamonds) can only move a maximum of 26 places.
  5. I’m looking at the absolute value of a movement so if card 3 moves to position 47, it has moved 44 places and likewise card 47 moving to position 3 moves 44 (not -44) places.
  6. So to normalize a card’s move, divide its move by its maximum possible distance it can move. So wherever card 0 moves divide it by 51, card 1 by 50, card 26 ‘ move by 26.
  7. Sum up all 52 normalized move’s and multiply by 100. That is the measure of shuffledness.

I’ll write a C program to measure how shuffled a deck is and publish it in a day or two. Also here is a conversation on Reddit about shuffling cards.

 

New C Tutorial published on arrays

New C Tutorial published on arrays

arrays
Image by Andrew Martin from Pixabay

This continues the series of C tutorials. In this one, I’m looking at arrays and how to declare them. An array is an essential part of C programming, but they are always fixed size. You can’t change the size at runtime or specify the size in a variable before declaring it unless you declare them using pointers which is a bit advanced for the fourth tutorial.

The picture is a metal grid but it illustrates what a two dimensional array [5][7] might look like. I looked but I couldn’t find any pictures of seven dimensional arrays!

Tutorial 3 on Enum variables published

Tutorial 3 on Enum variables published

Magic Numbers
Image by John Hain from Pixabay

This is the third in a series of C Tutorials that I originally published on about.com between 2006 and 2013.  I’m republishing them on here. This time it’s about enum variables. While these aren’t anywhere as important as say in C++ or other languages (because C’s type checking is not great!) they make the program more readable.

I see them as banishing magic numbers. A magic number is a number in a program that is just there. Like when you declare an array and use the number 20. That is a magic number and it would be better if there was a #define NUMBERMONSTERS 20.  This avoids the problem of your program being full of 20s until one day you change it to 30 but manage to miss a couple of them and you introduce bugs. By using NUMBERMONSTERS everywhere you can change it in just one place (at the #define) and avoid the problem of missing.

Enum variables are similar. Behind the scenes they are just ints. In other programming languages like C++, Pascal, C#, the compiler enforces the enum values. In those languages you can’t declare an enum variable then assign any int value to it, but in C you can.  But they can at least make your program more readable.

The picture? Magic numbers!

First C Tutorial published

First C Tutorial published

TutorialAs I add these (one or two each week), I’ll add them to the tutorials page. The first is introducing C Programming and has the almost mandatory Hello World.  To speed up trying the code out, I’ve included links to two online C compilers where you can run the program.

The two online compilers Ideone.com and Codepad.org were both around when I wrote the original tutorial and the original C program (Ideone) link still exists on Ideone. (After you compile a program successfully they provide a shortcut back to it).

I’ve taken the original C tutorials and have stripped all the cruft (CSS, much Html, and JavaScript) and edited slightly).  It helps that I wrote them originally back around 2006-2007. There’s approximately 30 in total. I will be beefing them up as well.

Follow the Tutorials link on the top menu.

My earlier work in C, C++ and C#

My earlier work in C, C++ and C#

Cplus.About.com screenshotThe tutorials I wrote on C++ and C# on cplus.about.com between 2006 and 2013 are all a bit dated now. Both languages have been updated several times since 2013 when I stopped writing for About.com. But thanks to the Wayback machine you can view all of my work from the early stages in Mid 2006 to the finish in July 2013.  I owe the copyright to this material so I can reuse it as I wish.

On this page, there’s an index to 43 C tutorials, most written by me.  So as a little side task, I’m downloading these, cleaning them up, fixing the odd error and adding them to this website via the Tutorials page. Some but not all are also available on the ThoughtCo website which is the reinvention of About.com.

Ironically I got better at writing for them towards the end. About.com had been very successful back in the late 90s when the web was still fairly new but could never sustain that and declined more or less from the year 2000. I think the highest daily viewing figure I ever got was 12,000 pages but some of the others (particularly Southern Cooking) got in the millions.

I recommend you visit archive.org earlier in the day as it slows up a bit once the USA wakes up typically around 1.00 PM (GMT). Given the volume of stuff it stores, it is a totally amazing place.

Useful list of tutorials in C

Useful list of tutorials in C

 

Online educatioon
Image by Mudassar Iqbal from Pixabay

This GitHub repository has a pretty long list of beginner to medium sized project tutorials in C. There are over 30 on game development alone with titles like “Create a 2D platformer” and “SDL2 Isometric Game Tutorial“.

Other tutorials are on databases, networking, programming languages and operating systems plus even a bit on Blockchain. Recommended!

I’ve added a permanent link on the Links to C utilities page (on the top menu).