概述学习手册

收录于 2023-04-20 00:10:05 · English · بالعربية · Español · हिंदीName · 日本語 · Русский язык · 中文繁體

数据结构是一种组织数据以有效使用数据的系统方法。以下术语是数据结构的基础术语。
Interface-每个数据结构都有一个接口。接口表示数据结构支持的一组操作。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。 Implementation-实现提供数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。

数据结构的特征

正确性-数据结构实现应正确实现其接口。 时间复杂度-运行时间或数据结构操作的执行时间必须尽可能小。 空间复杂度-数据结构操作的内存使用应尽可能少。

需要数据结构

随着应用程序变得越来越复杂和数据丰富,应用程序现在面临三个常见问题。
数据搜索-考虑商店的 100 万(106)个商品的库存。如果应用程序要搜索一个项目,它每次都必须在 100 万(106)个项目中搜索一个项目,这会减慢搜索速度。随着数据的增长,搜索速度会变慢。 处理器速度-处理器速度虽然非常高,但如果数据增长到十亿条记录,则会受到限制。 多个请求-由于成千上万的用户可以同时在 Web 服务器上搜索数据,即使是快速服务器在搜索数据时也会失败。
为了解决上述问题,数据结构来拯救。可以将数据组织在数据结构中,这样可能不需要搜索所有项目,并且几乎可以立即搜索所需的数据。

执行时间案例

通常用于比较各种数据结构的执行时间的三种情况。
Worst Case-这是特定数据结构操作需要最大时间的情况。如果一个操作的最坏情况时间是 ƒ(n),那么这个操作将不会超过 ƒ(n) 时间,其中 ƒ(n) 表示 n 的函数。 Average Case-这是描述数据结构操作的平均执行时间的场景。如果一个操作需要 ƒ(n) 时间执行,那么 m 个操作将需要 mƒ(n) 时间。 Best Case-这是描述数据结构操作的最短执行时间的场景。如果一个操作需要 ƒ(n) 时间执行,那么实际操作可能需要时间作为随机数,最大为 ƒ(n)。

基本术语

Data-数据是值或值集。 Data Item -数据项是指单个值单位。 Group Items-分为子项的数据项称为 Group Items。 Elementary Items-不能分割的数据项称为基本项。 Attribute and Entity-实体是包含某些属性或属性的实体,这些属性或属性可以被赋值。 Entity Set-具有相似属性的实体形成实体集。 Field-字段是表示实体属性的单个基本信息单元。 Record-记录是给定实体的字段值的集合。 File-文件是给定实体集中实体的记录集合。