计算机考研408（数据结构（持续更新））
数据结构
一、数据结构
(一)基本概念：
1、数据
数据定义：信息载体、识别符号集、加工原料(所有被计算机存储、处理的对象)
2、 数据元素(数据基本单位)(由若干数据项组成)(整体)(元素)
- 数据项：构成数据元素的不可分割的最小单位
3、 数据结构：(有关系的数据元素集合)(值集)
4、数据对象：(是性质相同的数据元素的集合、是数据的一个子集)
5、数据类型=值集+操作集
1.原子类型：一种值的集合 + 定义在值集合上的一组操作
2.结构类型：一种数据结构 + 定义在这种数据结构上的一组操作
3.抽象数据类型(ADT)：数据对象+关系集+操作
1分类：原子、固定聚合、可变聚合类型
2三元组表示：(D，S，P)=(对象，关系集，操作)
D是数据对象
S是D上的关系集
P是对D的基本操作集
3定义格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
6、 总结：
数据结构：值集
数据类型：值集+操作集
数据类型=数据结构+操作
数据类型(全集)
数据结构(子集)
数据类型(全)⊇数据结构(子)
数据结构是一种数据类型(广义)
数据(数据对象(数据元素(数据项)))
(二)数据结构三要素：逻辑、存储、运算
1、逻辑结构(逻辑关系)
1.形式定义：二元组( Datat-Structure=(D ,S))
D：是数据元素的有限集
S：S是D上关系的有限级(可用序偶表示：<x ,y> (x,y属于D))
直接前驱：x元素为y元素的直接前驱
直接后驱：y元素为x元素的直接后驱
2.分类：(线性+非线性)
1 线性结构(1:1)：(1对1)(前驱后继)(线性表)
线性表：(一维)
1 一般线性表：
顺序表(顺序存储)
链表：
单链表
双链表
循环链表
静态链表
2 受限线性表：
栈
队列：
单向、双向、循环队列
串(字符串)
3 线性表推广：
数组(可存储链表.顺序表)(逻辑+物理)(线+非线)
广义表
2 非线性结构：
集合：(松散关系)
树形结构：(1:n)(1对多)
一般树
二叉树：
堆：
图：(图状结构)(网状结构)：(m:n)(多对多)
无向图
有向图
2、存储结构(物理结构)
分类：存取+存储 直接+随机
①顺序存储：(地址连续、依次存储、线性结构)(逻辑与物理统一)(随机访问)
数组：
②链式存储：(节点值、指针)(随意)(非顺序)(索引表)(随机存储)
单链表：链表=值域+链域
堆区(heap)(堆内存)：二维链表(顺序)
③索引存储：(结点索引号)(索引表)(关键字、地址)(非顺序)
索引表：
④散列存储(哈希hash存储)：(结点关键码值)(散列表)(非顺序)(哈希表)
哈希表：
3、运算=定义+实现
运算定义：(逻辑结构)(实现功能)
运算实现：(存储结构)(具体操作过程)
数据的运算：增、插、删、修、查、排、清、访
⑴ 建立(Create)一个数据结构；
⑵ 消除(Destroy)一个数据结构；
⑶ 从一个数据结构中删除(Delete)一个数据元素；
⑷ 把一个数据元素插入(Insert)到一个数据结构中；
⑸ 对一个数据结构进行访问(Access)；
⑹ 对一个数据结构(中的数据元素)进行修改(Modify)；
⑺ 对一个数据结构进行排序(Sort)；
⑻ 对一个数据结构进行查找(Search)。
(三)算法：程序=算法+数据结构
1、算法的特征：有穷性、确定性、可行性、输入≥0、输出≥1
2、 算法效率的度量：时间复杂度、空间复杂度(大O渐进表示法)
1. 时间复杂度：：常对幂指阶
选取最高阶规模、放弃低阶、简化计算、数量级不变
时间复杂度分类：最坏+平均+最好
最坏时间复杂度：是指在最坏情况下，算法的时间复杂度。
平均时间复杂度：是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度：是指在最好情况下，算法的时间复杂度。
算法运算规则：加法+乘法
加法规则：
乘法规则：
时间复杂度计算步骤：
1. 计算出基本操作的执行次数T(n)
2. 计算出T(n)的数量级：忽略 常量、低次幂、最高次幂系数
3. 用大O来表示时间复杂度
2. 空间复杂度： 临时占用存储空间大小的量度
存储空间分类：
1．程序本身所占空间
2．输入数据所占空间
3．辅助变量所占空间
3、计算机处理问题的步骤：
问题分析
数学模型建立
算法设计与选择
算法表示
算法分析
算法实现
程序调试
结果整理，编写文档
4、好算法要求(优劣)：正确、可读、健壮、效率与低存储
二、线性表：前驱元素 本元素 后继元素
数据元素：元素＝ 数据域 指针域
线性表基本操作：&取地址
线性表的基本运算：
存储结构：顺序存储(顺序表)链式存储(链表)
顺序存储：顺序表
链式存储：单链表 双链表 循环链表(单|双) 静态链表
线性表特点：有限+逻辑先后次序+单个数据元素+类型大小相同+抽象
(一)顺序表：随机访问 随机存取 大量移动元素
1、静态顺序表：(需要先定义数组长度)静态数组、有限个确定数
1.定义一个静态数组：确定数组长度和类型、表长类型
2.初始化静态数组：表长=0=空表
3.主函数调用初始化：函数调用传参
2、动态顺序表：(malloc | free)(new | delete)先默认长度再通过动态数组增加
1.定义一个静态数组：定义指针、容量、表长度、表类型
2.初始化静态数组函数：指针转换类型、表长=0、最大容量=默认
3.增加数组长度函数：使用malloc申请新空间、再复制数据、增加容量、释放空间
4.主函数调用初始化：调用传参
3、计算地址公式：
4、顺序表特点：随机访问、存储密度高、只存数据元素、逻辑物理相邻
1.随机访问：通过首地址和元素序号可以在O(1)时间内找到第i个元素
2.存储密度高：每个结点只存储数据元素
3.逻辑相邻物理相邻：
3.拓展容量不方便：用动态分配的方式实现拓展长度其时间复杂度也比较高
4.插入、删除操作不方便、需要移动大量元素
5.线性表顺序存储类型描述：
5、顺序表上基本操作实现：插入、删除、查找(位|值)
1.插入操作：先判断、后移元素、插入新元素、表长+1
顺序表：L
第i个元素位置(位序)：
插入新元素及位置：
不合法=插入失败：flase
合法=插入成功：true
重要操作：第i个位置及其之后的所有元素右移1个位置：for L(j)=L(j-1)
得到1个空位：L(j)=L(j-1)
插入新元素e：i-1=e
表长+1：L++
插入成功：返回true
1.插入代码：先移动后面再移动前面
2.时间复杂度：
2.删除操作：判断范围、复制删除元素、元素前移、表长-1
1.删除代码：先移动前面再移动后面
2.时间复杂度：、、
3.按值查找(顺序查找):
1.按值查找函数
2.时间复杂度：、、
4.按位查找：
1.按位查找函数：无循环
2.时间复杂度：
(二)链表：指针、离散存储 逐点访问=顺序访问 地址间跳转访问
头指针：必须有(最最前面) 他是链表访问的接口
头结点：第一个元素节点之前(可不要)
头结点和头指针关系： 头指针 ——> 头结点数据 指针
首元结点(首节点)：存放第一个有效数据的节点
尾节点：存放最后一个有效数据的节点
头指针地址：存放指向链表第一个节点的地址
头插法：(符合先进后出特点，是天生的链栈)
尾插法：(符合先进先出的特点，是天生的链队列)
1、链表的创建(初始化)：
2、单链表：节点 = data next
1.无头结点单链表创建：
1原始定义
2头插法
3尾插法
2.有头结点单链表创建：
1原始定义
2头插法
3尾插法
3、双链表：
4、循环链表：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/75313.html
