已读96%
预计阅读本页时间：-
预计阅读本页时间：-
A.17 第17章
1．定义数据类型要包括确定如何存储数据以及设计一组函数来管理数据。
2．这个列表只能沿一个方向进行遍历，因为每个结构中包含着下一个结构的地址，但是没有包含前一个结构的地址。可以对结构定义进行修改，使每个结构包含两个指针，一个指向前一个结构，另一个指向下一个结构。当然程序也要在每次添加一个新结构时头这些指针赋予正确的地址值。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
3．一个ADT是一个抽象数据类型，是对一种类型的属性集和可以对这种类型执行的操作的正式定义。ADT应该用通用的语言来表达，而不是用某种特定的计算机语言来表达，它也不应该含有实现细节。
4．直接传递变量的好处：这些函数查看一个列表或队列，但是不能改变它们。直接传递一个列表或队列变量意味着函数对原始值的拷贝进行工作，这可以保证函数不改变原始数据。当直接传递变量时，不需要记住使用地址运算符或指针。
直接传递变量的缺点：程序不得不分配用于存放变量的足够的空间，然后对原始数据的信息进行拷贝。如果变量是一个大型结构，使用这种方法会花费大量的时间和空间。
传递变量地址的好处：传递一个地址，可以更快地访问原始数据；如果变量是一个大型结构，这比直接传递变量需要更少的内存。
传递变量地址的缺点：必须记得使用地址运算符或指针。在K&R C下，函数可能会不小心改变原始数据，但是使用ANSI C的const限定词可以克服这个问题。
5. a．
| 类型名称 | 栈 |
|---|---|
| 类型属性 | 可存放规则的项目序列 |
| 类型操作 | 把栈初始化为空 |
| 确定栈是否为空 | |
| 确定栈是否已满 | |
| 向栈顶添加项目（压入一项） | |
| 从栈顶删除并恢复项目（弹出一项） |
b．下面以数组的形式实现了栈，但是这些信息只影响结构定义和函数定义的细节，而不影响函数原型描述的接口。
6.比较所需的最大次数如下:
| 项 目 | 顺序搜索 | 二叉搜索 |
|---|---|---|
| 3 | 3 | 2 |
| 1023 | 1023 | 10 |
| 65535 | 65535 | 16 |
7．请参见图A.1。
图A.1 单词的二叉搜索树
8．请参见图A.2。
图A.2 删除操作之后单词的二叉搜索树
