一、简介
1.1 基本概念
数据对象：就是数据的子集
数据元素：就是数据的个体
数据类型：是一组值的集合和定义在该集合上的操作的总和。
1.原子类型：原子就是不可再分割的意思，它是原子类型值的集合和定义在该集合上的操作。例如在 C 语言中的 int、char、float 等都是原子类型。
2.结构类型：它是结构的集合和定义在集合上的操作。结构就是多个原子类型值的组合
3.抽象数据类型：它是数据模型以及定义在该数据模型上的操作，可以用一个三元组来表示，分别是数据对象、数据关系和相关的操作。对于抽象数据类型，只考虑它的逻辑特性，具体的内部实现是不考虑的。例如在生活中所有的人、汽车都可以把它抽象出来作为一种抽象数据类型。
1.2 三要素
逻辑结构、物理结构、数据预算
1.2.1 逻辑结构
1.逻辑结构：线性结构、集合、树形结构、图状结构，其中，集合、树形结构、图状结构统称为非线性结构
2.线性结构：一个对一个就是线性结构，比如，成绩排序
3.集合：集合是指除了所有的元素均在一个集合之内，之外再无其他的关系。
4.树形结构：指一对多的关系。比如说狗是一类的总称，狗中又有柯基、哈士奇等具体的种类，这样一个种类的分支关系，它们就是一个树形结构。
5.图状结构：也叫做网状结构，它是多对多的关系。比如城市的交通网络，每一个城市都连接这其他的许多城市。
1.2.2 物理结构
1.存储结构：也称物理结构，分为：顺序存储、链式存储、索引存储、散列存储。
2.顺序存储：顺序存储元素之间的关系是通过物理位置相邻来体现的，其最大的好处就是可以实现随机存储，在知道第一个单元的位置时，通过简单运算，根据它相邻的特性也就知道其后所有元素的数据位置。
什么叫随机存取？
答：随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。
3.链式存储：指在逻辑上相邻的元素，在物理存储位置上是不相邻的。链式存储通过名字来看，它有一个链接的含义，它在具体的实现上也是利用这样一个具体操作的。
4.索引存储（了解）：在内存中不仅仅要存放每一个数据元素，还要建立一张索引表。
5.散列存储（了解）：散列存储也称为哈希存储，它是通过关键字的相应函数运算直接求得对应数据元素的地址。
1.2.3 数据运算
数据的运算包括运算的定义和实现方式，运算的定义针对逻辑结构，运算的实现针对存储结构。
1.3 算法与评价
1.3.1 算法5个特性
1.有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，
每一步都可在有穷时间内完成。
2.确定性：算法中每一条指令必须有明确的含义，读者理解时不会产生二义性。
即对于相同的输入只能得到相同的输出。
3.可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的。
基本运算执行有限次来实现的。
4.输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集
合。
5.输出：一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系
的量。
1.3.2 算法和程序三方面的区别
1.有穷性：算法必须是有穷的，程序可以是无穷的，所以在操作系统中，那些很有用的，但又无限循环的，可以 称之为程序。
2.正确性：算法必须是正确的，程序可以是错误的。设计出的算法必须正确的来解决问题，而程序可以编写错误然后进行修改。
3.描述方法：算法可以用伪代码、程序语言、自然语言、程序框图等描述，程序只能用程序设计语言编写并可以运行。
1.3.3 “好”算法的4个目标
1.正确性：算法应当能够正确地解决求解问题。
2.可读性：算法应当具有良好的可读性，以助于人们理解。
3.健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，
而不会产生莫名其妙的输出结果
4.效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算
法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
1.3.4 算法的度量
1.时间复杂度：
两个概念：语句的频度、T（n）
三种分类：最坏时间复杂度、最好时间复杂度、平均时间复杂度
常见时间复杂度：
2.空间复杂度
算法的空间复杂度是指算法消耗的存储空间，记作 S(n) = O(g(n)) ，O 表示同阶无穷大，g(n) 表示数量级，n 代表问题规模。
