绪论

1.知识框架

 

2.结构的基本术语

数据：信息的载体

数据元素：数据的基本单位

数据对象：具有系统性质的数据元素的集合，是数据的一个子集

数据类型：原子类型、结构类型、抽象数据类型

 

3.结构三要素

• 逻辑结构

  逻辑结构是指数据元素之间的逻辑关系，它与数据的存储无关，是独立与计算机的。

• 存储结构

  存储结构是指数据在计算机中的表示（又称映像），也称为物理结构。数据的存储结构是用计算机语言实现的逻辑结构，依赖于计算机语言

• 数据的运算：

  施加在数据上的运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤

  

4.算法的基本概念

  算法是对特定问题求解步骤的一种描述。是指令的有限序列。一个算法应该具备的5个重要特征：

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成
• 确定性：算法中的每个指令都必须有确切的含义，对于相同的输入只能得出相同的输出
• 可行性：算法中描述的操作都可以通过研究实现的基本运算执行有限次来实现
• 输入：一个算法有零个或多个输入，这些输入取自于某中特定的对象的集合
• 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

 

5.算法的目标

• 正确性：能够正确的解决求解问题
• 可读性：简洁可读，以帮助人理解
• 健壮性：当输入非法数据时，算法能适当地作出反应或进行处理，二不会产生奇怪的输出结果
• 效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间

 

6.算法效率的度量

  算法效率的度量是通过时间复杂度和空间复杂度来描述的

• 时间复杂度

  一个语句的频度是指该语句在算法中被重复执行的次数，算法中所有语句的频度之和记为*T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级，算法中基本运算的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)*来分析算法的时间复杂度：

T(n)=O(f(n))

  时间复杂度加法规则：

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

  时间复杂度乘法规则：

T(n) = T1(n)×T2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))

  常见的渐近时间复杂度为：

• 空间复杂度

  算法的空间复杂度S(n)定义为该算法所耗费的存储时间，它是问题规模n的函数，记为：

S(n)=O(g(n))