跳至主要內容

数据结构

xuweiqiang大约 8 分钟

数据结构

一、数据结构起源

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。程序简单来说就是程序设计 = 数据结构 + 算法。

  1. 逻辑结构

定义: 数据对象之间数据元素之间的相互关系

  • 集合结构
  • 线性结构
  • 树形结构
  • 图形结构
  1. 物理结构
  • 顺序存储。数据在内存块上连续有序分配比如数组。
  • 链式存储。数据在内存块位置不连续但是在程序中有指针将这些串起来比如链表。

二、算法时间复杂度

  1. 算法和时间复杂度是什么意思

告诉我算法是什么？算法让你快速获取1+2+3+..+100的结果，算法说白了就是一种计算规则。获得上述题目结果的方式普通人想到的是一个个加起来，高斯想到的是：

int i,sum =0,n=100
sum = (1 + n) * n / 2

时间复杂度，可以认为得到这个结果需要的执行步骤。步数越大，时间复杂度越大。程序行业用一个公式表示时间复杂度，那就是T(n) = O(f(n))，详细说明如下:

# n表示元素个数
# T(n)表示算法的运行时间
# 大O符号表示时间复杂度
# f表示执行方法
# 简单认为: 执行时长 = 时间复杂度[执行方法[元素个数]]
T(n)  = O(f(n))
  1. 常见的时间复杂度级别

  • 常数阶O(1)

    比如哈希算法，只需要一个步骤就能获取到结果或者数组只需要一个标就能拿到值。散列表查找，直接根据查找值计算hash算法获取地址或者高斯算法。

    int sum = 0,n = 100;        /* 执行一次 */
sum = (1 + n) * n / 2;      /* 执行一次 */
printf（"%d", sum）;         /* 执行一次 */

  • 线性阶O(n)

    比如链表查询,查询一个元素的最大时间有可能需要遍历整个n个元素的链表。比如有序链表顺序查找(执行n次)

    int i;
for（i = 0; i < n; i++）
{
    /* 时间复杂度为O(1)的程序步骤序列 */
}

  • 对数阶O(LogN)

    如二分法查找，查找一个8个元素的链表使用二分法最多需要3个步骤,3 = Log2(8)。二分法查找算法就是对数阶，底数是2^x=n 得到x=log2n，时间复杂度为O(logN):

    int count = 1;
while （count < n）
{
    count = count * 2;
    /* 时间复杂度为O(1)的程序步骤序列 */
}

  • 平方阶O(n^2)

    外层循环次数为n,内部也为n，时间复杂度为O(n^2):

    int i,j;
for（i = 0; i < n; i++）
{
    for（j = 0; j < n; j++）                       
    {                                      
        /* 时间复杂度为O(1)的程序步骤序列 */
    }                                      
}

  • 立方阶O(n^3)

  • 指数阶O(2^n)

# 时间复杂度由小到大
# 指数是最慢的因为元素个数n的增长会带来时间复杂度猛涨
O(1) < O(logn) < O(n) < O(n^2) < O(n^3) < O(2^n)
  1. 空间复杂度

算法的空间复杂度指的是在运行过程中临时占用存储空间大小的量度。空间复杂度衡量的是算法所需的存储空间。算法空间复杂度的计算公式记作：S(n)=O(f(n))。

三、线性表

  1. 定义

零个或多个有限序列，单条线，元素前面后面都只有一个(多个就不是了)，这就叫线性表。常见的线性表有数组。

  1. 线性表顺序存储结构

地址连续的存储单元存储线性表的数据元素，注意：地址连续，比如数组的内存地址连续的。

  1. 查找时间复杂度

假设一个线性表元素是a0 a1 ~ an,存储器之中的每个存储单元都有自己的编号，这个编号也就是地址0 1 2 3...，算位置的方式就是(假设每个元素占据c个存储单元)，Location(ai) = Location(a1) + c(i-1)，所以获取地址的算法，任意一个元素的时间复杂度都是一样的 O(1)，所以数组下标找元素只需要一个步骤。

  1. 删除或新增元素的时间复杂度

删除元素需要将后面的元素每个往前挪一个位置所以最大是O(n)，不过如果删除最后一个元素时间复杂度就是O(1)，大 O 记号（渐近上界）表示时间复杂度最大的情况所以数组的插入时间复杂度是O(n)。而插入元素也是一样的，时间复杂度是O(n)。

  1. 内存碎片是啥意思

内部碎片就是已经被分配出去却不能被利用的内存空间。

  1. 链式存储结构（单链表）的时间复杂度

链表的特征就是数据元素在存储上不按顺序，只需要元素存储它下一个单元地址（指针）。插入节点的时候不需要惊动所有节点，只需要将某一个节点的next指针指向更改就可以了，删除节点的也是一样的。所以插入和删除的时间复杂度是O(n)，查找的时间复杂度也是O(n)。插入或删除数据越频繁的操作，单链表的效率对比数组优势就越是明显。单链表不需要预分配存储空间，数组是一开始就分配了连续的存储空间，链表是加一个元素分配一个元素的内存空间。

  1. 线性表分类
  • 顺序表指的是一整块足够大小的物理空间，依次存储数据。
  • 单链表指链表存储的数据元素，物理存储位置随机，每个元素存储时配备指针，指向直接后继元素。
  • 静态链表指的是用数组来模拟链表的数据结构。内存是连续和预先分配的，但是又有指针，删除和新增元素不需要挪动后面所有元素位置，查询数据又可以使用下标直接访问。每个元素存储游标cur指向下一个后继元素，插入元素只需要更改插入的前一个节点和元素本身的cur。
  • 动态链表，特征是链表在初始时不一定分配足够的空间, 但是在后续插入的时候需要动态申请存储空间
  • 单向链表，无论动态还是静态，每一个元素都统一指向直接后继节点
  • 双向链表，每个节点不但有指针指向后继元素，还有一个指针域指向前面元素
  • 循环链表指的是单链表的终端结点的指针指向头节点，环状链表，成为循环链表

四、栈和队列

  1. 栈

栈是一种只能从表的一端存取数据且遵循LIFO（Last - In - First - Out）后进先出的原则的存储结构，注意是线性存储结构，有顺序的栈顶是开口端， 栈底封口端表示无法获取数据，存储角度有顺序存储结构和链式存储结构。

  1. 队列

队列的特征是先进先出（FIFO）,实现有顺序队列比如数组特征是内存连续固定大小并且使用下标访问速度快，链式队列比如链表特点是动态大小。

五、堆

数据结构，堆是一种特殊的树形数据结构。是一个完全二叉树，完全二叉树意味着除了最后一层外，每一层都是满的，并且最后一层的节点是从左到右依次排列的。堆分为两种类型：最大堆和最小堆。最大堆每个节点的值都大于或等于它的子节点的值所以根节点的值是整个堆中最大的。最小堆每个节点的值都小于或等于它的子节点的值所以根节点的值是整个堆中最小的。

六、图

  1. 概念

图（Graph）是一种数据结构，用于表示对象之间的关系。顶点（Vertex，也称为节点 Node）集合和边（Edge）集合组成。在社交网络中，可以将每个用户看作一个顶点，用户之间的好友关系看作边。如果用户 A 和用户 B 是好友，那么在图中就有一条连接顶点 A 和顶点 B 的边。

  1. 广度优先

广度优先遍历（Breadth - First Search，BFS）,从一个顶点开始，先访问该顶点的所有邻接顶点，然后依次访问这些邻接顶点的邻接顶点，以此类推，就像一层一层地向外扩展访问。

  1. 深度优先

深度优先遍历（Depth - First Search，DFS），从一个顶点开始，沿着一条路径尽可能深地访问顶点，直到不能再前进，查找不到元素再回来顶点，继续探索其他路径。

相关文章