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