您的位置:首页 > 百科大全 |

数据结构

由简单类型的数据构造复合类型数据的方法和表示。把简单的数据类型的数据(如整数、实数和字符)加以组合,构造复合类型的数据(如数组、记录等)。把复合类型的数据再加以组合,可构造更为复杂的复合类型的数据。

1966年,N.沃思和C.A.R.霍尔提出了数据结构的概念。随后,沃思在PASCAL程序设计语言中提出数据类型的构造方法。1972年,霍尔进一步阐述数据结构,并对每种结构进行非形式的描述,讨论了建立数据结构的几类方法。

自从提出数据结构概念以来,70年代所设计的程序设计语言,大多都提供基本数据类型,如整型、逻辑型、实型和字符型,也都提供如何由基本数据类型构造复合数据类型的方法。如PL/1中的“结构型”,PASCAL中的“记录型”等。高级程序设计语言具有这种构造能力,使得这种语言适用范围扩大。像 PASCAL语言就比ALGOL、FORTRAN、COBOL等语言的应用广泛。数据结构的研究,反映了程序设计研究对象的转移。

根据不同的构造方法,可构成不同的数据结构。

(1)数组结构:所有成分都属于同一类型;

(2)记录结构:各成分不一定属于同一类型;

(3)集合结构:它定义的值集合是其基类型的势集,也就是基类型的值域的所有子集的集合;

(4)文卷结构:属于同一类型的各成分的一个序列,这个序列规定各成分的自然次序;

(5)递归数据结构:在数据结构的定义式中出现本身的名的数据结构。

数据结构尚有静态和动态之分。静态数据结构是在整个使用期间,大小始终保持恒定的一种数据结构;而动态数据结构是在整个使用期间,大小是有变化的,如动态数组结构。上述的递归数据结构,也是动态数据结构中经常出现的一种数据结构形式。