02-研究数据表示

17.1　研究数据表示

我们先从数据开始。假设要创建一个地址簿程序。应该使用什么数据形式存储信息？由于存储的每一项都包含多种信息，用结构来表示每一项很合适。如何表示多个项？是否用标准的结构数组？还是动态数组？还是一些其他形式？各项是否按字母顺序排列？是否要按照邮政编码（或地区编码）查找各项？需要执行的行为将影响如何存储信息？简而言之，在开始编写代码之前，要在程序设计方面做很多决定。

如何表示存储在内存中的位图图像？位图图像中的每个像素在屏幕上都单独设置。在以前黑白屏的年代，可以使用一个计算机位（1或0）来表示一个像素点（开或闭），因此称之为位图。对于彩色显示器而言，如果8位表示一个像素，可以得到256种颜色。现在行业标准已发展到65536色（每像素16位）、16777216色（每像素24位）、4294967296色（每像素32位），甚至更多。如果有32位色，且显示器有2560×1440的分辨率，则需要将近1.18亿位（14M）来表示一个屏幕的位图图像。是用这种方法表示，还是开发一种压缩信息的方法？是有损压缩（丢失相对次要的数据）还是无损压缩（没有丢失数据）？再次提醒读者注意，在开始编写代码之前，需要做很多程序设计方面的决定。

我们来处理一个数据表示的示例。假设要编写一个程序，让用户输入一年内看过的所有电影（包括 DVD 和蓝光光碟）。要存储每部影片的各种信息，如片名、发行年份、导演、主演、片长、影片的种类（喜剧、科幻、爱情等）、评级等。建议使用一个结构存储每部电影，一个数组存储一年内看过的电影。为简单起见，我们规定结构中只有两个成员：片名和评级（0～10）。程序清单17.1演示了一个基本的实现。

程序清单17.1　 films1.c 程序

/* films1.c -- 使用一个结构数组 */
#include <stdio.h>
#include <string.h>
#define TSIZE       45   /* 存储片名的数组大小 */
#define FMAX        5    /* 影片的最大数量 */
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);
     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');    // 查找换行符
          if (find)                   // 如果地址不是 NULL,
               *find = '\0';          // 在此处放置一个空字符
          else
               while (getchar() != '\n')
                    continue;         // 处理剩余输入行
     }
     return ret_val;
}

该程序创建了一个结构数组，然后把用户输入的数据存储在数组中。直到数组已满（用 FMAX 进行判断）或者到达文件结尾（用 NULL 进行判断），或者用户在首行按下 Enter 键（用 '\0' 进行判断），输入才会终止。

这样设计程序有点问题。首先，该程序很可能会浪费许多空间，因为大部分的片名都不会超过 40 个字符。但是，有些片名的确很长，如The Discreet Charm of the Bourgeoisie和Won Ton Ton, The Dog Who Saved Hollywood。其次，许多人会觉得每年5部电影的限制太严格了。当然，也可以放宽这个限制，但是，要多大才合适？有些人每年可以看500部电影，因此可以把 FMAX 改为500。但是，对有些人而言，这可能仍然不够，而对有些人而言一年根本看不了这么多部电影，这样就浪费了大量的内存。另外，一些编译器对自动存储类别变量（如 movies ）可用的内存数量设置了一个默认的限制，如此大型的数组可能会超过默认设置的值。可以把数组声明为静态或外部数组，或者设置编译器使用更大的栈来解决这个问题。但是，这样做并不能根本解决问题。

该程序真正的问题是，数据表示太不灵活。程序在编译时确定所需内存量，其实在运行时确定会更好。要解决这个问题，应该使用动态内存分配来表示数据。可以这样做：

#define TSIZE 45    /*存储片名的数组大小*/
     struct film {
     char title[TSIZE];
     int rating;
};
...
int n, i;
struct film * movies;    /* 指向结构的指针 */
...
printf("Enter the maximum number of movies you'll enter:\n");
scanf("%d", &n);
movies = (struct film *) malloc(n * sizeof(struct film));

第12章介绍过，可以像使用数组名那样使用指针 movies 。

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

使用 malloc() ，可以推迟到程序运行时才确定数组中的元素数量。所以，如果只需要20个元素，程序就不必分配存放500个元素的空间。但是，这样做的前提是，用户要为元素个数提供正确的值。