数据结构和算法(一)——简介

前言

学习数据结构与算法能够让你了解该用什么数据结构储存数据,这涉及到编程中关键的性能和效率问题。

数据结构

数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的基本功能,可归纳为增删改查及遍历。

数据结构可分为逻辑结构和物理结构:

逻辑结构

数据对象中数据元素的关系

  1. 集合结构:数据元素同属于一个集合,没有其他关系。
  2. 线性结构:数据元素之间事一对一的关系。
  3. 树状结构:数据元素之间是一对多关系。
  4. 图形结构:数据元素之间是多对多关系。

物理结构

数据的逻辑结构在计算机中的储存方式。

  1. 顺序结构:数据元素存放在地址连续的储存单元里,其数据间的逻辑关系和物理关系。

  2. 链式储存结构:数据元素存放在任意的储存单元里,同是需要指针储存下一个元素的地址。

算法

算法简单来说就是解决问题的步骤。

五要素

  • 有穷性。
  • 确定性。
  • 可行性。
  • 有输入。
  • 有输出。

设计原则

  • 正确性。
  • 可读性。
  • 健壮性。
  • 高效率与低存储量需求。

复杂度

一般只关注时间复杂度。

注:当然,空间复杂度本身也有其存在的意义,尤其是在对空间效率非常在乎的应用场合,或者是当问题的输入规模极为庞大时。

时间复杂度

表示算法复杂度的度量记号大 O 级别,常见的时间复杂度:

  • 常数阶O(1)
  • 线性阶O(n)
  • 平方阶O(n²)
  • 对数阶O(log n)
  • 线性对数阶O(n log n)

时间复杂度分析方法:

  1. 只关注循环执行次数最多的一段代码。
  2. 总复杂度等于量级最大的那段代码的复杂度。
  3. 嵌套代码的复杂度等于嵌套你内外代码复杂的的乘积。

空间复杂度分析

表示算法的储存空间与数据规模之间的增长关系。

int[] a = new int[n]

这段代码的空间复杂的就是O(n)。

数组

线性、顺序结构,储存同一种数据类型(Object数组除外)。

随机访问

因为是连续的内存空间,很容易根据下标定位到内存地址。

低效的插入和删除

插入和删除数组末尾,时间复杂度为O(1),其他位置插入元素设计到元素的位置的移动,平均复杂度为O(n),效率低下。

链表

线性、链式结构

链表类型

  1. 单链表

    链表有一个头指针指向链表的第一个节点,最后一个节点指向空。

  2. 循环链表

    循环链表的尾结点指针是指向链表的头结点。

  3. 双向链表

    双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历。

查找慢、插入删除很快

一般我们都使用双向链表,因为它能够很快定位到前驱和后继节点。

因为链表是链式储存结构,定位元素只能通过遍历,复杂度为O(n);

针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是 O(1)。

只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性

栈的应用

  • 符号匹配
  • 中缀表达式转换为后缀表达式
  • 计算后缀表达式
  • 实现函数的嵌套调用
  • HTML 和 XML 文件中的标签匹配
  • 网浏览器中已访问页面的历史记录

队列

队列是一种线性表,它支持 先进先出(FIFO)

尾部添加、头部删除,跟我们生活中的排队类似

队列类型

  1. 单队列

    单队列就是常见的队列, 每次添加元素时,都是添加到队尾:

    单队列会出现“假溢出”现象,每次从队首删除元素,元素都要上前移动一个位置,能放的空位就相对减少了。

  2. 循环队列

    我们可以将队列看成一个首位相连的环。当一个元素从队列删除后,新空余出来的空间可以作为队列的尾部。

队列应用

消息队列中间件

树状结构,像是一个倒挂的树。

基本术语

节点:根节点、叶节点、叶子节点、父节点、子节点、兄弟节点。

高度:

文章目录
  1. 1. 前言
  2. 2. 数据结构
    1. 2.1. 逻辑结构
    2. 2.2. 物理结构
  3. 3. 算法
    1. 3.1. 五要素
    2. 3.2. 设计原则
  4. 4. 复杂度
    1. 4.1. 时间复杂度
    2. 4.2. 空间复杂度分析
  5. 5. 数组
    1. 5.1. 随机访问
    2. 5.2. 低效的插入和删除
  6. 6. 链表
    1. 6.1. 链表类型
    2. 6.2. 查找慢、插入删除很快
  7. 7.
    1. 7.1. 栈的应用
  8. 8. 队列
    1. 8.1. 队列类型
    2. 8.2. 队列应用
  9. 9.
    1. 9.1. 基本术语
|