高级数据表示

主要内容：

函数:进一步学习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) ;

}

三、抽象数据类型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．**编写代码实现接口。**这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。

再次以上面电影哪个实例来熟悉这个过程

3.1 建立抽象

从根本上看，电影项目所需的是一个项链表。每一项包含电影名和评级。你所需的操作是把新项添加到链表的末尾和显示链表中的内容。我们把需要处理这些需求的抽象类型叫作链表。**链表具有哪些属性?首先，链表应该能储存一系列的项。也就是说，链表能储存多个项，而且这些项以某种方式排列，这样才能描述链表的第1项、第2项或最后一项。其次，链表类型应该提供一些操作，如在链表中添加新项。**下面是链表的一些有用的操作:

• 初始化一个空链表;
• 在链表末尾添加一个新项:确定链表是否为空;
• 确定链表是否已满;
• 确定链表中的项数;
• 访问链表中的每一项执行某些操作，如显示该项。

对该电影项目而言，暂时不需要其他操作。但是一般的链表还应包含以下操作:

• 在链表的任意位置插入一个项;
• 移除链表中的一个项;
• 在链表中检索一个项（不改变链表);
• 用另一个项替换链表中的一个项;在链表中搜索一个项。

非正式但抽象的链表定义是:链表是一个能储存一系列项且可以对其进行所需操作的数据对象。该定义既未说明链表中可以储存什么项，也未指定是用数组、结构还是其他数据形式来储存项，而且并未规定用什么方法来实现操作（如，查找链表中元素的个数)。这些细节都留给实现完成。

3.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()函数把该函数作用于链表中的每一项，显示链表中的内容。

3.3 使用接口

伪代码方案

创建一个List类型的变量。

创建一个Item类型的变量.

初始化链表为空。

当链表未满且有输入时:

把输入读取到Item类型的变量中。

在链表末尾添加项。

访问链表中的每个项并显示它们.

3.4 实现接口

当然，我们还是必须实现List接口。C方法是把函数定义统一放在list.c文件中。然后，整个程序由 list.h(定义数据结构和提供用户接口的原型)、list.c(提供函数代码实现接口）和films3.c(把链表接口应用于特定编程问题的源代码文件）组成。

四、链表和数组

许多编程问题，如创建一个简单链表或队列，都可以用链表(指的是动态分配结构的序列链)或数组来处理。每种形式都有其优缺点，所以要根据具体问题的要求来决定选择哪一种形式。

五、关键概念

一种数据类型通过以下几点来表征:如何构建数据、如何储存数据、有哪些可能的操作。抽象数据类型(ADT)以抽象的方式指定构成某种类型特征的属性和操作。从概念上看，可以分两步把ADT翻译成一种特定的编程语言。第Ⅰ步是定义编程接口。在C中，通过使用头文件定义类型名，并提供与允许的操作相应的函数原型来实现。第2步是实现接口。在C中，可以用源代码文件提供与函数原型相应的函数定义来实现。