考研408|计算机考研408（数据结构（持续更新)) 链表|算法|图论|数据结构

计算机考研408（数据结构（持续更新））

数据结构
- 一、数据结构
- - (一)基本概念：
  - - 1、数据
    - 2、数据元素(数据基本单位)(由若干数据项组成)(整体)(元素)
    - 3、数据结构：(有关系的数据元素集合)(值集)
    - 4、数据对象：(是性质相同的数据元素的集合、是数据的一个子集)
    - 5、数据类型=值集+操作集
    - - 1.原子类型：一种值的集合 + 定义在值集合上的一组操作
      - 2.结构类型：一种数据结构 + 定义在这种数据结构上的一组操作
      - 3.抽象数据类型(ADT)：数据对象+关系集+操作
      - 1分类：原子、固定聚合、可变聚合类型
        
        2三元组表示：(D，S，P)=(对象，关系集，操作)
        
        3定义格式：
    - 6、总结：
  - (二)数据结构三要素：逻辑、存储、运算
  - - 1、逻辑结构(逻辑关系)
    - - 1.形式定义：二元组( Datat-Structure=(D ,S))
      - 2.分类：(线性+非线性)
      - 1 线性结构(1:1)：(1对1)(前驱后继)(线性表)
        
        2 非线性结构：
    - 2、存储结构(物理结构)
    - - 分类：存取+存储直接+随机
    - 3、运算=定义+实现
    - - 数据的运算：增、插、删、修、查、排、清、访
  - (三)算法：程序=算法+数据结构
  - - 1、算法的特征：有穷性、确定性、可行性、输入≥0、输出≥1
    - 2、算法效率的度量：时间复杂度、空间复杂度(大O渐进表示法)
    - - 1. 时间复杂度：：常对幂指阶
      - 时间复杂度计算步骤：
      - 2. 空间复杂度：临时占用存储空间大小的量度
      - 存储空间分类：
    - 3、计算机处理问题的步骤：
    - 4、好算法要求(优劣)：正确、可读、健壮、效率与低存储
- 二、线性表：前驱元素本元素后继元素
- - (一)顺序表：随机访问随机存取大量移动元素
  - - 1、静态顺序表：(需要先定义数组长度)静态数组、有限个确定数
    - 2、动态顺序表：(malloc | free)(new | delete)先默认长度再通过动态数组增加
    - 3、计算地址公式：
    - 4、顺序表特点：随机访问、存储密度高、只存数据元素、逻辑物理相邻
    - 5、顺序表上基本操作实现：插入、删除、查找(位|值)
    - - 1.插入操作：先判断、后移元素、插入新元素、表长+1
      - 2.删除操作：判断范围、复制删除元素、元素前移、表长-1
      - 3.按值查找(顺序查找):
      - 4.按位查找：
  - (二)链表：指针、离散存储逐点访问=顺序访问地址间跳转访问
  - - 1、链表的创建(初始化)：
    - 2、单链表：节点 = data next
    - - 1.无头结点单链表创建：
      - 2.有头结点单链表创建：
    - 3、双链表：
    - 4、循环链表：

【考研408|计算机考研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属于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个位置：forL(j)=L(j-1) 得到1个空位：L(j)=L(j-1) 插入新元素e：i-1=e 表长+1：L++ 插入成功：返回true1.插入代码：先移动后面再移动前面 2.时间复杂度：

2.删除操作：判断范围、复制删除元素、元素前移、表长-1

1.删除代码：先移动前面再移动后面 2.时间复杂度：、、

3.按值查找(顺序查找):

1.按值查找函数 2.时间复杂度：、、

4.按位查找：

1.按位查找函数：无循环 2.时间复杂度：

(二)链表：指针、离散存储逐点访问=顺序访问地址间跳转访问

头指针：必须有(最最前面)他是链表访问的接口头结点：第一个元素节点之前(可不要) 头结点和头指针关系：头指针——>头结点数据指针首元结点(首节点)：存放第一个有效数据的节点尾节点：存放最后一个有效数据的节点头指针地址：存放指向链表第一个节点的地址头插法：(符合先进后出特点，是天生的链栈) 尾插法：(符合先进先出的特点，是天生的链队列)

1、链表的创建(初始化)： 2、单链表：节点 = data next 1.无头结点单链表创建：