使用 C 的 DSA - 概述
什么是数据结构？
数据结构是一种以高效使用数据的方式组织数据的方法。以下术语是数据结构的基础术语。
接口 − 每个数据结构都有一个接口。接口表示数据结构支持的一组操作。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。
实现 − 实现提供数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。
数据结构的特征
正确性 − 数据结构实现应正确实现其接口。
时间复杂度 − 数据结构操作的运行时间或执行时间必须尽可能小。
空间复杂度 − 数据结构操作的内存使用量应尽可能少。
数据结构需求
随着应用程序变得越来越复杂和数据丰富，应用程序现在面临三个常见问题。
数据搜索 − 考虑一家商店有 100 万 (106) 件商品的库存。如果应用程序要搜索一件商品。它每次都必须在 100 万 (106) 件商品中搜索一件商品，这会减慢搜索速度。随着数据的增长，搜索速度会变慢。
处理器速度 − 处理器速度虽然非常高，但如果数据增长到十亿条记录，速度就会受到限制。
多个请求 − 由于数千名用户可以同时在 Web 服务器上搜索数据，即使是非常快的服务器在搜索数据时也会失败。
为了解决上述问题，数据结构可以派上用场。数据可以以这样的方式组织在数据结构中，即可能不需要搜索所有项目，并且可以几乎立即搜索所需的数据。
执行时间情况
通常有三种情况用于以相对方式比较各种数据结构的执行时间。
最坏情况 − 这是特定数据结构操作花费最大时间的场景。如果操作的最坏情况时间是 ƒ(n)，那么该操作所花费的时间不会超过 ƒ(n) 时间，其中 ƒ(n) 表示 n 的函数。
平均情况 − 这是描述数据结构操作平均执行时间的场景。如果操作在执行中花费 ƒ(n) 时间，那么 m 个操作将花费 mƒ(n) 时间。
最佳情况 − 这是描述数据结构操作最短可能执行时间的场景。如果操作在执行中花费 ƒ(n) 时间，那么实际操作可能花费随机数的时间，最大值为 ƒ(n)。
