数据结构札记

II. 数据结构札记

C.A.R.霍尔

　　　　　　　　　　　　　　　　　　1.引论

　　人类在认识复杂现象的过程中所使用的最有力的思维工具是抽象。人们认识到，在现实世界中，一定的事物、状态或过程之间存在着某些相似的方面。把这些相似方面集中概括起来，暂时忽略它们之间的差异，这就是抽象。一旦发现那些对预测和控制事件发展有影响的相似方面之后，我们就把这些相似方面看成是基本的，而把差异方面看成是次要的。这样就可以说，我们已经建立起了某种抽象概念来概括我们所论述的事物或状态。在此阶段，我们通常要用一个词或一个图象来象征这个抽象概念。尔后，这个词或图象在任何口头或书面的特定场合都可以用来“表示”相应状态的个别或一般的情况。

　　“表示”主要是用来把现实世界的某些重要的信息传递给别人，并用书面形式将这些信息记录下来，一方面是帮助人们的记忆，另一方面是传给后代。然而，在原始社会里，人们曾相信“表示”本身有时也是有用的，因为曾认为对“表示”的处理本身就会引起现实世界的相应变化。所以，我们听到这样的事情：把针刺入模拟敌人的蜡制模型里，能引起真正敌人相应部分的疼痛。这种活动无疑是一种魔术和妖巫的行为。但是，现代科学相信，对“表示”的处理，虽不能引起事件的变化，却可用来预期现实世界里事件的发生及其变化的结果。例如，通过对某些函数和方程式的符号表示的处理，人们可以预期落体着陆的速度。虽然人们知道，这种处理本身既不会引起物体下落，也不会减慢最后的冲击。

　　抽象过程的最后阶段是极其复杂的；它力图通过扼要有力的公理来综合和抽象有关事物和状态的最一般性质，并力图精确地证明（在这些公理正确地反映现实世界的条件下）：对“表示”的处理所得的结果也可以成功地应用于现实世界。例如，欧几里德几何公理正是相当准确地反映了现实世界和度量世界，因而保证了几何结构和定理在土地丈量和地球表面测量上实际应用的正确性。

　　于是，抽象过程可以总结为四个阶段：

　　(1) 抽象：集中和概括现实世界中一定事物或状态的共性，忽略它们之间的差异。

　　(2) 表示：选择一组符号代表某一抽象；可用作通讯手段。

　　(3) 处理：符号表示的转换规则，作为预期现实世界中类似的处理所产生的效果的手段。

　　(4) 公理化：对从现实世界中抽象出来的那些共性进行严格的陈述，这些性质是现实世界处理和符号（表示现实世界）处理所共有的。　

1.1. 数和数字

　　让我们用一个比较具体的例子——数"4"，来说明数这个相当抽象的描述。人们注意到，在现实世界中，事物可以按类来组合，例如，四个苹果。这就已经有了一定程度的抽象了，即忽略了各苹果之间的差异，例如，其中可能有一个是坏的，两个未熟，而第四个可能给鸟吃掉了一部分。

    于是，人们可以考虑具有四个项目的种种不同的组合，例如，四个桔子，四只梨，四只香蕉等等。如果我们忽略这些组合之间的差别，集中它们的相似性，那末，我们就能形成一个相对抽象的概念——数"4"。相同的过程可以得到数3，15的概念，如此等等。而进一步的抽象将使我们建立起自然数的概念。

    现在，我们来谈谈这个概念的表示问题，例如，将数画在羊皮纸上或刻在石头上。一个数的表示称为一个数字。古罗马数字显然是象形的，4就用刻在石头上的四个竖道来表示，即IIII。另一个更方便的表示是IV。阿拉伯（十进）表示就不太形象，但仍然容许某种选择：4和04（乃至004等等）均被认为是有效的数字，它们都表示同一个数。

    其次，我们来研究电子计算机表示数的一种十分方便的办法。这里，数“4”是由一组铁      氧磁心的不同磁化方向表示的，在宽行的纸面上，这些不同的磁化方向表示为一串零么序列，即对所处理的数用二进制表示。

    数字处理的一个简单例子是相加，它可用来预期现实世界中两个由某种对象组成的集合体连合的结果。对于罗马数字来说，加法规则是简单明了的，应用起来也很简单。





1.2 抽象和计算机程序设计

    抽象的过程是数学应用于现实世界的基础。我相信，这个过程也正是计算机应用于现实世界的基础。设计一个程序，　


                           2. 类型概念






                         3.非结构数据类型







                         4.笛卡尔积

                         5.分歧和
                         6.数组
                         7.幂集
                         8.序列
                         9.递归数据结构
                         10.稀疏数据结构
                         11.例子:排考表
                         12.公理化

                         参考文献
[1] E.W.Dijkstra, (1972). Notes on Structured Programming.
"Structured Programming". pp.1-82. Academic Press, London
[2] D.E.Knuth, (1968). "The Art of Computer Programming"
Vol.1, Chapter 2.Addison-Wesley, Reading, Mass.
[3] J.McCarthy, (1963). "A Basis for a Mathemetical Theory of Computation in Computer Programming and Formal Systems"(eds.Braffort,P.&Hirschberg D.).North-Holland Publishing Company, Amsterdam.
[4] G.H.Mealy, (1967). Another look at Data.A.F.I.P.S.Fall Joint Computer Conference Proceedings.31.pp.525-534.
[5] N.Wirth, (1970). Programming and Programming Languages. Contribution to Conference of European Chapter of A.C.M, Bonn.
[6] N.Wirth, (1971). Program Development by Stepwise Refinement. Comm.A.C.M. 14,4, pp.221-227.
[7] N.Wirth, (1971). The Programming Language PASCAL. Acta Informatica, 1,1,pp.35-63.












本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/civili/archive/2007/12/19/1953748.aspx