跳至主要內容

必备算法基础知识


数据结构是什么?

程序 = 数据结构 + 算法

上⾯这句话是⾮常经典的,程序由数据结构以及算法组成,当然数据结构和算法也是相辅相成
的,不能完全独⽴来看待,但是本⽂会相对重点聊聊那些常⽤的数据结构。

数据结构是什么呢?

⾸先得知道数据是什么?数据是对客观事务的符号表示,在计算机科学中是指所有能输⼊到计算机中并被计算机程序处理的符号总称。那为何加上“结构”两字?

数据元素是数据的基本单位,⽽任何问题中,数据元素都不是独⽴存在的,它们之间总是存在着某种关系,这种数据元素之间的关系我们称之为结构。

因此,我们有了以下定义:数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。通常情况下,精⼼选择的数据结构可以带来更⾼的运⾏或者存储效率。数据结构往往同⾼效的检索算法和索引技术有关。

简单讲,数据结构就是组织,管理以及存储数据的⽅式。虽然理论上所有的数据都可以混杂,或者糅合,或者饥不择⻝,随便存储,但是计算机是追求⾼效的,如果我们能了解数据结构,找到较为适合当前问题场景的数据结构,将数据之间的关系表现在存储上,计算的时候可以较为⾼效的利⽤适配的算法,那么程序的运⾏效率肯定也会有所提⾼。

常⽤的4种数据结构有:

  • 集合:只有同属于⼀个集合的关系,没有其他关系
  • 线性结构:结构中的数据元素之间存在⼀个对⼀个的关系
  • 树形结构:结构中的数据元素之间存在⼀个对多个的关系
  • 图状结构或者⽹状结构:图状结构或者⽹状结构

何为逻辑结构和存储结构?

数据元素之间的逻辑关系,称之为逻辑结构,也就是我们定义了对操作对象的⼀种数学描述。但是我们还必须知道在计算机中如何表示它。数据结构在计算机中的表示(⼜称为映像),称之为数据的物理结构,⼜称存储结构。

数据元素之前的关系在计算机中有两种不同的表示⽅法:顺序映像和⾮顺序映像,并且由此得到两种不同的存储结构:顺序存储结构和链式存储结构,⽐如顺序存储结构,我们要表示复数z1 =3.0 - 2.3i ,可以直接借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系:

⽽链式结构,则是以指针表示数据元素之间的逻辑关系,同样是z1 =3.0 - 2.3i ,先找到下⼀个是100 ,是⼀个地址,根据地址找到真实的数据-2.3i :

数组

详情请看数组

链表

详情请看链表

详情请看

队列

详情请看队列

哈希表

详情请看哈希表

详情请看

详情请看

详情请看

其他结构

十大经典排序算法

这里简单为大家讲解一下一些算法基础知识与十大排序,在面试考察中十大排序出现的频率是非常高的,特别是冒泡排序、快速排序、归并排序等,具体可点击这里

算法基本知识铺垫

有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度,这里先简单解释一下:

  1. 稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。
  2. 非稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。
  3. 原地排序:原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
  4. 非原地排序:需要利用额外的数组来辅助排序。
  5. 时间复杂度:一个算法执行所消耗的时间。
  6. 空间复杂度:运行完一个算法所需的内存大小

十大排序一图总览

十大排序中的稳定排序

  • 冒泡排序
  • 插入排序
  • 归并排序

十大排序中的非稳定排序

面试考察中一般问快排,选择,希尔,堆这几种非稳定排序

  • 选择排序
  • 希尔排序
  • 堆排序
  • 快速排序
seven97官方微信公众号
seven97官方微信公众号