Plume Blog
数据结构课堂笔记
灰羽 Lv3
  2022-01-10 17:10:42   2023-03-30 08:57:50  

第一章 绪论

计算机主要用途

  • 早期进行数值计算
  • 后期扩展到非数值计算

表格   线性结构    一对一关系
井字棋 人机对弈 树型结构 一对多关系
比赛时间安排 图状结构 多对多关系

数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。

基础概念和术语

数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项(data item) 组成。

数据对象(data object) ：是性质相同的数据元素的集合，是数据的一个子集。

**数据结构(data structure)**：是相互之间存在一种或多种特定关系的数据元素的集合。

数据元素之间存在着某种关系，这种关系称为结构，通常有四类：(1)集合 (2)线性结构(3)树形结构(4)图状结构或网状结构。

由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure=(D,R)

  • 逻辑结构  :数据元素间抽象化的相互关系
  • 储存结构(物理结构) ：数据元素及关系在计算机储存器中的储存方式
  • 运算（算法）

储存结构两方面的内容

  1. 数据元素自身值的表示（数据域）
  2. 该结点与其它结点关系的域

四种基本存储方法

  1. 顺序的存储方法（顺序映像）

    逻辑上相邻物理上相邻

  2. 链接存储方法（非顺序映像）

    逻辑上相邻物理上不一定相邻(指针)

  3. 索引存储方法

  4. 散列存储方法

数据类型和抽象类型

数据类型

定义：一个数据(值)的集合，以及定义在这个数据集(值集)上的一组操作总称

因为值的不同特性，高级程序语言的数据类型可以分为两类，一类是非结构的原子类型。原子类型的值是不可分解的。另一类是可分解的结构类型。

抽象数据类型（ADT）

  • 虚拟存储结构
  • 由用户定义，用以表示应用问题的数据模型
  • 将逻辑结构向存储结构转换（虚拟）
  • 由基本的数据类型组成
  • 数据封装和信息隐蔽，

基本操作的定义

&有返回值并且值是可以变的

例1-6 抽象数据类型三元组的定义

多形数据类型是指其值的成分不确定的数据类型。

抽象数据类型的表示和实现

1.4 算法和算法分析

1.4.1 算法

定义:一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。

是对特定问题求解步骤的一种描述，实施指令的有限序列，其中每一条指令表示一个或多个操作；

特性：有穷性，确定性，可行性，输入，输出

1.4.2 算法设计的要求

正确性，可读性，健壮性，效率与低存储量需求

1.4.3 算法效率的度量

T(n)=O(f(n)) 表示问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

1.4.4 算法的存储空间需求

S(n)=O(f(n))

嵌套相乘，&相加

第二章 线性表

2.1 线性表的类型定义

线性表是n个数据元素的有限序列，一个数据元素刻有若干个数据项组成。

没有数据元素时称为空表

2.2.1 顺序表的表示

逻辑上相邻，物理上就相邻

b+（i—1）l

2.2.2 顺序表的实现

采用数组描述顺序表的两种方法

  • 静态分配
  • 动态分配

指针和数组可以通用

顺序表的优缺点：

优点：无须为表示节点间的逻辑关系而增加额外的存储空间（存储密度大）；可以方便的随机存储访问表中的任一结点 o（1）；

缺点：插入和删除平均移动一半结点读写

作业：算法2.4/2.5

2.3 线性表的链式表示和实现

2.3.1 与链式存储有关的术语

结点：数据元素的存储映像。由数据域和指针域两部分组成；

链表：

单链表：

双链表：

多链表：

头指针：是指向链表中的第一个结点

头结点：是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长信息。

好处：为了对链表进行操作时，可以对空表，非空表的情况以及对首元结点进行统一处理，更加方便。

如何表示空表：

无头结点时，当头指针的值为空

头结点的数据域放什么：

首元结点：

头指针无法移动，创建移动指针，指针运算中等号表示的是指向。

2.3.2 循环链表

表中最后一个结点的指针域指向头结点，整个链表形成一个环。

2.3.3 双向链表

为克服单链表单向性的缺点，可以利用双向链表，顾名思义，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。

1
2
3
4
5
typedef struct DuLNode{
     ElemType      data;
     struct DuLNode  *prior;
     struct DuLNode  *next;
}NuLNode,*DuLinkList;

2.4 一元多项式的表示及相加

一般情况下一元n次多项式可写为：$P_n=p_1x^{e_1}+p_2x^{e_2}+…+p_mx^{e_m}$

第三章 栈和队列

3.1 栈

3.1.1 抽象数据类型栈的定义

栈(stack) 是仅在表尾进行插入或删除操作的线性表，表尾称为栈顶(top)，相应的表头称为栈底(bottom)，不含元素的称为空栈。

栈的修改是按照后进先出的原则进行的，又称后进先出的线性表，简称LIFO结构。

栈的抽象数据类型定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ADT Stack{
  数据对象：D={a_i|a_i属于ElemSet，i=1,2,...,n,n≥0}
  数据关系：R_1{<a_{i-1},a_i>|a_{i-1},a_i属于D,i=2,...,n}约定a_n为栈顶a_1为栈底。
  基本操作：
  InitStack(&S)
  DestroyStack(&S)
  ClearStack(&S)
  StackEmpty(S)
  StackLength(S)
  GetTop(S,&e)
  Push(&S,e)
  Pop(&S,&e)
  StackTraverse(S,visit())
}ADT Stack

3.1.2 栈的表示和实现

非空栈的栈顶指针始终在栈顶元素的下一位置上

Status Push(SqStack&S,SElemType e){
//插入元素
if(S.top-S.base>=S.stacksize){

}

}

链栈

3.2 栈的应用举例

3.2.1 数制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void conversion(){
  //对于输入任意一个非负十进制整数，打印输出与其等值的八进制数
  InitStack(S); 
  // 构造空栈
  scanf("%d",N);
  while(N){
    Push(S,N%8);
    N=N/8;
  }
  while(!StackEmpty(s)){
    Pop(S,e);
    printf("%d",e);
  }
}//conversion

3.3 栈与递归的实现

一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，叫做递归函数。

特点：结构简单，但占空间

3.4 队列

队列是一种先进先出的线性表，它只允许在队尾进行插入，在队头进行删除

3.4.1 抽象数据类型

3.4.2 队列的链式表示和实现

3.4.3 队列的顺序表示和实现 循环队列

初始化时 front=rear=0

在顺序队列中，内存尚有空间但无法入队，这种情况叫做假溢出

第四章 串

4.1 串类型的定义

串是由零个或多个字符组成的有限序列，零个字符称为空串，由一个或多个空格组成的串称为空格串(长度为空格字符的个数)

4.2 串的表示和实现

4.2.1 定长顺序存储表示

0号单元格存放串的长度

超出预定的长度串值会被舍去，称为截断。

4.2.2 堆分配存储表示

仍是一组地址连续的存储单元存放串值字符序列，但空间存储是动态分配得到的

0号位置不放串长

4.2.3 串的块链存储表示

结点中数据域被分为几部分，就说该结点大小为几

存储密度=串值所占存储位/实际分配存储位

4.3 串的模式匹配

子串定位操作称为模式匹配

缺点：回溯次数多，低效O(mn)

KMP快速模式匹配

无回溯，高效O(m+n)

第五章 数组与广义表

5.1 数组的定义

数组一旦被定义，它的维数和维界就不再改变，因此数组只有存取元素和修改元素的操作。

5.2 数组的顺序表示和实现

loc（aij）=首地址+前面所有元素所占存储空间的总数

5.3 矩阵的压缩存储

压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间

5.3.1 特殊矩阵

对称矩阵 [n(n+1)/2]

三角矩阵 [n(n+1)/2+1]

下三角矩阵是指矩阵的上三角(不包括对角线)中的元均为常数c或0的n阶矩阵

对角矩阵 (3n-2)

5.3.2 稀疏矩阵

在m×n的矩阵中，有t个不为0元素，令δ=t/mn，称δ为矩阵的稀疏因子，通常认为δ≤0.05时称为稀疏矩阵。
(i，j，t)

广义表非空时，称第一个元素为表头

第六章 树与二叉树

6.1树的定义和基本术语

树是包含n个结点的有限集

空树中没有结点

结点的度：子结点的个数
叶结点/终端结点：度为0
分支结点/非终端结点：度不为0
双亲结点/父结点：含有子结点，为该节点的父节点
子结点/孩子结点：根节点的子结点
兄弟结点：含有相同父节点的结点

结点的层次：根为第一层，以此类推
树的高度或深度：树中结点的最大层次

子孙：某结点为根的子树任一结点
森林：互不相交的树的集合

结点数-1=分支数

6.2 二叉树

二叉树的子树有左右之分

满二叉树：所有分支结点度为2，叶子结点都在最下一层。
完全二叉树：最多只有下面两层的度数为2，最下面一层叶结点都在左边位置

性质：

6.2.3 二叉树的存储结构

顺序存储结构仅适用于完全二叉树

n个结点的二叉链表有n+1个空链域

6.3.1 遍历二叉树

访问每个结点且仅一次
先序遍历
中序遍历
后序遍历

6.3.2 线索二叉树

lchild LTag data RTag rchild
线索链表其中指向结点前驱和后继的指针叫做线索。加上线索的二叉树叫做线索二叉树。

6.4 树和森林

6.4.1 树的存储结构

双亲表示法

孩子表示法

树和二叉树转换

6.4.2 森林与二叉树的转换

森林转化成二叉树

兄弟加线，左孩子右兄弟

二叉树转化成森林

左孩子的右孩子加线

6.4.3 树和森林的遍历

由树的定义引出两种方法：先根(次序)遍历树，即先访问树的根节点，然后依次先根遍历根的每棵子树；另一种是后根(次序)遍历，即先依次后根遍历每棵子树，然后访问根节点。

树的先序遍历相当于二叉树的先序遍历
树的后序遍历相当于二叉树的中序遍历
树没有中序遍历，树的子树无左右之分

按照森林和树相互递归的定义引出两种方法：
线序遍历森林
中序遍历森林

6.6 哈夫曼树

树的带权路径长度WPL为树中所有叶子结点带权路径长度之和。

6.6.2 哈夫曼编码

任一个字符的编码都不是另一个字符编码的前缀，叫做线索前缀编码。

第七章 图

7.1 图的定义和术语

图是一种数据结构，加上一组基本操作，就构成抽象数据类型。

图中数据元素通常称为**顶点V,**是有穷的非空集合。弧头为终端点，弧尾为初始点。

对于无向图弧数的取值从0到n(n-1)/2，最大的取值时称为完全图。有向图弧的取值是从0到n(n-1)，最大时称为有向完全图。

第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复的路径称为简单路径。

在无向图中任意两顶点都是连通(之间有路径)的，则称其为连通图。所谓连通分量指的是无向图中的极大连通子图。

7.2 图的存储结构

7.2.1 数组表示法

以二维数组表示n个顶点的图时，需存放n个顶点和n平方个弧信息。

对于无向图(对称)，顶点的度是邻接矩阵中第i行(或第i列)的元素之和。对于有向图，第i行的元素之和为该顶点的出度OD，第j列元素之和为顶点的入度ID。

7.2.2 邻接表

邻接表是一种链式存储结构，每个顶点建立一个单链表。每个结点由3个域组成，其中**邻接点域(adjvex)指与顶点邻接的点在图中的位置，链域(nextarc)指下一条边或弧的结点，数据域(info)**存储边或弧的信息，如权值。

每个链表有一个表头结点，除了包含设有**链域(firstarc)指向第一个结点之外，还有数据域(data)**存储顶点的名或其他相关的信息。这些表头结点通常以顺序结构存储。

建立邻接表时，若顶点信息为顶点的编号，则时间复杂度为O(n+e)，否则查找O(n×e)

7.2.3 十字链表

十字链表是有向图另一种链式存储结构。可以看作是将有向图的邻接表和逆邻接表结合起来得到的一种链表。顶点＋弧的信息。

在弧节点中有5个域。其中尾域(tailvex)和头域(headvex)分别指示弧头和弧尾这两个顶点在图中的位置。链域hlink指向弧头相同的下一条弧，而链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。

头结点即为顶点结点，由三个域组成，data存储顶点名称等相关信息，firstin和firstout分别指向以该顶点为弧头或弧尾的第一个结点。

7.2.4 邻接多重表

邻接多重表是无向图的另一种链式存储结构。顶点一维数组，边为链式存储。

7.3 图的遍历

从图中一顶点出发，彷遍其中其余结点，每一个顶点访问一次。

7.3.1 深度优先搜索

路径用栈保存

7.3.1 广度优先搜索

路径用队列保存

7.4 图的连通性问题

最小生成树：最小代价生成树

  1. 第一章 绪论
    1. 计算机主要用途
    2. 基础概念和术语
      1. 储存结构两方面的内容
      2. 四种基本存储方法
    3. 数据类型和抽象类型
      1. 数据类型
      2. 抽象数据类型（ADT）
      3. 基本操作的定义
      4. 抽象数据类型的表示和实现
  2. 1.4 算法和算法分析
    1. 1.4.1 算法
    2. 1.4.2 算法设计的要求
    3. 1.4.3 算法效率的度量
    4. 1.4.4 算法的存储空间需求
  • 第二章 线性表
    1. 2.1 线性表的类型定义
      1. 2.2.1 顺序表的表示
      2. 2.2.2 顺序表的实现
    2. 2.3 线性表的链式表示和实现
      1. 2.3.1 与链式存储有关的术语
      2. 2.3.2 循环链表
      3. 2.3.3 双向链表
    3. 2.4 一元多项式的表示及相加
  • 第三章 栈和队列
    1. 3.1 栈
      1. 3.1.1 抽象数据类型栈的定义
      2. 3.1.2 栈的表示和实现
      3. 3.2 栈的应用举例
      4. 3.2.1 数制转换
    2. 3.3 栈与递归的实现
    3. 3.4 队列
      1. 3.4.1 抽象数据类型
      2. 3.4.2 队列的链式表示和实现
      3. 3.4.3 队列的顺序表示和实现 循环队列
  • 第四章 串
    1. 4.1 串类型的定义
    2. 4.2 串的表示和实现
      1. 4.2.1 定长顺序存储表示
      2. 4.2.2 堆分配存储表示
      3. 4.2.3 串的块链存储表示
    3. 4.3 串的模式匹配
  • 第五章 数组与广义表
    1. 5.1 数组的定义
    2. 5.2 数组的顺序表示和实现
    3. 5.3 矩阵的压缩存储
      1. 5.3.1 特殊矩阵
      2. 5.3.2 稀疏矩阵
  • 第六章 树与二叉树
    1. 6.1树的定义和基本术语
    2. 6.2 二叉树
      1. 6.2.3 二叉树的存储结构
      2. 6.3.1 遍历二叉树
      3. 6.3.2 线索二叉树
    3. 6.4 树和森林
      1. 6.4.1 树的存储结构
      2. 6.4.2 森林与二叉树的转换
      3. 6.4.3 树和森林的遍历
    4. 6.6 哈夫曼树
      1. 6.6.2 哈夫曼编码
  • 第七章 图
    1. 7.1 图的定义和术语
    2. 7.2 图的存储结构
      1. 7.2.1 数组表示法
      2. 7.2.2 邻接表
      3. 7.2.3 十字链表
      4. 7.2.4 邻接多重表
    3. 7.3 图的遍历
      1. 7.3.1 深度优先搜索
      2. 7.3.1 广度优先搜索
    4. 7.4 图的连通性问题
    1. 第一章 绪论
      1. 计算机主要用途
      2. 基础概念和术语
        1. 储存结构两方面的内容
        2. 四种基本存储方法
      3. 数据类型和抽象类型
        1. 数据类型
        2. 抽象数据类型（ADT）
        3. 基本操作的定义
        4. 抽象数据类型的表示和实现
    2. 1.4 算法和算法分析
      1. 1.4.1 算法
      2. 1.4.2 算法设计的要求
      3. 1.4.3 算法效率的度量
      4. 1.4.4 算法的存储空间需求
  • 第二章 线性表
    1. 2.1 线性表的类型定义
      1. 2.2.1 顺序表的表示
      2. 2.2.2 顺序表的实现
    2. 2.3 线性表的链式表示和实现
      1. 2.3.1 与链式存储有关的术语
      2. 2.3.2 循环链表
      3. 2.3.3 双向链表
    3. 2.4 一元多项式的表示及相加
  • 第三章 栈和队列
    1. 3.1 栈
      1. 3.1.1 抽象数据类型栈的定义
      2. 3.1.2 栈的表示和实现
      3. 3.2 栈的应用举例
      4. 3.2.1 数制转换
    2. 3.3 栈与递归的实现
    3. 3.4 队列
      1. 3.4.1 抽象数据类型
      2. 3.4.2 队列的链式表示和实现
      3. 3.4.3 队列的顺序表示和实现 循环队列
  • 第四章 串
    1. 4.1 串类型的定义
    2. 4.2 串的表示和实现
      1. 4.2.1 定长顺序存储表示
      2. 4.2.2 堆分配存储表示
      3. 4.2.3 串的块链存储表示
    3. 4.3 串的模式匹配
  • 第五章 数组与广义表
    1. 5.1 数组的定义
    2. 5.2 数组的顺序表示和实现
    3. 5.3 矩阵的压缩存储
      1. 5.3.1 特殊矩阵
      2. 5.3.2 稀疏矩阵
  • 第六章 树与二叉树
    1. 6.1树的定义和基本术语
    2. 6.2 二叉树
      1. 6.2.3 二叉树的存储结构
      2. 6.3.1 遍历二叉树
      3. 6.3.2 线索二叉树
    3. 6.4 树和森林
      1. 6.4.1 树的存储结构
      2. 6.4.2 森林与二叉树的转换
      3. 6.4.3 树和森林的遍历
    4. 6.6 哈夫曼树
      1. 6.6.2 哈夫曼编码
  • 第七章 图
    1. 7.1 图的定义和术语
    2. 7.2 图的存储结构
      1. 7.2.1 数组表示法
      2. 7.2.2 邻接表
      3. 7.2.3 十字链表
      4. 7.2.4 邻接多重表
    3. 7.3 图的遍历
      1. 7.3.1 深度优先搜索
      2. 7.3.1 广度优先搜索
    4. 7.4 图的连通性问题