数据结构和算法教程

什么是数据结构?

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

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

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

数据结构的特征

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

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

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

数据结构的需要

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

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

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

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

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

执行时间案例

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

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

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

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

基本术语

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

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

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

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

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

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

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

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

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


猿狮妹
2022-12-05
数据结构 算法 教程 编程课程
热门教程
1 二进制搜索/查找程序(C语言) 二进制搜索/查找程序( C语言),如下代码所示: #include stdio.h#define MAX 20// array of items on which linear search will be conducted. int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};void pri
2 数据结构和算法教程 数据结构是存储数据,使数据可以有效地应用于编程方法。几乎每一个企业应用程序中的一个或其他的方式使用不同类型的数据结构。本教程介绍企业级应用和需求的算法,数据结构的复杂性需要的数据结构。
3 数据结构渐近分析 算法的渐近分析,指的是定义它的运行时性能的数学基础/帧。利用渐近分析,我们可以很好地得出一种算法结论:最好的情况,平均情况和最坏的情况。 渐近分析输入的约束,即如果
4 递归基础知识 一些计算机编程语言允许一个模块或函数来调用自身。这种技术被称为递归。在递归函数α直接调用自己或调用函数β,反过来调用原函数α。该函数α被称为递归函数。 特性 递归函数可
5 链表实例程序(C语言) 下面是用 C语言来实现链表的一个实例程序,具体细节如下: #include stdio.h#include string.h#include stdlib.h#include stdbool.hstruct node { int data; int key; struct node *next;};struct node *head = NULL;struct node *
6 线性搜索实例程序(C语言) 线性搜索实例程序,使用 C语言实现如下所示: #include stdio.h#define MAX 20// array of items on which linear search will be conducted.int intArray[MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};void printlin
7 线性搜索(查找) 线性搜索是一个非常简单的搜索算法。在这种类型的搜索,顺序查找是由在所有项目一个接一个来的。 每一个项目一个一个地检查,如果找到匹配则特定数据项被返回,否则继续搜索,
8 数据结构基本概念 数据结构是一种能够以这样一种方式,它可以有效地利用组织的数据。本教程介绍了相关的数据结构的基本条件。 数据定义 数据定义定义了以下特征的特定数据。 Atomic − 定义应该定
9 哈希表 哈希表是一个数据结构,其中插入和搜索操作都非常快而不管哈希表的大小。 这几乎是一个常数或 O(1)。哈希表使用数组作为存储介质,并使用散列技术来生成索引,其中的元素是被插
10 队列实例代码(C语言) 队列实例代码(C语言),具体的实现如下代码所示: QueueDemo.c #include stdio.h#include string.h#include stdlib.h#include stdbool.h#define MAX 6int intArray[MAX];int front = 0;int rear = -1;int itemCount = 0;int peek(){
  • Copyright © 2021 猿狮院, All rights reserved.