数据结构-概念总结

数据结构概念总结

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算法

思维导图:

数据结构-概念总结

相关推荐