数据结构-概念总结
数据结构概念总结
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(n2)<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算法
思维导图：
