数据结构
一、相关概念
程序=数据结构+算法
算法：对特定问题求解方法和步骤的一种描述，是指令的有限序列
算法的描述：
- 自然语言
- 流程图：传统流程图、NS流程图（盒图）
- 伪代码
- 程序代码
算法的特性：
- 有穷性：有穷步之后结束，每一步都在有穷时间内
- 确定性：有确切含义，无二义性
- 可行性：可执行的
- 输入：0或多个输入
- 输出：1或多个输出
算法的设计要求：
- 正确性
- 可读性
- 健壮性
- 高效性
具体问题抽象为数学模型：
- 分析问题
- 提取操作对象
- 找出操作对象之间的关系
- 用数学语言描述 ->数据结构
- 数据：
- 能输入计算机并能被计算机处理的各种符号的集合
- 信息的载体
- 对客观事物的符号化表示
- 能被计算机识别、存储、加工
- 数据元素/元素/记录/顶点/结点：数据的基本单位，在计算机中通常作为一个整体进行考虑
- 数据项：构成数据元素的不可分割的最小单位
数据>数据元素>数据项
数据对象：性质相同的数据元素的集合，是数据的子集
数据结构：数据元素相互之间的关系
-
逻辑结构；是数据结构的抽象
-
线性结构：有且仅有一个开始和一个重点结点，并且一个结点只有直接前驱和一个直接后继，如：线性表、队列、串、栈
-
非线性结构：（一对多或多对多）一个结点可能有多个直接前驱和直接后继，如：树、图
-
集合结构：结构中的数据元素除了在一个集合外，无其他关系
-
线性结构：结构中的数据元素存在一对一的线性关系
-
树形结构：结构中的数据元素存在一对多的层次关系
-
图状结构：结构中的数据元素存在多对多的任意结构
-
-
存储结构（物理结构）：数据元素及其关系在计算机内存中的表示（映像）；是数据结构的实现
-
顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示（C语言中的数组）
-
连式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针表示（C语言中的指针）；存储了元素本身还存储了下一个元素的地址
-
索引存储结构：在存储结点信息的同时，还建立附加的索引表
-
散列存储结构：根据结点的关键字直接计算出该结点的存储地址
-
-
数据的运算和实现：对数据元素可以施加的操作，以及这些操作在相应存储结构上的实现
二、时空复杂度
算法效率：
-
时间效率：程序在计算机上执行所消耗的时间
-
事后统计
- 缺：编写程序实现算法要花费较多时间精力；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法分身的优劣
-
事前分析：估算；算法运行时间=一个简单操作所需的时间*简单操作次数（转化为语句频度的比较）
例：
-
1 for(i=1;i<=n;i++) // n+1次，虽然不满足条件但也执行一次
2 for(j=1;j<=n;j++){ // n(n+1)次
3 c[i][j]=0; //n*n次
4 for(k=0;k<n;k++) //n*n*(n+1)次
5 c[i][j]=c[i][j]+a[i][k]*b[k][j]; // n*n*n次
6 }
-
T(n)=2n^3+ 3n^2+2n +1=时间复杂度O(n^3)（为了便于比较仅比较数量级）
T(n)=O(f(n))；O(f(n))（O是数量级的符号）为算法的渐进时间复杂度， 简称时间复杂度
步骤：
- 找出语句频度最大的那条语句作为基本语句
- 计算基本语句的频度得到问题规模n的某个函数f(n)
- 取其数量级将用O表示
例：
for( i=1; i<=n; i++)
for (j=1; j<=i; j++)
for (k=1; k<=j; k++)
x=x＋1;语句频度=n(n+1)(n+2)/6
T(n)=O(n^3)
例：
i=1;
while(i<=n)
i=i*2;
T(n)=O(log2 n)
有的情况下基本重复执行次数还随问题的输入数据不同而不同
例：顺序查找，在数组a[i]中查找值为e的元素，返回其所在位置
最好的情况：1次；最差的情况：n次；平均时间复杂度：O(n)
所以，一般考虑的是最差情况下的时间复杂度，以保证算法的运行时间不会更长
复杂度低->高
常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ... K次方阶 指数阶 O(1) O(log2 n) O(n) O(nlog2 n) O(n^2) O(n^3) O(n^K) O(2^n)
-
空间效率：算法所需存储空间的度量 S(n)=O(f(n))
算法占据的空间：
- 算法本身要占据的空间：输入/输出、指令、常数、变量等
- 算法要使用的辅助空间
例：将一维数组a中的n个数逆序存放到原数组中
for(i=0;i<n/2;i++){
t=a[i]; a[i]=a[n-i-1];
a[n-i-1]=t;
}
变量为t,其空间复杂度S(n)=O(1)
for(i=o;i<n;i++)
b[i]=a[n-i-1];
for(i=0;i<n;i++)
a[i]=b[i];
变量为b[i],其空间复杂度S(n)=O(n)
时间效率空间效率有时候是矛盾的
程序是用某种程序设计语言对算法的具体实现
三、数据类型及抽象数据类型
数据类型：定义在一组性质相同的值的集合以及定义在这个值的集合上的一组操作的统称，即数据类型=值的集合+值集合上一组操作
数据类型的作用：
- 约束变量或常量的取值范围
- 约束变量或常量的操作
抽象数据类型（ADT）：一个数学模型以及定义在此数学模型上的一组操作；不考虑计算机内的具体存储结构与运算的具体实现方法
抽象数据类型的形式定义：（D（数据对象）,S（关系集）,P（基本操作集））三元组表示
ADT 抽象数据类型名{
数据对象：<数据对象的定义（伪代码）>
数据关系：<数据关系的定义（伪代码）>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
基本操作的定义格式：
- 基本操作名（参数表）
- 赋值参数：只为操作提供输入值
- 引用参数：以&打头，除可提供输入值外，还将返回操作结果
- 初始条件<初始条件描述>：描述操作执行之前数据结构和参数应满足的条件，若不满足,则操作失败，并返回相应出错信息；若初始条件为空，则省略
- 操作结果<操作结果描述>：说明操作正常完成之后，数据结构的变化状况和应返回的结果
例：ADT Circle {
数据对象:D=
数据关系:R=
基本操作:
Circle(&C,r,x,y)
操作结果:构造一个圆。
double Area(C)
初始条件:圆已存在。
操作结果:计算面积。
double Circumference (g)
初始条件:圆已存在。
操作结果:计算周长。
......
}ADT Circle
标签：存储,复杂度,元素,算法,数据结构,数据 From： https://www.cnblogs.com/yuanyu610/p/17071988.html