数据结构

[拼音]：shuju jiegou

[外文]：data structure

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

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

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

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

（1）数组结构：所有成分都属于同一类型；

（2）记录结构：各成分不一定属于同一类型；

（3）集合结构：它定义的值集合是其基类型的势集，也就是基类型的值域的所有子集的集合；

（4）文卷结构：属于同一类型的各成分的一个序列，这个序列规定各成分的自然次序；

（5）递归数据结构：在数据结构的定义式中出现本身的名的数据结构。

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