---

数据结构和算法

1：程序设计=数据结构+算法。 

   数据结构就是关系，就是数据元素之间的一个或多种特定关系。

   数据结构：1）逻辑结构（集合结构，线性结构，树形结构，图形结构），2）物理结构（数据存储方式，顺序存储，链式存储）。

2：算法：解决特定问题求解步骤的描述，计算机中表现为多个指令的有限序列，并且每条指令表示一个或多个操作。

   算法的特性：输入（0个或多个），输出（至少一个），有穷（有限步内完成），确定（无歧义），可行（每一步都是可行的）。 

3：算法效率的度量方法：效率或执行时间。

   影响因素：1）算法策略；2）编译产生的代码质量；3）问题的输入规模；4）机器的指令执行速度；

   判断效率时，关注最高项即可（忽略次要项以及系数）。

4：时间复杂度和空间复杂度：O（），又称大O记法。一般情况下，随着输入规模n的增大，T（n）增长最慢的算法为最优算法。0(1)<0(logn)<O(n)<0(nlogn)<0(n^2)<0(n^3)<0(2^n)<0(n!)<0(n^n),

   时间复杂度表示运行时间的需求，空间复杂度表示空间需求。

5：线性表：零个或多个元素组成的有限序列。（第一个无前驱，最后一个无后继，其余元素都有一个前驱和后继。元素的个数为n。）

   数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。例如，编程语言中的整型，浮点型等。

   抽象数据类型ADT：对数据类型进行抽象，抽取出事务具有的普遍性的本质，是特征的概括，而不是细节。（数据类型和相关的操作捆绑在一起）

   线性表抽象数据类型（List）:

   Data:线性表的数据对象集合为{a,b,c...},每一个元素的数据类型为DataType

   Operation: InitList(*L),初始化，判断，取值，返回，插入...

6：线性表的顺序存储结构：类...