3.7　算法和数据结构初窥

3.7　算法和数据结构初窥

1976年，著名的计算机大师、Pascal语言之父Niklaus Wirth提出：

算法+数据结构=程序（Algorithms+Data Structures=Programs）

这个揭示了程序本质的公式使得他在1984年获得了计算机科学界的最高奖——图灵奖。他是唯一一个“凭借一句话获得图灵奖”的人物。他的这种深刻的对程序本质的洞见，使得后来对大师的这个公式的任何修正企图，都显得如狗尾续貂般的可笑。

那么，究竟什么是算法，什么又是数据结构？实际上离开了数据类型，就根本谈不上数据结构，而离开了数据结构，算法只能算做是一种乌托邦式的幻想。希望读者通过下面的例子自己总结归纳出什么是算法、什么是数据结构，你心中得到的答案就是标准答案。

例题：编程求123456×654321。

程序代码3-6

3.7　算法和数据结构初窥 - 图1

很多初学者会写出类似程序代码3-6那样的代码，然而令人遗憾的是，它的输出竟然是：

3.7　算法和数据结构初窥 - 图2

结果明显是错的。这不是一件坏事，而是一件非常幸运的事情。更坏的情况是，如果输出的结果是835224192的话，相信很多人就会误以为自己做对了而轻易地放过了这个错误。

经验表明，这种莫名其妙的负数通常是由于溢出。下面分析溢出的原因。

由于123456≈1×10⁵，654321≈6×10⁵，所以123456×654321≈6×10¹⁰。然而由于int类型是32bits，每个bit有取值0或1两种可能，所以一共能表示2³²个数。由于int表示的是0附近的正整数和负整数，且正数和负数大体各占一半，所以能表示的最大正数应该近似地等于2³¹==2×2³⁰==2×2¹⁰×2¹⁰×2¹⁰=2×10²⁴×10²⁴×10²⁴≈2×10⁹。这虽然是一个十位数，但它明显小于6×10¹⁰。这样会发生溢出就很显然了。而程序代码3-6，很明显只注意到了123456和654321可以表示成int类型，但却没有注意到它们的积不可能表示成int类型值，因而它们的乘法运算没有意义。因为C语言要求两个int量做乘法运算时结果必须也能用int类型表示，否则就是未定义的行为。

所以编程始终需要清醒，对数据类型的清醒是最起码的要求。否则像程序代码3-6那样写代码，得到错误的结果几乎是必然的。当然，瞎猫碰到死耗子的情况也有。

难道C语言对待如此简单的小学生都会做的算术问题都束手无策吗？倒也不是这样，办法是有的，但需要你自己去想。编程的乐趣大抵在此。

由于本题目问题的核心在于两个较大的数相乘超过了it类型的范围，所以可以考虑把乘数拆成较小的数。比如：

3.7　算法和数据结构初窥 - 图3

如果能分别求出（123×654）、（123×321+456×654）、456×321，问题不就解决了吗？而（123×654）、（123×321+456×654）、456×321，可以确信，是可以用int类型表示的。

在这种情况下，用一个int变量存储123456或654321是不行的，需要两个，一个用来记录123456或654321的前3位，另一个记录后3位。这种对数据的组织和安排方式，就是所谓的数据结构。尽管这里的还只是一种很粗糙的数据结构。此外还可以发现，设计数据结构首先涉及到的问题恰恰是选择合适的数据类型。

在这种数据结构下的算法就是：首先求出（123×654）、（123×321+456×654）、456×321。可以断定积的最后3位是456×321对1000求余的结果，最前面几位是（123×654）+（123×321+456×654）/10⁽³⁾，中间3位的值为（123×321+456×654）%10⁽³⁾+456×321/1000（这些示意性的东西叫伪代码（Pseudocode））。

从对算法的描述中还可以发现，积最好用3个int来表示。

所以，所谓的算法无非就是对操作步骤的描述。描述算法的方式有很多，其中之一就是使用自然语言来描述。用C语言描述的算法和数据结构就是C代码。

程序代码3-7

3.7　算法和数据结构初窥 - 图4