数据结构与算法－概述

数据结构(Data structure）是指一组相互 之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

数据组织的三个层次

1. 数据（Data)：所有能被计算机处理的符号的集合。

2. 数据元素（Data Element）：是数据这个集合中的一个个体，即数据的基本单位。

3. 数据项（Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。在数据库中数据项又称为字段或域，它是数据的不可分割的最小标识单位。

数据的四种逻辑结构

1. 集合，任意两个结点之间都没有邻接关系,组织形式松散。

2. 线性结构，结点按逻辑关系依次排列形成一条 "锁链"

3. 树状结构，具有分支、层次特性，上层的结点可以和 下层多个结点相邻接，但下层结点只能和 上层的一个结点相邻接。

4. 图状结构，任何两个结点都可以相邻接。

逻辑结构与数据元素本身形式和内容无关，与数据元素的相对位置无关，与所含结点个数无关。

数据的四种存储结构

1. 顺序存储方式：借助数据元素的相对存储位置来表示数据的逻辑 结构；线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。

特点：

(1). 预先分配好长度，需要预估存储数据需要的存储量；

(2). 插入和删除需要移动其它元素；

(3). 存取快捷，是随机存取结构。

2. 链式存储方式：借助数据元素地址的指针表示数据的逻辑结构。

(1). 动态分配，不需要预先确定内存分配；

(2). 插入和删除不需要移动其他元素；

(3). 非随机存取结构。

3. 索引存储方式：借助索引表中的索引指示各存储节点的存储位置。

4. 散列存储方式：用散列函数指示各节点的存储位置。

算法描述

一个算法是对特定问题求解步骤的一种描述，它是指令的有穷序列，算法具有以下特性：

1. 有穷性： 一个算法总是在执行有穷步后结束。

2. 确定性：算法的每一步都必须是明确地定义的。

3. 可行性：算法中的每一步都是可以通过已经实现 的操作来完成的。

4. 输入：一个算法有零个或者多个输入, 这些输入 取自于特定的对象集合。

5. 输出：一个算法有一个或者多个输出，它们是 与输入有特定关系的量。

算法设计原则

1. 正确性：对于合法的输入产生符合要求的输出。

2. 易读性：算法应该易读、便于交流， 这也是保证算法正确性 的前提；添加注释也是一种增加可读性的办法。

3. 健壮性：当输入非法时， 算法还能做出适当的反应而不会崩 溃， 如输出错误信息；算法中应该考虑适当的错误处理。

4. 时空性：一个算法的时空性是指算法的时间复杂度和空间复杂度，算法分析主要分析算法的时间复杂度和空间复杂度，目的是 提高算法的效率。

时间复杂度

时间复杂度为算法运行时需要的总步数，通常是问题规模的函数。

合理地选择一种或几种操作作为“标准操作”，无特殊说明， 默认以赋值语句作为标准操作。确定每个算法共执行多少次标准操作，并将此次数规定为该算 法的计算量。

以算法在所有输入下的计算量的最大值作为算法的 计算量，称为算法的最坏情况时间复杂度。

以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度。

以下是一些常用的采用大O标记法定义的时间复杂度。

空间复杂度

空间复杂度为算法执行时所占用的存储空间， 通常是问题规模的函数。

一个算法在执行期间所需要的存储空间量包括以下部分：

1. 程序代码所占用的空间。

2. 输入数据所占用的空间。

3. 辅助变量所占用的空间。

估算算法空间复杂度时，一般只分析辅助变量所占用的空间。

以下为将有100个整数的数组进行逆置的算法，其中第一个算法的空间复杂度为o(1)，第二个算法的空间复杂度为o(n)。