Exploring Data Representation

I l @ ve RuBoard

Exploring Data Representation

Let's begin by thinking about data. Suppose you had to create an address book program. What data form would you use to store information? Because there's a variety of information associated with each entry, it makes sense to represent each entry with a structure. How do you represent several entries? With a standard array of structures? With a dynamic array? With some other form? Should the entries be alphabetized? Should you be able to search through the entries by zip code? by area code? The actions you want to perform might affect how you decide to store the information. In short, you have a lot of design decisions to make before plunging into coding.

How would you represent a bitmapped graphics image that you want to store in memory? A bitmapped image is one in which each pixel on the screen is set individually. In the days of black-and-white screens, you could use one computer bit (1 or 0) to represent one pixel (on or off), hence the name bitmapped . With color monitors , it takes more than one bit to describe a single pixel. For instance, you can get 256 colors if you dedicate 8 bits to each pixel. Now the industry has moved to 65,536 colors (16 bits per pixel), 16,777,216 colors (24 bits per pixel), and even 2,147,483,648 colors (32 bits per pixel). If you have 16 million colors and if your monitor has a resolution of 1024 — 768, you'll need 18.9 million bits (2.25 MB) to represent a single screen of bitmapped graphics. Is this the way to go, or can you develop a way of compressing the information? Should this compression be lossless (no data lost) or lossy (relatively unimportant data lost)? Again, you have a lot of design decisions to make before diving into coding.

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) 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> #define TSIZE        45      /* size of array to hold title   */ #define FMAX         5       /* maximum number of film titles */ struct film {    char title[TSIZE];    int rating; }; int main(void) {    struct film movies[FMAX];    int i = 0;    int j;    puts("Enter first movie title:");    while (i < FMAX && gets(movies[i].title) != NULL &&       movies[i].title[0] != ` 
  /* films1.c -- using an array of structures */ #include <stdio.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; }; int main(void) { struct film movies[FMAX]; int i = 0; int j; puts("Enter first movie title:"); while (i < FMAX && gets(movies[i].title) != 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); printf("Bye!\n"); return 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);    printf("Bye!\n");    return 0; } 

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 enormous 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 decisions at compile time that are better made at runtime. This suggests switching to a data representation 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; }; ... int n, i; struct film * movies;       /* pointer to a structure       */ ... printf("Enter the maximum number of movies you'll enter:\n"); scanf("%d", &n); movies =  (struct film *) malloc(n * sizeof(struct film)); 

Here, as in the preceding chapter, you can use the pointer movies just as though it were an array name:

 while (i < FMAX && gets(movies[i].title) != NULL &&          movies[i].title[0] !=` 
  while (i < FMAX && gets(movies[i].title) != NULL && movies[i].title[0] !=`\0')  
 ') 

By using malloc() , you can postpone determining the number of elements until the program runs, so the program need not allocate 500 elements if only 20 are needed. However, it puts the burden on the user to supply a correct value for the number of entries.

I l @ ve RuBoard