数据作为整数的集合

不同编程语言中的数据结构核心概念是相同的，尽管实现方式在语法上有所不同。

此外，算法或指令序列与数据结构的核心概念密切相关。但在那之前，我们需要了解一些基本的离散数学代数概念，这些概念也与数据结构相关。

各种编程语言中的数据结构概念主要源于称为“数据集”的离散数学代数概念。因此，在深入探讨数据结构的核心概念之前，理论上我们需要理解“数据集”这一概念。

什么是数据集？数据集是一个结构化的数据点集合，通常以特定格式组织。例如，数据集可以表示为整数集合，如 {14, 1, 58, 3, 85} 或 {1, 2, 2, 4, 5, 6}。

人类在编程语言出现之前就已经开始存储数据并对其进行操作。从这个意义上说，我们最近才将这些古老的代数数据集概念融入到编程语言中。

在编程语言中，我们首先想到的是数组；后来发现数组并不足够，于是我们引入了栈、队列、链表、树、哈希等概念。如今，数据结构被用于每种编程语言中，以有组织且高效的方式存储数据。而要做到这一点，我们需要高效的算法。这就是基本理念。此外，离散数学代数数据集、算法和数据结构也被结合成有意义的整体。

我们不得不这样做，因为数据量的增长速度前所未有。能够对大量数据进行排序的有效算法正受到前所未有的关注。

让我们先看看与数据集相关的几个代数概念。之后，我们将进入复杂数据结构的世界。

在离散数学中，有两个始终相伴的概念：一是运算顺序：求解复杂表达式时，算术运算的顺序遵循 PEMDAS（括号、乘方、乘除同级、加减同级）；二是分配律：分配律是一种基本性质，定义了乘法如何对加法和减法进行分配。

考虑如下因素：

1x = 3 * (4 + 6)
2x = 3 * 10
3x = 30

现在我们可以重新排列这些因子：

1x = 3 * (4 + 6)
2x = (3 * 4) + (3 * 6)
3x = 12 + 18
4x = 30

我们可以看到，运算顺序和分配律在加法和减法中表现良好。然而，这在乘法和除法中不适用。

每一个代数运算本质上都是一种算法。在这种情况下，我们的算法失败了，因为正如上面所述，它适用于加法和减法，但不适用于乘法和除法。

同样的情况也可能出现在数据集中。我们可能会尝试将相同的算法应用于一组数字。考虑如下数据集：

1{14, 5, {78, 1, 56}, 8, 96, 0, 6}

这是一个嵌套的数据集。我们无法在此应用我们的算法，必须先使用运算顺序规则，优先计算子数据集内的加法。

我们不能总是像处理离散整数那样对待整数集合。我们需要设计不同的算法。

计算均值、中位数和众数

在任何代数数据集中，总存在一个集合的平均值。考虑以下数据集：

1{6, 2, 3, 8, 1}

该数据集的平均值为 (6 + 2 + 3 + 8 + 1) / 5，即 4。这也被称为数据集的均值。

除此之外，在任何代数数据集中，中位数代表数据集的中间值。对于包含奇数个整数的集合，找出中位数相对容易。

在上述数据集中，3 是中位数或中间值。但当集合中整数的数量为偶数时，这种方法就不适用了。

考虑以下数据集：

1{1, 2, 3, 4}

求均值相对简单，与集合中元素的奇偶性无关。然而，在上述数据集中，求中位数并不那么简单。为了找到中位数，我们需要找出位于数据集中间的两个数 2 和 3 的中间值。

2 和 3 的中间值是 2.5。因此，2.5 是上述数据集的中位数。

数据集的另一个重要特征是众数，即出现次数最多的数值（可能不止一个）。考虑以下数据集：

1{1, 56, 7, 89, 7, 3, 56, 2, 1, 7, 8, 9, 3, 45, 3, 96, 3, 78, 5, 3}

在上述数据集中，有多个数值重复出现。我们可以看到，1 和 56 各出现两次，7 出现三次，3 出现五次。出现次数最多的整数是 3。因此，3 是上述数据集的众数。

注意：数据集的均值通常被称为“算术平均数”，以避免与其他类型的平均数（如几何平均数或调和平均数）混淆。

就编程语言而言，假设我们需要计算一个国家人口的平均收入，即人均收入。

现在我们可以合理推测，仅用数据集的均值无法准确反映该数据集的集中趋势（均值、中位数和众数）。

设想一个数据集，其中某个国家的人均收入远高于大多数国家。理论上，该国的人均收入显示出了良好的集中趋势，但这是一种错误的说法。实际上，该国 70% 的人生活在贫困线以下。

在这种情况下，中位数可能更能准确描述集中趋势。为什么？因为中位数将数据样本的上半部分与下半部分分开，代表中间值。

均值对极端值敏感，可能导致集中趋势的偏差，但它在对称分布的数据中表现优异。与中位数不同，均值受数值大小的影响，即使少数极端值也会使其产生偏差。然而，如果异常值超过一半数据，则中位数是更稳健、更稳定的集中趋势度量。

数组：数据结构的第一步

我们知道，数组是一种按顺序排列的元素集合。这些元素类型相同，并在内存中连续存储。可以通过其索引获取数组中的元素。在 Java 中，数组被视为对象，这与 C 语言中的处理方式不同。

我们可以认为，数组是一种存储相同类型元素的数据结构。同时，它也可以表示大型代数数据集。我们可以如下生成一组随机元素：

1class ManipulatingArray {
2    private int arrayOfRandomNumbers[] = new int[20];
3
4    public void getRandomElements() {
5        for (int i = 0; i < arrayOfRandomNumbers.length; i++) {
6            arrayOfRandomNumbers[i] = (int)(Math.random() * 121) + 121;
7            System.out.println(arrayOfRandomNumbers[i]);
8        }
9    }
10
11    public static void main(String[] args) {
12        ManipulatingArray manArray = new ManipulatingArray();
13        manArray.getRandomElements();
14    }
15}

上述代码是一个生成大整数随机数据集的示例。我们可以生成 20 个这样的数值：

1191
2189
3202
4214
5219
6150
7141
8169
9195
10233
11197
12125
13174
14198
15219
16232
17216
18227
19146
20173

这里我们使用了一种简单的方法来获取随机数组。

• 第 1–2 行：我们定义了一个名为 ManipulatingArray 的类，其中包含一个随机数数组作为属性。

• 第 5–9 行：在 getRandomElements() 方法中，我们使用 for 循环迭代，并通过 Math.random() 方法生成随机数。

Java 代码生成随机元素

我们现在了解了如何大规模操作数据。我们可以如下搜索随机输出中的任意值：

1// Java
2
3class ManipulatingArray {
4    private int arrayOfRandomNumbers[] = new int[20];
5
6    public void getRandomElements() {
7        for (int i = 0; i < arrayOfRandomNumbers.length; i++) {
8            arrayOfRandomNumbers[i] = (int)(Math.random() * 121) + 121;
9            System.out.println(arrayOfRandomNumbers[i]);
10        }
11    }
12
13    public boolean getValueInArray(int findTheValue) {
14        boolean theValue = false;
15        for (int i = 0; i < arrayOfRandomNumbers.length; i++) {
16            if (arrayOfRandomNumbers[i] == findTheValue) {
17                theValue = true;
18            }
19        }
20        return theValue;
21    }
22
23    public static void main(String[] args) {
24        ManipulatingArray manArray = new ManipulatingArray();
25        manArray.getRandomElements();
26        System.out.println("**********");
27        System.out.println(manArray.getValueInArray(121));
28    }
29}

我们试图判断 121 是否存在于随机生成的整数数组中。结果将是 false。我们在生成随机整数时使用了以下代码行：

1arrayOfRandomNumbers[i] = (int)(Math.random() * 121) + 121;

由于 Math.random() 方法返回 double 类型，我们需要将其强制转换为整数类型（int）。每次运行代码都会得到不同的结果。如果我们把 121 改为更大的值，结果也会更高。

因此，预期输出如下：

1190
2126
3171
4160
5205
6231
7174
8163
9127
10177
11210
12157
13126
14128
15233
16226
17182
18167
19180
20138
21**********
22false

在这个示例输出中，121 不属于随机生成的整数集合。

作为面向对象编程语言，Java 将此类集合的处理方式与 C 语言不同。在 Java 中，数组是一个容器对象，用于存储固定数量的单一类型值。一旦创建数组，其长度即被确定，之后无法更改。

在这里，我们添加了一个名为 getValueInArray() 的方法，用于检查指定值是否存在。它遍历数组，若找到该值，则将标志或返回值设为 true。

在 Java 中，创建数组对象时，我们写成如下形式：

1private int arrayOfRandomNumbers[] = new int[20];

但在 C 语言中则不同。一些计算机科学家认为，C 语言介于面向问题的高级语言（如 Fortran、Basic 和 Pascal）与低级机器语言（如汇编语言或机器语言）之间。

每个 C 程序由一个或多个独立单元组成，称为函数。在 C 中，如上述代码所示，我们这样声明数组：

1// 声明数组
2int individualGrades[10];

无论语言类型是基于函数还是面向对象，访问数组元素的方式是一样的。都是通过下标实现的，所有数组元素从 0 开始编号。C 语言中的“下标”在 Java 中被称为“数值索引”。在 Java 中，数组中的每一项称为“元素”，而在 C 中也称为“维度”。

C 代码计算均值

均值、中位数和众数是操作数组时广泛使用的代数数据集概念。考虑以下示例，我们计算 10 名学生的平均成绩。程序要求用户输入成绩，并计算数据集的均值。

1#include <stdio.h>
2
3int main() {
4    float grades[10];
5    float sum = 0;
6    float averageNumber;
7
8    printf("Enter grades: ");
9    for (int i = 0; i < 10; i++) {
10        scanf("%f", &grades[i]);
11        sum += grades[i];
12    }
13
14    averageNumber = sum / 10;
15    printf("Average number = %f", averageNumber);
16
17    return 0;
18}

上述代码的输出如下：

1Enter grades: 35
2Enter grades: 65
3Enter grades: 98
4Enter grades: 99
5Enter grades: 48
6Enter grades: 75
7Enter grades: 67
8Enter grades: 54
9Enter grades: 89
10Enter grades: 36
11Average number = 66.599998

代码中关键的一行是：

1printf("Average number = %f", averageNumber);

我们期望输出为浮点数。在每种语言中，我们都使用各种原始数据类型来声明数组类型。

在 Java 中，我们可以声明多种类型的数组，如下所示：

1byte[] anArrayOfBytes;
2int[] anArray;
3short[] anArrayOfShorts;
4long[] anArrayOfLongs;
5float[] anArrayOfFloats;
6double[] anArrayOfDoubles;
7boolean[] anArrayOfBooleans;
8char[] anArrayOfChars;
9String[] anArrayOfStrings;

我们可以使用快捷语法以几乎相同的方式创建和初始化数组。

我们看到，C 代码的主要区别在于使用了 scanf() 和相应的格式说明符（%d 用于整数，%f 用于浮点数）。

在 Java 中，我们这样使用快捷语法：

1int[] anArrayDeclaration = {
2    100, 200, 300,
3    400, 500, 600,
4    700, 800, 900, 1000
5};

在 C 中，我们可以几乎以相同方式使用快捷语法。有时，如果数组在声明时就被初始化，就不需要指定维度：

1int numArray[] = {1, 21, 3, 45, 7};

无论使用哪种语言，数组的主要优势在于它有助于节省系统内存。我们可以动态分配内存；当内存分配不是动态时，数据会存储在连续的内存位置中。这一过程使程序比其他数据结构更快。

代数数据集的概念以及均值、中位数和众数的相关知识，也将帮助我们理解复杂数组的操作。在进入下一节之前，让我们先了解一下数组的一些简单特性。为此，我们将使用 Java，这是一种最容易学习的语言之一。