数据结构：基本概念及术语

一、基本概念

        在数据结构中，有这样一些基本概念：数据、数据元素、数据项、数据对象，对于它们的具体含义我就不赘述了，在这就简要说明一下它们之间的关系：

        首先，我们可以把数据看成一个大集合，那数据元素就相当于这个集合中的一个个元素，然后一些性质相同的数据元素组成一个个小集合，也就是一个个数据对象，而这些数据对象是被数据这个大集合包含着的，所以数据对象就是数据的子集。

        至于数据项，则是数据元素的最小单位，是不可分割的（通常情况下），但在特殊情况或不同层次下可以被再一次细分。

        总的来讲就是：数据 > 数据对象 > 数据元素 > 数据项。

二、术语

        1、结构相关术语

        结构相关术语有：数据结构、逻辑结构、存储结构（物理结构），这三个术语之间也有一定的关联。首先，数据结构包含逻辑结构和存储结构；其次，逻辑结构是数据结构的抽象；最后，存储结构是逻辑结构在计算机的具体实现。

        现在我们来看一下逻辑结构，它是可以被细分的，一种是分为线性结构和非线性结构，另一种则是分为集合结构、线性结构、树状结构和图状结构。这是它们的一些含义：

前一种：

        线性结构：有且只有一个起始节点和终端节点，并且每个节点最多只有一个直接前趋和直接后继；

        非线性结构：每个节点可能有多个直接前趋和直接后继。

后一种：

        集合结构：结构中的数据元素之间除同属于一个集合外，再无任何关系；

        线性结构：结构中的数据元素之间存在一对一的线性关系；

        树状结构：结构中的数据元素之间存在一对多的关系；

        图状结构：结构中的数据元素之间存在多对多的关系。

        接下来就是存储结构了，它可以被分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构，这里着重讲的是前两种存储结构，含义如下：

        顺序存储结构：用一组连续的存储单元依次存储数据元素，并用元素的存储关系来表示数据元素之间的逻辑关系；

        链式存储结构：用一组任意的存储单元来存储数据元素，并用指针将其链接起来.

        在实际应用中，对于这么多种存储结构，我们自然要进行选择，至于要选择哪种存储结构，则需要你了解这些存储结构的优点与缺点后，才能更好地进行选择。正所谓“知己知彼，百战不殆”,当你了解这些存储结构的利弊后，就能更好地根据实际情况来分析究竟要用哪种数据结构了。下面就是前两种存储结构的一些优缺点：

         顺序存储结构：

                优点：1、存储密度大；

                           2、进行随机存取，一步计算就能得到任意元素的地址。

                缺点：1、在进行删除和插入操作时，需要移动大量元素，效率低下；

                           2、不便于动态扩展。

        链式存储结构：

                优点：1、进行删除和插入操作时，不需要移动大量元素；

                           2、便于动态扩展。

                缺点：1、存储密度小；

                           2、进行顺序存取，无法快速得到任意元素的地址。

          2、运算相关术语

        运算相关术语有数据的运算和算法，其中常见运算有：插入、删除、查找、排序等，而对于算法，我们则有如下要求：正确性、可读性、健壮性和高效性。

        这些要求的意思也很好理解，顾名思义，正确性就是保证自己的代码结果是正确的；可读性就是让自己的代码能更容易被人看懂；健壮性则是在面对异常情况时仍能正常运行；最后的高效性是让自己的代码所花费的时间更少。

        当然，这些要求也有分轻重缓急，最紧要的是保证算法的正确性，最后的最后才是高效性。谈到高效性，自然也少不了时间复杂度和空间复杂度，这两个可谓是衡量算法效率的重要指标。

        那如何用它们来判断算法效率呢？如果是时间复杂度的话，就看执行次数最多的那个语句，也就是基本语句，根据基本语句执行的次数就可以判断出时间复杂度，例如：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int i = 0;
	int j = 0;
	int n = 0;
	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		j++;//基本语句
	}

	printf("%d\n", j);//结果为所输入的值

	return 0;
}

        这是在 vs2022 下用 C 语言写的代码，从中我们可以看出 j++; 这个语句执行次数最多，所以该语句就是基本语句，总共执行了 n 次，那么时间复杂度就是 n，由于时间复杂度用大 O 符号表示，所以可记为 O(n) 。还有一点就是，如果一个基本语句执行次数为 n * 1/2，那也要记为 O(n)，其他的情况也可由此推断。

        空间复杂度则是根据算法所用的额外存储空间来判断，也用大 O 符号表示。注意，这里的额外存储空间不包括输入数据本身所占的空间，只考虑算法所用的辅助空间。

        到这，我们可以发现，时间复杂度越小，那耗费的时间就越少，算法效率就越高，空间复杂度也是同理。那为了提高算法效率，我们自然是希望这两个复杂度越小越好，但在某些情形下，我们不可避免地要对其进行选择，因为此时若是减小时间复杂度，空间复杂度就会增大，而若是减小空间复杂度，就会使时间复杂度增大。对此，我们需要对实际情况有充分地了解，进而更好地根据实际情况来进行选择，找到其中的平衡点。

附：若有不足，望指出。

        ^_^感谢^_^