高级数据表示
主要内容：
函数:进一步学习malloc ( )
使用C表示不同类型的数据
新的算法，从概念上增强开发程序的能力
抽象数据类型( ADT)
学习计算机语言和学习音乐、木工或工程学一样。首先，要学会使用工具:学习如何演奏音阶、如使用锤子等，然后解决各种问题，如降落、滑行以及平衡物体之类。到目前为止，读者一直在本书中学和练习各种编程技能，如创建变量、结构、函数等。然而，如果想提高到更高层次时，工具是次要的，真正的挑战是设计和创建一个项目。
学到现在应该明白C语言的内置类型
简单变量、数组、指针、结构和联合
后面还会讲一些算法，即操控数据的方法
之后是研究设计数据类型的过程，这是一个把算法和数据相匹配的过程，会讲到常用的数据形式，如队列、列表和二叉树
小荔枝
#include <stdio.h> #include <string.h> #define TSIZE 45 //存储片面的数组大小 #define FMAX 5 //影片的最大数量 struct film { char title[TSIZE]; int rating; }; char * s_gets(char str[] , int lim); //一个函数类型的指针 int main(void) { struct film movies[FMAX]; //定义一个结构数组，数组中的每一个元素都是film类型的结构变量 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) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val; }
输出结果为：
PS D:\Code> cd "d:\Code\C\结构\" ; if ($?) { gcc structDemo03.c -o structDemo03 } ; if ($?) { .\structDemo03 } Enter first movie title: Roman holiday Enter your rating<0-10>: 2 Enter next movie title (empty line to stop): Here is the movie list: Movie: Roman holiday Rating: 2 Bye!
程序解析
该程序创建了一个结构数组，然后把用户输入的数据储存在数组中。直到数组已满（用FMAX进行判断）或者到达文件结尾（用NULL进行判断)，或者用户在首行按下 Enter键(用’\0’进行判断)，输入才会终止。
这样设计程序有点问题。首先，该程序很可能会浪费许多空间，因为大部分的片名都不会超过40个字符。但是，有些片名的确很长，如The Discreet Charm of the Bourgeoisie和 Won Ton Ton, The Dog Who SavedHollywood。其次，许多人会觉得每年5部电影的限制太严格了。当然，也可以放宽这个限制，但是，要多大才合适?有些人每年可以看500部电影，因此可以把FMAX改为500。但是，对有些人而言，这可能仍然不够，而对有些人而言一年根本看不了这么多部电影，这样就浪费了大量的内存。另外，一些编译器对自动存储类别变量（如movies）可用的内存数量设置了一个默认的限制，如此大型的数组可能会超过默认设置的值。可以把数组声明为静态或外部数组，或者设置编译器使用更大的栈来解决这个问题。但是.这样做并不能根本解决问题。
该程序真正的问题是，数据表示太不灵活。程序在编译时确定所需内存量，其实在运行时确定会更好。要解决这个问题，应该使用动态内存分配来表示数据。可以这样做:
更新之后的程序不在程序运行前才确定数组中的元素数量，这种属于是一次调用分配连续的内存空间。
创建指针，指向这个结构，最后为指针分配地址（n*sizeof(struct film)）
一、从数组到链表
理想的情况是用户不断的添加数据，而不是先指定要输入多少项，也不用让程序分配多余的空间。这可以通过在输入每一项后调用malloc（）分配正好能存储该项的空间。如果输入3部影片，程序就调用malloc（）3次；如果用户输入300部就调用300次！
比较一下，一种方法是调用malloc()一次，为300个filem结构请求分配足够的空间;另一种方法是调用malloc ()300次，分别为每个file结构请求分配足够的空间。前者分配的是连续的内存块，只需要一个单独的指向struct变量(film）的指针，该指针指向已分配块中的第Ⅰ个结构。简单的数组表示法让指针访问块中的每个结构，如前面代码段所示。第⒉种方法的问题是，无法保证每次调用malloc()都能分配到连续的内存块。这意味着结构不一定被连续储存(见图17.因此，与第1种方法储存一个指向300个结构块的指针相比，你需要储存300个指针，每个指针指向一个单独储存的结构。
书里面这段话写的太好了，我全加粗了！
每次使用malloc()为新结构分配空间时，也为新指针分配空间。但是，还得需要另一个指针来跟踪新分配的指针，用于跟踪新指针的指针本身，也需要一个指针来跟踪，以此类推要重新定义结构才能解决这个潜在的问题，即每个结构中包含指向next 结构的指针。然后，当创建新结构时，可以把该结构的地址储存在上一个结构中。简而言之，可以这样定义film结构:
#define TSIZE 45 //储存片名的数组大小 struct film { char title [ TSIZE]; int rating; struct film * next; };
1.1 重要的一个点
虽然结构不能含有与本身类型相同的结构，但是可以含有指向同类型结构的指针。这种定义是定义链表( linked list）的基础，链表中的每一项都包含着在何处能找到下一项的信息。
在学习链表的代码之前，我们先从概念上理解一个链表。假设用户输入的片名是Modern Times，等级为10。程序将为film类型的结构分配空间，把字符串 Modern Times拷贝到结构中的title成员中，然后设置rating成员为10。为了表明该结构后面没有其他结构,程序要把next成员指针设置为NULL(NULL是一个定义在stdio.h头文件中的符号常量，表示空指针)。当然，还需要一个**单独的指针储存第1个结构的地址，该指针被称为头指针( head pointer)。头指针指向链表中的第1项。**图17.2演示了这种结构（为节约图片空间，压缩了title成员中的空白)。
现在，假设用户输入第2部电影及其评级，如Midnight in Paris和8。程序为第2个film类型结构分配空间，把新结构的地址储存在第Ⅰ个结构的next成员中（擦写了之前储存在该成员中的NULL)这样链表中第Ⅰ个结构中的next 指针指向第2个结构。然后程序把Midnight in Paris和8拷贝到新结构中，并把第2个结构中的next 成员设置为NOLL，表明该结构是链表中的最后一个结构。图17.3演示这两个项。
书上的介绍写的太好了！
每加入一部新电影，就以相同的方式来处理。新结构的地址将储存在上-一个结构中，新信息储存在新结构中，而且新结构中的next成员设置为NULL
假设要显示这个链表，每显示一-项， 就可以根据该项中已储存的地址来定位下一个待显示的项。然而，这种方案能正常运行，还需要一个指针储存链表中第1项的地址，因为链表中没有其他项储存该项的地址。此时，头指针就派上了用场。
二、使用链表
我们用代码来实现一个链表！
#include <stdio.h> #include <stdlib.h> #include <string.h> #define TSIZE 45 struct film { char title[TSIZE]; int rating; struct film *next; //指向链表中的下一个结构 }; char *s_gets(char *st, int n); //函数返回值为char类型的指针 int main(void) { struct film *head = NULL; struct film *prev, *current; char input[TSIZE]; puts("Enter first movie title:"); while (s_gets(input, TSIZE) != NULL && input[0] != '\0') { current = (struct film *)malloc(sizeof(struct film)); if (head == NULL) head = current; else prev->next = current; current->next = NULL; strcpy(current->title, input); puts("Enter your rating <0-10>:"); scanf("%d", ¤t->rating); while (getchar() != '\n') continue; puts("Enter next movie title (empty line to stop)"); prev = current; } /*显示电影列表*/ if (head == NULL) printf("No data entered. "); else printf("Here is the movie list: \n"); current = head; while (current != NULL) { printf ("Movie: %s Rating: %d\n",current->title,current -> rating); current = current->next ; } /*完成任务,释放已分配的内存*/ current = head; while (current != NULL) { current = head; head = current->next; free(current); } 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) *find = '\0'; else while (getchar() != '\n') continue; } return ret_val;c } 输出结果为： PS D:\Code\C\结构> cd "d:\Code\C\结构\" ; if ($?) { gcc 链表Demo01.c -o 链表Demo01 } ; if ($?) { .\链表Demo01 } Enter first movie title: Roman Holiday Enter your rating <0-10>: 8 Enter next movie title (empty line to stop) Rose Enter your rating <0-10>: 2 Enter next movie title (empty line to stop) Here is the movie list: Movie: Roman Holiday Rating: 8 Movie: Rose Rating: 2
该程序用链表执行两个任务。第1个任务是，构造一个链表，把用户输入的数据储存在链表中。第2个任务是，显示链表。显示链表的任务比较简单，所以我们先来讨论它。
2.1 程序解析
2.1.1显示链表
由于书上的写的太好了，我直接照抄下来给大家参考！
显示列表从设置一个指向结构的指针开始（名为current）。由于头指针（head）已经指向链表中的第一个结构，所以可以这样表示
current = head；
然后用前面章节讲的指针表示法访问结构体中的成员
printf ("Movie: %s Rating: %d\n",current->title,current -> rating);
打印之后，在把current指针指向下一个结构
current = current->next
完成这些之后，再重复整个过程。当显示到链表中最后一个项时，current将被置为null，因为这是链表最后一个结构中next成员的值
while (current != NULL) { //指针访问结构中的成员可以用指针.成员即可 printf ("Movie: %s Rating: %d\n",current->title,current -> rating); current = current->next ; }
遍历链表时，为何不直接使用head指针，而要重新创建一个新指针？因为用head就会改变head中的值，程序就找不到链表的开始处
2.1.2创建链表
创建链表涉及下面3步:
(1）使用malloc ()为结构分配足够的空间;
(2）储存结构的地址;
(3）把当前信息拷贝到结构中。
如无必要不用创建一个结构，所以程序使用临时存储区（input数组）获取用户输入的电影名。如果用户通过键盘模拟EOF或输入一行空行，将退出下面的循环:
while (s gets(input,TSIZE)!= NULL && input [0] != '\0 ')
如果用户进行输入，程序就分配一个结构的空间，并将其地址赋给指针变量
current:current = (struct film *) malloc(sizeof(struct film) ) ;
链表中第1个结构的地址应储存在指针变量head中。随后每个结构的地址应储存在其前一个结构的next成员中。因此，程序要知道它处理的是否是第1个结构。最简单的方法是在程序开始时，把 head指针初始化为NULL。然后，程序可以使用head的值进行判断:
if (head == NULL) //第1个结构 head = current; else //subsequent structures prev->next = current;
在上面的代码中，指针prev指向上一次分配的结构。
接下来，必须为结构成员设置合适的值。尤其是，把next成员设置为NULL，表明当前结构是链表的最后一个结构。还要把input数组中的电影名拷贝到title成员中，而且要给rating成员提供一个值如下代码所示:
current->next = NULL; strcpy (current->title, input) ; puts ( "Enter your rating <0-10> :");scanf ( "%di",¤t->rating) ;
由于s_gets ()限制了只能输入TSIZE-1个字符，所以用strcpy()函数把input 数组中的字符串拷贝到title成员很安全。
最后，要为下一次输入做好准备。尤其是，要设置 prev指向当前结构。因为在用户输入下一部电影且程序为新结构分配空间后，当前结构将成为新结构的上一个结构，所以程序在循环末尾这样设置该指针:
prev = current;
程序是否能正常运行?下面是该程序的一个运行示例;
Enter first movie title: Spirited Away Enter your rating <0-10>: 9 Enter next movie title (empty line to stop): The Duelists Enter your rating : 8 Enter next movie title (empty line to stop) : Devil Dog: The Mound of Hound Enter your rating <0-10>: 1 Enter next movie title (empty line to stop) : Here is the movie list: Movie: Spirited Away Rating: 9 Movie: The Duelists Rating: 8 Movie: Devil Dog: The Mound of Hound Rating: 1 Bye!
2.1.3释放链表
在许多环境中，程序结束时都会自动释放malloc ()分配的内存。但是,最好还是成对调用malloc()
和free()。因此，程序在清理内存时为每个已分配的结构都调用了free()函数:
current = head; while (current != NULL) { current = head; head = current->next; free (current) ; }
