数据结构
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 条评论
下一页
