Question

既然有释放链表的函数，就需要在用完链表以后调用它。程序只需要显示链表的内容，显示完以后就可以释放它：

display(start);release(start);

写完后你可以测试代码。

试驾

编译代码，运行程序并把文件传给它，看看发生了什么。

程序正确运行了。记住，你无法知道文件有多大。在这个例子中，即使你不把所有数据都保存在存储器中，也能把它们打印出来，但只有把数据放进存储器，才能自由地处理它们。你可以在旅途中添加或删除一些站点，还可以重新调整旅行的顺序，或扩充它。

有了动态分配存储器，就能在运行时创建需要的存储器。使用 malloc() 与 free()，可以访问动态堆存储器。

今夜话题：栈与堆在讨论他们之间的差异

栈 ：堆 ：堆？你在家吗？平时这个时候很少见到你，最近忙啥呢？刚刚从一个函数返回，实在不好意思，最近一直在整理东西……你都做了些什么？代码刚刚退出函数，我需要释放局部变量的空间。你应该活得更简单一点，放轻松……也许你是对的，我能坐下么？要啤酒吗？不用管这个帽子，扔一边就行了。这个东西是你的吗？嘿，你找到了披萨！太好了，我找了它一个礼拜。你应该让别人来帮忙收拾一下这里。不用担心，在线点餐程序把披萨留在了这里，他应该还会回来的。你怎么知道？万一他忘了呢？他重新联络过我，他调用了嗯？你确定？这个程序是写“打兔子”游戏的那个家伙写的么？存储器泄漏得到处都是，满地的兔子结构，我都没法走路了。到处都是垃圾，太可怕了。喂，清理存储器可不是我的责任。有人申请空间，我就给他，我会把空间留在那里，直到他叫我清理它。你这样很不负责任。也许吧，但使用起来很简单，不像你那么瞎折腾。瞎折腾？我从来不瞎折腾！你可能想要一张纸巾……（打嗝）什么？我只是说你很难追踪。你应该更合理地维护存储器。随便，我一向宽以待人。如果程序想把存储器搞得乱七八糟，那也不是我的责任。你真邋遢。是随遇而安。为什么你不做“垃圾收集”？！又来了……一丁点儿整理工作而已，现在你什么也不干！！！放松。（哭）对不起，我受不了了，这里实在是太乱了。嘿，你的鼻子“溢出”了，用这个……（擤鼻涕）谢谢，等一下，这是什么？“打兔子”游戏的排行榜。别担心，我想程序不需要再用它了。free() 。 这里没有蠢问题问：为什么“堆”要叫做“堆”？答：因为计算机不会自动组织它，它只是一大“堆”数据而已。问：什么是“垃圾收集（garbage colloection）”？答：一些语言会跟踪你在堆上分配的数据，当你不再使用这些数据时，就会释放它们。问：为什么 C 语言没有“垃圾收集”？答：C 语言非常古老，发明它的时候，绝大多数语言都没有自动“垃圾回收”机制。问：这个例子中，复制 island 名字的原因我知道，但为什么 open 和 close 的值不需要复制？答：open 和 close 的值都设为了字符串字面值，而字符串字面值无法更新，即便多项数据引用了相同字符串也没关系。问：strdup() 函数实际上会调用 malloc() 函数吗？答：这取决于 C 标准库是如何实现的，不过通常情况下，是这样的。问：我需要在程序结束前释放所有数据吗？答：不必，操作系统会在程序结束时清除所有存储器。不过，你还是应该显式释放你创建的每样东西，这是一种好的习惯。

　

要点

可以用动态数据结构保存可变数量的数据项。

可以很方便地在链表这种数据结构中插入数据项。

在 C 语言中，动态数据结构通常用递归结构来定义。

递归结构中有一个或多个指向相同结构的指针。

栈用来保存局部变量，它由计算机管理。

堆用来保存长期使用的数据，可以用

malloc() 分配堆空间。

sizeof 运算符告诉你一个结构需要多少空间。

数据会一直留在堆上，直到用 free() 释放它。

　你已经学会了用 C 语言创建链表，但链表并不是唯一的数据结构，可能还需要创建其他数据结构。下面是一些其他数据结构的例子，看你能不能把数据结构与使用说明连起来。

　

你已经学会了用 C 语言创建链表，但链表并不是唯一的数据结构，可能还需要创建其他数据结构。下面是一些其他数据结构的例子，你将把数据结构与使用说明连起来。

　数据结构很有用，但要小心使用！当用 C 语言创建这些数据结构时需要非常小心，如果没有记录好保存的数据，就很可能把不用的数据留在堆上。时间一久，它们就开始消耗机器上的存储器，程序也可能因为存储器错误而崩溃。所以，你必须学会如何追查代码中的存储器泄漏，并学会如何修复它们……

最高机密

华盛顿特区美国司法部联邦调查局

发件人：小埃德加·胡佛（局长）

主题：政府专家系统中的可疑泄漏

麻省剑桥市分局报告“可疑人物识别专家系统”（Suspicious Persons Identification Expert System，SPIES）中存在可疑泄漏。据可靠消息和几位精通软件的线人透露，该泄漏是由“临时工”编码造成的，涉案人员未知。

一名曾提供过可靠消息并声称与当事人有着密切关系的线人表示，该漏洞是由存储器中某块区域数据的管理不善所引起的，黑客兄弟会的人把该区域称为“堆”。

现在，我赋予你查看专家系统源代码以及动用 FBI 软件工程实验室所有资源的权力，请考虑种种迹象，仔细地分析案件的每一个细节，找到并修复这个漏洞。

只许成功不许失败。

此致

敬礼！

物证一：源代码

以下是“可疑人物识别专家系统”（SPIES）的源代码。这款软件可以用来记录嫌疑犯，并辨认他们。你不需要现在就细读代码，但请留一份副本，调查的过程中可能会用到它。

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node { char *question; struct node *no; struct node *yes;} node;int yes_no(char *question){ char answer[3]; printf("%s? (y/n): ", question); fgets(answer, 3, stdin); return answer[0] == 'y';}node* create(char *question){ node *n = malloc(sizeof(node)); n->question = strdup(question); n->no = NULL; n->yes = NULL; return n;}void release(node *n){ if (n) { if (n->no) release(n->no); if (n->yes) release(n->yes); if (n->question) free(n->question); free(n); }}int main(){ char question[80]; char suspect[20]; node *start_node = create("Does suspect have a mustache"); start_node->no = create("Loretta Barnsworth"); start_node->yes = create("Vinny the Spoon"); node *current; do { current = start_node; while (1) { if (yes_no(current->question)) { if (current->yes) { current = current->yes; } else { printf("SUSPECT IDENTIFIED\n"); break; } } else if (current->no) { current = current->no; } else { /* Make the yes-node the new suspect name */ printf("Who's the suspect? "); fgets(suspect, 20, stdin); node *yes_node = create(suspect); current->yes = yes_node; /* Make the no-node a copy of this question */ node *no_node = create(current->question); current->no = no_node; /* Then replace this question with the new question */ printf("Give me a question that is TRUE for %s but not for %s? ", suspect, current->question); fgets(question, 80, stdin); current->question = strdup(question); break; } } } while(yes_no("Run again")); release(start_node); return 0;}

SPIES 系统综述

SPIES 程序是一个专家系统，通过学习嫌疑犯的特征，它能够辨认他们。你往系统中输入的人越多，软件也就学得越多，也就越聪明。

程序建立一棵嫌疑犯树

程序用一棵二叉树记录数据。二叉树可以把一条数据与另外两条数据连接在一起，方法如下：

这是程序启动时的数据组成。二叉树中第一项（也叫节点）保存了一个问题：“嫌疑犯有胡子吗？”它与另外两个节点相连：一个代表 yes，另一个代表 no，yes 与 no 节点中分别保存了一个嫌疑犯的名字。

为了辨认嫌疑犯，程序将利用这棵树来向用户提出一系列问题。如果找不到嫌疑犯，程序会要求用户输入这名新嫌疑犯的名字，和一些用于辨认他的信息。程序会把这些信息保存在二叉树中，随着程序学到的东西越来越多，二叉树会渐渐长高。

运行程序看看。

试驾

特工编译了 SPIES 程序，并进行了测试，结果如下：

第一遍运行时，程序未能辨认出嫌疑犯 Hayden Fantucci。但当用户输入了嫌疑犯的详细信息，程序便获取了足够的信息，第二遍运行时就能辨认出 Fantucci 了。

真聪明。有问题吗？

有人在实验室中连续用了这个系统几个小时，他注意到，尽管程序看起来运行正确，但却多用了一倍存储器。

所以我们把你请来。源代码深处藏着一段代码，它在堆上分配存储器，但从不释放。你可以搬个椅子坐下来，然后通读所有代码，并祈祷能发现问题所在。通常情况下，很难发现存储器泄漏。

也许你应该跑一趟软件实验室……