Writing C Program(s) Using Dynamic Data Structures

775 Exploring 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 #include #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() != ' ') continue; puts("Enter next movie title (empty line to stop):"); } if (i == 0) printf("No data entered. "); else printf ("Here is the movie list:

"); for (j = 0; j < i; j++) printf("Movie: %s Rating: %d ", movies[j].title, movies[j].rating); 776 Chapter 17 Advanced Data Representation printf("Bye!

"); 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, ' '); // look for newline if (find) // if the address is not NULL, *find = '\0'; // place a null character there else while (getchar() != ' ') 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; };