算法与数据结构【30天】集训营——概念术语介绍及基础知识准备（01）

数据结构基本介绍

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素的集合。它包含三方面的内容，逻辑关系、存储关系以及操作。

正确的算法的含义是：能够解决实际问题，输入的所有可能的合法的输入都能产生预期的正确的结果；能够在有穷的步骤内执行完程序；能够用最简短的语句最高效的完成任务。

为什么要学数据结构？

有人肯定会有疑惑，学数据结构不就是为了“应付期末考试，考研科目要求，大厂面试所需”，如果你是计算机领域的学生，把学习一门编程语言或者技术当做是一个任务，那么永远很难达到你所达到的高度。技术不像是你的高数，学完之后反复的刷题，上考场之前熟记这些公式和解题思路，最终可以获得一个不错的分数。但是对于数学来说，如果你不是从事那种基础深度的研究领域，你可能无法一直保持对它的热爱，总而言之，我想说的是：“知识是一门技能，要懂得学以致用”，来之于书本，还之于平常。

至于数据结构什么领域，什么行业，什么职位可以用到，我就不多说了，总之其实，数据结构和算法这个东西，如果你不去学，可能真的这辈子都用不到，也感受不到它的好。但是一旦掌握，你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码，需要花很多心思来设计的架构，用了数据结构和算法之后，很容易就可以解决了。

学数据结构的基本功（C…）

数据结构与算法这一门课程或者说能力，目前的实现语言有很多，比如C，C++，java，Python等，本专栏采用的是C语言编程，所以这需要各位掌握一些基本C语言的语法知识，在前期的专栏里面我也写过《手写C语言代码实战+原理》，大家可以去学习一下基础的语法知识，正所谓磨刀不误砍柴工，学好基本的知识，才能顺利的进行下一阶段的提升。

这里简单的介绍一下，数据结构当中最为常用的一些C语言语法知识，其实有提前了解的小伙伴都应该知道：指针和结构体是数据结构C语言版的基石。

引用和函数调用：

引用：对一个数据建立一个“引用”，它的作用是为一个变量起一个别名。

例如：

int a = 5;

int &b = a;
1
2
3

b是a别名，b与a代表的是同一个变量，占内存中同一个存储单元，具有同一地址。

如果你无法理解，可以去尝试上机一下

通过这样一段代码，我们会比较直观的发现，在对变量进行操作的时候，在C语言编译环境中&是对其变量进行取地址操作。

注意事项：

声明一个引用，同时必须初始化，及声明它代表哪一个变量。（作为函数参数时不需要初始化）
在声明一个引用后，不能再作为另一变量的引用。
不能建立引用数组。
1
2
3

比如有一个经典的交换算法程序

void Myswap1(int a,int b)
{
	int c = a;
	a = b;
	b = c;
}
 
void Myswap2(int &a,int &b)
{
	int c = a;
	a = b;
	b = c;
}
 
void Myswap3(int *pa,int *pb)
{
	int c = *pa;
	*pa = *pb;
	*pb = c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这三个函数很简单，第一个只传了值进来，不改变全局变量；而第三个也很熟悉，就是传递了地址，方便操作。依旧是“值传递”的方式，只不过传递的是变量的地址而已；那二就彻底改变了这些东西，引用作为函数参数，传入的实参就是变量，而不是数值，真正意义上的“变量传递”。

细心的小伙伴肯定发现了，为什么这里会只出现了两个交换的结果，原因是我使用的是C语言的编译器，第二个函数会报错。.c文件为纯C语言，不支持引用。 但是思想适用于所有的

关于C函数参数传递方式总结如下:
  (1)传值，就是把你的变量的值传递给函数的形式参数，实际就是用变量的值来新生成一个形式参数，因而在函数里对形参的改变不会影响到函数外的变量的值。
  
  (2)传址，就是传变量的地址赋给函数里形式参数的指针，使指针指向真实的变量的地址，因为对指针所指地址的内容的改变能反映到函数外，也就是能改变函数外的变量的值。
  
  (3)传引用，实际是通过指针来实现的，能达到使用的效果如传址，可是使用方式如传值。

说几点建议：如果传值的话，会生成新的对象，花费时间和空间，而在退出函数的时候，又会销毁该对象，花费时间和空间。

数组和指针

1、函数传数组就是传了个指针，所以传的时候你写arr[],里面写多少，或者不写，都是没关系的，那你后面一定要放一个变量来把数组长度传进来。

2、定义：int arr[5]，你访问越界是不会报错的，但是逻辑上肯定就没有道理了。那用typedef int INTARR[3];访问越界，在vs上会报错，要注意。

3、再说一下指针和数组名字到底有什么区别？

第一：指针可以自增，数组名不行

第二：地址不同，虽然名字[n]，都可以这样用，但是数组名地址就是第一个元素地址。指针地址就是那个指针的地址，指针里存的才是第一个元素地址。

第三：sizeof（），空间不一样，数组是占数组那么大空间。指针是四个字节。

最后就是要熟悉*和&这两个操作符在C语言中的作用，一个是解引用，一个是引用，此外在定义指针的时候也需要：int *p

结构体

typedef struct Date
{
	int Year;
	int Month;
	int Day;
	struct Date *pDate;
}Date, *pDate;
1
2
3
4
5
6
7

对于C语言的结构体，如果说难度，应该算是简单的，基本的语法和访问调用，需要大家掌握的。

结构体知识详解
指针知识详解①
指针知识详解②

以上是我个人觉得比较好的知识讲解，了解了基本的语法知识，我们就开始数据结构之旅吧！

前言

基本术语

数据结构的前期知识，都是偏概念性的，需要我们有一定的了解这样才能对数据结构有一定的认识和体会。

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

数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项： 组成数据元素的、 有独立含义的、 不可分割的最小单位。例如 ：学生的姓名学号等。

数据对象： 是性质相同的数据元素的集合， 是数据的一个子集。只要集合内的性质均相同， 都可称之为一个数据对象。

数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。

我们可以通俗的想象，现在在我们面前有一张学生信息表，如下所示：

数据元素就是每一行的字段，比如：小明…A

数据项就是某一行上的某一列，比如：小明

数据对象就是这一张表

总而言之，数据元素对应行，数据项对应列，分别是基本单位和最小单位，其次数据对象就是一张大表，这张表集合了数据元素和数据项。

数据类型：

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1. 原子类型。 其值不可再分的数据类型。
2. 结构类型。 其值可以再分解为若干成分(分量)的数据类型。
3. 抽象数据类型。 抽象数据组织及与之相关的操作

数据结构

逻辑结构：

逻辑结构是指数据元素之间的逻辑关系， 即从逻辑关系上描述数据。 它与数据的存储无关，是独立于计算机的。

数据的逻辑结构分为线性结构和非线性结构， 线性表是典型的线性结构；集合、 树和图是典型的非线性结构

集合：结构中的数据元素之间除“同属一个集合” 外， 别无其他关系
线性结构：结构中的数据元素之间只存在一对一的关系
树形结构：结构中的数据元素之间存在一对多的关系
图状结构或网状结构： 结构中的数据元素之间存在多对多的关系

存储结构：

存储结构是指数据结构在计算机中的表示(又称映像)， 也称物理结构。 它包括数据元素的表示和关系的表示。 数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。 数据的存储结构主要有顺序存储、 链式存储、 索引存储和散列存储

顺序存储： 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
其优点是可以实现随机存取， 每个元素占用最少的存储空间； 缺点是只能使用相邻的一整块存储单元， 因此可能产生较多的外部碎片，便于查找，不便于删除，增加。

链式存储： 不要求逻辑上相邻的元素在物理位置上也相邻， 借助指示元素存储地址的指针来表示元素之间的逻辑关系。
其优点是不会出现碎片现象, 能充分利用所有存储单元； 缺点是每个元素因存储指针而占用额外的存储空间， 且只能实现顺序存取。

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中， 而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系， 需要给每个结点附加指针字段，用千存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

索引存储： 在存储元素信息的同时， 还建立附加的索引表。 索引表中的每项称为索引项,索引项的一般形式是（关键字， 地址） 。
其优点是检索速度快； 缺点是附加的索引表额外占用存储空间。 另外，增加和删除数据时也要修改索引表， 因而会花费较多的时间。【便于增加，删除数据】

散列存储。 根据元素的关键字直接计算出该元素的存储地址， 又称哈希（Hash）存储。
其优点是检索、 增加和删除结点的操作都很快； 缺点是若散列函数不好， 则可能出现元素存储单元的冲突， 而解决冲突会增加时间和空间开销。【不好掌握】

注意：在学习的过程中，主要掌握前面两种的存储结构

数据的运算

在数据上的运算包括运算的定义和实现。 运算的定义是针对逻辑结构的，指岀运算的功能； 运算的实现是针对存储结构的，指出运算的具体操作步骤

本次结合数据结构的基本类型，基本术语，以及学习数据结构需要掌握哪些编程的语法知识，下期文章，我们将会继续学习新的东西！

每文一语

开始一件事情很难，但过程一定充满了意义