808 数据结构 绪论

数据结构三要素

可以用抽象数据类型定义一个完整的数据结构

树是非线性数据结构

顺序表 单链表 哈希表 即描述逻辑又描述存储
有序表 仅描述逻辑结构 因为他既可以是链式存储也可以是顺序存储

栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。

数据的逻辑结构独立于其存储结构 而存储结构还是会受到逻辑结构的影响。
数据的逻辑结构是从面向实际问题的角度出发的，只采用抽象表达方式，独立于存储结构， 数据的存储方式有多种不同的选择；而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

在存储数据时 不仅仅存储数据元素的值 也要存储数据元素之间的关系

链式存储设计时 结点内的存储单元地址一定连续 各个结点之间的存储空间可以不连续

对于两种不同的数据结构 逻辑结构或者物理结构一定不相同吗
1

数据结构有三要素 还跟数据的运算有关。

试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同
1

顺序表和单链表 存取数据 增删改查时 运算效率都不同

算法和算法评价

一个算法应该满足五个基本特性 这只是算法的必要条件，不能是算法的定义
算法是对问题求解步骤的描述，而程序则是算法在计算机上的特定实现。

某算法的时间复杂度是O(n的平方) 表明该算法的执行实际与n的平方成正比

算法原地工作的意思是算法所需要的辅助空间是常量 o(1)。
在相同规模"下，复杂度为o(n)的算法在时间上总是优于复杂度为o(2的n次方)的算法.
所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界.
同一个算法，实现语言的级别越高，执行效率越低.

已知两个长度分别为m和n的升序链表，若将它们合并为长度为m + n的一个降序链表，则最坏情况下的时间复杂度是o(max(m,n))

一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别（或阶）。

1,				 n = 1
2T(n/2) + n,	 n > 1
1
2

式中，n是问题的规模，为简单起见，设n是2的整数次幂.