Chapter1 绪论

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。

面向过程：程序设计 = 数据结构 + 算法

数据结构的分类

• 逻辑结构：数据对象中数据元素之间的关系。
  • 集合结构：数据元素除了同属于一个集合之外，它们之间没有其它关系。
  • 线性结构：线性结构中的元素之间是一对一的关系。
  • 树形结构：数据元素之间存在一种一对多的层次关系。
  • 图形结构：数据元素之间存在多对多的关系。
• 物理结构（存储结构）：数据的逻辑结构在计算机中的存储形式。存储器主要是针对内存而言的，外部存储器中的数据组织通常用文件结构来描述。
  • 顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  • 连式存储结构：把数据结构存储在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

抽象数据类型

• C语言中，按照取值的不同，数据类型可以分为两类：
  • 原子类型：不可以再分节的基本类型，包括整型、实型、字符型等。
  • 结构类型：由若干个类型组合而成，是可以再分解的，例如，整型数组是由若干整型数据组成的。

抽象是值抽取出事物具有的普遍性的本质。 对已有的数据类型进行抽象，就有了抽象数据类型。 抽象数据类型(Abstract Data Type)是指一个数学模型及定义在该模型上的一组操作。

• 描述抽象数据类型的标准格式：

ADT 抽象数据类型Data    数据元素之间逻辑关系的定义Operation    操作一        初始条件        操作结果描述    操作二        ...    操作n        ...endADT复制代码

Chapter2 算法

算法的特性

• 算法具有五个基本特性：
  • 输入输出：算法有零个或多个输入，一个或多个输出。
  • 有穷性：算法执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间之类完成。
  • 确定性：算法的每一步都有确定的含义，不会出现二义性。相同的输入只会有唯一的输出结果。
  • 可行性：每一步都能够通过执行有限的次数完成。

复杂度

• 算法的时间复杂度：
  • 分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或者一系列步骤。
  • 判断一个算法的效率时，函数中的常数项和其他次要项常常可以忽略，而更应该关注主项 （最高阶项）的阶数。
• 算法的空间复杂度：

参考资料：《大话数据结构》