Data Structures and Algorithms: Arrays

Data Structures and Algorithms

3 Data Structures

In this section, we will examine some fundamental data structures: arrays, lists, stacks and trees.

3.1 Arrays

The simplest way to implement our collection is to use an array to hold the items. Thus the implementation of the collection object becomes:


/* Array implementation of a collection */
#include <assert.h>		/* Needed for assertions */
#include "collection.h"	/* import the specification */

struct t_collection {
	int item_cnt;
	int max_cnt;	/* Not strictly necessary */
	int item_size;	/* Needed by FindInCollection */
	void *items[];
	};

Points to note:

We have imported the specification of this object into the implementaton - this enables the compiler to verify that the implementation and the specification match. Although it's not necessary to include the specification (cf function prototypes), it is much safer to do so as it enables the compiler to detect some common errors and ensures that the specification and its implementation remain consistent when the object is changed.
items is typed as an array of void * in the struct. It is an array of item's which happen to be pointers - but remember that we are trying to hide this from users of the class. Many C programmers would write the equivalent void ** here.

A question:

Why is the attribute max_cnt not strictly necessary?
Hint: it's related to the pre- and post-conditions specified for methods on this object.

Points to note:

ConsCollection uses the memory allocator calloc to dynamically allocate memory off the program's heap for the collection. Two calls are necessary - one to allocate space for the "header" structure itself and one to allocate space for the array of item pointers.
assert calls have been added for the pre-conditions (cf full description of assert). Note that the pre-conditions here are expressed as a number of conditions linked by &&. Since assert requires a single boolean expression as its argument, one assert would suffice. However, we have chosen to implement each individual condition as a separate assert. This is done to assist de-bugging: if the pre-conditions are not satisfied, it is more helpful to know which one of multiple conditions has not been satisfied!
memcmp is a standard function which compares blocks of memory byte by byte [man page for memcmp].
The use of memcp and ItemKey severely constrain the form of the key - it must be in a contiguous string of characters in the item. There are ways of providing more flexible keys (eg ones having multiple fields within item or ones calculated from item. These rely on C capabilities which will be discussed in a later section.
There is no treatment of errors, e.g. if no memory is available on the heap for calloc.
This is a serious shortcoming.
No software without a consistent strategy for detecting, reporting and recovering from errors can be considered well engineered. It is difficult to debug, prone to crashes from faults which are difficult to correct because there is no indication of the source of the error.
Error handling is addressed in a later section.

Key terms

hacking: producing a computer program rapidly, without thought and