数据结构

1.请区分以下概念：

数据-数据对象-数据元素-数据项

数据：程序的操作对象，用于描述客观事物
数据的特点：1.可以输入到计算机
			2.可以被计算机处理
数据项：一个数据元素由若干数据项组成
数据元素：组成数据对象的基本单位
数据对象：性质相同的数据元素的集合（类似于数组）
结构：数据元素之间不是独立的，存在特定的关系，这些关系就是结构
数据结构：指的是数据对象中的数据元素之间的关系

2.逻辑结构有以下几种：

• 集合结构
• 线性结构
• 树形结构
• 图形结构

3.逻辑结构有以下几种：

• 顺序存储结构
• 链式存储结构

4.算法定义：

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

5.算法特性：

• 输入输出
• 有穷性
• 确定性
• 可行性
• 正确性
• 可读性
• 健壮性
• 时间效率高和储存量低

6.时间复杂度：

时间构成：

• 算法输入时间
• 编译可执行代码
• 执行指令
• 执行重复的指令

7.大O表示法：

1. 用常数1取代运行时间中所有常数
2. 在修改运行次数函数中，只保留最高阶项
3. 如果在最高阶存在且不等于1，则去除这个项目相乘的常数

8.时间复杂度类型：

1. 常数阶
2. 线性阶
3. 平方阶
4. 对数阶
5. 立方阶
6. nlog阶
7. 指数阶（不考虑），O(2^n)或者O(n!)除非是非常小的n，否则会造成噩梦般的时间消耗。这是一种不切实际的时间复杂度，一般不考虑。

//常数阶时间复杂度计算
void testSum2(int n){
	int sum=0;
	sum = (1+n)*n/2;
}

//线性阶时间复杂度计算
void add2(int x,int n){
	for(int i=0;i<n;i++){
		x=x+1;
	}
}

//对数阶
void testA(int n){
	int count=1;
	while(count<n){
		count=count*2;
	}
}

//平方阶
void add3(int x,int n){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			x=x+1;
		}
	}
} 

9.空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记做：S(n)=n(f(n)),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

10.程序空间计算因素

• 寄存本身的指令所占空间
• 常数所占空间
• 变量所占空间
• 输入所占空间
• 对数据进行操作的辅助空间

在考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间

11.线性表-顺序表

对于非空的线性表和线性结构，其特点如下：

• 存在唯一的一个被称作“第一个”的数据元素；
• 存在唯一的一个被称作“最后一个”的数据元素；
• 除了第一个之外，结构中的每个数据元素有一个前驱；
• 除了最后一个之外，结构中的每个元素都有一个后继；

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： KangLeon
• 本文链接： http://www.jiyoung.cn/2020/08/13/数据结构基础/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！