`
civili
  • 浏览: 23990 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

数据结构札记

阅读更多
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
分享到:
评论

相关推荐

    数据库的存储结构自学札记.pdf

    数据库存储结构自学札记 数据库存储结构是数据库系统的核心组件之一,决定了数据库的性能和效率。本札记主要涵盖了数据库存储结构的基本概念、逻辑文件中的记录在物理文件中的实现方式、文件组织方式、定长记录格式...

    LabView学习札记

    这些章节可能涵盖了LabView的基础知识,如G语言基础、界面设计、数据处理、控制流与结构以及可能深入到的高级主题,例如并行处理、实时系统应用或者模块化编程等。 在“一”部分,通常会讲解LabView的基本操作,...

    LabVIEW 学习札记 - 第一卷 上

    LabVIEW支持各种基本数据类型,如数值、字符串、布尔值等,还有一系列复杂的数据结构,如数组、簇和队列。理解这些数据类型及其转换方式,对于编写高效且无误的程序至关重要。 此外,控制流和错误处理也是LabVIEW...

    生物信息学札记_第三版_浙大版_2010年.pdf

    本文所提到的《生物信息学札记》第三版,由樊龙江在浙江大学多个研究所和实验室的背景下编写,对生物信息学的学习和研究提供了重要的资料。 本书的结构涵盖了生物信息学的多个重要方面,包括基础理论、分子数据库、...

    生物信息学札记(第三版)

    通过对基因组结构、转录组数据的分析,我们可以预测基因的功能,理解基因调控网络。书中可能介绍了GO(Gene Ontology)注释系统和KEGG(Kyoto Encyclopedia of Genes and Genomes)通路数据库,这些都是广泛使用的...

    生物信息学札记 pdf格式

    《生物信息学札记》与《分子信息学札记》是两本深入探讨生物信息学领域的专业书籍,它们以PDF格式提供,便于读者在线阅读或下载。这些札记全面覆盖了生物信息学的基础理论和实践应用,对于学习和研究这个交叉学科的...

    labview 学习札记3a

    这款强大的工具以其独特的图标和连线编程方式,即数据流编程模型,为工程师和科学家提供了直观的界面。"labview 学习札记3a"显然是一个关于LabVIEW的教程资源,旨在帮助初学者掌握这个平台的基础知识,并通过实际...

    labview论坛-LabVIEW 学习札记 - 第二卷

    学习札记可能详细讲解如何在不同数据类型之间进行转换,并处理不同类型的数据。 3. **VI(Virtual Instrument)设计**:LabVIEW中的每一个程序都是一个VI,由前面板和程序框图两部分组成。你将学习如何设计用户友好...

    labview 学习札记1b

    LabVIEW(Laboratory Virtual Instrument Engineering Workbench)是美国国家仪器公司(National Instruments,简称NI)开发的一款图形化编程环境,专为数据采集、控制和测试测量应用设计。它以其独特的图标和连线...

    mysql学习札记.zip

    这包括了解SQL(结构化查询语言),它是用于管理和操作数据库的语言。SQL的基本操作包括:创建数据库和表,插入、更新和删除数据,以及查询数据。例如,`CREATE DATABASE mydb;`用于创建一个名为`mydb`的新数据库,`...

    LabVIEW学习札记.zip

    这个“LabVIEW学习札记.zip”压缩包显然是一份丰富的学习资源,包含多个方面,旨在帮助用户从基础到深入地理解并掌握LabVIEW的使用。 1. **LabVIEW基础**: - **G语言**:LabVIEW的核心是G语言,一种基于图形的...

    生物信息学札记 第三版 pdf

    这些数据包括但不限于基因组序列、转录组数据、蛋白质结构信息等。 - **生物信息学的概念**:生物信息学是一门跨学科领域,它综合运用计算机科学、信息工程、统计学和生物学的知识和技术,对生物数据进行存储、处理...

    JSP基础札记笔记

    ### JSP基础札记笔记 #### 第一讲:环境的配置 JSP(Java Server Pages)是一种基于Java技术的Web开发技术,用于创建动态网页。为了进行JSP开发,需要搭建相应的开发环境。 - **配置虚拟目录**:首先,需要创建一...

    0-学习札记快速整理软件-小组成员及分工1

    这涉及到算法选择、数据结构优化、减少冗余代码、提高代码执行效率等方面。优化后的代码可以更快地响应用户操作,降低资源消耗,提升用户体验。 市场规模分析和商业计划书是项目可行性研究的一部分。团队需要评估...

    C语言书籍和个人学习札记

    5. **结构体与联合体**:理解这两种数据结构的特性,并能运用在实际编程中。 6. **指针**:C语言的灵魂,掌握指针的运算、指针与数组、指针与函数的关系,以及指针在内存操作中的重要作用。 7. **错误处理**:如何...

    Masm汇编札记Masm汇编札记Masm汇编札记

    Masm汇编语言的语法结构相对简单明了,主要包括指令、伪指令、宏定义等几个方面: 1. **指令**:直接映射到CPU的机器码,用于实现基本的计算、逻辑操作等功能。 2. **伪指令**:由汇编器解释执行的命令,不产生对应...

    JVM学习札记

    3. **初始化JVM**:通过`jvm.dll`初始化JVM环境,这一过程中会创建必要的数据结构和资源。 4. **加载主类**:初始化完成后,JVM会根据命令行参数或其他配置信息加载主类,并寻找该类中的`main`方法。 5. **执行main...

    html 语言 学习札记

    在学习HTML时,了解不同的DTD(Document Type Definition)声明至关重要,因为它们定义了HTML文档的规则和结构。 XHTML 1.0 提供了三种DTD声明: 1. 过渡的(Transitional): 这种类型的DTD允许使用HTML 4.01的标签...

    Simulink代码生成学习札记,simulink代码生成及编译,C,C++源码.zip

    5. **状态机和嵌套结构**:Simulink支持状态机建模,代码生成时会将其转换为相应的C或C++结构。同时,模型中的嵌套子系统也会被转换为嵌套函数或类。 6. **实时和嵌入式系统**:对于实时和嵌入式系统,Simulink提供...

Global site tag (gtag.js) - Google Analytics