数据结构期末复习

1. 基本术语

1. 数据结构分为逻辑结构与存储结构

   • 逻辑结构：关注元素之间的逻辑关系，决定数据如何组织和关联
   • 存储结构：决定数据之间在计算机内存中的物理存放方式

2. 逻辑结构分类

   • 集合：元素同属一个集合，无其他关系
   • 线性结构：一个对一个，比如线性表，栈，队列。
   • 树形结构：一个对多个。
   • 图形结构：多个对多个

3. 存储结构分类

   • 顺序存储结构：数据元素在物理位置上是连续的
   • 链式存储结构：数据元素在物理位置上不一定连续，但是数据元素除了要存信息，还要存储一个或多个指向其他元素的指针(也就是存下一个或多个元素的物理位置)。

2. 算法

1. 算法的五个基本特征

   1. 输入
   2. 输出
   3. 确定性
   4. 有穷性
   5. 可行性

2. 时间复杂度

   • 语块被执行的次数
   • 一次计算，无论n的大小如何，计算和返回结构所需时间都是O(1)

3. 空间复杂度

   • 占用多少空间的指标

3. 线性表

1. 定义：

   • 数据元素存在一对一线性关系，即每个元素(除了第一个和最后一个)都有一个前驱和一个后继

2. 特点:

   • 有序性：线性表中的元素是有序的，每个元素都有一个位置，我们可以通过位置来访问元素。
   • 元素唯一性：每个元素在线性表中的位置是唯一的。
   • 动态性：线性表的大小是动态变化的

3. 常见操作：

   1. 插入
   2. 删除
   3. 访问
   4. 搜索
   5. 排序

4. 线性表顺序表示和实现

   • 顺序表：把线性表顺序存储起来是顺序表。

   • 顺序存储定义：

     • 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

   • 例：

     • 顺序表中第一个元素存储地址是102，每个元素的长度是2，那么第四个元素的地址是108

• 顺序表优点：

  • 时间：可以随机存取表中任一元素
  • 空间：存储密度大

• 顺序表的缺点

  • 时间：在插入 删除某一元素时，需要移动大量元素
  • 空间：浪费存储空间，属于静态存储形式，元素个数不能自由扩充

• 为了克服顺序表的缺点 我们需要用链表

• 链表

  • 线性表的链式表示
  • 在逻辑上相邻的元素在物理上不一定相邻

• 节点：

  • 在链式存储结构中，火车的每一届车厢就像链式存储结构中的一个节点
  • 节点是构成线性表的基本单元，每个节点包括两部分：
    • 数据：车厢里装的货物，对应节点中存储的数据。
    • 指针：车厢之间的钩子，对应节点中用来指向下一节点的指针。
  • 头节点：火车的第一节车厢，对应链表存储的头节点
    • 头节点通常包含一个指向第一个实际数据节点的指针。
  • 尾节点：火车的最后一节车厢，对应链表存储的尾节点
    • 没有指针，只包括数据

• 循环链表：

  • 尾节点的指针指向头节点，叫做循环链表

4. 栈

• 定义：只能在表的一端(栈顶)进行插入和删除运算的线性表

  • 入栈出栈都通过栈顶

• 特点：先进后出，后进先出

• 顺序栈

//定义顺序栈的结构体
typedef struct {
  int *data; //存储栈元素的数组
  int top; //栈顶指针
  int base; //栈底指针
  int maxSize; //栈的最大容量
}SeqStack

• 链栈
  • 运算首先的单链表，只能在链表头部进行操作，栈顶指针就是链表的头指针。

5. 队列

队列是一种先进先出的线性表，在表一段插入，在另一端删除

6. 串

定义：由零个或多个字符组成的有限序列

串的匹配：KMP算法

• 利用已经匹配成功的部分信息

树

结构特点：一对多

子树：树中任意一个节点及其所有后代节点

二叉树

• 性质：二叉树的第i层上至多有2的i-1次方个结点
  • 深度为k的二叉树至多有2的k-1次方个结点

满二叉树

• 每层都两个节点的二叉树

完全二叉树

• 只有最后一层叶子不满，且全部集中到左边
• 具有n个节点的完全二叉树深度必为log下标二 n + 1