数据结构概念总结

Data Structures + Algorithms = Programs

一.数据结构

1.基本概念：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

2.数据结构的逻辑结构分为四种：

集合结构，线性结构，树形结构，图结构。

3.数据结构的物理结构分为两种：

顺序存储结构和链式存储结构.

4.学习数据结构的用途：

数据结构在计算机专业课程体系中起到承上启下的作业，熟练使用数据结构可以使程序运行的更快更流畅
思维导图：

二.算法

1.定义：

对特定问题求解步骤的一种描述，它是指令的特定序列，每一条指令表示一个或多个操作

2.特性：

有穷性，确定性，可行性，输入，输出。

3.算法的描述：

自然语言，流程图，程序设计语言，伪代码。

4.算法分析：

（1）算法设计的目标：

正确性，可使用性，可读性，健壮性，时间效率高与存储量低

（2）两种衡量算法效率的方法：

事后统计法（把程序跑一遍）：

必须执行程序，且存在其他因素掩盖算法本质

事前估计法（撇开软硬件相关因素，仅考虑算法本身效率）：

算法执行时间=基本运算时间*运算次数

基本运算：被视为算术运算的一般是最深层循环内语句

（3）算法效率分析：

算法的执行时间可由其基本运算的执行次数来计算

时间复杂度：记号"O",表示随问题规模n增大，算法执行时间的增长率和f(n)的增长率相同。

通常情况下，鉴于运算空间较为充足，常以算法的时间复杂度作为算法优劣的衡量指标

常数阶：O（1）：基本运算次数与问题规模无关。注意：O（1）不代表1次运算

常用的算法时间复杂度的关系：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)

算法的渐进时间复杂度是指：随着问题规模的增大，算法执行时间的增长趋势

（4）算法存储空间分析：

空间复杂度：算法在运行过程中临时占用的空间的度量，一般也是问题规模n的函数s（n）=O(g(n)).

算法的时间复杂度和空间复杂度相互影响，好的时间复杂度可能会导致占用较多的存储空间。
思维导图：

三.线性表

1.线性表的基本概念：

线性表是最简单，最常用的线性结构，线性结构是一个数据元素的有序关系

2.线性表的逻辑结构：

定义：具有相同特性的数据元素的一个有限序列

3.线性表的基本运算：

初始化InitList（&L）,销毁DestroyList(&L),判断是否为空ListEmpty(L),输出DisList(L),返回L中元素的个数ListLength(L)

4.线性表的顺序结构：

使用一块地址连续的存储空间，按照线性表中元素的逻辑顺序依次存放相应元素

特点：

逻辑上相邻以及物理地址相邻，实现随机存储。

顺序表的基本操作：

初始化，销毁，获取元素，查找，插入，删除

5.线性表的链式结构：

特点：

线性表中的数据元素存放在一组地址任意的存储节点，节点之间用链进行连接

结构：

节点= 数据元素 + 指针

头指针：

指向线性表的第一个元素，有时为了简化插入和删除操作，需要在第一个节点之前设置一个头节点

存储密度

存储密度=数据所占空间/节点所占空间 （因此链表的存储密度不高，比起顺序表来说存储空间的利用率比较低）

链式表的基本操作：

初始化，销毁，判断是否为空表，输出，插入，删除，建立单链表：头插法和尾插法
思维导图：

四.特殊的线性表

1.栈：

(1)基本概念：

是限制仅在线性表的一端进行插入和删除运算的线性表

（2）特性：

LIFO：后进先出；具有线性关系

（3）存储结构：

顺序存储结构和链式存储结构；

（4）存储内容：

栈中元素和指示栈顶的标记

（5）进栈和出栈可以穿插进行

2.队列：

(1)基本概念：

是限制仅在线性表的一端进行插入，另一端进行删除的线性表

（2）特性：

FIFO：后进先出；具有线性关系

（3）存储结构：

顺序存储结构和链式存储结构；

（4）入队和出队可以穿插进行

（5）问题：“假溢出”-队伍为“满”，实际为空。解决方法：采用循环队列

栈和队列都是操作受限制的线性表。
思维导图：

3.串：

（1）基本概念：

是由0个或者多个字符组成的有限序列，是数据元素为单个字符的特殊线性表

（2）串与线性表的不同之处:

处理的数据类型不同：

串仅仅处理字符类型，线性表处理任何数据类型。

基本操作针对的类型不同：

线性表的基本操作中，大多以“单个元素”作为操作对象，而串大多以“串的整体“作为操作整体

（3）存储结构：

1.顺序存储结构：串中字符被依次存放在一组连续的存储单元中

两种顺序存储方式：

非紧缩格式：1个内存单元存1个字符

紧缩格式 ：1个内存单元存放多个字符

2.链式存储结构：链式串中的一个节点可以存储一个或多个字符

在链式串中，基本操作的实现大多利用尾插法，建立返回的结果串

（3）两种算法：BF算法和KMP算法

思维导图：