数据结构&算法 教程
-
数据结构&算法概述
数据结构是存储数据的编程方式，因此可以有效地使用数据。几乎每个企业应用程序都以一种或另一种方式使用各种类型的数据结构。本教程将使您对理解企业级应用程序的复杂性以及算法和数据结构的需求所需的数据结构有很好的了解。数据结构是一种组织数据以有效使用数据的系统方法。以下术语是数据结构的基础术语。- 接口 - 每个数据结构都有一个接口。接口表示数据结构支持的一组操作。接口仅提供支持的操作的列表，它们可以接受的参数类型以及返回这些操作的类型。
- 实现 - 实现提供数据结构的内部表示。实现还提供了在数据结构操作中使用的算法的定义。
-
数据结构的特征
- 正确性 -数据结构实现应正确实现其接口。
- 时间复杂度 -数据结构的运行时间或操作的执行时间必须尽可能短。
- 空间复杂度 -数据结构操作的内存使用应尽可能少。
-
数据结构需求
随着应用程序变得越来越复杂和数据越来越丰富，当今应用程序面临三个常见问题。- 数据搜索 - 考虑一家商店的一百万（106）件商品的库存。如果应用程序要搜索商品，则每次使搜索速度变慢时，它都必须搜索一百万（106）个项目中的项目。随着数据的增长，搜索将变得越来越慢。
- 处理器速度 - 处理器速度虽然很高，但是如果数据增长到十亿条记录，则会受到限制。
- 多个请求 - 由于成千上万的用户可以在Web服务器上同时搜索数据，因此即使快速服务器在搜索数据时也会失败。
为了解决上述问题，数据结构得以抢救。可以以不需要搜索所有项目的方式将数据组织在数据结构中，并且几乎可以立即搜索所需的数据。 -
执行时间案例
通常有三种情况以相对方式比较各种数据结构的执行时间。- 最坏的情况 - 在这种情况下，特定的数据结构操作将花费最多的时间。如果操作的最坏情况时间为ƒ(n)，则此操作将花费不超过ƒ(n)时间，其中ƒ(n)表示n的函数。
- 平均情况 - 这是描述数据结构操作的平均执行时间的场景。如果一个操作花费ƒ(n)时间执行，则m个操作将花费mƒ(n)时间。
- 最佳情况 - 这是描述数据结构操作最少可能执行时间的场景。如果某个操作在执行中花费ƒ(n)时间，则实际操作可能会花费时间作为随机数，而该随机数最大可能为ƒ(n)。
-
基本术语
通常有三种情况以相对方式比较各种数据结构的执行时间。- 数据 - 数据是值或值集。
- 数据项 - 数据项是指值的单个单位。
- 组项目 - 分为子项目的数据项目称为组项目。
- 基本项目 - 无法分割的数据项目称为基本项目。
- 属性和实体 - 实体是包含某些属性或属性的实体，可以为其分配值。
- 实体集 - 相似属性的实体形成一个实体集。
- 字段 - 字段是表示实体属性的单个基本信息单元。
- 记录 - 记录是给定实体的字段值的集合。
- 文档 - 文档是给定实体集中实体记录的集合。
-
数据结构和算法的应用
算法是一个分步过程，它定义了一组指令，这些指令将以某种顺序执行以获得所需的输出。通常，算法是独立于基础语言而创建的，即，一种算法可以用一种以上的编程语言来实现。从数据结构的角度来看，以下是算法的一些重要类别-- 搜索 - 在数据结构中搜索项目的算法。
- 排序 - 按特定顺序对项目进行排序的算法。
- 插入 - 将项目插入数据结构的算法。
- 更新 - 更新数据结构中现有项目的算法。
- 删除 - 从数据结构中删除现有项目的算法。
使用数据结构可以解决以下计算机问题-- 斐波那契数列
- 背包问题
- 汉诺塔
- 所有节点最短路径 - Floyd-Warshall 算法
- 最短路径图算法 - Dijkstra
- 项目调度
-
听众
本教程适用于愿意通过简单的步骤学习数据结构和算法编程的计算机科学专业的毕业生以及软件专业人士。完成本教程后，您将处于中等专业知识水平，从这里您可以进入更高的专业知识水平。 -
先决条件
在继续本教程之前，您应该对C编程语言，文本编辑器和程序执行等有基本的了解。