C Primer Plus，十七

17.1 研究数据表示

先来研究一个实例，假设您想要写一个程序来输入您一年中看过的所有电影。下面来一个简单实现的程序

1. #include<stdio.h>
2. #define TSIZE 45 /* 存放片名的数组大小 */
3. #define FMAX 5 /* 最多的影片数 */
4. struct film{
5. char title[TSIZE];
6. int rating;
7. };
8. int main(void)
9. {
10. struct film movies[FMAX];
11. int i=0;
12. int j;
13. puts("Enter first movie title: ");
14. while(i<FMAX&&gets(movies[i].title)!=NULL&&movies[i].title[0]!='\0')
15. {
16. scanf("%d",&movies[i++].rating);
17. while(getchar()!='\n')
18. continue;
19. puts("Enter next movie title(empty line to stop): ");
20. }
21. if(i==0)
22. printf("No data entered. ");
23. else
24. printf("Here is the movie lise:\n");
25. for(j=0;j<i;j++)
26. printf("Movie: %s Rating: %d\n",movies[j].title,movies[j].rating);
27. printf("Bye!\n");
28. return 0;
29. }

程序创建了一个结构数组，然后把用户输入的数据填充到这个数组中。直到数组满，或者到达文件结尾，或者用户在行首按下回车键，输入才会终止。

但是存在一些问题：

一、程序很可能会浪费大量空间，因为大多数电影的片名并没有40个字符。

二、每年5部电影的限制太严格了。

三、movies数组可能超过默认限制的内存大小。

这里的根本问题就是数据表示方法不太灵活。可以使用以下办法进行更改

struct film *movies;

int n;

printf("Enter the maxmimum\n");

scanf("%d",&n);

movies=(struct film *)malloc(n*sizeof(struct film));

通过使用malloc()，可以将确定元素个数的时间延迟到程序运行时，进行按需分配。

17.2 从数组到链表

上述办法又导致了一个新问题，有两种情况，调用malloc()函数1次，请求保存300个film结构的空间，和调用malloc()函数300次，每次请求保存1个film结构的空间。

第一种情况将分配一个连续的内存块，用以跟踪这些内容的只是一个指向struct film的指针变量，它指向块中的第一个结构。

第二种方法的问题是不能保证连续的malloc()调用产生相邻的内存块。这意味着这些结构不一定会被连续存储。

因此，需要存储300个指针，其中每个指针指向一个独立存储的结构，而不是存储一个指向有300个结构的块的指针。

一种解决方法是创建一个大的指针数组，并在分配新的结构时逐个地对这些指针赋值。但是，无用指针占用的空间仍然会被浪费，并且仍然有500个结构的限制。

有一种更好的方法，每次使用malloc()为新结构分配空间时，也为新指针分配空间。但是就要另一个指针来跟踪新分配的指针。

简而言之，需要这样来重新定义film结构：

#define TSIZE 45

struct film{

char title[TSIZE];

int rating;

struct film *next;

};

结构本身不能含有同类型的结构，但是它可以含有指向同类型结构的指针。

这样的定义是定义链表的一个基础。链表是一个列表，其中的每一项都包含描述何处能找到下一项的信息。

一个实例

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<string.h>
4. #define TSIZE 45
5. struct film{
6. char title[TSIZE];
7. int rating;
8. struct film *next;
9. };
10. int main(void)
11. {
12. struct film *head=NULL;
13. struct film *prev,*current;
14. char input[TSIZE];
15. while(gets(input)!=NULL&&input[0]!='\0')
16. {
17. current=(struct film*)malloc(sizeof (struct film));
18. if(head==NULL)
19. head=current;
20. else
21. prev->next=current;
22. current->next=NULL;
23. strcpy(current->title,input);
24. scanf("%d",&current->rating);
25. while(getchar()!='\n')
26. continue;
27. prev=current;
28. }
29. current=head;
30. while(current!=NULL)
31. {
32. printf("%s %d\n",current->title,current->rating);
33. current=current->next;
34. }
35. current=head;
36. while(current!=NULL)
37. {
38. free(current);
39. current=current->next;
40. }
41. printf("Bye!\n");
42. return 0;
43. }

为什么不使用head来遍历整个列表，而是创建一个新指针current？因为使用head会改变它的值，这样程序将不再找到列表的开始处。

程序在终止时会自动释放由malloc()分配的内存，但最好是养成调用free()来释放由malloc()分配内存的习惯。

该程序还能进行改进。例如添加检查malloc()的返回值是否为NULL的代码。

17.3 抽象数据类型(ADT)

一个类型指定两类信息：一个属性集和一个操作集。

加上您想定义一个新的数据类型。

首先，您需要提供存储数据的方式，可能是通过设计一个结构。

第二，需要提供操作数据的方式。

计算机科学已经研究出一种定义新类型的成功方法。

1、为类型的属性和可对类型执行的操作提供一个抽象的描述。这个描述不应受任何特定实现的约束，这样一种正式的抽象描述被成为ADT。

2、开发一个实现该ADT的编程借口。即说明如何存储数据并猫鼠用于执行所需操作的函数集合。

3、编写代码来实现这个接口。

接口的设计应和ADT的描述尽可能密切地保持一致。因此应该用某种通用的Item类型来进行表达，而不是用诸如int或struct film之类的专用类型。

这样做的方法之一是使用C的typedef工具将Item定义为所需类型例如

#define TSIZE 45

struct film{

char title[TSIZE];

int rating；

};

typedfef struct film Item;

定义了Item之后，您需要决定如何存储这种类型的项目。这一步属于实现阶段，但是提前决定可以使例子更简单一些。

typedfef struct node

{

Item item;

struct node *next;

}Node;

typedef Node * List;

在链表的实现中，每一个链接被称为一个节点。每一个节点包哈形成列表内容的信息和指向下一个节点的指针。

最后为了管理链表，需要一个指向其开始处的指针，我们通过typedef使List成为指向Node类型的指针的名称。

如果编译器不支持C99布尔类型，可以在头文件中用enum bool{false,true};替换#include<stdbool.h>