数据结构保研复习

作者：IT小白 | 2024-08-09 22:45:05

踩

数据结构保研复习

数据结构

今天是六月的第一天正式开始数据结构的复习，数据结构的复习主要是根据青岛大学王卓老师的《数据结构课程》展开，在此附上[B站传输门](https://www.bilibili.com/video/BV1nJ411V7bd?from=search&seid=11001905830630457029)

Day 1 6月1号

1.1数据结构研究

程序 = 数据结构 + 算法

1.2基本概念和术语

数据：
数据元素：数据的基本单位【元素，记录，结点，顶点】
数据项：构成数据元素的不可分割的最小单位

数据>数据元素>数学项
数据对象：性质相同的数据元素的集合，是数据的一个子集
数据结构：数据元素之间的关系
- 逻辑结构【数据元素之间的逻辑关系】
- 物理结构（数据的存储结构）【在计算机中存储器中的结构】
- 数据的运算和实现
逻辑结构
- 划分一
  - 线性结构
    - 有且仅有一个开始和一个终端节点，最多只有一个直接前趋和一个后继
    - 线性表、栈、队列、串
  - 非线性结构
    - 一个结点可能有多个直接前驱和直接后继
    - 图、树
- 划分二：四种基本逻辑结构
  - 集合
  - 线性结构
  - 树形结构
  - 图状结构
存储结构
- 顺序存储结构
  - 一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
- 链式存储结构
  - 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针（地址）来表示
- 索引存储结构
  - 在存储结点信息的同时，还建立附加的索引表。
  - 每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引；若一组结点在索引表总只对应一个索引项，则该索引表称之为稀疏索引。
- 散列存储结构
  - 根据结点的关键字直接计算出该结点的存储地址

1.3抽象数据类型的表示与实现

数据类型和抽象数据类型
- 数据类型（Data Type）
  - 数据类型 = 值的集合+操作
- 抽象数据类型（Abstract Data Type, ADT）
  - 抽象数据类型 = 抽象出来的数据模型 + 抽象运算
  - 抽象数据类型的形式定义
    - 抽象数据类型可用（D,S,P）三元组表示
      - 数据对象D：<数据对象的定义>
      - 数据关系S：<数据关系的定义>
      - 基本操作P：<基本操作的定义>

1.4算法和算法分析

算法是我们求解问题的方法和步骤
算法的描述：自然语言，流程图（传统流程图、NS流程图），伪代码（类语言【类C语言】），程序代码
算法与程序的关系：一个问题有多个算法，程序时利用某种程序设计语言对算法的具体实现。
算法的特性：
- 有穷性：执行若干步就可以结束，每一步都在有穷时间内完成
- 确定性：每句话没有二义性
- 可行性：可以执行
- 输入：有零个或者多个输入
- 输出：有一个或者多个输出
算法设计的要求
- 正确性（Correctness）：程序能满足一些刁难的问题
- 可读性 (Readability)：便于人的阅读和立即
- 健壮性 (Robustness)：输入非法数据时，算法恰当的做出反映
- 高效性 (Efficiency):画尽可能少的时间啊和空间
算法分析
- 上述四个设计要求满足的情况下，考虑算法的效率
  - 算法的时间效率
    - 事后统计（测算）
    - 事前分析（估算）
    - 一个算法的时间复杂度 = 一个简单的操作 $\times$ 简单操作次数
    - $\sum每条语句执行的次数（语句的频度）\times该语句执行依次所需的时间（可以简化其为单位时间）$
    - $\sum每条语句执行的次数（语句的频度）$
    - 为了便于比较不同算法的时间效率，我们仅比较他们的数量级
    - $O (f (n))$ 为算法的渐进时间复杂度，简称为时间复杂度
    - 找算法当中执行次数最多的语句
    - 计算时间复杂度的方法
      - 找出语句频度最大的语句作为基本语句
      - 计算基本语句的频度得到问题规模n的某个函数 $f (n)$
      - 取其数量级用符号 $O$ 表示
      - 一些例子：有点难的
      - 例2的答案是 $O(N^3)$
      - 最坏时间复杂度
      - 平均时间复杂度
      - 最好时间复杂度
      - 对于复杂的算法可以分为几个容易估算的部分
        
        加法规则
        乘法规则
  - 算法的空间效率
    - 空间复杂度：算法所需存储空间的度量 $S (n) = O (f (n))$
  - 两者在一般情况下是矛盾的
  - 算法的空间效率
    - 空间复杂度：算法所需存储空间的度量 $S (n) = O (f (n))$
  - 两者在一般情况下是矛盾的

第二章

2.1线性表的定义和特点

线性表时具有相同特性的数据元素的一个有限序列

2.2案例引入

稀疏多项式的存储=》同时记录系数与指数=》二维数据

在这里插入图片描述

稀疏多项式求和
- 创建一个新数组C
- ❓ 数组C的大小范围为【0,a+b】,多少比较合适？顺序存储，存储空间分配不灵活=》链式存储
- 分别从头遍历比较a和b的每一项
  - 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项
  - 指数不相同，则将指数较小的项复制到c中
- 一个数据遍历结束后把另外一个数据的剩余内容放在C的后面
线性表中的数据元素的类型可以是简单类型，也可以是复杂类型
许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序

2.3线性表的类型定义

在这里插入图片描述

InitList(&L)
- 操作结果：构造一个空的线性表L
DestroyList(&L)
- 初始条件：线性表L已经存在
- 操作结构：销毁线性表L
ClearList(&L)
- 初始条件：线性表L已经存在
- 操作结果：将线性表L重置为空表

2.4线性表的顺序表示和实现

线性表顺序存储结构占用一片连续的存储空间

计算在数组中元素存放的位置
在这里插入图片描述

顺序表元素的特点：地址连续，依次存放，随机存取，类型相同 =》用一维数组来进行表示

线性表长可变（删除）

===》用一变量来表示顺序表的长度属性

数组长度不可动态定义

2.6 类C语言有感的操作补充

在这里插入图片描述

C语言的动态内存分配
- malloc(m)函数，开辟m字节长度的地址空间并返回空间的首地址
- sizeof（x）运算，计算变量x的长度
- free§函数，释放指针p所指变量的存储空间，彻底删除一个变量
- 需要加上头文件<stdlib.h>
C++的动态存储分配

在这里插入图片描述

delete p1
1

C++中的参数传递
- 函数调用时传递给形参表的实参必须与形参三个一致（类型，个数，顺序）
- 参数传递的两种方法

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-20GvizVk-1622642924994)(C:\Users\lizzle\AppData\Roaming\Typora\typora-user-images\image-20210602203748643.png)]$