数据结构
2022-06-30 19:08:40 0 举报
AI智能生成
数据结构
作者其他创作
大纲/内容
支持 O(1) 的随机访问
平均为 O(n) 的插入和删除
警惕越界错误,导致 Stack Over Flow
数组
顺序结构
不支持随机访问,需要遍历去访问结点
插入和删除只需要移动指针,时间复杂度为 O(1)
每个结点需要额外的空间存储指针,需要的内存比数组大
单链表
在单链表的基础上,除头结点外,每个结点多了一个存放前驱结点内存地址的指针
双链表
尾节点指针指向头结点
循环链表
借助数组,伴随指向后继结点的指针
静态链表
链式结构
非受限线性表
顺序和链式都可以实现,先进后出
浏览器的前进与后退
括号匹配
表达式计算
实际应用
栈
大顶堆
小顶堆
找第 K 大元素
实际应用
堆
顺序和链式都可以实现,先进先出
普通队列
入口和出口都可以进队和出队
双边队列
根据优先级来出队
优先级队列
LRU Cache
实际应用
队列
受限线性表
顺序和链式都可以实现
广度优先搜索
前序遍历
中序遍历
后序遍历
深度优先搜索
遍历方式
特点
完全二叉树
满二叉树
二叉搜索树
红黑树
平衡二叉搜索树
二叉树
哈夫曼树
字典树
树与二叉树
冒泡排序
插入排序
选择排序
O(n^2)
快速排序
归并排序
O(nlogn)
桶排序
计数排序
基数排序
O(n)
排序
数据结构
0 条评论
回复 删除
下一页