C++ 数组、链表和二叉树的比较
2021-04-10 02:28
标签：https 必须 存储 关系 二叉树 操作 速度 难度 完全二叉树 数组：按序号访问元素，连续存储，元素可以有序、也可以无序，用下标来定位元素，元素的数量确定(有上限)，按下标访问很快，插入和删除元素、排序的开销比较大(元素的移位操作)，数组元素无序时，元素的排序速度比较慢(依次比较)，数组元素有序时，元素的查找速度比较慢(二分查找，比无序时快)。 链表：插入、删除方便；元素数量不受限制。非连续存储，元素可以有序、也可以无序；查找、访问元素的开销比较大：依次比较每一个元素。元素的数量不受限制。插入和删除元素、排序的开销比较小(修改指针域)。 二叉树：插入、删除方便，查找快。非连续存储，元素一定是有序(建树时判定在左子树、还是右子树上需要有依据)，查找、访问元素的开销比较小(比较次数不超过二叉树的深度)，元素的数量不受限制，插入和删除元素、排序的开销比较小(修改指针)。 数组、链表、二叉树各自适用的场合 数组：数据集中元素的数量基本可以确定；不需要频繁的插入、删除。 链表：需要频繁的插入、删除元素；不可预知元素的数量范围。 二叉树：需要频繁的插入、删除、查找元素。 发挥二叉树的优势：必须降低二叉树的深度，同样的深度，完全二叉树能够保存的元素数量最多。但除非在建树时，就按照顺序添加节点，否则构造的难度大，退而求其次：建立平衡二叉树。每个节点，它的左子树与右子树的深度之差不超过1。 对大规模的元素序列进行排序，比如有几万个、甚至更多的元素 用数组：频繁的数组元素交换 链表：越往后，插入一个元素需要的比较次数与已排序元素的数量成线性增加。 平衡二叉树：越往后，插入一个元素需要的比较次数与已排序元素的数量按对数关系增加。 参考：https://jingyan.baidu.com/article/d5c4b52b1e42d99a560dc588.html C++ 数组、链表和二叉树的比较 标签：https 必须 存储 关系 二叉树 操作 速度 难度 完全二叉树 原文地址：https://www.cnblogs.com/zhibei/p/13371223.html