CS201: Elementary Data Structures

At this point we introduce dynamic C data structures. Till now we have seen fixed size data structures like arrays and structs. The size of these data structures remains the same through the program execution. This is alright for small programs.

These structures don't cover our needs for more complex and sophisticated programs. Ideally we need programs that consist of flexible data structures that can increase or decrease their size according to our needs at the run time of a program.

We can build dynamic data structures to overcome this problem. Some of these are: Linked lists, stacks, queues and binary trees. We will discuss them later in depth.

To build those dynamic data structures we will need two things.

Self referential structures

A self referential structure has a pointer that points to a structure of the same type.

Let's see an example:

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

This struct has two members. The first is an integer number.

The second is a type of struct node. This points to a struct node data type the same data type we defined at the beginning. This is why we call these structures self referential. They can link data structures of the same type to create dynamic structures like linked lists, stacks, queues and binary trees.

Dynamic memory allocation

Dynamic data structures need dynamic memory allocation. They must allocate or free memory according to our needs. The limits of the memory they can allocate are the limits of our system memory or the memory the operating system allow us to allocate.

To allocate memory we will use the "malloc()" function from the "memory allocation" words. The prototype is the following:

void* malloc (size_t size);

The size_t is the size of the memory we want to allocate for example "3*sizeof(int)". The malloc() function returns a pointer to the first block of the memory the function allocated. This object will have a NULL reference if it's empty or if something went wrong with the malloc() function.

To clean up the memory we can use the "free()" function. The prototype is the following:

void free (void* ptr);

It takes as input the pointer that points to the allocated memory block and cleans it up.

We must never forget to use the free() function to clean up the memory.

Let's see it in an example:

/*
	C dynamic memory
	allocation example
*/
 
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
	int *ptr;
	int size;
	int i;
 
	printf("How many integers do you want?:");
	scanf("%d",&size);
 
	ptr = (int*) malloc(size * sizeof(int));
 
	if(ptr == NULL)
	{
		printf("Error! memory not allocated.");
	}
	else
	{
		for(i = 0; i < size; ++i)
		{
			ptr[i] = i+1;
		}
	}
 
	if(ptr == NULL)
	{
		printf("Error! memory not allocated.");
	}
	else
	{
		for(i = 0; i < size; ++i)
		{
			printf("%d ",ptr[i] = i+1);
		}
	}
 
	free(ptr);
 
	return 0;
}

Functions malloc() and free() are living under the <stdlib.h> library so we must include it every time.

In line 11 we define a pointer to an integer object.

In line 18 we dynamically allocate memory for this pointer. Now the integer pointer points to a memory block of integers.

In line 20 and line 32 we evaluate the pointer with NULL in case of something went wrong with malloc() function.

As you can see C has not built in function to find dynamically the size of the memory block. For this we should program our "tracking mechanism" to know every time how many blocks we allocated.

If we run this example we will get the following output:

How many integers do you want?:10
1 2 3 4 5 6 7 8 9 10

Next we will see an example with a student struct:

/*
	C dynamic memory
	allocation with structs
*/
 
#include <stdio.h>
#include <stdlib.h>
 
struct student
{
	int code;
	char name[20];
	double grade;
};
 
int main()
{
	struct student *std;
	int size;
	int i;
 
	printf("How many students do you want?:");
	scanf("%d",&size);
 
	std = (struct student *) malloc( size * sizeof(struct student));
 
	if ( std == NULL )
	{
		printf("Error! memory not allocated.");
	}
	else
	{
		for (i = 0; i < size; i++)
		{
			printf("Student| Code Name Grade:");
			scanf("%d%s%lf",&std[i].code,std[i].name,&std[i].grade);
		}
	}
 
    if ( std == NULL )
	{
		printf("Error! memory not allocated.");
	}
	else
	{
		for (i = 0; i < size; i++)
		{
			printf("\nStudent Code:%d Name:%s Grade:%.1f\n",std[i].code,std[i].name,std[i].grade);
		}
	}
 
	free(std);
 
	return 0;
}

In this example we allocating memory for struct student data types.

Let's test this example:

How many students do you want?:4
Student| Code Name Grade:384 John 7.8
Student| Code Name Grade:886 Mary 8.8
Student| Code Name Grade:465 Alex 6.5
Student| Code Name Grade:223 Tom 5.5
 
Student Code:384 Name:John Grade:7.8
 
Student Code:886 Name:Mary Grade:8.8
 
Student Code:465 Name:Alex Grade:6.5
 
Student Code:223 Name:Tom Grade:5.5

Source: Hootnest, http://hootnest.com/programming-tutorials/c-tutorials/c-data-structures
 This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.