Review of Structures in C

We use structures when we want to process multiple data types while still referring to the data as a single entity. For instance, we can create a structure and name it student; this structure will contain two data items called fields. One field will be called name and be of type char, the other field will be called score and be of type double.

#include 
#include 

struct student
{
 char name[30];
 double score;
} studentOne, studentTwo;

int main(void){

 char s1[30];
 double d;

 printf("Name: ");
 scanf(" %s:", s1);
 printf("Score: ");
 scanf(" %lf", &d);

 strcpy(studentOne.name, s1);
 studentOne.score = d;

 printf("%s \t %f\n", studentOne.name, studentOne.score);


 return 0;

}

Note that when using scanf() to get a double value, we should use the conversion specifier %lf, as we are passing the function a pointer and not a variable.

We can have structures that have nested structures within them.

#include 
#include 

struct address{
	char street[30];
	char city[30];
	char state[2];
	int zip;
};

struct worker{
	unsigned int id;
	char name[30];
	struct address addr;
};

int main(void){

	struct worker mike;

	mike.id = 1138;
	strcpy(mike.name, "Mike");
	strcpy(mike.addr.street, "1428 Elm Street");
	strcpy(mike.addr.city, "Madison"),
	strcpy(mike.addr.state, "WI");
	mike.addr.zip = 53705;

	printf("#%d %s\n", mike.id, mike.name);
	printf("%s \n%s, %s %d\n", mike.addr.street, mike.addr.city, mike.addr.state, mike.addr.zip);

	return 0;
		
}

Don’t forget to put the semicolon at the end of the structure definition.

Note that structure members are allocated consecutive memory locations.

 #include <stdio.h>
#include <string.h>
//compiling on a Windows machine today
//so I include windows.h for malloc()
#include <Windows.h>

struct album{
char name[30];
char band[30];
int year;
};

struct album* GetAlbum(){
struct album *returnAlbum = (struct album*)malloc(sizeof(struct album));

strcpy(returnAlbum->name, “The North Borders”);
strcpy(returnAlbum->band, “Bonobo”);
returnAlbum->year = 2013;

return returnAlbum;
}

void PrintAlbum(struct album *a){
printf(“Album name = %s\n”, a->name);
printf(“Band name = %s\n”, a->band);
printf(“Year = %d\n”, a->year);
}

int main(void){

struct album *ptrAlbum = GetAlbum();

PrintAlbum(ptrAlbum);

free(ptrAlbum);

return 0;

}

Advertisements

Function Pointers in C

A function pointer is a pointer that holds the address of a function, thereby giving our programs greater flexibility. This flexibility might (or might not, depending) come at the cost of increased use of system resources. 

The simplest function pointer we can have is a pointer to a function that accepts no parameters and doesn’t return a value. Such a pointer would look like void (*func)(); – we note here that the function pointer’s identifier, func, is preceded by an asterisk and enclosed in parentheses. 

Let’s look at an example.

#include <stdio.h>

void functionOne(void);
void functionTwo(void);

int main(void){

void (*funcA)();
void (*funcB)();

funcA = functionOne;
funcB = functionTwo;

funcA();
funcB();

return 0;

}

void functionOne(void){
printf("Function One called.\n");
}

void functionTwo(void){
printf("Function Two called.\n");
}

Assigning the function addresses to a function pointer is easy, just use the assignment operator use the function name as the rvalue. There’s no need to place the address-of operator before the function name. Just as with array names, the function name by itself returns the function’s address in memory. 

#include <stdio.h>

void printInt(int n);
void addDoubles(double dX, double dY);
int factorial(int n);

int main(void){

void (*funcOne)(int);
void (*funcTwo)(double, double);
int (*funcThree)(int);


funcOne = printInt;
funcTwo = addDoubles;
funcThree = factorial;

funcOne(73);
funcTwo(68.803, 18.0025);
printf("4! = %d\n", funcThree(4));

return 0;

}

void printInt(int n){
printf("Function received the integer %d\n", n);
}

void addDoubles(double dX, double dY){
printf("%f + %f = %f\n", dX, dY, dX + dY);
}

int factorial(int n){
int total = 1;
while(n>1){
total *= n--;
}
return total;
}

Passing a function as an argument to another function is not difficult. We must simply define a function pointer declaration as the parameter in the target function’s definition.

#include <stdio.h>

int divide(int x, int y);
int subtract(int x, int y);
int add(int x, int y);
void compute(int x, int y, int (*operation(int,int)));


int main(void){

int (*func)(int, int) = subtract;

compute(10, 20, func);

func = add;

compute(13, 191, func);

func = divide;

compute(17, 3, func);

return 0;

}

int divide(int x, int y){
if(x % y == 0){
return x / y;
} else {
printf("warning: remainder omitted.\n");
return x / y;
}
}

int subtract(int x, int y){
return x - y;
}

int add(int x, int y){
return x + y;
}

void compute(int x, int y, int (*operation(int,int))){
printf("performing an operation on %d and %d\n", x, y);
printf("the result is %d\n", operation(x, y));
}

Using typedef, we can make our function parameter lists a little clearer. The typedef keyword enables us to create new, more complex types out of simpler types.

#include <stdio.h>

#define ARRAY_SIZE 7

typedef int (*funcPtr)(int);

int makeEven(int n);
int makeOdd(int n);
void modifyArray(int array[], funcPtr fPtr);

int main(void){

int array1[ARRAY_SIZE] = {2161, 400, 25, 636, 18, 338, 41};
int array2[ARRAY_SIZE] = {47, 3, 424, 7, 33, 1999, 8};
int i;

funcPtr fPtrOne = makeEven;
funcPtr fPtrTwo = makeOdd;

for(i = 0; i < ARRAY_SIZE; i++){
printf("%d\t", array1[i]);
}

modifyArray(array1, fPtrOne);

for(i = 0; i < ARRAY_SIZE; i++){
printf("%d\t", array1[i]);
}

printf("\nNow for the second array.\n");

for(i = 0; i < ARRAY_SIZE; i++){
printf("%d\t", array2[i]);
}

modifyArray(array2, fPtrTwo);

for(i = 0; i < ARRAY_SIZE; i++){
printf("%d\t", array2[i]);
}

}


int makeEven(int n){
if(n % 2 == 0){
return n;
} else {
return n * 2;
}
}

int makeOdd(int n){
if(n % 2 == 0){
return n * 2 - 1;
} else {
return n;
}
}

void modifyArray(int array[], funcPtr fPtr){

printf("\nmodifying array\n");
for(int i = 0; i < ARRAY_SIZE; i++){
array[i] = fPtr(array[i]);
}

}

 

 

 

Windows MessageBoxes in C

Creating a MessageBox in C is surprisingly easy. We need to include Windows.h and then call the MessageBox() function as we would in a .Net program.

#include <Windows.h>

int main(){
MessageBox(NULL, NULL, NULL, NULL);
}

Four NULL arguments! 

The first argument to MessageBox() is an HWND, which is an integer handle to the parent window. Let’s leave this NULL, for now. The second argument is the message. Note that this argument / parameter is of type LPCTSTR, which is a pointer to a character string. When passing a string literal as an argument, we will use the TEXT() macro. Basically, LPCTSTR uses Unicode  characters, so we may or may not need to cast the string literal to Unicode. The TEXT() macro takes care of this for us. 

#include <Windows.h>

int main(){

LPCTSTR msg = TEXT("Saluton, Mundo!");

MessageBox(NULL, msg, NULL, NULL);

}

The third argument is the message box title. LIke the message itself, it is an LPCTSTR

#include <Windows.h>

int main(){

LPCTSTR title = TEXT("Message!");

MessageBox(NULL, TEXT("Han shot first!"), title, NULL);

}

The fourth argument to the MessageBox() function can be taken from a set a of dentfined token strings, as in #define ARRAY_BOUNDS 256, that are defined in WINUSER.H. This fourth argument specifies what buttons will be displayed on the MessageBox. We can use the | operator to combine options to define the default option or the icon.

#include <Windows.h>
#include <WinUser.h>
#include <stdio.h>

int main(){

printf("MB_OKCANCEL = %x\n", MB_OKCANCEL);
printf("MB_YESNOCANCEL = %x\n", MB_YESNOCANCEL);
printf("MB_YESNO = %x\n", MB_YESNO);

printf("MB_DEFBUTTON1 = %x\n", MB_DEFBUTTON1);
printf("MB_DEFBUTTON2 = %x\n", MB_DEFBUTTON2);
printf("MB_ICONWARNING = %x\n", MB_ICONWARNING);


}

Note that all of the token strings begin with MB.

#include <Windows.h>
#include <WinUser.h>

int main(){

LPCTSTR message = TEXT("You are likely to be eaten by a Grue.");
LPCTSTR title = TEXT("Zork");

MessageBox(NULL, message, title, MB_RETRYCANCEL | MB_ICONWARNING);

return 0;

}

Creating File Handles in C using the Windows API

Before reading and writing to a file, we must first create a handle to the file. We create a file handle using the CreateFile() function, which returns a Win32 HANDLE. The CreateFile() function’s name is something of a misnomer, as it is used both to create new files as well as open existing files. 

Note that in the Win32 API, the maximum length of a file’s path should not exceed 260 characters.

An access mask defines how a process can interact with an object. In the case of a file handle, we will work with the generic access rights GENERIC_READ and GENERIC_WRITE, or a combination of the two. 

#include <stdio.h>
#include <Windows.h>

int main(void){

//260
printf("%d is the maximum length of a path.\n\r", MAX_PATH);

printf("0x%x generic read.\n\r", GENERIC_READ);
printf("0x%x generic write.\n\r", GENERIC_WRITE);
printf("0x%x generic read & write.\n\r", GENERIC_READ | GENERIC_WRITE);


return 0;

}

The file share mode specifies how the file can be shared. We can either allow other processes to read the file while we are accessing it, or we can specify that the file is locked to other processes. Putting NULL defaults to the later. To allow other processes to read the file, we put FILE_SHARE_READ

When creating a file handle, we should set its disposition. There are five possible dispositions, we will focus on four: CREATE_NEW, CREATE_ALWAYS, OPEN_EXISTING, and OPEN_ALWAYS.

#include <stdio.h>
#include <Windows.h>

int main(void){

printf("0x%x FILE_SHARE_READ\n\r", FILE_SHARE_READ);
printf("0x%x CREATE_NEW\n\r", CREATE_NEW);
printf("0x%x CREATE_ALWAYS\n\r", CREATE_ALWAYS);
printf("0x%x OPEN_EXISTING\n\r", OPEN_EXISTING);
printf("0x%x OPEN_ALWAYS\n\r", OPEN_ALWAYS);

return 0;

}

Alright, now let’s actually create the file handle. Note that that if the CreateFile() function fails, it returns the INVALID_HANDLE_VALUE. For more detailed information regarding the error, we can use the GetLastError() function, which is included in the Windows.h header file. 

#include <stdio.h>
#include <Windows.h>

int main(void){

int returnValue;
LPCWSTR filename = TEXT("somefile.txt");

HANDLE fileHandle = CreateFile(
filename, //file name
GENERIC_WRITE, //file access type (read, write, read & write)
0, //do we allow sharing? no. NULL also works
NULL, //default security
CREATE_ALWAYS, //create a new file only if an old one doesn't exist
FILE_ATTRIBUTE_NORMAL, //just a normal file, not an archive or hidden file, etc.
NULL
);

if(fileHandle != INVALID_HANDLE_VALUE){
printf("file handle created successfully.\n\r");
} else{
printf("There was a problem creating the file.\n\r");
}

returnValue = CloseHandle(fileHandle);

if(returnValue!=0){
printf("file handle successfully closed.\n\r");
}

return 0;

}

Note the use of the TEXT() macro to convert char * to LPCWSTR. LPCWSTR stands for long pointer to constant wide string; by wide they mean Unicode (16 bit) rather than ANSI (8 bit) characters. Basically, we use TEXT() to convert between Unicode and ANSI. 

 

 

 

 

Allocating and Freeing Dynamic Variables in C

We create a pointer variable to an integer with the declaration int *p; Having declared a variable p as a pointer to a specific type, it is possible to dynamically create an object of that type and assign its address to p.

We do this by calling the standard library function malloc(), which dynamically allocates a portion of memory of a specified size and returns  a pointer to it.

#include <stdio.h>
#include <stdlib.h>

int main(void){

    int *i, *j;

    int x;

    i = (int *) malloc(sizeof(int));

    *i = 1138;

    j = i;

    printf("%d %d\n", *i, *j);

    x = 73;

    *i = x;

    printf("%d %d\n", *i, *j);

    *i = 5;

    printf("%d %d\n", *i, *j);

    return 0;

}

The sizeof operator returns the size, in bytes, of its operand.  We can use sizeof in conjunction with malloc() to get an object of the proper size.

The free() function is used to return allocated storage. Calling free() on a pointer makes the memory pointed to by the pointer available for reuse.  While most operating systems “clean up” memory after a program exits, it’s still really a good idea to explicitly clean up any dynamically allocated memory ourselves.

#include <stdio.h>
#include <stdlib.h>

int main(void){

    int *p = (int *)malloc(sizeof(int));
    int *q = (int *)malloc(sizeof(int));
    double *d = (double *)malloc(sizeof(double));
    double *e = (double *)malloc(sizeof(double));

    *p = 404;
    *q = 711;
    free(p);    
    p = q;
    printf("%d %d\n", *p, *q);
    
    *d = 0.57721;
    *e = 1.12358;

    printf("%f %f\n", *d, *e);

    free(e);
    e = d;
    *d += 7.11;

    printf("%f %f\n", *d, *e);

    //clean up time
    free(d);
    free(q);
        
    return 0;

}

As we have seen in these past two programs, if two pointers point at the same variable, they are functionally identical. Thus, an assignment to one changes the value of the other.

Next, let’s take a look at creating a linked list using dynamic variables. A linked list consists of a set of nodes, each of which has two fields: an information field and a pointer to the next node in the list. In addition, we have an external pointer that points to the first node in the list.

#include <stdio.h>
#include <stdlib.h>

struct node * getNode();

struct node{
    int data;
    struct node *next;
};

int main(void){

    struct node *begin, *temp;    
    struct node *nodePtr;

    temp = getNode();
    temp->data = 42;
    
    begin = temp;
    nodePtr = temp;
    
    nodePtr->next = getNode();
    temp = nodePtr->next;

    temp->data = 73;
    nodePtr = temp;
    nodePtr->next = getNode();

    temp = nodePtr->next;
    temp->data = 1999;
    temp->next = NULL;

    nodePtr = begin;

    while(1){
        printf("%d\n", nodePtr->data);
        if(nodePtr->next==NULL){
            break;
        } else {
            nodePtr = nodePtr->next;
        }
    }
    
    return 0;

}

struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

When looking at the above code, we should ask ourselves how we would go about returning all of the nodes’ memory to the heap.

Note that the getnode() function could as well be implemented via a macro.

Next, let’s look at implementing a list as a queue. A queue follows the first in, first out principle – the first item to be inserted into a queue, will also be the first to be taken out. To do this, we will create a second structure, known as a queue. This structure will have two fields; the first field will be a node pointer to the first node in the list, and the second pointer will be a pointer to the last node in the list.

Our function for getting a queue will initialize both of these fields to NULL. We will then implement two functions, pop() and push(). The pop() function takes a node out out of the queue, frees it in memory, and then returns the value it was storing. The push() function creates a new node, assigns its data field a value, and then assigns it to the end of the queue.

#include <stdio.h>
#include <stdlib.h>

struct node *getNode();
struct queue * getQueue();
int empty(struct queue *q);
void push(struct queue *q, int x);
int pop(struct queue *q);

struct node{
    int data;
    struct node *next;
};

struct queue{
    struct node *first;
    struct node *last;
};

int main(void){
    struct queue *q = getQueue();
    printf("queue allocated.");
    if(empty(q)){
        printf("queue is empty.\n");
    }

    push(q, 2001);
    push(q, 2600);
    push(q, 80);
    push(q, 1970);
    push(q, 1701);

    while(empty(q)==0){
        printf("%d\n", pop(q));
    }


    return 0;    
}




struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

struct queue * getQueue(){
    struct queue *q;
    q = (struct  queue*)malloc(sizeof(struct queue));
    q->first=NULL;
    q->last=NULL;
    return q;
}    

int empty(struct queue *q){
    if(q->first==NULL){
        return 1;
    } else {
        return 0;
    }
}

void push(struct queue *q, int x){
    struct node *n = getNode();
    n->data = x;
    n->next = NULL;
    if(q->last!=NULL){
        (q->last)->next = n;    
    } else {
        q->first = n;
    }
    q->last = n;
}

int pop(struct queue *q){
    int x;
    struct node *n = q->first;
    q->first = n->next;
    if(q->first==NULL){
        q->last=NULL;
    }
    x = n->data;
    free(n);
    return x;
}

One of the nice things about working with higher level languages such as C# is that data structures such as linked lists are already implemented for us in the language.

To learn more about C, take a look at my book at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/

 

 

 

 

 

Multidimensional Numeric Arrays

A two dimensional array is a matrix; it can be visualized as a spreadsheet table, with the first index giving the row, and the second index giving the column.

#include <stdio.h>

int main(void){

    int array[2][3] = {
            /* row one */{42, 47, 73},
            /* row two */{7, 11, 3}
            };

    int row, column;

    for(row = 0; row < 2; row++){
        for(column = 0; column < 2; column++){
            printf("array[%d][%d] = %d \t", row, column, array[row][column]);
        }
        printf("\n");
    }
    

    return 0;
    
}

The indexes [2][3] define the array as a two-dimensional array with two rows consisting of three columns each. Note that for each dimension of the array we must include a set of brackets. We use nested for loops to iterate through multidimensional arrays. Remember here that each index starts at 0, not 1.

Our next program will sum each row in an array.

#include <stdio.h>

int main(void){


    int array[3][3] = {
        /* row 1 */ {128, 256, 512},
        /* row 2 */ {161, 389, 443},
        /* row 3 */ {80, 25, 118}
    }; //note the semicolon
    
    //traditional to use i, j
    //rather than row, column
    int i, j, total;
    for(i = 0; i < 3; i++){
        for(j = 0, total = 0; j < 3; j++){
            total += array[i][j];
            printf("%d ", array[i][j]);
        }
        printf(" \t total = %d\n", total);
    }

    return 0;

}

For our next program, we will pass the array to a function. Because an array of more than one dimension will be used, we must specify the dimensions of the array in the formal parameter list, in order for the compiler to properly set the array pointer for each of the rows.

#include <stdio.h>

int addColumn(int array[][3], int column, int numRows);

int main(void){


    int array[4][3] = {
        {25, 118, 123},
        {143, 161, 389},
        {80, 443, 22},
        {53, 88, 546}
    };

    int i, j;

    //go down each column
    //rather than across each row
    for(i = 0; i < 3; i++){
        printf("Column %d: \t", i+1);
        for(j = 0; j < 4; j++){
            printf("%d ", array[j][i]);
        }
        printf(" total = %d\n", addColumn(array, i, 4));
    }

    return 0;

}


int addColumn(int array[][3], int column, int numRows){
    int r = 0;
    for(int i = 0; i < numRows; i++){
        r += array[i][column];
    }
    return r;
}

Matrix multiplication is another useful thing we can do with two dimensional arrays. Matrix multiplication works by multiplying the columns of one matrix by the number of rows in the other. The general rule is that the number of columns in the first matrix must be equal to the number of rows in the second matrix; but, in order to simplify things, we will only be multiplying square matrices, where the number of columns and rows are equal.

#include <stdio.h>

void printMatrix(int array[3][3], int bounds);
void multiplyMatrix(int arrayX[3][3], int arrayY [3][3], int result[3][3], int bounds);

int main(void){
    
    int array1[3][3] = {
        {1, 2, 3},
        {2, 3, 4},
        {4, 5, 6}
    };

    int array2[3][3] = {
        {1, 3, 6},
        {3, 1, 6},
        {6, 3, 1},
    };

    int result[3][3];

    printf("Matrix one: \n");
    printMatrix(array1, 3);
    
    printf("\n\nMatrix two: \n");
    printMatrix(array2, 3);

    multiplyMatrix(array1, array2, result, 3);

    printf("\n results:\n");
    printMatrix(result, 3);

    return 0;


}


void printMatrix(int array[3][3], int bounds){
    int i, j;
    for(i = 0; i < bounds; i++){
        for(j = 0; j < bounds; j++){
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
}


void multiplyMatrix(int arrayX[3][3], int arrayY [3][3], int result[3][3], int bounds){
    int row, column, row2, column2;

    for(row = 0; row < bounds; row++){
        for(column = 0; column < bounds; column++){
            result[row][column] = 0;
            printf("Multiplying row %d of arrayX by column %d of arrayY\n", row, column);
            for(row2 = 0, column2 = 0; column2 < bounds; column2++, row2++){
                result[row][column] += arrayX[row][column2] * arrayY[row2][column];
            }
        }
    }

    
}

Take a look at my author’s page at: http://www.amazon.com/Big-Als-PHP-Al-Jensen-ebook/dp/B0084AKY18/

 

 

 

 

 

 

 

Writing Recursive Programs in C

A factorial is an example of a problem that has a recursive solution, but also an iterative solution that is, ultimately, more direct and simple. In such cases, it is my firm belief that the iterative solution is one to use. However, let’s take a look at developing a recursive function for deriving a factorial.

First, a factorial can have a limitless number of cases – we can have 0!, 1!, 2!, 10!, and so on; note here that the ! simply means factorial, so first we should find a base or “trivial” case for which a solution is readily obtainable. Obviously, we should use 0!, where the answer is quite direct: it’s 1. Next, we must a means to solve more complex problems in terms of this simple solution, thereby reducing a complex problem to a simple problem that’s merely been scaled upwards.

Of course, this what problem solving is all about – reducing a complex system into a series of simple, clearly defined steps. Recursion is simply another means of doing this. With recursive logic, we are always trying to, in a sense, work backwards from a more complex case to the simple, base case, sort of like going from the tree to the seed.

Let’s take the factorial of 5, 5!, this would be 4! * 5, right? Likewise, we could say that 4! is really 4 * 3!, and 3! is really 3 * 2!. So we can see that the factorial of any number is itself multiplied by itself minus one. If we use n to represent a number, we get the formula

n ! = n * (n – 1)!

Thus, a factorial meets the two criteria for a recursive function: a base case whose solution is immediately apparent, and a clear chain from any other case back to the base case. In the formula n! = n * (n – 1)!, it is assumed that (n – 1)! is known; well, wait, how do we know what (n-1)! is? It’s simply ((n-1)!-1)! Likewise, ((n-1)!-1)! is really (((n-1)!-1)!-1)! So wait, does this go on forever? No! Because the buck stops at 0, that’s our base case, and 0! simply equals 1.

I think part of the problem for people to understand recursion in programming is that the popular notion of recursion is that it keeps going backwards forever.

This is getting obnoxious, I know, but the cool thing with a program is we don’t have to keep manually performing the recursion, we can have the computer do it for us. With the computer, we can always just assume that, as long as n-1! has been defined in a function, that it has already been solved for us, because functions are placed first in, first out on the stack.

A full explanation of the stack is beyond the scope of this post, but what should be understood is that the stack functions in a first-in, first-out manner, like a stack of plates by the sink. What this means is that if a function calls another function, which in turn calls another function, which in turn calls another function, the last function to be called will be the first to be executed, and the computer will work backwards from there. So all we have to do is make sure that when a function calls itself repeatedly, the last time it calls itself it reaches the base case, were a definite answer is returned.

It also helps if we think of a value-returning function as being a variable, that is, a logical stand-in for an associated mutable value.

#include <stdio.h>

#define BASECASE 1

int fact(int n);
int fact2(int n);
int fact3(int n);

int main(void){

printf(“3! = %d\n”, fact(3));
printf(“4! = %d\n”, fact(4));
printf(“5! = %d\n”, fact(5));

printf(“\n\n”);
fact3(6);
return 0;

}

int fact(int n){
if(n!=0){
return n * fact(n-1);
} else {
return 1;
}

}

//with the steps broken down
int fact2(int n){
int x;
if(n!=0){
x = fact2(x-1);
return (n*x);
} else {
return BASECASE;
}
}

//with the steps really broken down
int fact3(int n){
printf(“factorial function called with parameter %d\n”, n);

int x, y;
if(n!=0){
x = n – 1;
y = fact3(x);
printf(“Returning %d\n”, n * y);
return n * y;

} else {
printf(“Base case reached.\n”);
return BASECASE;
}

}

Next, we will look at the classic Towers of Hanoi problem. In the Towers of Hanoi problem, there are three pegs, labelled A, B, and C. On peg A we have stacked five disks, visually each disk is shown to have a larger diameter than the one above it, so the disk on top is the smallest and the disk on bottom is the largest, we want to move all of the disks, in order from smallest to largest, to peg C.

Simple enough, right? Just pick it up and drop it.

Well, the problem is we can only remove the topmost disk from a peg, and at any given point of time, the disks on each peg must be in order, so that the smaller disks are always on the larger disks. In fact, this is why we three pegs rather than two, and at any given point in time, one peg is the source, one peg is the goal, and one peg is the buffer between the two.

If you want a visual reference, see http://en.wikipedia.org/wiki/Towers_of_hanoi but, for me at least, it’s easier if I don’t have a picture in front of me.

Now, let’s cheat a little bit.

The cheat is that we already know the optimum solution: the number of steps to arrive at the solution is 2^n-1, with n being the number of disks. What does this tell us? Two things: one, with every disk we add, the number of extra steps doubles, and two, in the base case, we only have to move the disk once to arrive at the solution. Of course, this makes perfect sense, if there’s only one disk on the board, then the largest disk is the only disk, and we only have to move it to C.

Next, let’s use some tricks.

Our first trick is to think of the problem as a game. Seen as a game, the basic strategy is to make sure there are no disks on top of the largest disk, and no disks on peg C, and then we simply move the disk to C, where we remove it from play. Now, we don’t actually take the disk off of peg C, but as the disk is “out” we no longer have to think about it, and we can even mentally remove it, if we like. So, no matter how many disks we have “in play” at any given moment, the strategy is still the same – get all other disks off of the largest disk, and make sure no disk that is still in play is on peg C. Whenever we get the largest disk to C, it’s out of the game, and the next largest disk becomes the largest disk.

In other words, once we solve for n, n-1 becomes n. We don’t have to solve for n, we just have to get everything that isn’t n out of the way.

We can say that once the largest disk is at C, it’s “out”, we don’t have to worry about it, or think about it anymore, mentally we can just take it off the peg and throw it away, for all we care. Next, we see that all we have to do is make sure there are no disks on top of the largest disk, and no disks on C. How do we do that? Simple, we make sure that all of the disks except for the largest disk are neither on peg C nor the peg the largest disk is on.

Thus, while the description of the problem states that there are three pegs, A, B, C, we really ought to think that there are three pegs – the destination peg, which ultimately is always C, and the auxiliary and source pegs, which can be either A or B depending on the number of disks and where we are in executing the algorithm.

To sum up:

n = the largest disk still “in play”

n-1 = the set of all other disks

buffer / auxiliary peg = where we want n-1 to go

destination peg = where we want n to go

source peg = where n is

#include <stdio.h>
void towers(int n, char source, char buffer, char destination);

int main(void){

towers(4, 'A', 'B', 'C');

return 0;

}

void towers(int n, char source, char buffer, char destination){

if(n!=1){
     //move all but the largest disk to the buffer peg
        //note that the buffer peg becomes the destination peg
towers(n-1, source, destination, buffer);
 //move remaining largest disk from a to c
printf("move disk %d from peg %c to peg %c\n", n, source, destination);
 //now n-1 is the new n, so pass it back to the function to be moved to C
        //note the source is now the buffer, where the rest of the disks are
        //the original source peg will then be used as the buffer
        //the destination, of course, remains the same.
towers(n-1, buffer, source, destination);

} else {
printf("move disk %d from peg %c to peg %c\n", n, source, destination);
return;
}
}

If you can, please buy my book on C: http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/