When most people come to a new language, they think in terms of the capabilities of their old languages for quite a while. If their old language didn't support a given capability (for example, pointers to functions), they may not even know about that capability, or have any real idea why they would want to use it. So the more educated you can become about C's data structure capabilities, the better off you'll be. I hope this series will help.

I plan to cover the following topics:

• simple arrays and array operations (such as insertion, deletion, and searching)
• arrays of pointers versus multi-dimensional arrays
• the use of malloc and friends to extend arrays
• stacks, queues, deques, and linked lists (single, double, circular, and lattice)
• recursion
• pointers to functions and tables thereof
• trees

If you wish to read a little on your own, I recommend Donald E. Knuth's The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley ISBN 0-201-03809-9. Chapter 2 (Information Structures) runs some 230 pages and is full of useful information on data structures. Although much of this was written more than 20 years ago, it is still quite relevant.

• Add a new node to the end
• Change a user-selected node
• Display a user-selected node
• Insert a new node between nodes or before the first node
• Remove a user-selected node
• Search for first occurrence of a node value
• Search for last occurrence of a node value
• Report the number of nodes
• Sort the nodes in ascending order
• Show all entries in the table
<

I use scanf to get user-supplied input. If you want robust error recovery on invalid input, scanf is difficult (if not impossible) to use. That is a separate issue, not directly relevant to the main theme. So I have chosen to ignore input validation for the most part. If you want, you can easily supply input that will break the program.

The commands are defined using macros, so you can change the characters used. You could also obtain input using a mouse-driven menu. Again, that is peripheral to the main topic.

Throughout the series, I will adapt this program to use different data structures behind the scenes. For example, in this first part I use a simple automatic one-dimensional array. Next, I use one allocated at runtime via malloc. Eventually, in a future installment, I will use a dynamically allocated linked list.

Standard C provides a family of routines to allocate memory at runtime. I will refer to this as dynamic memory allocation. (See my column "The Memory Management Library" in CUJ Vol. 8, No. 1.) With careful design, you can easily change from using an automatic or static object to a dynamic one. The only changes you need to make to the program are as follows:

#include <stdlib.h>

main()
{
   int *ary;/* ary is now a pointer, NOT an array */
   ...
   ary = malloc(MAX_NODES * sizeof(int));
   if (ary == NULL) {
      printf ("Cannot allocate memory for ary\n");
      exit(2);
}

int *ptr;
int max_nodes = 1;

ary = malloc(max_nodes * sizeof(int));
if (ary == NULL) {
   printf ("Cannot allocate initial memory"
      "for ary\n");
   exit(2);
}

The only other changes are to the cases ADD_NODE and INSERT_NODE. Instead of complaining when the table is full, these operations can now extend the array by one node, as follows:

if (nodes_in_use == max_nodes) {
   ptr = realloc(ary,
      (max_nodes + 1) * sizeof(int));
   if (ptr == NULL) {
      printf("Cannot allocate new node\n");
      break;
   }
   ary = ptr;
   ++max_nodes;
}

realloc lets you extend the array by one node with a very small amount of code, but it is probably not efficient over the long run. You might want to extend the array by a cluster of nodes (say 5 to 10 at a time). Or you might chose to use a linked list instead to avoid the need for realloc to copy any of the existing array.

In my realloc version, I chose not to shrink the array when a node was deleted. This was an arbitrary choice. You could argue that it would be good housekeeping to do so. You could also argue that by not freeing deleted nodes you can maintain a cache of available nodes when the next addition or insertion is needed.