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