【数据结构和算法的概念等】

一、数据结构

1、数据结构的基本概念

数据： 是所有能输入到计算机中并能被程序识别和处理的符号集合。包括：数值数据（整数、实数等），非数值数据（图形、图像、声音、文字等）。

数据元素： 数据的基本单位，通常作为一个整体进行考虑和处理，一个数据元素可由若干数据项组成；

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

数据对象： 数据对象是具有相同性值的数据元素的集合，是数据的一个子集；

关系：

举例进行理解：

1. 学校里有很多不同类型的表：数据
2. 单独的一张成绩单：数据对象
3. 成绩单中每一行有姓名、学号、班级等：数据元素
4. 成绩单中每一行的每一个表格姓名等都是一个个的数据项

数据类型： 一组值的集合以及定义于这个值集上的一组操作
1.原子类型：其值不可再分的数据类型，如bool和int类型
2.结构类型：其值可以再分解为若干成分的数据类型，如结构体

抽象数据类型（Abstract Data Type, ADT）： 一个数据模型以及定义在该模型上的一组操作，也就是定义了一个数据结构

2、数据结构的三要素

数据结构： 相互之间存在相互关系的数据元素的集合，如下为数据的三要素：

逻辑结构、存储（物理）结构、数据的运算

2.1 数据的逻辑结构

数据的逻辑结构是指：数据之间逻辑关系的整体。

集合：数据元素之间没有关系；
线性结构：数据元素之间是一对一的线性关系；
树结构：数据元素之间是一对多的层次关系；
图结构：数据元素之间是多对多的任意关系。

2.2 数据的存储（物理）结构

数据的存储结构是指：数据及其逻辑结构在计算机中的表示。

顺序存储结构： 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示；
链式存储结构： 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示；
索引存储结构： 又称为直接寻址，可以通过下标来进行直接访问，索引项的一般形式是（关键字，地址）；
散列存储结构： 又称为哈希存储，地址会通过hash算法来运算成一个相同长度的hash值，然后存放这个hash值，而不是直接存放地址，在访问关键字的时候会通过运算解码hash值，然后再访问。

注意：

1. 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的；
2. 数据的存储结构会影响存储空间分配的方便程度；
3. 数据的存储结构会影响对数据运算的速度。

2.3 数据的运算

根据逻辑结构来定义，根据存储结构来实现。

二、算法

1、算法概念

算法： 是对特定问题求解步骤的一种描述，是指令的有限序列。程序 = 数据结构 + 算法 ；算法必须是有穷的，而程序可以是无穷的。

2、算法的特性及特点

算法的基本特性：

1. 有穷性： 有穷时间内能执行完
2. 确定性： 相同输入只会输出相同结果
3. 可行性： 可以用乙游的基本操作实现算法
4. 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合
5. 输出： 一个算法有一个或多个输出，这些输出是与输入有着某种特定的关系

好算法的特点：

1. 高效性与低存储要求：即算法执行省时、省内存，时间复杂度低、空间复杂度低
2. 正确性：能正确解决问题
3. 健壮性：指能处理一些异常
4. 可读性：对算法的描述要让其他人也能看懂

3、算法分析

1. 时间复杂度：当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，关注的是增长趋势，用大写O记号表示；
2. 空间复杂度：算法在执行过程中需要的辅助空间数量，地柜程序看递归深度与问题规模n的关系。