数据结构与算法 01基础

忘是亡心i 2022-04-13 14:15 191阅读 0赞

数据结构与算法入门  
线性表  
堆和队列  
递归  
树和二叉树  
图  
查找  
排序

有哪些数据结构？  
线性表，栈，队列，数组，广义表，树，二叉树，图  
学习数据结构的四四种境界：  
境界1：听懂理论，听懂算法思路  
境界2：完成主要数据结构基本算法的实现  
境界3：完成更多数据结构更多算法的实现  
境界4：融会贯通，举一反三，在后续开发中综合护具结构知识

--------------------

\#\# 数据结构与算法入门

**1.基本概念**  
数据:  
数据（data）是描述客观事物的数据，字符以及能输入机器的处理的各种符号的集合。  
数据项：  
数据项具有原子性，是不可在分割的最小单位。  
如描述学生信息的姓名,性别，学号等都是数据项。  
数据元素：  
数据元素（data element）是数据的基本单位。树数据集合的个体通常由若干个数据项组成。在计算机中通常作为一个整体进行处理。  
例如一条描述学生的完整信息的数据记录就是一个数据元素。  
数据对象：  
数据对象（data object）是性质相同的数据元素集合，是数据的子集。例如一个学校的所有学生的集合就是数据对象，空间中所有的点集合就是数据对象。  
![在这里插入图片描述][20181129115033230.png]

数据结构:  
数据结构（data structure）是指相互之前存在一种或多种特定关系的集合。  
是组织并存储数据以便有效使用的一种专门格式，它用来反映一个数据的内部构成。以什么构成，呈什么结构。如果队列，数。  
表示一组数据元素及其相互关系的数据结构同样也有两种不同的表现形式。  
一种是数据结构的逻辑层面，即数据的逻辑结构  
一种存在于计算机世界的物理层面，即数据的存储结构

**数据结构=逻辑结构+存储结构**  
\*\*数据结构=逻辑结构+存储结构+（在存储结构上的）运算/操作

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70]

--------------------

## 数据结构类型 ##

数据的逻辑结构指数据元素之间的逻辑关系（和实现无关）  
**分类1：线性结构和非线性结构**  
线性结构：  
有且只有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前驱和一个直接后继。  
线性表就是一个典型的线性结构，它有四个基本特征：  
a.集合中必须存在唯一的一个‘第一个元素’；  
b.集合中必须存在唯一的一个‘最后的元素’；  
c.除最后元素之外，其他数据元素均有唯一的‘后继’；  
d.除第一元素之外，其他数据元素均有唯一的‘前驱’；  
![在这里插入图片描述][20181129132257765.png]  
非线性结构  
相对应于线性结构，非线性结构的逻辑特征是一个结点可能对应多个直接前驱和多个直接后继。常见的非线性结构有：数，图等。  
![在这里插入图片描述][20181129132611329.png]

**分类2：集合结构 线性结构 数状结构 网状结构**  
逻辑结构有四种基本类型：集合结构，线性结构，数状结构和网状结构。  
表和树是最常用的两种高效数据结构，许多高效的算法能够用着两种数据结构来设计实现。

集合结构：就是数学中数学的集合，集合中的元素有三个特征：  
a.确定性（集合中的元素必须是确定的）  
b.唯一性（集合中的元素互不相同，例如集合=\{1，a\},则a不能等于1 ）  
c.无序性（集合中的元素没有先后之分），如集合\{3，4，5\}和\{3,5,4\}算作同一个集合。  
该结构的数据元素间的关系是‘属于同一个集合’，别无其他关系。  
因为集合中的元素关系很弱，数据结构中不对该数据进行研究。

--------------------

线性结构:数据结构中线性结构指的是数据元素之间存在着‘一对一’的线性关系的数据结构。 树状结构：除了一个数据元素（元素01）以外每个数据有且有一个直接的前驱元素，但是可以有多个直接后继元素，特点是数据元素之间是1对多的联系。 网状结构：每个数据元素可以有多个之间前驱元素，也可以有多个之后后续元素，特点是元素之间是多对多的联系。 !\[在这里插入图片描述\](https://img-blog.csdnimg.cn/2018112914043122.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY=,size\_16,color\_FFFFFF,t\_70)

**3.数据的存储结构**  
数据的存储结构主要包括数据元素本身的存储元素之间关系的表示，是数据的逻辑结构在计算机中的表示。  
常见的存储结构有顺序存储，链式存储，索引存储，以及散列存储。  
a.顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，节点之间的逻辑关系由存储三元的邻接关系来表现。由此得到的存储结构为顺序存储结构。  
有点：节省空间，因为分配的数据存储单元全用存放加点的数据。  
缺点：插入和删除需要移动元素，效率低  
b.链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素。每个节点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链接关系反映出来。  
特点：  
1.比顺序存储结构的存储密度小。  
2.逻辑上相邻的节点，物理上不必相邻。  
3.插入，删除，灵活（不必移动节点，只要改变节点中的指针）  
4.查找节点时链式存储要比顺序存储慢  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70 1]

3.索引储存结构：除建立存储索引的节点信息外，还建立附加的索引表来标识节点的地址。比如图书，字典目录。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70 2]  
4.散列储存结构：根据节点的关键字直接计算出该节点的存储地址。一种神奇的结构，增加，查询速度快。

--------------------

## 算法 ##

是指令的集合，是为解决特定问题而规定的一系列操作。  
它是明确定义的可计算的过程，以一个数据集合作为输入，并产出一个数据集合作为输出。  
一个算法通常来说具有以下五个特性：  
1.输入：一个算法应以待解决的问题的信息作为输入。  
2.输出：输入对应的指令集处理后得到的信息。  
3.可行性：算法是可行的，即算法中的每一条指令都是可以实现的。均能在有限的时间内完成。  
4.有穷性:算法执行的指令个数有限的，每个指令又是在有限的时间内完成的，因此整个算法也是在有限的时间内可以结束的。  
5.确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始。多次执行同一指令集结构总是相同的。  
简单的说：算法就是计算机解题非工程

评价算法优劣的依据：复杂度（时间复杂度和空间复杂度）  
算法的复杂性体现在运行该算法时计算机所需资源多少，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度。  
时间复杂度：是指执行算法时需要的计算工作量。  
空间复杂度：是指执行短发时需要的内存空间。

--------------------

## 时间复杂度（Time Complexity）定义 ##

时间频度：  
一个算法执行所消耗的时间。从理论上不能推算出来。必须上机测试才能知道。  
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中的语句执行次数多，它的花费时间就多。  
一个算法中的语句执行次数称为语句频度或时间频度，表示为T（n），n表示问题的规模。

时间复杂度：  
但有时我们想知道它变化时呈现什么规律，想知道问题的规模，而不是具体的次数，引入时间复杂度  
。时间复杂度是在时间频度去掉低阶项和首相常数。用O表示：  
T(n) = O(f(n))

[20181129115033230.png]: /images/20220413/5e7fd6948acf464a94832d9601265ac5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70]: /images/20220413/39fff162771f499797df307eecb9f422.png
[20181129132257765.png]: /images/20220413/4d20ac11438141fdac780eb02ce61212.png
[20181129132611329.png]: /images/20220413/a9345a59ab124dda80ef72c5130f4c30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70 1]: /images/20220413/065d98ae508b4e48b29147aa8b58922b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5sYW5zZTc2MjY_size_16_color_FFFFFF_t_70 2]: /images/20220413/66177fda7fcd4202ab3c2a09ab964989.png