第八章 生成数据

第八章 生成数据

这一章是讲如何有效生成数据。
好的数据结构所带来的收益往往是在需求分析和结构设计阶段体现出来的。为了尽可能地利用好的数据结构带来的收益，应在需求分析和结构设计阶段就定义主要数据结构。

8.1 数据识别

有效生成数据的第一步是应该知道该生成什么样的数据结构。

1. 线性表
   1. 数组实现
   2. 链表
2. 栈与队列
3. 树与二叉树
   1. 树
   2. 二叉树基本概念
   3. 二叉查找树
   4. 平衡二叉树
   5. 红黑树
4. 图

8.2 自建数据类型的原因

程序语言所赋予你的阐明自己对程序理解的最强有力的工具之一便是程序员定义的变量类型。它们可以使程序更容易阅读。
建立自己的类型的几条理由：

• 使得改动更加容易。建立一种新类型工作量极小，但这却可以带来极大的使用灵活性。

对于一个浮点数Coordinate_t，你认为可能会用到双精度浮点数，但是在十分确定之前，你只想用单精度浮点数。可以专门定义一种变量。

typedef float Coordinate_t；

现在，假设程序发生了变化，发现最终还是得用双精度变量。由于专门定义了一种类型，因此所要做的就是改变一下类型定义而已。而且只需在一个地方进行改动.

• 为了增加可靠性。

在 Ada 和 Pascal 中，可以定义类似 Age_t = 1~99 的类型。然后，编译程序会产生运行检查信息，以保证 Age_t类型总是在 1~99 的范围内。

• 为了补偿语言的弱点。

C 中不含逻辑类型，通过建立你自己的类型，很容易弥补这个缺点：

typedef int Boolean_t; 

8.3 自建数据类型的准则

建立具有面向功能名称的类型

应避免用暗指计算机本身数据类型的名称,要使用代表实际问题某一部分的名称。

要避免使用含有已定义变量类型的名称

比如像 BigInteger 和 LongString 等指的是计算机数据而不是客观世界中实体的名称就应避免使用。

避免使用已定义类型

如果类型存在变动的可能性，那么除了在 typedef 和 type 定义之外，不要再使用已定义的类型。建立面向功能的类型是非常容易的，而改变程序中该类型的数据是非常困难的。而且，当使用自建的面向功能类型说明变量时，也同时对变量进行了说明。Coordinate_x 所告诉你的关于 x 的信息要比 float x 多得多。因此应尽可能使用自建类型。

不要对已定义类型重新定义

例如，语言中已经有了Integer 类型，而你又自建了叫作 Integer 的类型。程序的阅读者往往会记住你所定义的Integer 的含义，而仍把它当作语言中的标准 Integer 类型。

定义替换类型以增强移植性。

与避免重新定义标准类型的建议相反，你可能想为标准类型定义一种替换类型，从而++使得在不同的硬件环境下变量所代表的都是同一实体++?。例如，你可以定义 INT 类型来代替标准的 int 类型，它们之间的唯一区别便是字母的大小写。但当你把程序移到新的硬件环境下时，你只要重新定义一个 INT 类型，就可以在新的硬件环境下使得数据类型与旧环境下相容。

使用其它类型来建立新类型

可以在已经建立的简单类型的基础上建立复杂类型。这种变量类型可以进一步推广你用原来类型所达到的灵活性。

8.4 使变量说明更容易

使用模板（template）进行变量说明

在一个文件中存储一个变量说明模板。需要说明新的变量时，你可以把这个模板调入程序，对其进行编辑以说明新变量。下面是用 C 写成的一个模板：

extern * *; /* */
static * *; /* */
       * *; /* */ 

extern告诉编译器这个变量或函数在其他文档里已被定义了。

这个模板有几个优点。首先，很容易从中选择出与你要求最接近的行，然后删掉其余各行；第二，每行中“*”的作用是占有位置，这使得进入每行的编辑位置都非常容易；第三，如果你忘记了更改“*”，那么一定会产生语法错误，从而起到了提醒的作用；第四，使用模板可以保持说明形式的一致性；最后，预留的注释空格将提醒你在说明变量时进行注释，这简化了以后的程序注释工作。

隐式说明

有些语言具有隐含变量说明功能。
隐式说明是所有语言特性中的最具危害性的特性之一。

比如说在js代码中的某一行，我想使用的一个已声明的变量x，结果由于打字或者拼写错误，这个变量被写成y了，结果相当于“隐式”声明了一个变量y，这种错误有时比较难以发现。

要求你对变量进行显式说明的语言其主要优点之一，便是可以使你在使用变量时更加谨慎。

8.5 初始化数据的准则

在编程中，最大的错误原因之一便是对数据不恰当的初始化。
下面是如何避免初始化错误的一些准则：

• 检查输入参数的有效性。

在赋给输入参数任何值之前，要首先确认它是合理的。

• 在使用变量的位置附近对其进行初始化

防止改动后忘记初始化

• 要特别注意计数器和累加器

常见的错误是在下次用到它们时，忘记了对其进行清零操作。

• 查找需要重新进行初始化的地方

重新初始化的原因可能是由于变量在循环中被用过多次，也可能是由于变量在对子程序的调用中间要保持原值且需清零。如果需要重新初始化的话，要确保初始化语句是在被重复的代码段中。

• 对命名常量只初始化一次，用可执行代码初始化变量

应在使用变量的位置附近的可执行代码对其进行初始化。

• 按照所说明的对每个变量进行初始化
• 利用编译程序的警告信息
• 设置编译程序使其自动初始化所有变量
• 使用内存存取检查程序来查找无效的指针

在某些操作系统中，操作系统会自动查找无效指针，也可以买一个内存存取检查程序来检查程序中的指针操作。

Coverity代码静态检测工具

1. 列出不会被执行到的代码
2. 列出没被初始化的类成员变量
3. 列出没有被捕获的异常
4. 列出没有给出返回值的return语句
5. 某个函数虽然有返回值，但调用该函数的地方没有用到它的返回值，这也会被列出来
6. 列出没有被回收的new出来的对象
7. 列出没有被关闭的句柄
8. 精确定位到代码行，并提供逐层展开函数的功能
9. 列出可能的数值类型溢出。例如，无符号int数做 ++ 操作，可能导致int溢出，都会被检测到。
10. 什么地方该用&位运算，而不应该用|位运算，都能定位出来并作出建议
11. ostream在一个函数中被修改了格式，但退出该函数之后没有将ostream恢复成先前的格式，也会被检测到
12. .....

• 在程序开始初始化工作内存

小结

• 推荐准备一张全部数据结构的清单，以便用最合适的方法处理每一种问题。
• 建立自己的数据类型，以增加程序的可变动性，并使其成为自说明的。
• 数据初始化很容易产生错误，避免由于未初始值所产生的错误。