数据结构和算法教程

管理员 数据结构和算法教程

本文章向大家介绍数据结构和算法教程,主要包括数据结构和算法教程使用实例、应用技巧、基本知识点总结和需要注意事项,具有一定的参考价值,需要的朋友可以参考一下。

什么是数据结构?

数据结构是组织数据,以便有效地使用它的系统方法。下列术语的数据结构的基础方面。

  • 接口 − 每个数据结构有一个接口。接口表示一个数据结构支持的操作集合。一个接口仅提供支持的操作的列表,参数类型,他们可以接受并返回这些操作的类型。

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

数据结构的特征

  • 正确性 − 数据结构的实现应该正确地实现它的接口。

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

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

数据结构的需要

随着应用程序越来越复杂和数据丰富,有三种常见的问题应用要面临。

  • 数据搜索 − 考虑100万(106)物品商店的清单。如果应用程序搜索一个项目。它需要搜索项目100万次(106) 项目每次减慢搜索。随着数据的增长,搜索将变得更加缓慢。

  • 处理器速度 − 处理器速度虽然是非常高的,属于有限的,如果数据增长到十亿的记录。

  • 多个请求 − 随着成千上万的用户可以同时搜索Web服务器上的数据,甚至是非常快的服务器,也有可能搜索数据失败。

为了解决上述问题,使用数据结构来解救。数据可以组织在数据结构中,使得在一种方式在所有的项目可以不要求搜索和所需的数据,可几乎立即搜索。

执行时间案例

有三种情况通常用于相对地对各种数据结构的执行时间进行比较。

  • 最坏的情况 − 这是一个特定的数据结构操作,需要采取的最大时间的方案。如果一个操作的最坏情况下的时间是:ƒ(n),那么这个操作不会花时间超过ƒ(n)的时间,其中: ƒ(n)表示n个函数。

  • 平均情况 − 这是该方案描绘的数据结构的一个操作的平均执行时间。如果一个操作需要:ƒ(n)时间执行,则 m 的操作将采取mƒ(n)的时间。

  • 最佳案例 − 这是该方案描绘的数据结构的一个操作,至少可能的执行时间。如果一个操作需要ƒ(n)的时间,然后执行实际操作可能需要一段时间的随机数,这将是最大到 ƒ(N)。

基本术语

  • 数据 − 数据值或设定值。

  • 数据项 − 数据项是指值的一个单元。

  • 组项 − 被划分为子项数据项被称为组项目。

  • 基本项目 − 不能分割数据项被称为基本项目。

  • 属性和实体 − 实体是含有某些属性或可被分配的值的属性。

  • 实体集 − 类似属性的实体构成的实体集。

  • 字段 − 字段是信息表示一个实体的属性单个基本单元。

  • 记录 − 记录是一个给定的实体的字段值的集合。

  • 文件 − 文件是在给定实体集的实体记录的集合。