初识数据结构

一、数据结构与算法概述

1、数据结构

定义：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合； 通俗点来讲的话：我们把现实世界中海量以及复杂的问题，以特定的数据类型和特定的存储结构保存到主存储器（内存）中；

特定的数据类型、特定的存储结构释义：

例1：当我需要存储一个班级学生的信息，假设有20个学生，那么直接可以使用连续的存储结构（数组）就可以了。

例2：如果需要保存1万个人，这个时候依然可以使用数组来存储，但是这样就比较困难了，当数据量很大的时候，数组的连续内存空间无法支撑那么大的数据量，这个时候就可以使用链表进行保存，它不需要一块连续的空间。例如图2-1，每一块内存都不是连续的，每一块内存除了需要保存自身属性外，还额外存储一个指针，这个指针指向下一块内存的地址，以此来串联起来。

2-1

例3：如果说现在需要存储学校、年级、班级的数据，那么链表就无法进行存储了，链表无法体现出来层级，这个时候就需要使用树形结构来存储。

如图3-1

3-1

例4：还有一种情况，存储交通图的情况，每一个站点都存在关系，这个时候用数组存储不了、链表、树也存储不了，这个时候就只能使用图来存储了。

2、算法：

定义：

实现某个功能而执行的相应的操作叫做算法；

衡量算法的标准：

1. 时间复杂度；程序大概执行的次数（算法最核心的步骤运行的次数），而非执行的时间。因为执行的时间会因为环境的差异而发生变化。
2. 空间复杂度；算法执行过程中大概需要占用最大内存；
3. 可读性（难易程度）；如果写的算法只有自己看的懂，它也不算做是好的算法。
4. 健壮性；在算法输入一些非法值的时候不能产生崩溃。

还有一个是正确性，但是这个标准比较废话，算法最基本的就是计算正确了，如果计算不正确它也不叫算法了。

二、数据结构的结构划分

数据结构整体可划分为逻辑结构和物理结构

1. 逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关；这个也是主要的研究方向。
2. 物理结构：指数据的逻辑结构在计算机存储空间的存放形式；

逻辑结构包含的内容：

1. 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

集合

1. 线性结构：数据结构中的元素存在一对一的相互关系；
2. 树形结构：数据结构中的元素存在一对多的相互关系；

树形结构

1. 图形结构：数据结构中的元素存在多对多的相互关系。

图形结构