（三） 数组和链表的区别

数 组不允许动态地定义其大小 ， 只能够将其定义成足够大小 ， 这样可能会造成空间的浪 费。 数组在内存中是顺序的存储 ， 可以以 O(1) 时间查找元素 ， 但是需要 O(n) 时间插入和删 除元素（因为其后面的元素都需要跟着移动）。 链表可以动态地定义其大小 。 其在内存中是链式的存储 ， 访问元素是需要从头开始向后 顺序访问 ， 所以需要 O(n) 时间查找元素 ； 如果在所需位置直接插入或删除元素 ， 需要 O(1) 时间，如果在需要先找到所需位置再插入或删除元素，需要 O(n) 时间。

树的代价

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积带权路径长度最小 ( 即代价最小 ) 的二叉树称为最优二叉树或哈夫曼树。

基本概念与术语

1 、数据 : 数据是对客观事物的符号表示 , 在计算机科学中是指所有能输入到计算机中并 被计算机程序所处理的符号的总称。

2 、 数据元素 : 数据元素是数据的基本单位 , 是数据这个集合中的个体 , 也称之为元素 , 结点 ， 顶点记录。 ( 补充 ： 一个数据元素可由若干个数据项组成 。 数据项是数据的不可分割的最小单位 。 )