数据结构发展史
祁隆的全部歌曲-
数据结构发展史
张抒菲
12
一、数据结构起源于程序设计
随着计算机科学与技术的不断发展，
计算机的应用领域已不再局
限于科学计算，
而更多地应用于控制、管理等非数值处理领域。
与此
相应，计算机处理的数据也由纯粹的数值发展到字符、表格
、图形、
图象、声音等具有一定结构的数据，
处理的数据量也越
来越大，
这就
给程序设计带来一个问题：
应如何组织待处理的数据以及数据之间的
关系（结构）。
1968
年克努思教授
[1]
开创了数据结构的最初体系，他所著的
《计
算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述
数据的逻辑结构和存储结
构及其操作的著作。
70
年代初，
数据结构
作为一门独立的课程开始进入大学课堂。
数据结构在计算机科学界至今没有标准的定义。
个人根据各自的
理解的不同而有不同的表述方法。
例的数据元素之间的各种联系。
这
些联系可以通过定
义相关的
函数
来给出。
”
他将数据对象
（
data object
）
定义为“一个数据对象是实例或值的集合”。
数据结构在
计算机科
学
界至今没有标准的定义。
个人根据各自的理解的不同而有不同的表
述方法：
Sartaj
Sahni
在他的《数据结构、算法与应用》一书中称：“数据
结构是
数据对象
，以及存在于该对象的
实例
和组成实
Clifford r
在《
数据结构与算法分析
》一书中的定义是：
“数据结构是
ADT
（
抽象数据类型
Abstract Data
Type
）
的物理实
现。”
Lobert
在
< br>《数据结构与程序设计》一书中，将一个数据结
构的设计过程分成抽象层、数据结
构层和实现层。
其中，
抽象层是指
抽象
数据类型层，
它讨论数据的
逻辑结构
及
其运算，
数据结构层和实
现层讨论一个数据结构的表示和在计算
机内的存储细节以及运算的
实现。
数据结构是指同一数据元素类中各数据元素之间存在的关系。
数
据结构分别为逻辑结构、存储结构（
物理结构
）和数据的运算。
数
据的逻辑结构是对数据之间关系的描述，
有时就把逻辑结构简
称为数
据结构。逻辑结构形式地定义为（
K
，
R
）（或（
D
< br>，
S
）），其中，
K
是数据元素的有限集，
R
是
K
上的关系的有限集。
数据元素相互之间的关系称为结构
。
有四类基本结构：
集合、
线性结构<
/p>
、
树形结构
、图状结构（网状结构）。树
形结构和
图形结构
全称为非线性结构。集合结构中的数据元素除
了同属于一种类型外，
别无其它关系。
线性结构中元素之间存在
一对一关系，
树形结构中元
素之间存在一对多关系，
图形结构中元素之间存在多对多关系。
在图
形结构
中每个结点的前驱结点数和后续结点数可以任意多个。
数据结构在计算机中的表示
（映像）
称为数据的物理
（存储）
结构。
它包括数据元素的表示和关系的表示。
数据
元素之间的关系有
两种不同的表示方法：
顺序映象和非顺序映象
，
并由此得到两种不同
的存储结构：顺序存储结构和
链式存储结构
。顺序存储方法：它是把
逻辑上相邻
的结点存储在物理位臵相邻的
存储单元
里，
结点间的逻辑
关系由存储单元的邻接关系来体现，
由此得到
的存储表示称为顺序存
储结构。
顺序存储结构是一种最基本的存
储表示方法，
通常借助于程
序设计语言中的数组来实现。
链接存储方法：
它不要求逻辑上相邻的
结点在
物理位臵上亦相邻，
结点间的逻辑关系是由附加的
指针
字段表
示的。
由此得到的存储表示称为链式存储
结构，
链式存储结构通常借
助于程序设计语言中的指针类型来实
现。
索引
存储方法：
除建立存储
结点信息外，
还建立附加的索引表来标识结点的
地址
。
散列存储方法
：
就是根据结点的关键字直接计算出该结点的存储地址。
数据结
构中，
逻辑上
（逻辑结构：
数据元素之
间的逻辑关系）
可以把数据结构分成线性结构和非线性结构。
线
性结构的顺序存储结
构是一种
随机存取
的存储结构，
线性表
的链式存储结构是一种顺序存
取的存储结构。
线性表若采用链式存储表示时所有结点之间的存储单
元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相
对位
臵、所含结点个数都无关。
自从美国唐〃欧〃克努特教授用汇
编语言编写的《计算机程序设
计技巧》第一卷《基本算法》问世以来，已经出现了用
Pascal
、
Java
< br>、
C
、
C++
< br>、
C#
等语言编写的数据结构方面的书。总体说来，这些
语言
基本上分为面向过程的语言和面向对象的语言两大类，
也出
现过采用
两种语言描述数据结构的书籍，如
C
< br>和
C++
语言描述，但作者实际
上是按照
C++
语言描述。同时采用面向过程和面向对象语言描
述数
据结构，
目前国内基本上是空白。对于同一种数据结构与算
法，
同时
采用面向过程和面向对象语言进行描述，
可以从中更深刻理解这两种
思想的不同，这对于深刻理解计算机语言和思想有
着重要的作用。
C
语言是现在最流行的面向过程的语言，在业界
使用非常广泛。而
C#
语言作为微软在新一代开发平台
(.NET)
上推出的、
完全面向对象的语
言，凭着其简洁、高效、模板、标准化的特性，使得
C#
语言像程序
设计语言中的一件艺术品，
也吸引着越
来越多的开发人员。
当然，
C#
语言也
吸收了
C
语言的一些东西，如语法等，所以，在有些方面，
C#
与
C
是相似的
。
二、数据结构随着程序设计的发展而发展
< br>。
程序设计经历了三个阶段：
无结构阶段、
结构化阶段和面向对象阶段，
相应地，数据结构的
发展也经历了三个阶段：