数据结构与算法基础总结
线性表 |
性能类别 | 具体项目 | 顺序存储 | 链式存储 |
---|---|---|---|
空间性能 | 存储密度 | =1,更优 | 小于1 |
空间性能 | 容量分配 | 事先确定 | 动态改变,更优 |
时间性能 | 查找运算 | O(n/2) | O(n/2) |
时间性能 | 读运算 | O(1),更优 | O([n+1]/2),最好情况为1,最坏为n |
时间性能 | 插入运算 | O(n/2),最好情况为0,最坏为n | O(1),更优 |
时间性能 | 删除运算 | O([n-1]/2) | O(1),更优 |
栈:先进后出
队列:先进先出
队列 |
循环队列
判满:tail+1=head
判空:head=tail
图 |
邻接矩阵 |
假设图有n个节点,顶点编号为1,2,…n,用一个n阶方阵R来存放途中各节点的关联信息,其矩阵元素Rij定义为:R=1 若顶点i到顶点j有邻接边 0 若顶点i到顶点j无邻接边
邻接表 |
算法排序 |