上一次修改时间:2016-07-05 11:03:31

数据结构笔记

  1. 线性表、树、图的关系

    1)线性表如数组,不管是连续存储或离散存储都不能反应数据之间的层级关系,比如要存储一个公司的组织架构图,只能用树存储;

    2)树能表示上下级的层级关第,但不能表示如寻路算法中,需要求任意两点之间的最短路径,此时只能用图;

  2. 算法依据数据的存储结构,数据的存储结构不同,对应的算法也不相同;

  3. 衡量算法的四个标准,主要是前两个

    1)时间复杂度,程序执行的次数,如循环里一次循环算一次;

    2)空间复杂度,程序执行时占用的内存大小;

    3)可读性

    4)健壮性

  4. 栈和队列都是表(线性表或链表);

  5. 树的先序遍历可以用于树的目录结构打印,后序遍历可以用于计算目录的大小,中序遍历可以用于计算表达式树T的值;

  6. 树的先序遍历时从根节点开始,依据树的深度依次遍历;后序遍历时先计算出所有节点的值,再进行遍历;中序遍历时,先分别计算出左右子树的值;