线性表、树、图的关系
1)线性表如数组,不管是连续存储或离散存储都不能反应数据之间的层级关系,比如要存储一个公司的组织架构图,只能用树存储;
2)树能表示上下级的层级关第,但不能表示如寻路算法中,需要求任意两点之间的最短路径,此时只能用图;
算法依据数据的存储结构,数据的存储结构不同,对应的算法也不相同;
衡量算法的四个标准,主要是前两个
1)时间复杂度,程序执行的次数,如循环里一次循环算一次;
2)空间复杂度,程序执行时占用的内存大小;
3)可读性
4)健壮性
栈和队列都是表(线性表或链表);
树的先序遍历可以用于树的目录结构打印,后序遍历可以用于计算目录的大小,中序遍历可以用于计算表达式树T的值;
树的先序遍历时从根节点开始,依据树的深度依次遍历;后序遍历时先计算出所有节点的值,再进行遍历;中序遍历时,先分别计算出左右子树的值;