锐客网

  1. 首页 > it技术 > >

33 数据结构 数组 链表 栈 队列

数组 场景：数量固定，不需要频繁插入删除时。
优点：占用空间小，支持随机访问。
链表 场景：数量不确定，需要频繁插入删除时。
栈 场景：
1.浏览器的回退和前进功能
2.检查符号是否成对出现（{}）
3.反转字符串
4.维护函数调用（虚拟机栈）
队列 场景：
1.生产者-消费者模型
图 度：表示一个顶点连着多少边。
入度：指向顶点的边。
出度：顶点指向别的顶点的边。
无权图和带权图：边有权重
图的存储 1 使用矩阵存储，A[X,Y]表示x y两顶点之间的关系

  • 无向图：矩阵内容是角对称的1 0 1 0
  • 有向图：矩阵内容是不对称的1 0 1 0
    2 使用链表储存：
  • 无向图：X-Y-Z-K表示x和yzk相连。
  • 有向图：X-Y-X-K表示x指向yzk
    图的搜索广度优先搜索：先搜索x，然后搜索x直接相连的xy，xz，然后搜索隔一层的xyk，xyj。可以利用队列。
    深度优先搜索：先搜索x，然后搜索xy，然后xyk，然后再xz。可以利用栈实现。
    堆初始化有序数组的时间：Onlogn
    初始化堆的时间：Onlogn
    从堆里插入删除数据的时间：Ologn
    用数组存储二叉树：根是节点1，左子树是21，右子树是21+1
    插入堆
  • 将要插入的元素放到最后
  • 【33 数据结构 数组 链表 栈 队列】如果该节点的父节点不如他大，则交换。直到父节点比自己大。
    删除堆顶方法1
  • 删除堆顶，空出堆顶。
  • 左右子树，大的成为堆顶，空出位置。
  • 循环，直到没有空位。
    方法2
  • 删除堆顶，把末尾的数放到堆顶
  • 左右子树和末尾，谁大谁做堆顶，和末尾换位。
  • 循环，直到末尾回到末尾。
    堆排序
  • 将无序数组建立为一个堆
  • 将堆顶和堆底位置调换，对剩下的n-1个元素堆化，然后把新堆顶和倒数第二个位置调换，循环。
  • 循环。
    建堆
  • 如果有n个节点，则第1个节点到第n/2个节点是有叶子节点的。从第N/2个节点开始整理，一直到第1个节点。堆化就完成了。

    推荐阅读


    上一篇：31 linux

    下一篇：34 布隆过滤器