在你点进来这里的一瞬间，欢迎你找到了宝藏

这是一些关于数据结构和算法里最详细的阐述和学习心得，我十分乐意和你分享这些知识。

如果你已经看完这篇杂谈，可以前往下一篇→数据结构杂谈（二）_尘鱼好美的小屋-CSDN博客

1 绪论

1.1 什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科。

1.2 基本概念和术语

数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：是数据的基本单位（相当于数据库的元组），数据元素在计算机程序中通常作为一个整体进行考虑和处理，也简称为元素，或称为记录、结点或顶点；一个数据元素由若干个数据项组成。

在数据库原理中，层次模型采用的就是记录，也就是关系数据库中所说的元组。从中我们可以理解了，某一个类的实例就是数据元素。

数据项：构成数据元素的不可分割的最小单位

相当于数据库中的属性；在数据库中我们也曾叫作数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集，在不产生混淆的情况下，我们一般把数据对象简称为数据。

数据结构：数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构。

在看完以上的概念后，我想我有必要来说几句。

我们可以举生活中的例子来说明以上的概念。假设我们把人看成数据（数据对象），而把小红小明看成数据元素，把小红小明等人的性别、学号、年龄看成数据项，如果我们要把小红小明等人按照一定的规则放在一起，这个规则就叫数据结构。

对于数据结构来说包含以下三个方面的内容

1. 数据元素之间的逻辑关系，也称为逻辑结构。
2. 数据元素及其关系在计算机内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构。
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

1.2.1 数据结构的两个层次

数据结构分为逻辑结构和物理结构，兹分别列举如下：

1.2.2 逻辑结构的种类

对于逻辑结构来说，有两种划分方式：

划分方法一：

划分方法二：

1.2.3 四种基本的存储结构

我们可以把存储结构划分为四种，兹列举如下：

C语言中用数组来实现顺序存储结构

C语言中用指针来实现链式存储结构

从上面的简洁的总结来看，我们如何更好地理解这些数据结构呢？实际上，逻辑结构指的是数据元素之间的关系，如果拿数据库中类比的话，就是你要用层次数据模型还是用关系数据模型来表示数据的区别。而物理结构指的是数据在电脑上面存放的形式，有的是整整齐齐连续排列在内存中，有些是不连续地排列在内存中。

而之所以出现这两种结构，是因为实际业务的需要，你想想看，如果使用连续的内存（顺序存储结构）来存储数据，万一你频繁地删除数据，而且考虑最坏情况，刚好删掉第二个数据元素，那么假设总共由n个数据元素的话，那么后面就有n-2个数据元素需要前移，十分麻烦。

但是如果用不连续存储（链式存储结构）就不一样了，链式存储结构采用的是一种寻址的方式，即数据元素能够寻找上一个数据元素的地址。这样的话如果频繁做更改，拿删除来说，只需要把一个数据元素删除，然后前后的数据元素地址改动一下即可，当然，这些操作都是有小细节的，这里只是大概提一下罢了。

逻辑结构是面向问题的，而物理结构是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

1.2.4 数据类型和抽象数据类型

数据类型：是一组性质相同的值的集合以及定义在这个值集上的一组操作的总称

抽象数据类型（Abstract Data Type，ADT）：是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的说明

• 由用户定义，从问题抽象出数据模型。（逻辑结构）
• 还包括定义在数据模型上的一组抽象运算。（相关操作）
• 不考虑计算机内的具体存储结构和运算的具体实现算法

抽象数据类型的定义格式

ADT 抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名

   

  

   
1
   
2
   
3
   
4
   
5
  

基本操作的定义格式

基本操作名<参数表>
	初始条件：<初始条件描述>
	操作结果：<操作结果描述>

   

  

   
1
   
2
   
3
  

说明：

1. 参数表：参数表中引用参数以&开头，表示不仅可以作为参数输入值，还能返回操作后的结果。
2. 初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应的，并返回相应出错信息。若初始条件为空，则省略
3. 操作结果：说明操作正常完成之后，数据结构的变化状况和返回的结果。

数据类型的出现不是偶然而是必然，如果不规定数据类型的话，那么就会造成资源的浪费。拿C语言来举例，如果你不使用int，long这些基本数据类型的话，那么无端给出一个7，谁知道你的7占几个字节？好比住房子，诶，当然，如果你想提前举手：住房子当然是越大越好啦，那国家可就不同意了，你住那么大，别人住哪里？所以，根据公民的所需来规定每个公民住所的大小，对应到C上，每个数据都应该有自己在内存中所占的对应大小。故数据类型出现了。

那么抽象数据类型又是怎么出现的呢？我们试想，如果要对两个整数做加法，我们关心的是哪两个整数，它们做的操作是不是加法，它们做出来的结果如何。而不关心它们在计算机的时候用到计算机的底层逻辑，比如动到了哪里的内存，CPU做了什么工作，这通通都是我们不关心的，由此抽象数据类型应运而生了。

抽象是指抽取出实物具有的普遍性的性质。它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所需要的信息；如果你学过java，你就知道里面的抽象类深谙此道理。

1.3 算法的基本概念

1.3.1 算法和算法分析

1.3.1.1 引入

我们首先写一个求和算法出来，如下：

int sum = 0;
for(int i = 1;i<=100;i++)
{
	sum = sum + i;
}
cout << "100 = "<<sum<<endl;

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

上面我想大多数人从上大学第一门课程C语言开始学的就是这个求和算法。可以我们可以看到，这个算法是采用for循环来设计的；在深度学习中，for循环是效率最低的顺序扫描，所以在不得已的情况下，我们不会采用for循环。那我们有更好地求和方法吗？

在高中的时候，我们曾经学过倒序相加法，值得一提的是，倒序相加法现在没几个人记得，为啥？因为它们根本不理解其中的原理，而是靠大量的题目堆出来的记忆，所以在这里，我讲一下倒序相加法的由来。

大名鼎鼎数学家高斯在很小的时候就因为老师刁难的一道题很闻名，老师故意刁难1加到100要让还在上小学的高斯做出来，而高斯花的时间也不多，三下五就做出来了，他是这么做的：既然要算1加到100，那么我再搞一个1加到100，但是是倒序排放，那么上面的1和下面的100相加刚好为101,2和99相加为101，以此类推总共有100个101，也就是10100，那么除以二就是1加到100的结果，即5050。

如果把100看成n，我们可以写出下列的程序：

int i = 0;
int sum = 0;
int n = 100;
sum = (1+n)*n/2;
cout<<sum<<endl;

  

 

  
1
  
2
  
3
  
4
  
5
 

由此我们可以发现，好的算法可以起到事半功倍的效果。由此我们引出算法的定义，算法是什么？

1.3.1.2 算法

算法：是对特定问题求解步骤的一种描述

弄懂了算法的概念，那么算法和程序有什么区别呢？

算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法；而程序是用某种设计语言对算法的具体实现。

对于算法来说有几大特性，如下所示：

在给出上面算法的特性后，我们来避免记忆，给出一个比较简单的故事，假如你的算法是无穷步，那还有意义吗？本来人们就是用来解决问题，不能解决问题要这个算法有什么用。每个算法的每个步骤都是确定的，也就是说不会出现二义性。也就是说，你不能说输出1然后会出来两个数。并且你的算法做出来要可行，如果你的算法开销太大，以现有的机器根本跑不出来，那这个算法也是没有什么意义的。当然，一个算法可以没有输入，但是不能没有输出，就比如我们最简单的每个编程教材最开始都有的一个案例：hello world

1.3.1.3 衡量算法

对于算法设计我们应该有如下要求：

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。算法效率从以下两个方面来考虑：

时间效率和空间效率有时候是矛盾的，有时候为了提高时间效率，不得已要牺牲空间效率；所以为了提升总体效率，我们要折中选择。

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。

对于一个算法的度量，我们有下面两种方法：

**事后统计：**将算法实现，测算其时间和空间开销。

事前分析：对算法所消耗资源的一种估算方法

事后统计一般就像马后炮，所以我们一般采用事前分析

1.3.2 函数的渐近增长

输入规模n在没有限制下，只要超过一个数值N，这个函数就总是大于另一个函数，我们则称函数是渐进增长的。即：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)。

1.4 算法的时间复杂度

1.4.1 渐进时间复杂度

渐进时间复杂度：若有某个辅助函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度。

定义里用大写O来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。而为了便于比较不同算法的时间效率，我们仅比较它们的数量级。

1.4.2 推导大O阶的方法

指路：大O阶推导方法

1.4.3 常见的时间复杂度

1.4.3.1 算法时间效率的比较

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。

实际上下面的表不用记，只需要利用高数的函数图形去理解就行。

1.4.3.2 三种复杂度

**最坏时间复杂度：**考虑输入数据“最坏”的情况。

平均时间复杂度：考虑所有输入数据都等概率出现的情况。

**最好时间复杂度：**考虑输入数据“最好”的情况。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度。

**加法规则：**T(n) = T1(n)+T2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))

**乘法规则：**T(n) = T1(n)T2(n) = O(f(n))O(g(n)) = O(f(n)g(n))

文章来源: blog.csdn.net，作者：ArimaMisaki，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/chengyuhaomei520/article/details/122782142