使用 C 和 C++ 的编程语言概念/数据级结构

在本章中，我们将首先定义在编程环境中可用的所有数据项的通用属性，然后根据其结构和类型对数据进行分类。在这样做的过程中，我们还将尝试了解它们如何在内存中布局。

一般属性

可变性

不可变数据

常量是在其整个生命周期内保持不变的数据项。常量可以按字面使用，也可以命名。命名的常量有时被称为符号常量或形象常量。

字面常量和命名常量。
3、'5'、.TRUE.、"String literal" 是字面常量的示例，而 const double pi = 3.141592654; 是 C++ 中将 [对] Π 作为命名常量定义的示例。

一些编程语言区分了在编译时确定值的常量和在运行时确定值的常量。例如，在 C# 中，前者用关键字 const 标记，后者用 readonly 标记。在 Java 中，字段（或局部标识符）的常量性用 final 关键字标记，而 static 修饰符的存在或不存在分别将关联的数据项分类为编译时常量或运行时常量。

示例：C# 中的编译时常量。
public class Math { ... public const /* static final in Java */ double pi = 3.141592654; public const double e = 2.718281; ... }

这里，pi 和 e（欧拉常数）的值甚至可以在程序开始运行之前确定。因此，它们被定义为常量。

请注意，如果存在任何 Math 类实例，则相同的定义对所有实例都有效。也就是说，pi 或 e 的值不会从一个实例更改为另一个实例。事实上，它们独立于实例作为类字段存在。换句话说，它们是 [隐式] 静态的。在 C++ 中，与 C# 的灵感来源相同，显式使用 static 和 const 就是这种体现。

示例：C# 中的运行时常量。
public class Citizen { ... Citizen (..., long SSNoftheNewCitizen, ...) { ... SSN = SSNoftheNewCitizen; ... } ... private readonly long SSN; /* private final long SSN in Java*/ } // end of class Citizen

这里，SSN 的值无法在相关 Citizen 对象创建之前确定。一旦对象被创建，其 SSN 字段在对象的生命周期内永远不会改变。因此，我们得出结论，初始化的唯一可能位置是构造函数。此值可以作为参数提供给构造函数，也可以使用对象的和其他属性和/或类计算得出。

观察到此类字段的值可能因实例而异。在我们的示例中，这是预期的行为：任何两个 Citizen 对象必须具有不同的 SSN 值。

可变数据

变量为我们提供了命名的内存存储，我们可以在程序执行过程中写入、检索和操作它。

变量有两个相关联的值

1. 它的数据值，存储在某个内存地址中。这有时被称为对象的右值（读作“are-value”）。你可以将其理解为读取（或右侧）值。常量和变量都可以充当右值。
2. 它的地址值——也就是说，它在内存中的地址，其中存储着它的数据值。这有时被称为对象的左值（读作“ell-value”）。你可以将其理解为位置（或左侧）值。请注意，常量不能充当左值。（因为它不能出现在赋值语句的左侧）。

可以通过三种方式为变量提供值

1. 在创建时进行初始化。这可以由用户提供，也可以是语言分配的默认值。Java编程语言就是第二种方法的一个例子。
2. 通过输入操作。
3. 通过赋值语句。

将标识符（无论是变量、常量还是函数）与其左值相关联的行为称为绑定，并且可以通过两种不同的方式建立。在标识符和左值之间是一对一关系的情况下，绑定发生在运行时之前，因此被称为静态绑定。全局变量就是一个例子，它只有一个标识符实例。在其他情况下，当关系是一对多时，绑定发生在运行时，称为动态绑定。局部变量就是一个例子，每次调用函数时，都会为其重新分配零个或多个实例。

可见性

我们还可以谈论标识符的作用域。作用域可以定义为声明一个标识符有效的程序部分。具有有效声明的标识符被称为在作用域内，而不在作用域内的标识符则被称为超出作用域。

语言的作用域规则决定了对非局部标识符的引用的处理方式。大多数编程语言使用一个称为词法或静态作用域规则的通用规则，通过单独检查程序文本来确定适用于标识符的声明。另一种规则，称为动态作用域规则，在运行时通过考虑当前子程序的激活来确定适用于标识符的声明。

标识符在作用域内并不意味着它是可见的。如果某个上下文中标识符的使用将绑定到该声明，则标识符的声明在该上下文中是可见的。也就是说，标识符将与该声明相关联。声明可能在其整个作用域内可见，但它也可能被其他作用域和可见性与第一个声明重叠的声明隐藏。

示例：C语言中的作用域和可见性。
... { int i1, i2; ... { double i1; double d; ... } /* 内部块结束 */ ... } /* 外部块结束 */ ...

在上面的代码片段中，变量（标识符）的作用域为

i1（外部块）、i2：从其声明点到外部块的末尾

i1（内部块）、d：从其声明点到内部块的末尾

变量的可见性为

i2、i1（内部块）、d：与其作用域相同

i1（外部块）：其作用域减去内部块

可访问性

可访问性约束是模块化和面向对象语言中的一种概念，可以应用于数据。这样做有两个目的

1. 为了保持数据的完整性，以及
2. 为了给予实现者更改实现细节的自由。

示例：Java中的访问约束。
public class Stack { ... private int _top; private Object[] _contents; } // Stack类结束

在上面的类定义中，将实现细节声明为private，这意味着它们对用户是不可访问的，即以下语句是不允许的。

stk._top = 0; stk._contents[7] = new Integer(5);

发出第一个语句可能会导致一个非空的Stack对象看起来为空。类似地，第二个语句可能会通过在_top指示的位置以外的其他位置添加新元素来填充Stack对象，这绝对违反了堆栈的定义。

此外，这样的定义使Stack类的实现者能够更改实现细节。例如，她可以选择使用Vector作为底层数据结构。现在，由于外部世界不知道这一点，因此Stack类的用户不会受到此决定的影响。

数据类别

数据元素

最基本的数据实体是数据元素。这些数据实体可以组合在一起形成结构。

原始数据元素

原始数据元素是可以由机器语言指令直接操作的元素，主要分为数值型、字符型和逻辑型（布尔型）。数值型数据元素可以进一步细分为整数和实数。

示例：C/C++中的原始数据元素。
在C/C++中，char、int、short、long和long long用于表示整数。char也可以解释为保存单个字节的字符。float、double和long double表示单精度、双精度和扩展精度的浮点数。bool用于表示布尔值。

作为地址的数据元素

地址是一个值，它指示运行程序后创建的进程映像中的一个位置。根据它指向的程序段，地址属于以下两组之一。

1. 标签实际上是程序语句的地址，是程序代码段中的一个地址。它也可以被认为是一个数据元素，可以通过goto操作进行操作。

2. 指针引用或指向代码和数据段中的其他元素。在前一种情况下，指示子程序开始的指针可用于动态调用子程序，从而能够通过回调实现多态子程序。指向数据段的指针通常引用未命名的数据元素。它们在构建动态数据结构和递归算法中被大量使用。句柄可以被视为智能指针，它们具有相同的用途。

复合数据元素

字符字符串，通常简称为字符串，是字符的线性序列。它们有时被认为是原始数据元素，因为它们由机器语言指令直接操作，有时被归类为数据结构。

结构体

数据结构

数据结构是经过组织的数据元素集合，这些元素受某些允许的操作约束。数据结构在逻辑上是实体，因为它们是由程序员创建的，并由高级程序操作。这些可能与物理实体（即机器语言代码操作的存储结构）几乎没有关系。

数据结构可以分类为

• 线性与非线性：线性数据结构与非线性数据结构相反，是指各个组件是有序序列的数据结构。线性数据结构的示例包括字符串、数组和列表。非线性数据结构的示例包括树、图和集合。
• 静态与动态：静态结构是指在执行过程中其大小无法改变的结构。数组和记录是静态数据结构的示例。动态数据结构的示例是列表。

存储（内存）结构

存储结构是在数据结构映射到内存之后的数据结构。数据结构是数据的逻辑组织，而存储结构表示在程序执行期间数据在内存中的物理存储方式。

多维数组可能的布局。
假设您正在使用二维数组。您的数组，例如n乘以m，实际上并没有在内存中以二维方式存储，而是作为元素的线性序列存储。在行主序中，数组按以下方式存储 A(1, 1), A(1, 2), ..., A(1, m), A(2, 1), ..., A(n, 1), A(n, 2), ..., A(n, m) 在列主序中，相同数组在内存中的布局如下 A(1, 1), A(2, 1), ..., A(n, 1), A(1, 2), ..., A(1, m), A(2, m), ..., A(n, m)

存储可以通过两种方式分配

• 顺序：以这种方式分配的结构也可以称为静态结构，因为它在其整个生命周期中都无法更改。此类结构使用隐式排序：组件通过其在结构中的顺序排序（索引）来排序。
• 链接：以这种方式分配的结构也可以称为动态结构，因为数据结构可以在其生命周期中增长和缩小。它们使用显式排序：每个组件在其自身内部包含下一个项目的地址，因此它实际上“指向”其自己的后继。

至于每种方法的优缺点

• 在静态结构中，整个存储在结构的整个生命周期内都保持分配状态。此外，为了避免溢出，在结构的声明中使用最大理论大小。由于这些原因，静态结构不是内存高效的。在动态结构中，由于指针字段的存在，存在空间开销。
• 由于可能发生移位（可以通过牺牲一些额外的内存来避免），因此除了静态结构末尾之外，从任何位置插入和删除都是代价高昂的。动态结构并非如此。
• 在静态结构中可以使用索引值进行直接访问，这意味着访问结构中的任何项都花费恒定时间。但是，这对于动态结构无效。但是，可以通过对数据强加分层结构来缓解此弱点。

文件结构

文件结构指的是驻留在辅助存储器中的数据。当程序执行终止时，文件结构是唯一在程序终止后仍然存在的结构。

数据层次结构指的是数据的逻辑组织，这些数据可能存储在辅助存储或外部存储介质（如磁带）上。

文件是与特定应用程序相关的相关记录的集合。记录是与单个处理对象相关的一组相关数据项或字段。字段是数据项，是包含在记录中的信息（数据元素或结构化数据项）。

可以访问文件以进行输入、输出、输入/输出和追加。它可以以两种不同的模式处理：批处理模式、查询模式。在批处理模式下，文件的组件记录按顺序操作。生成班级测试结果的报告是此类处理的示例。在查询模式下，通过直接访问来操作单个记录。检索单个学生的记录属于此类别。

另一个重要问题是文件在辅助存储器上的组织方式。记录的这种（物理）排序可以通过三种方式完成

• 顺序：文件被视为记录的线性序列。此类文件无法在输入/输出访问模式下访问。文本文件是顺序文件的典型示例。
• 相对：文件中的每个记录都可以通过位置直接访问。当然，只有当文件存储在直接访问存储设备 (DASD) 上时，这种组织才成为可能。记录中的键字段与磁盘上的位置之间的映射可以通过两种方式完成：直接映射和散列。
• 索引顺序：这是前两种方法之间的折衷方案。文件按顺序存储在 DASD 上，但还有一个索引文件，允许通过索引搜索进行最佳的直接访问。

必须根据以下方面评估每种文件组织技术

• 访问时间：查找特定数据项所需的时间。
• 插入时间：插入新数据项所需的时间。这包括查找插入新数据项的正确位置所需的时间以及更新索引结构所需的时间。
• 删除时间：删除数据项所需的时间。这包括查找要删除的项所需的时间以及更新索引结构所需的时间。
• 空间开销：索引结构占用的额外空间。

这些反过来又受三个因素的影响。系统必须首先将磁头移动到相应的磁道或柱面。这种磁头移动称为寻道，完成所需的时间为寻道时间。磁头到达正确的磁道后，必须等到所需的块旋转到读写磁头下方。此延迟称为延迟时间。最后，可以进行磁盘和主内存之间数据的实际传输。这最后部分是传输时间。

文件上的典型操作包括：打开、关闭、读取、写入、EOF 和维护操作，例如排序、合并、更新和备份。

数据类型

数据类型，通常简称为类型，由数据元素的域和作用于这些元素的操作集组成——这些操作可以构造、销毁或修改这些数据元素的实例。

除了可以结构化为原始数据类型的内置类型外，大多数语言还具有用户定义新数据类型的功能。[ALGOL68 和 Pascal 是首批提供此功能的编程语言。]

类型系统是定义新类型以及声明变量为这些类型的工具。类型系统还可以具有类型检查功能，该功能可以是静态的或动态的，具体取决于此检查是在编译时还是在执行期间完成。

示例：C 的（受限）类型系统。
基本类型：char、short、int、long、float、double 类型构造器：*、[]、()、struct、union typedef char Performance[2]; typedef char* String; typedef struct { String first_name; String last_name; Performance grades; } Student; typedef void (*EVAL_PERF) (Student* Class); ...

强类型编程语言是指所有变量的类型在编译时都确定的语言。用这种语言编写的程序（被称为具有静态类型）必须显式声明所有程序员定义的词。全局变量和局部变量的存储需求在编译期间完全确定。强类型编程语言可能包含用于定义新类型的类型机制。

在动态类型中，变量在编译时不与类型绑定。允许变量动态类型的语言（也归类为弱类型）可以使用动态类型检查，这需要存在运行时例程来检查类型并执行正确的操作，例如涉及存储映射和代码选择的那些操作。也可以说类型与值相关联，而不是与变量相关联。

示例：Scheme中的动态类型。
> (define x 3)↵ ; x表示类型为数字的值 > (+ x 1)↵ 4 > (number? x)↵ ; x是数字吗？-是的。 #t > (set! x "Nermin")↵ ; x现在表示类型为字符串的值 > (string-length x)↵ 6 > (number? x)↵ ; x是数字吗？-不再是了！ #f > (string? x)↵ ; x是字符串吗？-是的。 #t >_

数据类型之间的关系

等价性

在赋值语句（以及许多其他编程结构）中，编译器不仅检查语法正确性，还测试语义有效性。例如，不允许将字符串值赋给整型变量；编译器会强制执行某种赋值兼容性规则。此过程的一个重要组成部分是找出表达式和变量的类型是否等价。

这可以通过两种不同的方式完成：结构等价和名称等价。在前者中，如果两种类型由相同的底层数据类型组成，则它们是等价的。

示例：伪C中的结构等价。
struct S1 { int i; double d; char c; }; struct S2 { int f1; double f2; char f3; }; S1和S2被认为是等价的。

在名称等价中，只有当两个类型的名称相同时，它们才相等。这是大多数基于Algol的语言采用的方法。

示例：Pascal中的名称等价。
type arrtype1: array [1..10] of integer; arrtype2: array [1..10] of integer; var v1, v2: arrtype1; v3: arrtype2; 在以上片段中，v1和v2具有等价的类型，而v3的类型与这些变量的类型不同。

扩展

如果某个类型的全部实例都可以被视为其扩展类型的实例，则称该类型扩展另一个类型。基类型（被扩展的类型）被称为扩展类型的泛化，而扩展类型被称为其基类型的特化。

由于关系的性质，扩展类型的表达式与基类型变量是赋值兼容的。

提供这种关系最常用的技术是继承，它在大多数面向对象编程语言中都很常见。

实现

如果某个类型为已实现类型接口中列出的所有操作提供了实现，则称该类型实现了另一个类型。

实现可以被视为扩展的一种特例，其中基类型不提供其任何操作的实现。

在许多面向对象编程语言中，这种关系存在于接口与其实现类之间。

声明

在具有静态类型检查的语言中，程序必须以某种方式传达其使用的标识符的类型。编译时对标识符类型的完整了解可以提高程序效率，原因如下。

更有效的存储分配。例如，所有整型都可以使用最大的整型类型进行类似存储。但是，如果知道确切的类型，则不必分配最大的大小。运行时更有效的例程。A + B 的处理方式不同，具体取决于 A 和 B 是整数还是实数。编译时检查。在程序开始运行之前，就会发现许多编程结构的无效用法。

另一方面，以确保类型安全为代价，编译器有时可能会拒绝有效的程序。

标识符类型可以通过两种方式传达。

显式类型声明

与其他方法相比，程序员更倾向于使用声明语句来告知变量、函数等的类型。一些编程语言，例如 ML 和 Haskell，不要求程序员为所有标识符提供类型声明。通过一个称为类型推断的过程，编译器尽力推断出表达式的类型。

隐式类型声明

在（某些版本的）Fortran 和 BASIC 等语言中，变量的命名方式揭示了它的类型。

Fortran 中的隐式类型声明。
在 FORTRAN 90 之前的 FORTRAN 版本中，以 I-N 开头的标识符被视为整数，而以其他任何字母开头的标识符被视为实数。

标量数据类型

标量数据类型的域仅由单个基本数据元素组成。

数值类型

数值类型与外部世界中的数量相关或表示数量。但是，尽管在现实生活中这些类型的域可能是无限的，但在计算机的世界中，它们的域是有限的。

数值类型。
整数、浮点数、定点数和复数。

逻辑（布尔）类型

此类类型的变量只能取两个值，true 或 false，它们可以在机器中表示为 0 和 1、零和非零。布尔值上的典型运算包括and、or、not。

指针类型

指针是对对象或数据元素的引用。指针变量是一个标识符，其值为对对象的引用。

指针对于动态分配先前未确定数量的数据非常重要。此外，它们允许相同的数据同时驻留在不同的结构中。换句话说，它们使数据共享成为可能。

指针变量指向并提供访问未命名或匿名变量的方法。因此，指针上的操作必须区分对指针变量本身的操作和对指针指向的数量的操作。

示例：C/C++ 中的指针
int num1, num2, *pnum; ... ... pnum = &num1; num1 = 15; num2 = *pnum; ...
	第 6 行之后的内存布局

pnum 在上述示例中用于访问保存 int 值的位置。事实上，它只能保存对 int 的引用。这是指针和普通地址之间最重要的区别：虽然地址可用于引用任何类型的值，但指针保存对特定数据类型的引用。然而，作为在 C 中实现泛型集合的宝贵工具，可以通过规范使用 void * 来恢复地址的类型不可知性。

在 C 中，指针被大量使用，优点可能会变成维护噩梦。以下程序就是一个例子。

示例：C 中的指针陷阱。
#include <stdio.h> int main(void) { int ch = 65; int* p2i; const int *p2ci = &ch; p2i = p2ci; /* !!! */ printf("p2ci: %i\tp2i: %i\n", *p2ci, *p2i); *p2i = ch++; /* !!! */ printf("p2ci: %i\tp2i: %i\n", *p2ci, *p2i); exit(0); } /* end of int main(void) */

当我们编译并运行此程序时，它将产生以下输出。

p2ci: 65 p2i: 65 p2ci: 66 p2i: 66

这违反了我们所做的约定。在第 6 行，我们保证由 p2ci 指向的位置的内容不会改变。在第 8 行，我们将 p2ci 分配给 p2i，后者是另一个允许自身更新的指针。我们随后继续通过非常量指针 p2i 更改该位置处的值，这意味着由 p2ci 指向的值也发生了更改。

编译器可能会针对此错误发出警告，这在 GNU C 编译器中就是这种情况。但你不能依赖这一点：并非所有编译器都会发出警告。有时，程序员会关闭警告以避免阅读烦人的消息，并且该消息会被忽略。

结构化数据类型

结构化数据类型的域元素本身由其他标量或结构化类型元素组成。

字符串

字符串是动态变化大小的数据元素的有序集合。

可以将两个属性与字符串关联：类型和长度。类型指的是各个元素的域，而长度指的是元素的数量。（请注意，长度和大小是两个不同的概念。）

类型属性通常是字符，尽管位字符串也常用于实现集合。

示例：C/C++ 中的字符字符串。
char *name = "Atilla";

在其他语言中，同一个字符串的另一种可能的表示形式为

请注意，为长度前缀保留的字节数在不同的实现中可能会有所不同。还需要记住的一点是：ASCII 并非没有竞争对手。替代方案包括 Unicode 和基于 ASCII 的 ISO/IEC-8859 系列编码。在 Unicode 的情况下，每个字符在内存中占用两个字节。

示例：在 [OLE] 自动化中使用的 BSTR 类型。
CString name = _T("Atilla"); BSTR bstrName = name.AllocSysString();

如上图所示，BSTR 用于在可能使用不同语言编写的组件之间交换字符字符串数据。事实上，长度前缀继承自 Visual Basic，而终止空字符则来自 C。

请注意，长度前缀保存字符字符串本身所占用的字节数，而 bstrName 标识符实际上是指向第一个字符的指针。

字符串的典型操作包括

• 连接 从较小的字符串创建一个字符串。
• 子字符串 从另一个字符串的子序列创建一个字符串。
• 索引测试 用于检查较小字符串是否包含在较大字符串中。它返回包含较小字符串的子序列开始的索引值。
• 长度 返回字符串中的组件数。
• 插入、删除、替换 等。

数组

数组可以定义为一个固定大小、有序的同构数据集合。它存储在连续的内存位置，这使得可以直接访问。其固定大小使得数组成为一个静态结构。

在某些编程语言（如标准 Pascal）中，大小必须在编译时已知，而在许多语言中，此大小也可以在运行时给出。但是，即使在后一种情况下，数组的大小在其生命周期内也不会改变。

示例：标准 Pascal 中数组的静态特性。
program primes(input, output); const N = 1000; var a: array [1..N] of boolean; ... begin ... end
对于 N 的不同值，此 Pascal 代码片段必须重新编译并运行。

示例：Oberon 中的开放数组。
PROCEDURE SetZero (VAR v: ARRAY OF REAL); VAR j: INTEGER; BEGIN j := 0; WHILE j < LEN(v) DO v[j] := 0; INC(j) END END SetZero;

在上面的 Oberon 代码片段中，任何元素类型为 REAL 的实际（一维）数组参数都与 v 兼容。可以使用任何大小的一维数组调用子程序。但是，一旦数组作为参数传递，其大小就不能更改。

数组的重要属性包括组件类型、数组的维数以及每个维度的尺寸。

数组可以在内存中以两种不同的方式表示

1. 行主序（几乎所有主要的编程语言）
2. 列主序（FORTRAN）

为了最大程度地减少对单个数组组件的访问时间，我们应该确保程序中变化最快的索引（即最内层循环变量）对应于内存布局中变化最快的索引。如果忽略循环顺序，对于大型多维数组，虚拟内存性能可能会严重下降。

示例：Pascal 中多维数组的使用。
var a: array [3..5, 1..2, 1..4] of integer; ... for i := 3 to 5 do for j := 1 to 2 do for k := 1 to 4 do {some processing done using a[i, j, k]}

此程序片段显示了使用行主序表示数组的语言的正确循环顺序。请注意，片段中最内层循环变量（变化最快的变量）对应于内存布局中变化最快的索引。此对应关系必须扩展到其他循环变量和索引，即第二内层循环变量必须对应于内存中变化速度第二快的索引，依此类推。

示例：Fortran 中多维数组的使用。
DO k = 1, 4 DO j = 1, 2 DO i = 3, 5 {some processing done using a(i, j, k)} END DO END DO END DO

第二个片段给出了使用列主序表示的语言的正确循环顺序。

需要注意的是，包含在数组表示中的头信息不是标准的，并且在某些编程语言中可能会有所不同甚至消失。最显著的例子是 Java，其中数组的大小不用于类型检查。这意味着可以使用数组句柄来操作不同大小的数组。

示例：Java 中数组的类型兼容性。
int[] intArray = new int[10]; ... // use intArray as an array of 10 ints intArray = new int[20]; // OK! ... // use intArray as an array of 20 ints

这起初似乎与数组的静态特性相矛盾。毕竟，intArray 的大小已从 10 更改为 20。并非如此！我们在前面的代码片段中所做的是使 intArray 指示堆中的两个不同的数组对象。换句话说，我们更改了数组句柄，而不是数组对象本身。

确定 Pascal 样式数组中元素的地址。

给定伪 Pascal 声明 var a: array [5..10, 0..3, -2..2] of integer; 假设 a) 列主序表示和 b) 行主序表示，计算 a[7, 2, 1] 的地址。对于这两种情况，假设 a 的基地址为 200，一个整数以四个字节表示。 a) (10 – 5 + 1) * (3 – 0 + 1) * (1 – (-2 )) + 1 给我们 [5, 0, 1] 处的组件的顺序。我们需要 (10 – 5 + 1) * (2 – 0) 来到达 [5, 2, 1]。再加 (7 – 5)，我们就到达了 [7, 2, 1]。因此，[7, 2, 1] 是第 (6 * 4 * 3 + 1) + (6 * 2) + 2 = 87 个组件。它可以在地址 200 + (87 – 1) * 4 = 544 处找到。 上述计算可以推广如下 $order(n_{1},n_{2},n_{3},...,n_{m})=1+(n_{1}-l_{1})\sum _{i=m}^{2}{(n_{i}-l_{i})\prod _{j=1}^{i-1}{(u_{j}-l_{j}+1)}}\!$ 在基于 C 的编程语言中，下界始终取为 0，因此该公式可以简化为 $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{1}\sum _{i=m}^{2}{n_{i}\prod _{j=1}^{i-1}{u_{j}}}\!$ 某个组件的内存地址如下给出： $address(n_{1},n_{2},n_{3},...,n_{m})=base+componentSizex(order(n_{1},n_{2},n_{3},...,n_{m})-1)$ b) (2 – (-2) + 1) * (3 – 0 + 1) * (7 – 5) + 1 给我们 [7, 0, -2] 处组件的顺序。(2 – (-2) + 1) * (2 – 0) 更多，我们就到了 (7, 2, -2)。[7, 2, 1] 是 [7, 2, -2] 之后 (1 – (-2)) 个位置。所以，[7, 2, 1] 是第 (5 * 4 * 2 + 1) + (5 * 2) + 3 = 54 个组件。它的地址是 200 + (54 – 1) * 4 = 412。 经过推广，我们得到 $order(n_{1},n_{2},n_{3},...,n_{m})=1+(n_{m}-l_{m})+\sum _{i=1}^{m-1}{(n_{i}-l_{i})\prod _{j=i+1}^{m}{(u_{j}-l_{j}+1)}}\!$ 对于基于 C 的编程语言，这简化为 $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{m}+\sum _{i=1}^{m-1}{n_{i}}\prod _{j=i+1}^{m}{u_{j}}\!$

确定 C 样式数组中元素的地址。

给定伪 C 声明 double a[13][10][9]; 计算 a[7][6][8] 的地址，假设 a) 列主序表示和 b) 行主序表示。对于这两种情况，假设 a 的基地址为 200，并且 double 用 8 个字节表示。 a) $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{1}\sum _{i=m}^{2}{n_{i}\prod _{j=1}^{i-1}{u_{j}}}\!$ $order(7,6,8)=1+7+8(13x10)+6x13=8+1040+78=1126\!$ $address(7,6,8)=200+8x(1126-1)=9200\!$ b) $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{m}\sum _{i=1}^{m-1}{n_{i}\prod _{j=i+1}^{m}{u_{j}}}\!$ $order(7,6,8)=1+8+7(10x9)+6x9=9+630+54=693\!$ $address(7,6,8)=200+8x(693-1)=5736\!$

多维数组

对多维数组的支持可以通过两种方式提供：锯齿数组（有时称为不规则数组）和矩形数组。

示例：Java 中的锯齿数组。
int[][] numArr = { {1, 2, 3}, {4, 5, 6, 7}, {8, 9} };

这里我们实际上得到的是一个数组的数组。由于不同的数组可能具有不同的组件数量，因此我们示例中的子数组可以并且确实具有不同的长度。可以使用以下代码形成相同的数组，该代码反映了 Java 中数组的处理方式。

int[][] numArr = new int[3][]; numArr[0] = new int[3]; for (int i = 0; i < numArr[0].length; i++) numArr[0][i] = i + 1; numArr[2] = new int[2]; for (int i = 0; i < numArr[2].length; i++) numArr[2][i] = i + 8; numArr[1] = new int[4]; for (int i = 0; i < numArr[1].length; i++) numArr[1][i] = i + 4;

观察到涉及四次数组分配：numArr、numArr[0]、numArr[1]和numArr[2]。这些分配不需要以特定的顺序进行，可以在代码中交错出现。唯一的限制是子数组不能在包含数组之前分配。也就是说，必须先分配numArr，然后才能分配其他数组。这使我们得出了结论，这也反映在前面给出的布局中，即 Java 样式的多维数组不一定在连续的内存位置分配。

示例：C# 中的矩形数组。
int[,]4 numMatrix = { {1, 2}, {3, 4}, {5, 6} };
这里，我们有一个 3×2 的矩阵。它也保证整个矩阵在连续的内存位置分配。

关联数组

数组索引通常是标量类型，尽管像 Perl 和 Tcl 这样的语言通过使用散列提供了非标量索引。5 这种数组称为关联数组。

示例：Perl 中的关联数组。
$dictionary{'word'} = 'sözcük, kelime'; $grade{'Emrah'} = 90; $dictionary{'sentence'} = 'tümce, cümle';
由于运算符名称重载功能，像 C++ 和 C# 这样的语言通过重载下标运算符（[]）的类来合并此类功能。

示例：C# 中的关联数组。
HashTable dictionary = new HashTable(); ... dictionary["word"] = "sözcük, kelime"; dictionary["sentence"] = "tümce, cümle"; ... Console.Write("sentence in Turkish is {0}", dictionary["sentence"]); // 将在标准输出上打印“sentence in Turkish is tümce, cümle”

在缺少运算符名称重载的语言（如 Java）中，必须使用其消息的相关类。

示例：Java 中的关联数组。
Map dictionary = new HashMap(); ... dictionary.put("word", "sözcük, kelime"); dictionary.put("sentence", "tümce, cümle"); ... System.out.print("Sentence in Turkish " + dictionary.get("sentence")); // 将在标准输出上打印“sentence in Turkish is tümce, cümle”

列表

列表是广义的、动态的、线性数据结构。列表（链接列表）是一组按顺序组织的项目，就像数组一样。在数组中，顺序组织是隐式提供的（通过数组中的位置）；在列表中，我们使用显式安排，其中每个项目都是节点的一部分，该节点还包含指向下一个节点的链接。

示例：Pascal 中的链接列表。
type link = ^node; node = record key : integer; next : link end; var head : link; ...

根据链接的提供方式，我们有

• 单向链表：这些只为我们提供了一个前向指针，指向列表中的下一个节点。
• 双向链表：这些为我们提供了两个指针，一个指向下一个节点，一个指向列表中的前一个节点。

另一种分类是根据列表中第一个和最后一个节点的关系

• 循环列表：在循环列表中，列表中的第一个和最后一个节点通过链接连接起来。在循环双向链表中，最后一个节点的 next 链接指向第一个节点，第一个节点的 previous 链接指向列表的最后一个节点。在循环单向链表的情况下，从第一个节点到最后一个节点没有指针。
• 线性列表：在线性列表中，第一个和最后一个节点之间没有链接。最后一个节点的 next 字段和第一个节点的 previous 字段不指向任何地方，即它们为 null。

在列表的实现中，可以使用头节点和/或虚拟尾节点。

列表上的操作是

• 创建/销毁操作。
• 插入：在具有特定键值的节点之前/之后；插入到末尾，在开头。
• 删除：具有特定键值的组件；第一个、最后一个组件。
• 搜索：具有特定键值的组件。
• 空：测试列表是否为空。

一些常用的、专门的（受限的）列表形式是栈（LIFO）、队列（FIFO）、双端队列（Deque）、输出受限双端队列和输入受限双端队列。

多列表

多列表类似于列表。唯一的区别是节点同时驻留在多个列表上。

示例：使用多列表表示稀疏矩阵的 Pascal 表示形式。
type link = ^node; node = record row_no, column_no : integer; key : integer; next_row, next_column : link end;

动态数组

动态数组是数组和列表的混合体，可以在运行时增长或缩小其大小。Java 世界中称为 Vector，C# 世界中称为 ArrayList，动态数组维护一个内部的、堆分配的数组，并根据需要用更大（更小）的数组替换它。

记录

作为逻辑数据结构的记录是固定大小的、有序的、可能异构的组件集合，这些组件本身可能是有结构的。它也可以称为分层或结构化类型。记录组件，通常称为字段，通过名称而不是下标访问。

示例：COBOL 中的记录类型定义。
01 STUDENT-RECORD. 02 NAME. 03 FIRST-NAME PIC X(15). 03 MIDDLE-INITIAL PIC X. 03 LAST-NAME PIC X(15). 02 STUDENT-NO PIC 9(9). 02 TEST-SCORES. 03 MIDTERM PIC 9(3).99. 03 FINAL PIC 999.99. 02 ASSIGNMENTS OCCURS 5 TIMES PICTURE IS 9(3).9(2).

变体记录

一些语言允许我们拥有记录的不同变体。这种带有变体的记录称为变体记录。这意味着某些字段对所有变体都是通用的，而某些字段对每个变体都是唯一的。

示例：C语言中的变体记录。

enum shape_tag {Circle, Square}; struct SHAPE { float area; enum shape_tag tag; union { float radius; float edge_length; }; }; typedef struct SHAPE shape; shape s; ... ... s.tag = Square; or s.tag = Circle; s.edge_length = 3.5; s.radius = 5; ... ... void print_areas(shape s) { switch (s.tag) { case Circle: printf("圆的面积：%f\n", PI * s.radius * s.radius); break; case Square: printf("正方形的面积：%f\n", s.edge_length * s.edge_length); } /* switch语句结束 */ } /* void print_areas(shape)结束 */

请注意，随着类型扩展功能的引入，变体记录现在已成为一项过时的特性。除了像C++这样的为了与C兼容而保留它的语言外，面向对象的编程语言在其工具库中都不包含变体记录。

变长记录

变长记录类似于变体记录。在这种情况下，变体涉及重复字段的数量。

示例：COBOL中的变长记录。
01 CLASS. 03 NO-OF-STUDENTS PIC 99. 03 STUDENTS OCCURS 70 TIMES DEPENDING ON NO-OF-STUDENTS. 05 FIRST-NAME PIC X(15). 05 MIDDLE-INITIAL PIC X. 05 LAST-NAME PIC X(15). 05 TEST-SCORE PIC 999.99 OCCURS 3 TIMES.

一些编程语言提供元组，它们实际上是其字段由其位置隐式命名的记录。

示例：ML中的元组。
val t = (4, 5.0, "six");↵ val t = (4, 5.0, "six") : int * real * string #1(t);↵ val it = 4 : int #2(t);↵ val it = 5.0 : real #3(t);↵ val it = "six" : string

在查看记录如何在内存中布局的示例之前，让我们先看看一个相当重要的影响因素：对齐要求。

对齐要求

出于效率的原因，某些体系结构不允许数据元素从不是数据元素大小倍数的地址开始。由于这种对齐，获取程序所需数据需要更少的内存访问次数。然而，这种运行速度的提高是以占用更多内存为代价的。

需要注意的是，以下示例中提供的对齐方案并非唯一方案。编程环境可能会以某种方式让您更改数据对齐的方式。事实上，构建在英特尔架构之上的编程环境甚至可能允许您打开和关闭对齐。

double 的对齐要求
IEEE754双精度浮点数可以用8个字节表示。与该规范兼容并在具有如上所述对齐要求的体系结构上实现的数据类型不能从内存位置（例如4或6）开始。它应该从地址可被8整除的位置开始。因此，它可以从0、8、...、33272、...等位置开始。

记录类型的对齐要求至少与具有最严格要求的组件一样严格。记录必须在其开始的对齐边界上结束。

示例：记录中的对齐。
struct S { double value; char name[10]; };
struct S { char name[10]; double value; };

请意识到数组的对齐要求等于其组件的对齐要求。无论数组大小是1还是一百万字节，其对齐要求始终相同。这是因为数组声明是定义多个变量的简写。上述代码段实际上应该被认为如下所示

struct S { double value; char name0, name1, name2, ..., name9; };

因此，我们结构定义的对齐要求等于value的对齐要求：8。

示例：变体记录中的对齐要求。
type tagtype = (first, second); vtype = record f1 : integer; f2 : real; case c : tagtype of first : (f3, f4 : integer); second : (f5, f6 : real) end; var v : vtype;

如果我们将变体部分的选择器更改为case tagtype of，我们将得到

根据体系结构的不同，这可以为每个记录节省 4 到 8 个字节。但它让我们失去了类型安全。

集合

集合是一种非线性结构，包含一组无序的不同值的集合。集合上的典型操作包括插入单个组件、删除单个组件、并集、交集、差集和成员资格。

示例：Pascal 中的集合。
type days = (sun, mon, tues, wed, thur, fri, sat); dayset = set of days var weekdays, weekend: dayset; ... begin weekdays := [mon, tues, wed, thur, fri]; weekend := [sun, sat]; ... ... end.

集合中的基本类型限制为标量类型，并且由于存储要求；潜在成员的数量受到严格限制。

树

树是非空节点和边的集合，满足某些要求。节点是一个简单的对象，包含指向其他节点的链接以及一些值；指向另一个节点的链接称为边。

在一棵树中，

• 节点的前驱称为其父节点。
• 节点的后继称为其子节点。
• 没有后继的节点称为叶子节点。
• 没有前驱的节点称为根节点。
• 从根节点出发，没有不可到达的节点。
• 根节点和某个节点之间只有一条路径。

树在日常生活中经常遇到。例如，许多人用家谱来追踪他们的祖先和/或后代。事实上，许多术语都源于这种用法。另一个例子是在体育比赛的组织中。

示例：在 Pascal 中表示二叉树。
type link = ^node; node = record info: char; left_child, right_child: link end;

图

与树类似，图是节点和边的集合。与树不同，图没有根、叶、父或子的概念。节点，也称为顶点，可以独立存在；也就是说，它可能是不可到达的。对于某些顶点对，可能存在多条路径将它们相互连接。

许多问题都可以用图来自然地表达。例如，给定欧洲的航空路线图，我们可能会对以下问题感兴趣：“从伊兹密尔到圣彼得堡最快的方法是什么？”很可能许多城市对之间有多条路径将它们连接起来。另一个例子可以在有限状态机中找到。

图可以用两种方式表示

1. 邻接矩阵表示

一个 V×V 的布尔值数组，其中 V 是顶点的数量，如果从顶点 x 到顶点 y 存在一条边，则 a[x, y] 设置为 true，否则设置为 false。

示例：Pascal 中的邻接矩阵表示。
program adjmatrix (input, output); const max_no_of_vertices = 50; type matrix_type = array [1..max_no_of_vertices, 1..max_no_of_vertices] of boolean; var a: matrix_type; ... ...

2. 邻接结构表示

在这种表示中，连接到每个顶点的所有顶点都列在该顶点的邻接列表中。

示例：Pascal 中的邻接结构表示，
program adjlist (input, output); const max_no_of_vertices = 100; type link = ^node; node = record v: integer; next: link end; bucket_array = array [1..max_no_of_vertices] of link; var adj: bucket_array; ... ...

虽然邻接矩阵对于稠密图是更好的选择，但对于稀疏图，邻接结构表示法成为更可行的解决方案。

用户定义类型

除了增强程序文本的可读性和清晰度之外，定义用户定义类型还可以使我们能够一次构建复杂的数据结构，然后根据需要创建任意多个该类型的实例（变量），其次，还可以利用语言自身的类型检查功能进行输入数据验证，例如范围或一致性检查。

用户定义类型有两种形式

1. 枚举类型

枚举类型允许程序员枚举类型的域。域值在一个声明语句中列出。

示例：C++ 中的枚举类型
在 C++ 中，我们可以使用以下方式：
const int input = 1; const int output = 2; const int append = 3; ... bool open_file(string file_name, int open_mode); ... if (open_file("SalesReport", append)) ...
我们也可以使用以下方式：
enum open_modes {input = 1, output, append}; ... bool open_file(string file_name, open_modes om); ... if (open_file("SalesReport", input)) ...

2. 子类型

子类型是将域指定为另一个已存在类型的子范围。

示例：Pascal 中的子类型。
type ShoeSizeType = 35..46; var ShoeSize : ShoeSizeType;
有了这些声明，我们就不能将任何超出范围的值赋给ShoeSize变量。任何此类尝试都将被类型系统捕获，并导致程序因错误而终止。[在支持异常的编程语言中，这可以通过不终止程序的方式更优雅地处理。]

请注意，枚举和子类型定义不允许程序员为新定义的数据类型指定操作。

抽象数据类型

抽象数据类型 (ADT) 的定义特征是，数据结构和在其上操作的算法的定义之外的任何内容都不应该引用内部的任何内容，除非通过函数和过程调用来执行基本操作。

示例：Pascal 中的栈实现，

type link = ^node; node = record key: integer; next: link end; var head, z: link; procedure stackinit; begin new(head); new(z); head^.next := z; z^.next := z end; procedure push(v: integer); var t: link; begin new(t); t^.key := v; t^.next := head^.next; head^.next : = t end; function pop: integer; var t: link; begin t := head^.next; pop := t^.key; head^.next := t^.next; dispose(t) end; function peek: integer; begin peek := t^.key; end function stackempty: boolean; begin stackempty := (head^.next = z) end;

上面这段 Pascal 代码片段不幸不是 ADT 的理想实现。记录定义的字段可以被随意操作；没有语言结构可以禁止通过更改其组件来直接更改底层结构。程序员也可以使用任何子程序，无论是用于导出的子程序还是用于实现某些辅助功能的子程序。缺少一种机制来提供对子程序和记录字段的受控访问，例如面向对象编程语言中提供的访问说明符。

将相关的子程序组织到一个编译单元中不是由语言强制执行的。可以添加与正在实现的 ADT 无关的子程序。没有编译器强制的规则将预先存在的和/或新添加的子程序与相关的 ADT 联系起来。我们能做的最好的事情就是坚持约定，以便更好地组织我们的程序。

另一个缺点，一个可以很容易解决的缺点，是前面的代码片段无法创建多个栈。

我们需要的是类似于模块化编程语言中的模块构造或面向对象编程语言中的类构造的东西。

示例：Ada83 中的栈实现。
程序包 Stack_Package 是 类型 Stack_Type 是 私有; 过程 Init(Stack: 输入输出 Stack_Type); 过程 Push (Stack: 输入输出 Stack_Type; Item: 输入 整数); 函数 Pop (Stack: 输入输出 Stack_Type) 返回 整数; 函数 Peek (Stack: 输入 Stack_Type) 返回 整数; 函数 Empty (Stack: 输入 Stack_Type) 返回 布尔; 私有 Stack_Size: 常量 整数 := 10; 类型 Integer_List_Type 是 数组 (1..Stack_Size) 的 整数; 类型 Stack_Type 是 记录 Top: 整数 范围 0..Stack_Size; Elements: Integer_List_Type; 结束记录; 结束 Stack_Package; 程序包 主体 Stack_Package 是 过程 Init (Stack: 输入输出 Stack_Type) 是 开始 Stack.Top := 0; 结束 Init; 过程 Push (Stack: 输入输出 Stack_Type; Item: 输入 整数) 是 开始 Stack.Top := Stack.Top + 1; Stack.Elements (Stack.Top) := Item; 结束 Push; 函数 Pop (Stack: 输入输出 Stack_Type) 返回 整数 是 Item: 整数 := Stack.Elements (Stack.Top); 开始 Stack.Top := Stack.Top – 1; 返回 Item; 结束 Pop; 函数 Peek (Stack: 输入 Stack_Type) 返回 整数 是 开始 返回 Stack.Elements(Stack.Top); 结束 Peek; 函数 Empty (Stack: 输入 Stack_Type) 返回 布尔 是 开始 如果 Stack.Top = 0 那么 返回 真; 否则 返回 假; 结束 Empty; 结束 Stack_Package;
使用此实现，读取十个整数并以相反顺序打印它们的程序可以如下实现。
使用 Basic_IO, Stack_Package; 过程 Reverse_Integers 是 x: 整数; St: Stack_Package.Stack_Type; 开始 Stack_Package.Init(St); 为了 i 在 1..10 循环 Basic_IO.Get(x); Stack_Package.Push(St, x); 结束 循环; 为了 i 在 1..10 循环 x := Stack_Package.Pop(St); Basic_IO.Put(x); Basic_IO.New_Line; 结束 循环; 结束 Reverse_Integers;

以上实现比之前的实现好得多：操作堆栈的唯一方法是通过在其上定义的操作。ADT 的表示被声明为属于包的私有部分。这当然是对第一个示例的一个重大改进。但是，它仍然要求用户在两个单独的步骤中执行创建和初始化，这是一个相当容易出错的过程。如果我们忘记调用初始化例程会怎样？

这种方法的另一个问题是缺乏适应性。一旦定义，用户无法更改其行为，除非修改其定义。这有时可能非常限制。考虑在图形系统中定义形状类型。尽管形状在许多方面可能有所不同，但某些操作可以应用于所有形状，例如绘制、旋转、平移等。起初，我们可能会想出一个中心例程，在其中调用特定形状类型的相应绘制例程。非面向对象编程语言的典型实现如下所示

enum kind { circle, triangle, rectangle }; class Shape { // 所有形状的共有属性 kind k; ... public: // 所有形状的共有接口 void draw(void); void rotate(int degree); ... }; void Shape::draw(void) { switch(k) { case circle: // 绘制圆形 break; case triangle: // 绘制三角形 break; case rectangle: // 绘制矩形 break; default: error(...); } // switch(k) 结束 } // void Shape::draw(void) 结束 void Shape::rotate(int howManyDegrees) { switch(k) { case circle: // 旋转圆形 break; case triangle: // 旋转三角形 break; case rectangle: // 旋转矩形 break; default: error(…); } // switch(k) 结束 } // void Shape::rotate(int) 结束

前面解决方案的一个弱点是，核心函数draw和rotate必须了解所有不同类型的形状。如果定义了一个新的形状，则必须检查对形状的每个操作并可能进行修改。事实上，除非你拥有源代码，否则你甚至无法向系统添加新的形状。而通常情况下，当你只是一个类的用户时，你并不具备这样的权限。因此，实现者面临着一个两难境地：要么发布缺少形状的实现，要么无限期地推迟发布，直到你确保拥有所有可能形状的详尽列表。理想情况下，你希望尽早发布你的软件，并使其尽可能地功能完善。这被称为开闭原则。但是，当你的时间有限，并且对备选方案了解不多时，你如何才能提供详尽的功能呢？答案是让用户扩展你的软件，关键词是继承。在C++中，你会提供以下解决方案

class Shape { // 所有形状的共有属性。没有用于保存类型的属性！ ... public: // 所有形状的共有接口 virtual void draw(void); virtual void rotate(int degree); ... } // class Shape 结束 class Circle : public Shape { // Circle 的特有属性。 ... public: void draw(void) { /* draw 的圆形特有实现 */ } void rotate(int degree) { /* rotate 的圆形特有实现 */ } ... } // class Circle 结束 class Triangle : public Shape { // Triangle 的特有属性。 ... public: void draw(void) { /* draw 的三角形特有实现 */ } void rotate(int degree) { /* rotate 的三角形特有实现 */ } ... } // class Triangle 结束 class NewShape : public Shape { // 新形状的特有属性。 ... public: void draw(void) { /* draw 的新形状特有实现 */ } void rotate(int degree) { /* rotate 的新形状特有实现 */ } ... } // class NewShape 结束

除了上述优点外，编译器控制整个过程，而在之前的情况下，是用户在做所有簿记工作。