一、抽象数据类型ADT
什么是类型?类型特指两类信息:属性和操作。例如， int类型的属性是它代表一个整数值，因此它共享整数的属性。允许对int类型进行算术操作是:改变int类型值的符号、两个int类型值相加、相减、相乘、相除、求模。当声明一个int类型的变量时，就表明了只能对该变量进行这些操作。
注意整数属性 C的int类型背后是一个更抽象的整数概念。数学家已经用正式的抽象方式定义了整数的属性。例如，假设N和M是整数，那么N+M=M+N;假设S、Q也是整数，如果N+M=S，而且N+Q=S，那么M=Q。可以认为数学家提供了整数的抽象概念，而C则实现了这一抽象概念。注意，实现整数的算术运算是表示整数必不可少的部分。如果只是储存值，并未在算术表达式中使用，int 类型就没那么有用了。还要注意的是，C并未很好地实现整数。例如，整数是无穷大的数，但是2字节的int类型只能表示65536个整数。因此，不要混淆抽象概念和具体的实现。
计算机科学领域已开发了一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程。 1．**提供类型属性和相关操作的抽象描述。**这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型(ADT)。 2．**开发一个实现ADT的编程接口。**也就是说，指明如何储存数据和执行所需操作的函数。例如在C中，可以提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于作用于C基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程。 3．**编写代码实现接口。**这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。
再次以上面电影哪个实例来熟悉这个过程
1.1 建立抽象
从根本上看，电影项目所需的是一个项链表。每一项包含电影名和评级。你所需的操作是把新项添加到链表的末尾和显示链表中的内容。我们把需要处理这些需求的抽象类型叫作链表。**链表具有哪些属性?首先，链表应该能储存一系列的项。也就是说，链表能储存多个项，而且这些项以某种方式排列，这样才能描述链表的第1项、第2项或最后一项。其次，链表类型应该提供一些操作，如在链表中添加新项。**下面是链表的一些有用的操作:
- 初始化一个空链表;
- 在链表末尾添加一个新项:确定链表是否为空;
- 确定链表是否已满;
- 确定链表中的项数;
- 访问链表中的每一项执行某些操作，如显示该项。
对该电影项目而言，暂时不需要其他操作。但是一般的链表还应包含以下操作:
- 在链表的任意位置插入一个项;
- 移除链表中的一个项;
- 在链表中检索一个项（不改变链表);
- 用另一个项替换链表中的一个项;在链表中搜索一个项。
非正式但抽象的链表定义是:链表是一个能储存一系列项且可以对其进行所需操作的数据对象。该定义既未说明链表中可以储存什么项，也未指定是用数组、结构还是其他数据形式来储存项，而且并未规定用什么方法来实现操作（如，查找链表中元素的个数)。这些细节都留给实现完成。
1.2 建立接口
这个简单链表的接口有两个部分。第1部分是描述如何表示数据，第2部分是描述实现ADT操作的函数。例如，要设计在链表中添加项的函数和报告链表中项数的函数。接口设计应尽量与ADT的描述保持一致。因此,应该用某种通用的Item类型而不是一些特殊类型,如int或struct film。可以用C的typedef功能来定义所需的Item类型
#include <stdio.h> #define TSIZE 45 struct film { char title[TSIZE]; int rating; }; typedef struct film Item; //把film结构重命名为Item
定义了Item之后，现在必须确定如何储存这种类型的项。实际上这一步属于实现步骤，但是现在决定好可以让示例更简单些。在开始的程序中用链接的结构处理得很好，所以，我们在这里也采用相同的方法:
typedeof struct node { Item item; struct node * next; }Node; typedef Node * List;
**在链表的实现中，每一个链节叫作节点(node)。每个节点包含形成链表内容的信息和指向下一个节点的指针。**为了强调这个术语，我们把node 作为节点结构的标记名,并使用typedef把 Node作为struct node结构的类型名。**最后,为了管理链表,还需要一个指向链表开始处的指针,我们使用typedef把List作为该类型的指针名。**因此，下面的声明: List movies;
创建了该链表所需类型的指针movies。
这是否是定义List类型的唯一方法?不是。例如，还可以添加一个变量记录项数:
typedef struct list { Node * head;//指向链表头的指针 int size;//链表中的项数 }List;//List的另一种定义
可以像稍后的程序示例中那样，添加第2个指针储存链表的末尾。现在，我们还是使用List 类型的第1种定义。这里要着重理解下面的声明创建了一个链表，而不一个指向节点的指针或一个结构: List movies; movies代表的确切数据应该是接口层次不可见的实现细节。 例如，程序启动后应把头指针初始化为NULL。但是，不要使用下面这样的代码:
movies = NULL;
为什么?因为稍后你会发现List类型的结构实现更好，所以应这样初始 化:
movies.next = NULL; movies.size = 0 ;
使用List的人都不用担心这些细节，只要能使用下面的代码就行:
InitializeList (movies) ;
使用该类型的程序员只需知道用InitializeList()函数来初始化链表,不必了解List类型变量的实现细节。这是数据隐藏的一个示例，数据隐藏是一种从编程的更高层次隐藏数据表示细节的艺术。
这书写的太详细了，不敢错过哪一个细节
为了指导用户使用，可以在函数原型前面提供以下注释:
操作:初始化一个链表 前提条件:plist指向一个链表 后置条件:该链表初始化为空 void InitializeList (List * plist) ;
这里要注意3点。
第1，注释中的“前提条件”( precondition）是调用该函数前应具备的条件。例如,需要一个待初始化的链表。
第2，注释中的“后置条件”( postcondition）是执行完该函数后的情况。
第3，该函数的参数是一个指向链表的指针，而不是一个链表。所以应该这样调用该函数:InitializeList ( &movies ) ;
几个重要的函数
只有InitializeList ()、AddItem ()和 EmptyTheList ()函数要修改链表，因此从技术角度看，这些函数需要一个指针参数。然而，如果某些函数接受List类型的变量作为参数，而其他函数却接受 List类型的地址作为参数，用户会很困惑。因此，为了减轻用户的负担，所有的函数均使用指针参数。
参数pfun是一个指向函数的指针，它指向的函数接受item值且无返回值。第14章中介绍过，**可以把函数指针作为参数传递给另一个函数，然后该函数就可以使用这个被指针指向的函数。**例如，该例中可以让 pfun 指向显示链表项的函数。然后把Traverse ()函数把该函数作用于链表中的每一项，显示链表中的内容。
实例
//简单链表类型的头文件 #ifndef LIST_H_ #define LIST_H_ #include <stdbool.h> //C99特性 //特定程序的声明 #define TSIZE 45; struct film { char title[TSIZE]; int rating; }; //一般类型定义 typedef struct film Item; typedeof struct node { Item item; struct node * next; }Node; typedef Node * List; //函数原型 /* 操作:初始化一个链表 前提条件:plist指向一个链表 后置条件:链表初始化为空 */ void InitializeList(List * plist); /* 操作:确定链表是否为空定义，plist指向一个已初始化的链表 后置条件:如果链表为空，该函数返回true;否则返回false */ bool ListIsEmpty(const List *plist); /* 操作:确定链表是否已满，plist指向一个已初始化的链表 后置条件:如果链表已满，该函数返回真;否则返回假 */ bool ListIsFull(const List *plist); /* 操作:确定链表中的项数，plist指向一个已初始化的链表 后置条件:该函数返回链表中的项数 */ unsigned int ListItemCount(const List *plist); /* 操作:在链表的末尾添加项 前提条件:item是一个待添加至链表的项，plist指向一个已初始化的链表 后置条件:如果可以，该函数在链表末尾添加一个项，且返回true;否则返回false */ bool AddItem(Item item,List *plist); /* 操作: 把函数作用于链表中的每一项 plist指向一个已初始化的链表 pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值 后置条件:pfun指向的函数作用于链表中的每一项一次 */ void Traverse(const List *plist,void(*pfun)(Item item)); /* 操作: 释放已分配的内存（如果有的话) plist指向一个已初始化的链表 后置条件:释放了为链表分配的所有内存，链表设置为空 */ void EmptyTheList(List * plist); #endif
只有InitializeList ()、AddItem ()和EmptyTheList ()函数要修改链表，因此从技术角度看，这些函数需要一个指针参数。然而，如果某些函数接受List类型的变量作为参数，而其他函数却接受List类型的地址作为参数，用户会很困惑。因此，为了减轻用户的负担，所有的函数均使用指针参数。
/* 操作: 把函数作用于链表中的每一项 plist指向一个已初始化的链表 pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值/* 操作: 把函数作用于链表中的每一项 plist指向一个已初始化的链表 pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值 后置条件:pfun指向的函数作用于链表中的每一项一次 */ void Traverse(const List *plist,void(*pfun)(Item item));
**参数 pfun是一个指向函数的指针，它指向的函数接受item值且无返回值。**前面介绍过，可以把函数指针作为参数传递给另一个函数，然后该函数就可以使用这个被指针指向的函数。例如，该例中可以让pfun 指向显示链表项的函数。然后把Traverse()函数把该函数作用于链表中的每一项，显示链表中的内容。
1.3 使用接口
伪代码方案
创建一个List类型的变量。
创建一个Item类型的变量.
初始化链表为空。
当链表未满且有输入时:
把输入读取到Item类型的变量中。
在链表末尾添加项。
访问链表中的每个项并显示它们.
1.4 实现接口
当然，我们还是必须实现List接口。C方法是把函数定义统一放在list.c文件中。然后，整个程序由 list.h(定义数据结构和提供用户接口的原型)、list.c(提供函数代码实现接口）和films3.c(把链表接口应用于特定编程问题的源代码文件）组成。
二、链表和数组
许多编程问题，如创建一个简单链表或队列，都可以用链表(指的是动态分配结构的序列链)或数组来处理。每种形式都有其优缺点，所以要根据具体问题的要求来决定选择哪一种形式。
三、关键概念
一种数据类型通过以下几点来表征:如何构建数据、如何储存数据、有哪些可能的操作。抽象数据类型(ADT)以抽象的方式指定构成某种类型特征的属性和操作。从概念上看，可以分两步把ADT翻译成一种特定的编程语言。第Ⅰ步是定义编程接口。在C中，通过使用头文件定义类型名，并提供与允许的操作相应的函数原型来实现。第2步是实现接口。在C中，可以用源代码文件提供与函数原型相应的函数定义来实现。
