使用 C 语言的 DSA - 概述

什么是数据结构？

数据结构是一种组织数据以使其能够有效使用的方法。以下术语是数据结构的基础术语。

  • 接口- 每个数据结构都有一个接口。接口代表数据结构支持的操作集。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。

  • 实现- 实现提供数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。

数据结构的特征

  • 正确性- 数据结构实现应该正确实现其接口。

  • 时间复杂度- 数据结构操作的运行时间或执行时间必须尽可能小。

  • 空间复杂度- 数据结构操作的内存使用量应尽可能少。

对数据结构的需求

随着应用程序变得越来越复杂且数据越来越丰富，应用程序现在面临三个常见问题。

  • 数据搜索- 考虑商店的100 万（10 6 ）件商品的库存。如果应用程序是搜索一个项目。每次它必须搜索 100 万（10 6 ）个项目，这会减慢搜索速度。随着数据的增长，搜索会变得更慢。

  • 处理器速度- 虽然处理器速度非常高，但如果数据增长到十亿条记录，处理器速度就会受到限制。

  • 多个请求- 由于数千个用户可以在 Web 服务器上同时搜索数据，因此即使非常快的服务器在搜索数据时也会失败。

为了解决上述问题，数据结构就派上用场了。数据可以以这样的方式组织在数据结构中：不需要搜索所有项目并且几乎可以立即搜索所需的数据。

执行时间案例

通常使用三种情况以相对方式比较各种数据结构的执行时间。

  • 最坏情况- 这是特定数据结构操作花费最大时间的情况。如果操作的最坏情况时间为 f(n)，则该操作所花费的时间不会超过 f(n) 时间，其中 f(n) 表示 n 的函数。

  • 平均情况- 这是描述数据结构操作的平均执行时间的场景。如果执行一个操作需要 f(n) 时间，则 m 个操作将花费 mf(n) 时间。

  • 最佳情况- 这是描述数据结构操作的最短可能执行时间的场景。如果一个操作在执行中需要 f(n) 时间，那么实际操作可能会花费随机数的时间，该时间最大为 f(n)。