数据结构那些事

如果你现在在上大学，恰好又是计算机相关专业

那么你肯定知道有一个非常枯燥的必修课《数据结构导论》

当然，你现在没上大学或者不是计算机专业，那你现在应该知道了，他们有个必修课叫《数据结构导论》

从今天开始梦想橡皮擦要写一套非常有趣的课程了

这套课程目的很简单

目的：如何通过数据结构期末考试，有趣！

适合人群：

1. 大学计算机相关专业，有这门课程，然鹅你没学，或者因为一些莫名奇妙的原因，你旷课了
2. 你想通过自考，注意自考，然后获取计算机的一个本科学历，这门课也是必修。

一门课程开始前，我们要先关注这门课的重点

大纲如下

按照国内比较权威的教材，一般情况下，自考采用的是《全国高等教育自学考试指导委员会》给推荐的书籍

本套课程参考的是自考书籍《数据结构导论 2012 主编：郑诚》 外语教学研究出版社出版

知识点大纲如下

1. 第一章 概论
2. 第二章 线性表
3. 第三章 栈、队列和数组
4. 第四章 树和二叉树
5. 第五章 图
6. 第六章 查找
7. 第七章 排序

不同教材，侧重点不同，但是考点是覆盖的。包括你们的期末考试

来吧，今天开始第一章，概论

概论

重点考点

咱直接些，直接来重要考点就行了，搞定这些就OK啦

基本概念

数据、数据元素、数据项

这个要记住，牢牢的记住

先说概念

所有被计算机存储、处理的对象都是数据，你看计算机能处理图像、处理音频、处理文本，这些都是对象

数据的基本单位就是数据元素，一般叫做元素

然后元素是由数据项组成的，数据项还叫 字段或者域 ，并且数据项是数据的不可分割的最小标识单位

用图来表示，就下图即可理解

你看，好总结了

数据由若干数据元素组成，数据元素由若干数据项组成

数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系。逻辑关系是指数据元素之间的关联方式或“邻接关系”

说人话：每条数据元素之间的逻辑关系叫数据的逻辑结构

你看自然界，人群的组成，有一个个独自站着的，有拍着队站着的，有互相拉着手站着的....

这些反应到数据上，也是一样的

四种逻辑结构分别为

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

数据的存储结构

存储结构包括两部分：

1. 存储的数据元素
2. 数据元素之间的关联方式

表示数据元素之间的关联方式主要有 顺序存储方式 和 链式存储方式

其实需要记住四种

1. 顺序存储方式
2. 链式存储方式
3. 索引存储方式
4. 散列存储方式

算法分析

评价算法的好坏有四个方面的因素

1. 正确性
2. 易读性
3. 健壮性
4. 时空性 -- 包含时间效率（时间性能）和空间效率（空间性能）

重要知识点

时间复杂度

分析例子

编写函数求 1!+2!+...+n!

通过C语言编写代码实现如下

int fact1(int n){
	int i,j,temp,s;
	s = 0;
	for (i=1;i<=n;i++){
		temp = 1;
		for(j=1;j<=i;j++){
			temp = temp * j;
		}
		s = s + temp;
	}
	return s;
}

推导时间复杂度

如何估算算法的计算量，可以在算法中合理的选择一种或几种操作作为“基本操作”

例如，上述代码，我们分别去 乘法、加法和赋值为基本操作，然后推导计算量

例如，当n = 5 时候，上述代码的计算量如下

乘法：也就是 temp = temp * j; 执行的次数
1 + 2 + 3 + 4 + 5 = 15次

加法：也就是s = s + temp; 执行的次数
1+1+1+1+1 = 5次

赋值语句：s = 0; temp = 1; temp = temp * j; s = s + temp;执行的总次数

1. s=0 执行 1次
2. temp=1 执行 1+1+1+1+1 = 5 次
3. temp = temp * j; 执行 1+2+3+4+5 = 15次
4. s = s + temp; 执行 1+1+1+1+1 = 5次
   合计
   1+5+15+5 = 26次

上述是当n等于5的时候的计算量，如果当n就是n的时候
那么我们在计算一下计算量是多少

乘法：1+2+3+...+n = n(n+1)/2
加法：n
赋值语句：1+n+n(n+1)/2+n

在计算合计：也就是乘法+加法+赋值语句
n(n+1)/2 + n + 1+n+n(n+1)/2+n = 2(n²+n)/2+3n+1 = n²+4n+1

这时候，用T(n)表示这个计算量

T(n) = n²+4n+1

下面重点来了，当n无限大的时候，n²+4n+1 约等于 n²

可以用大O表示法 T(n) = O(n²)
看到了吧，这就是时间复杂度的表示方法，全称叫做 算法的渐进时间复杂度

上面例子的第二种代码编写方式

int fact2(int n){
	int i,j,temp,s;
	s = 0;
	temp = 1;
	for(i=1;i<=n;i++){
		temp = temp * i;
		s = s + temp;
	}
	return s;
}

用和编码1的方式推导之后
T(n) = 2n+2 ≈ O(n)

当n无限大时，算法的执行时间与n成正比

所以当你明白时间复杂度是怎么计算出来之后，需要记住一些常见的时间复杂度阶数

• 常数阶O(1)
• 对数阶O(log₂n)
• 线性阶O(n)
• 多项式阶O(n^c) 常见O(2²) O(2³)
• 指数阶O(Cⁿ) 常见的 O(2ⁿ)

最后的知识点是空间复杂度，这个一般在考试中不常见

一般需要考虑三部分

1. 程序代码所占用的空间
2. 输入数据所占用的空间
3. 辅助变量所占用的空间

在估算算法空间复杂度，一般只需要分析辅助变量所占用的空间即可

写在后面

对于考试来说，一些基本概念要掌握，算法时间复杂度的大小排序要掌握（后续博客中还会涉及），根据一个算法，分析时间算法的复杂度要会

出处：https://www.cnblogs.com/happymeng/p/12026521.html