Before defining the specifics of data types and data structures，let us first define a term that will be used throughout this text．A data value is a piece of data [1] that we can consider，perhaps only momentarily，as a single entity．We might consider，for example，the integer value 593 as a single data value． The set｛32．99，一1．04，0．395｝ might be considered in its entirety a single data value． It might also be considered to be composed of three distinct component values that are somehow related．In this case，their relationships to each other are that they are members of the same set． If we decompose a data value as we have done with the set value，we need term for the pieces that result．Each piece is a value of another data type in this case real． We will call these component values component elements，or simply elements． If a data value can be decomposed into component parts，we call each part a component element． An atomic data value is a piece of data that we choose to consider as a single，nondecomposable entity．For example，the integer 62 953 may be considered as a single integer value stored on this sheet of paper．We can decompose it if we wish to do so．The integer 62 953（see Fig．4-1）could be seen as a collection of digits stored on the page in a left-to-right order．Each digit一6，2，9，5，and 3一could either be considered to be atomic or be viewed as collections of dots of ink（suppose we are using a dot-matrix printer[2]）． If we choose to consider 62 953 as a single，nondecomposable entity，we may do so． If we wish to decompose it in any of a number of ways，we may do so．The decision to decompose is strictly at our discretion． What is a data type? The essence of a type is that it attempts to identify qualities common to a group of individuals or objects that distinguish it as an identifia-ble class or Kind．[3] If we rovide a set of possible data values and a set of operations that act on the values，we can think of the combination as a data type（see Fig．4-2）． Let us look at two classes of data types．We will call any data type whose values we choose to consider atomic an atomic data type．Often，we choose to consider integers to be atomic．We are then only concerned with the single quantity that a value represents，not with the fact that an integer is a set of digits in some number system．Integer is a common atomic data type found in most programming languages and in most computer architectures． We will call any data type whose values are composed of component elements that are related by some structure a structured data type，or data structure．In other words，the values of these data types are decomposable，and we must therefore be aware of their internal construction．There are two essential ingredients to any object that can be decomposed-it must have component elements and it must have structure，the rules for relating or fitting the elements together [4]． A data structure is a data type whose values are composed of component elements that are related by some structure．Since a data structure is a data type，it has a set of operations on its values．In addition，there may be operations that act on its component elements． The operations of a structured data type might not only act on the values of the data type，they might also act on component elements of the data structure．Let us look at an example（see Fig. 4-3）． Suppose that we have a data type called sample．Type sample：= array［1．．3］of real；Individual values of this data type are made up of three real numbers arranged linearly．Each set of three real numbers together with its order of arrangement is considered to be a single data value of the type sample．We can treat sample as a structured data type by considering each of the real numbers as a component element．We will specify a structure for each element of sample by prescribing each component element to be the first，second，or third．One way to show this structure is by appending the appriate integer（or index）to each component． Some values of the structured type sample are given in Fig．4-4，with the relationship between component elements-the structure-shown using appended indexes． It is important to note that each value of a data structure has an associated structure．The two values of the type sample shown in Fig. 4-5 are different even though their component elements（0．0，1．9 and 3．4）are the same．Only the structure（relationship among the elements）is different． Let us consider an operation for the data type．Suppose that we have three variables of type sample and that the addition operator“＋”is defined in accordance with the illustration in Fig. 4-6．The element values in corresponding positions are added． The operator“ ”operates on a pair of values of data type sample and produces a value of the same type（see Fig．4-6）． A second kind of operator is one that acts on component data elements instead of on the entire composite value．For example，languages that provide for the array data type also provide an operator that allows the user to read out the value of an array element．Let sample be implemented as a Pascal array．The assignment statement x：＝a[2] retrieves the value of the element that is associated with the index value 2 and subsequently moves it by the assignment operator“：=”into the real variable x．At first it might not be apparent that indexing on the right side of an assignment statement is such an operator [5]．Indexing on the left side of an assignment statement is a different operator that can be thought of as an update or change the value operation-a [2]：＝x． Thus we see that a structured data type can have operations defined on its composite values，as well as on the component elements of those values．Fig. 4-7 distinguishes between two classes of data types． 在定义数据类型和数据结构的细节之前，首先定义一个贯穿使用于本文的术语。 数据值是一个可以作为单个实体来考虑的一个数据，虽然这种考虑也许只是暂时的。例如，可以把整数593作为单个数据值。 集合｛32. 99，-1. 04，0. 395 }可整个地视为一个数据值，也可以认为它由3个以某种方式相关的不同组成部分的值所组成。在这种情况下，它们相互之间的关系就是它们都是同一集合的成员。如果像分解一个集合值一样分解一个数据值，那么需要一个术语来说明由此而产生的若干数据段。每一个数据段就成为另一种数据类型的值（在上述情况下就是实型），我们称这些组成成分的值为组成元素，或简称为元素。 如果一个数据值能分解成各个组成部分，我们称每部分为一个组成元素。 一个原子数据类型的值是一个数据段，可以认为它是单一的，不可分解的实体。例如，整数62 953就可以看成是表示储存在这一页上的单个整数值。如果希望分解它，就可以这样做。整数62 953（见图4-1）可以看成是一个储存在本页上，由一组按从左到右排列的数字汇集，每位数字（6、2、9、5和3）既可以看成是原子，也可以看成墨点汇集（假设我们使用点阵打印机）。 如果想把62 953视为单个不可分解的实体，我们这样做是可以的；如果希望用多个方法中的任意一个方法去分解62 953也可以这样做，分解与否完全按自己的愿望处理。 什么是数据类型？类型的本质在于它试图标识一组个体或对象所共有的特性，这些特性使得该组成为可识别的类。如果提供了一组可能的数据值及作用在这些值上的一组操作，那么，这两者结合在一起就称之为数据类型（见图4-2）。 下面来看两种数据类型，我们称任何选作原子的值构成的数据类型为原子数据类型。通常我们倾向于把整数视为原子。那么．我们关心的仅仅是一个值所代表的单个量，而不是把整数看成是一个在某一数制中的数位的集合。在多数程序设计语言和计算机体系结构中，整数型是一个常用的原子数据类型。 其值由组成元素组成，且这些组成元素通过某种结构而彼此相关的数据类型我们称之为结构化数据类型或数据结构。换句话说，这些数据类型的值是可分解的，因此必须知道它的内部构成。任何可分解的对象都必须有两个基本的组成成分－－组成元素与结构（即将这些元素相互关联或适配的规则）。 数据结构是一种数据类型，其值是由通过某种结构而相互关联的组成元素所构成的。由于数据结构是一种数据类型，因此，它有一组在其值上的操作。此外，可有一些操作是针对其组成元素的。 结构化的数据类型的操作不仅可以针对数据类型的值，并且可以针对数据结构的组成元素。让我们看一个例子（见图4-3）。 假设有一个数据类型叫sample，类型sample：＝array[1，…，3]（实型），此数据类型的单个值由3个线性排列的实数组成。我们把每3个实数组成的组及其排列次序看成是类型sample的单个数据值。把每一个实数看作一组成元素，就可以把sample看作结构化数据类型。可以通过规定哪一个组成元素是第一、第二、第三来为每一个sample元素定义一个结构。说明此数据结构的一种方法是给每一个组成元素附加适当的整数（下标）。 图4-4给出了结构化类型sample的一些值，其中组成元素间的关系（即结构）由附加下标表示。 数据结构的每一个值有一个相关的结构，注意到这一点是很重要的。尽管它们的组成元素（0．0，1. 9和3. 4）是一样的，但图4-5表示的sample类型是两个不同的值，只是其结构（元素之间的关系）不同。 下面考虑对sample数据类型的一种操作。假设sample类型有3个变量和与图4-6中相一致的加法操作符“十”，对应位置上的元素值进行相加操作。 操作符“ ”针对一对sample数据类型的值进行操作，并且产生一个同样类型的值（如图4-6所示）。 第二类操作符针对组成数据元素而非整个复合值的一种操作。例如，提供数组数据类型的（程序设计）语言也提供一种操作符，使用户能读出数组元素值。假设sample是用Pascal数组来实现的。赋值语句x：= a[2]首先检索下标值为2的元素值，然后通过赋值操作符“：=”把其值送到实变量“x”中。如果加下标的形式在一个赋值语句的右边，那么此操作符就是第二类操作符，对于这一点也许开始时并不明显。如果加下标的形式在赋值语句的左边，那么这又是另一种操作符，可以把这种操作符看成为更新或改变值的操作符，即a[2]：=x。 由此我们知道结构化数据类型可以有定义在其构成值之上的操作，也有定义在这些值的组成元素之上的操作。图4-7说明了两类数据类型的区别。 By 5ai9.com-->