Writing C Program(s) Using Dynamic Data Structures

775Exploring Data Representation

Let’s tackle a particular case of representing data. Suppose you want to write a program that

enables you to enter a list of all the movies (including videotapes, DVDs, and Blu-ray) you’ve

seen in a year. For each movie, you’d like to record a variety of information, such as the title,

the year it was released, the director, the lead actors, the length, the kind of film (comedy,

science fiction, romance, drivel, and so forth), your evaluation, and so on. That suggests using

a structure for each film and an array of structures for the list. To simplify matters, let’s limit

the structure to two members: the film title and your evaluation, a ranking on a 0-to-10 scale.

Listing 17.1 shows a bare-bones implementation using this approach.

Listing 17.1 The films1.c Program

/* films1.c -- using an array of structures */

#include <stdio.h>

#include <string.h>

#define TSIZE 45 /* size of array to hold title */

#define FMAX 5 /* maximum number of film titles */

struct film {

char title[TSIZE];

int rating;

};

char * s_gets(char * st, int n);

int main(void)

{

struct film movies[FMAX];

int i = 0;

int j;

puts("Enter first movie title:");

while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL &&

movies[i].title[0] != '\0')

{

puts("Enter your rating <0-10>:");

scanf("%d", &movies[i++].rating);

while(getchar() != '\n')

continue;

puts("Enter next movie title (empty line to stop):");

}

if (i == 0)

printf("No data entered. ");

else

printf ("Here is the movie list:\n");

for (j = 0; j < i; j++)

printf("Movie: %s Rating: %d\n", movies[j].title,

movies[j].rating);

776 Chapter 17 Advanced Data Representation

printf("Bye!\n");

return 0;

}

char * s_gets(char * st, int n)

{

char * ret_val;

char * find;

ret_val = fgets(st, n, stdin);

if (ret_val)

{

find = strchr(st, '\n'); // look for newline

if (find) // if the address is not NULL,

*find = '\0'; // place a null character there

else

while (getchar() != '\n')

continue; // dispose of rest of line

}

return ret_val;

}

The program creates an array of structures and then fills the array with data entered by the

user. Entry continues until the array is full (the FMAX test), until end-of-file (the NULL test) is

reached, or until the user presses the Enter key at the beginning of a line (the ‘\0’ test).

This formulation has some problems. First, the program will most likely waste a lot of space

because most movies don’t have titles 40 characters long, but some movies do have long titles,

such as The Discreet Charm of the Bourgeoisie and Won Ton Ton, The Dog Who Saved Hollywood .

Second, many people will find the limit of five movies a year too restrictive. Of course, you can

increase that limit, but what would be a good value? Some people see 500 movies a year, so you

could increase FMAX to 500, but that still might be too small for some, yet it might waste enor-

mous amounts of memory for others. Also, some compilers set a default limit for the amount

of memory available for automatic storage class variables such as movies , and such a large array

could exceed that value. You can fix that by making the array a static or external array or by

instructing the compiler to use a larger stack, but that’s not fixing the real problem.

The real problem here is that the data representation is too inflexible. You have to make deci-

sions at compile time that are better made at runtime. This suggests switching to a data repre-

sentation that uses dynamic memory allocation. You could try something like this:

#define TSIZE 45 /* size of array to hold title */

struct film {

char title[TSIZE];

int rating;

};