数据结构前言

梦里梦外; 2022-12-28 00:56 162阅读 0赞

**1.什么是数据结构**

数据结构是计算机存储、组织数据的方式。对于特定的数据结构(比如数组)，有些操作的效率很高(读取某个数组元素)，有些操作的效率很低(删除某个数组元素)。程序员的目标是为当前的问题选择最优的数据结构。

数据结构，直白的理解，就是研究数据的存储方式。

例如，一直以来大家面对的数据存储，都是类似存储 1、2、\{a,b,c\} 这样的问题，解决方式无疑是用变量或者数组对数据进行存储，即：  
int a=1; int b=2; char str\[3\]=\{‘a’,‘b’,‘c’\};  
但是，如果要存储这样一组数据：\{张亮，张平，张华，张群，张晶，张磊\}，数据之间具有这样的关系：张亮是张平、张华和张群的父亲，同时张平还是张晶和张磊的父亲，数据之间的关系如图所示：  
![在这里插入图片描述][20201213102238730.png]  
对于存储之间具有复杂关系的数据，如果还是用变量或数组来存储（比如用数组存储 \{“张亮”,“张平”,“张华”,“张群”,“张晶”,“张磊”\} ），数据存储是没有问题，但是无法体现数据之间的逻辑关系，后期根本无法使用，显然不明智。

**2.为什么要学习数据结构**

（1）数据结构是所有计算机专业的同学必学的一门课程  
（2）数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据  
（3）数据是程序的核心要素，因此数据结构的价值不言而喻。无论你在写什么程序，你都需要与数据打交道，比如员工工资、股票价格、杂货清单或者电话本。在不同场景下，数据需要以特定的方式存储，我们有不同的数据结构可以满足我们的需求。  
（4）一个好的程序无非是选择一个合理的数据结构和好的算法，而好的算法的选择很大程度上取决于描述实际问题所采用的数据结构，所以想编写出好的程序必须扎实的掌握数据结构。

**3.常见的数据结构**  
（1）数组  
（2）栈  
（3）队列  
（4）链表  
（5）散列表  
（6）树  
（7）堆  
（8）图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]  
**4.数据结构和算法中的一些概念**  
（1）数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。  
（2）数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位  
（3）数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。  
（4）数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等  
（5）逻辑结构：数据之间的相互关系。

> a.集合结构中的数据元素除了同属于一种类型外，别无其它关系。  
> b.线性结构 数据元素之间一对一的关系  
> c.树形结构 数据元素之间一对多的关系  
> d.图状结构或网状结构 结构中的数据元素之间存在多对多的关系

（6）物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等  
（7）在数据结构中,从逻辑上可以将其分为线性结构和非线性结构  
（8）数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”，存储的是“物理结构”。逻辑结构主要是对该结构操作的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。  
（9）顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。  
（10）算法的五个特性： 有穷性、确定性、可行性、输入、输出。  
（11）算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型，不是程序的描述方式。  
（12）设计算法在执行时间时需要考虑：算法选用的规模、问题的规模  
（13）时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)  
（14）空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占的额外空间。

[20201213102238730.png]: /images/20221120/b00ae8efe35c4bdebb1caecd2fd686f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]: /images/20221120/56bdcad0a3e24b7586bbde77712df49d.png