DataStructure（02142）

Posted Mar 31, 2022

By Cc 62 min read

数据结构导论（02142）

第一章概论（重点）

1 引言

数据结构：是计算机组织数据和存储数据的方式
计算机解决问题步骤
1. 建立数学模型
2. 设计算法
3. 编程实现算法
程序=数据结构+算法
通常操作：查找、读取、插入、删除、更新
合理的数据结构有什么用
1. 可降低程序设计的复杂性
2. 提高程序的执行效率

2 基本概念和术语

数据：所有被计算机存储、处理的的对象
数据元素：是数据这个集合的一个个体积数据的基本单位
数据项：数据元素常常分为若干个数据项，是数据的具有意义的最小单位

数据->数据元素->数据项
逻辑结构：元素之间的结构关系（集合、线性、树形、图结构）线性和非线性
- 线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素
- 树结构：除根结点外，每个数据元素只有一个前驱数据元素，可有 0 个或若干个后继数据元素。
- 图结构：每个数据元素可有 0 个或若干个前驱数据元素和 0 个或若干个后继数据元素。
- 集合结构：数据元素同”属于一个集合”之间没有任何联系。
物理结构：存储结构（顺序、链式、索引、散列），数据在计算机内的表示称为数据的存储结构
- 存储结点
- 数据元素之间关联方式的表示
- 分类
  1. 顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构；
    
    线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中
  2. 链式存储结构：借助数据元素地址的指针表示数据的逻辑结构。
  3. 索引存储结构：借助索引表中的索引指示各存储节点的存储位置。
  4. 散列存储结构：用散列函数指示各节点的存储位置。
运算：在逻辑结构上施加的操作，逻辑结构加工
加工型运算：操作改变原逻辑结构的值
引用型运算：不改变原有逻辑结构的值（查找、读取、插入、删除、更新）

算法及描述

算法规定了求解给定类型问题，所需的所有处理步骤 及 执行顺序 是给定类型问题能在有限时间内被机械的求解

算法特性（对特定问题求解步骤的描述，他是指令的有穷序列）
1. 有穷性：在执行有穷步后结束
2. 确定性：每一步必须明确地定义
3. 可行性：每一步都可以同步已经实现的操作完成
4. 输入：可以零个或多个输入
5. 输出：一个或多个输出（特定关系的量）

4 算法分析

算法设计满足
- 正确性：对于合法输入产生符合要求的输出
- 可读性：易读、添加注释
- 健壮性：非法输入是，能够作出反应而不会崩溃
- 效率高切内存消耗小：运行时间短，储存制算法执行过程中所需的最大内存空间
算法时空性：时间复杂度、空间复杂度；目的提高算法的效率
考虑两个度量分析
- 时间复杂度：运行时需要的总步数，通常时问题规模的函数（大 O 表示）
  - 常数 O(1)＜对数阶 O(log2n) ＜线性阶 O(n) ＜线性对数阶 O(nlog2n) ＜平方阶 O(n^2) ＜多项式阶 O(n^C) ＜指数阶 O(C^n)
  - 时间复杂度分析基本策略：从内向外分析，从最深层开始分析
  - 看有几层循环，一层循环是 O(n)或者 O(log2n)；两层循环是 O(n^2) ；三层循环是 O(n^3) （一般规律如此，具体问题具体分析）
- 空间复杂度：执行时所占用的储存空间，通常时问题规模的函数,运行过程中临时占用存储空间大小的度量
  - 程序代码所占用的空间
  - 输入数据所占用的空间
  - 辅助变量 所占用的空间（估算时间复杂度，一般值分析辅助变量所占用的空间)

5 小结

第二章线性表（重点）

1 线性表的基本概念

线性表是有 n(n>=0)个数据元素（结点）组成的有限序列
1. n 定义长度，n=0 称为空表
2. 非空（n>0）
3. 数据元素（1<=i<=n）
4. 1:1 的关系
非空的线性表
1. 有且仅有一个起始结点 a1 ,没有直接前驱，有且仅有一个直接后继 a2；
2. 有且仅有一个终端结点 an，没有直接后继，有且仅有一个直接前驱 an−1；
3. 其余的内部结点 ai（2≤i≤n-1）都有且仅有一个直接前驱 ai−1 和一个直接后继 ai+1
线性表的基本运算：初始化、求表长度、取表元、定位、插入、删除（区分引用和加工型操作）

2 线性表的顺序存储

定义：顺序表是线性表的顺序存储结构，一段连续内存存放的线性表
特点
- 顺序表是用 一维数组实现 线性表，数组下标是元素相对地址
- 逻辑上相邻元素，在存储物理位置也是相邻的单元中
- 线性表的逻辑结构 与 存储结构一致
- 可以对数据元素实现随机读取
存储地址计算
- 每个结点类型相同、占用存储空间大小相同
- 例如结点占用 L 个存储单元，其中第一个单元存储地址则是该结点的存储地址
- 设表开始结点 a1 的存储地址 d，结点 ai 的存储地址为LOC(ai) 公式：LOC(ai) = d+(i−1)*L （必考）

顺序表插入运算

当表空间已满，不可在插入操作
插入位置非法，不可正常插入操作
插入新的结点 x，插入位置 i=n+1 时，才无需移动结点，直接将 x 插入表的末尾
长度变为 n+1
需要移动 n-i+1

元素平均移动次数 n/2 时间复杂度 O(n)

        
      
void InsertSeqList( Seqlist *L DataType x int i )
{
  int j;
  if ( i < 1 || i > L.length + 1 )
        exit( "位置 错 误" );
  if ( L.length == MaxSize )
        exit( "溢出" );
  for ( j = L.length - 1; j >= i; j-- )
        L.data[j] = L.data[j - 1];      /* 依次后移   L.data[ i-1] = x; */
  L.length++;
}

删除操作运算

只需要删除终端结点，无需移动结点
长度-1
需要移动n-i+1

元素平均移动次数 n-1/2 时间复杂度 O(n)

        
      
void DeleteSeqList( SeqList *L, int i )
{
  int j;
    if ( i < 1 || i > L.length )
    Error( " 位置 错 误 " );
  for ( j = i; j < L.length; j++ )
    L.data[j - 1] = L.data[j];

  L.length--;
}

优点
- 无需表示该的单元的逻辑关系增加额外存储空间
- 方便的随机取表任意结点
缺点
- 插入删除运算不方便，必须移动大大量的结点
- 顺序表要求占用连续的存储空间，需要预先分配内存，表长变化较大是，难以确定合适储存规模

3 线性表的链接存储

线性表的链式存储值存储结构是链式的，常见的有（单链表、循环链表、双向链表）

存储表示
- 用一组内存的存储单元存放
- 链表中结点的逻辑次序和物理次序不一定相同，必须存储指示后续结点地址信息
- date 数据域
- next 存放即诶单直接后继的地址（位置）的指针域（链域）
- NULL 空指针^
- head 头指针变量，存放链表中第一个结点地址

单链表：(Head|exit)->(k|^)

插入运算（ai-1~ai）

找到 ai-1（p）存储 x
生成 x
p 指针域指向 x，然后插入 x

x 结点指针域指向 ai

        
      
void InsertLinkList( LinkList head, Data x, int i )     /* 在表中head的第i个数据元素结点之前插入一个以X为值的新结点。 */
{
  Node *p, *q;
  if ( i == 1 )
    q = head;
  else q = GetLinkList( head, i - 1 );            /* 找第i-1个数据元素结点 */
  if ( q == NULL )                                /* 第i-1个结点不存在 */
    exit( " 找到 插入位置 " );
  else{ p  = malloc( sizeof(Node) );       /* 生成新结点 */
        p->data = x;                            /* 生成新结点指向X */
        p->next = q->next;                      /* 新结点链域指向*q的后继结点 */  1
        q->next = p;                            /* 修改*q的链域 */              2
  }
}
// 特别要注意：上面1和2二行代码不可颠倒顺序，否则*q链先断了会找不到。

删除运算

找到 i-1 结点，存在继续，否则结束

删除 i 结点，释放对应的内存

        
      
void DeleteLinkList( LinkList head, int i )
{
  Node *q;
  if ( i == 1 )
    p = head;
  else p = GetLinkList( head, i - 1 );    /* 先找待删结点的直接前驱 */
  if ( p ！ = NULL && p->next != NULL )
  {
    q = p->next;              /* P指向待删结点 */
    p->next = q->next;              /* 移出待删结点 */
    free( q );                      /* 释放已移出结点P的空间 */
  }  else printf( " error " );
}

4、5 其它运算在单链表的实现、其他链表

单向循环链表：如果第一个结点指针域指向第一个结点构成循环，任意结点出发都能够扫描整个链表
- 普通链表的终端结点next只为NULL
- 循环链表终端结点next指向头结点
- 导致循环链表中结点只有一个指针
双向循环链表
- 链表中有两个指针域：一个指向后继结点、一个指向前驱结点（双向链表）
- Prior | date | next
- 头 prior 指向最后一个结点，最后一个结点 next 指向头结点
- 删除
  1 2 3 4 q = p->next; p->next = p->next->next; p->next->prior = p; free( q );
- 插入
  1 2 3 4 t->prior = p; t->next = p->next; p->next->prior = t; p->next = t;

6 顺序实现与链式实现的比较

存储密度 = 数据域占用存储量/整个存储节点占用存储量

时间复杂度	顺序表	链表
读	O(1)	O(n)
找	O(n)	O(n)
插	O(n)	O(n)
删	O(n)	O(n)

7 小结

基于空间考虑	顺序表	链表
分配方式	静态分配	动态分配
存储密度	1	<1

分配方式
- 顺序表：静态分配
  - 程序执行之前必须明确规定存储规模。
  - 若线性表长度 n 变化较大，则存诸规模难于预先确定估计过大将造成空间浪费，
  - 估计太小又将使空间溢出机会增多
- 链表：动态分配
  - 只要内存空间尚有空闲，就不会产生溢出
  - 当线性表的长度变化较大
  - 难以估计其存储规模时，以采用动态链表作为存储结构为好
存储密度
- 顺序表:1
  - 当线性表的长度变化不大，易于事先确定其大小时
  - 为了节约存储空间，宜采用顺序表作为存储结构
- 链表：< 1
  
  存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为 D，指针域所占的空间为 N，则存储密度为：D/(D+N)，一定小于 1

第三章栈、队列和数组（重点）

栈和队列何以看作特殊的线性表

1 栈

定义：栈只能在表一端(表尾)进行插入和删除的线性表
- 允许插入删除一端(尾部)称为栈顶(top),另一端表头称为栈底(bottom)
- 表中没有元素称空栈
特点
- 进栈push;出栈pop删除
- 先进先出 (LIFO)
- 用途：常用于暂时保存待有处理的数据
顺序栈：是一组连续的存储单元一次放栈中的每个元素(初始端为栈低)
链式栈：链式存储,运算受限单链表,插入删除受限表头位置上进行栈顶指针就是链表的头指针

2 队列(Queue)

定义: 是一种运算受限的线性表，只允许一端插入在另一端删除
- 允许删除的一端为队头(front),允许插入的一端为队尾(rear)
特点
- 先进先出 (FIFO)
- 用途：常用于暂时保存待有处理的数据
实现方式
- 顺序实现：顺序存储,由一个一维数组(存储元素)
  - 循环队列
    - 上溢条件：sq.rear=-maxsize-1(队满)
    - 下溢条件：sq.rear==sq.front(队列空)
    - 假溢出：极端情况会出现上溢,为了客服假溢出引入循环队列
    - 头尾连接
    - 插入：rear=(sq.rear+1)%maxsize
    - 删除：front=(sq.front+1)%maxsize
    - 下溢-队空：CQ.front==CQ.rear
    - 上溢-队满：(CQ.rear+1)%maxsize==CQ.front
- 链接实现
  - 使用一个带有头结点的单链表来表示队列
  - 头结点 exit 域指向队列首结点,尾指针指向队列尾结点

3 数组、应用

数组可以看成一种特殊的线性表，顺序存储；每一个元素值和一个下表组成,一般具有上界下界

数组
- 定义
  - 一维内存单元连续(又称向量)
  - 二维存储方式两种
    - 列序为主
    - 主序为主(C 语言)
  - 随机存取结构
- 读写:给一定下标读取和修改元素
- 寻址公式
  
  例如，二维数组 Amn 按”行优先顺序”存储在内存中，假设每个元素占用 k 个存储单元。元素 aij 的存储地址应是数组的基地址加上排在 aij 前面的元素所占用的单元数。因为 aij 位于第 i 行、第 j 列，前面 i 行一共有 i×n 个元素，第 i 行上 aij 前面又有 j 个元素，故它前面一共有 i×n+j 个元素，因此，aij 的地址计算函数为： LOC(aij)=LOC(a00)+(i*n+j)*k
矩阵的压缩存储
- 矩阵是一种常用的数据对象,来描述一个二维数组
- 矩阵存储下进行元素随机存储
- 存储密度为 1
- 矩阵中零元素存在大量的零元素,队矩阵造成极大的浪费,为了节省空间,对矩阵进行压缩存储
- 压缩存储:即多个相同元素的非零只分配一个存储空间,对零元素不分配空间
- 特殊矩阵压缩分类
  - 对称矩阵
  - 三角矩阵(上三角、下三角)
- 稀疏矩阵

4 小结

第四章树和二叉树（重、难点）

非线性结构
1:N 关系

1 树的基本概念

概念
- 定义：是 n(n>=0)个结点有限集
- 有且仅有一个特定的称为根结点
- 其余结点可分为 m(m>=0)个互相不交集的子集,其中每个子集有是一颗树,并称其为子树
- 递归是树的固有特性
- 逻辑表示
  - 直观表示
  - 嵌套括号法
  - 凹入表示法
相关术语
- 结点：由一个元素及若干个指向其他结点的分支所组成
- 度
  - 结点的度：该结点子树数(分支)
  - 树的度：树中结点的度最大值
- 叶子(终端结点)：度为零的结点
- 非终端结点：度不为零的结点
- 结点层次：从根开始算起,根为第一层
- 树的高度：所有结点层次树的最大值称该树的高度或深度
- 有序树：左右不能互换,有次序,最左子树的根称第一个孩子
- 无序树：各个结点的子树是无序的,可以互换
- 森林：m(>=0)课树的集合
- 结点和边的关系：n 个结点的树,共有 n-1 条边

2 二叉树

任何一棵树都可以与二叉树相互转换

定义
- 二叉树是 n（n>=0）个结点有限集合，或空（n=0）
- 每课子树都是二叉树
特点
- 二叉树可以是空，称空二叉树
- 每个结点最多是两个孩子
- 子树有左，右，之分次序不能颠倒

与树的比较

	结点	子树	结点顺序
树	n>=0	不定（有限）	无
二叉树	n>=0	<=2	有（左、右）

二叉树的性质
- 在二叉树的第 i(i>=1)层上至多有 2i-1 个结点。(i>=1)；至少 1 个
- 深度为 k(k>=1) 的二叉树至多有 2k－1 个结点；至少 K 个
- 对任何一棵二叉树，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 ＝ n2 ＋ 1。即：叶结点数 n0=度为 2 的结点数 n2+1
- 下图其中度为 2 的结点数共有 5 个，即 ABCEF（有 2 个孩子的，如 G 就不是），叶子共有 6 个，即 IJKLMH(没有结点，度为 0 的)，得出这二叉树终端结点数=度为 2 的结点数+1，即 6=5+1
```
graph TB;
A((A))
B((B))
C((C))
E((E))
F((F))
G((G))
H((H))
I((I))
J((J))
K((K))
L((L))
M((M))
A-->B
A-->C
B-->E
B-->F
E-->I
E-->J
C-->G
G-->M
F-->K
F-->L
C-->H
```
- 满二叉树:深度为 k(k>=1)且有2^k-1个结点的二叉树；下图满二叉树结点 2^3-1=7
```
graph TB;
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))
1-->2
1-->3
2-->4
2-->5
3-->6
3-->7
```
- 完全二叉树:深度为 K 的二叉树中，K-1 层结点数是满的(2k-2)，K 层结点是左连续的(即结点编号是连续的)
- 满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树过

3 二叉树的存储结构

顺序存储
- 一组连续的存储单元存储
- 必须把二叉树所有结点安排一个恰当的序列
- 对二叉树进行编号，然后用一维数组存储，其中编号为 i 的结点存储在数组中的下标为 i 对的分量中–称为以编号为地址策略
- 树从根起，自上层至下层，每层子左至右给所有结点编号
  - 缺点对存储空间造成极大的浪费（深度为 H 且只有 H 个结点右单只树需要 2^h-1 个结点存储空间）
  - 若经常需要插入删除树中结点是，顺序方式不是很好
链式存储
- 画二叉链 必考

4 二叉树的遍历

遍历二叉树：二叉树是非线性的，因而需要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只访问一次

遍历规则

D-根；L-左；R-右

  graph TB;
  A((根节点 D))
  B((左子树 L))
  C((右子树 R))
  A-->B
  A-->C

遍历分类

例子

graph TB;
A((A))
B((B))
C((C))
D((D))
E((E))
F((F))
G((G))
H((H))
I((I))
J((J))
K((K))
nil((nil))
nille((nil))
A-->B
A-->C
B-->D
B-->E
E-->nille
E-->I
D-->nil
D-->H
C-->G
C-->F
F-->J
F-->K

先序遍历(DLR)-根左右 A->B->D->H->E->I->C->F->J->K->G

根->左->右 首先访问根结点，其次便利根的左子树，最后遍历根右子树，对每棵子树同样操作

        
      
  void   preorder( bitreptr r )
  {
    /*先序遍历以r为根的二叉树*/
    if ( r == NULL )
      return;
    printf( r->data );         /*访问根结点*/
    preorder( r->lchild ) ；
    preorder( r->rchild );
    /*先序遍历以r的右孩子为根的右子树*/
  };

中序遍历(LDR)-左根右 D->H->B->E->I->A->J->F->K->C->G

左->根->右 首先遍历根的左子树，其次访问根节点，最后遍历右子树

        
      
  void   inorder( bitreptr r )
  {
    /*中序遍历以r为根的二叉树*/
    if ( r == NULL )
      return;
    inorder( r->lchild ) ；
    /*中序遍历以r的左孩子为根的左子树*/
    printf( r->data );              /*访问根结点*/
    inorder( r->rchild );           /*…….*/
  }

后序遍历(LRD)-左右根 H->D->I->E->B->J->K->F->G->C->A

左->右->根 首先遍历根的左子树，其次访问右子树，最后访问根节点

        
      
  void   postorder( bitreptr r )
  {
    /*后序遍历以r为根的二叉树*/
    if ( r == NULL )
      return;
    postorder( r->lchild ) ；
    /*后序遍历以r的左孩子为根的左子树*/
    postorder( r->rchild ) ；
    printf( r->data );       /*访问根结点*/
  }

5 树和森林

树的存储结构
- 孩子链表表示法：child|next
  - child：存放孩子结点在表头数组中的序号
  - exit：指向下一个孩子结点
- 孩子兄弟链表示法（二叉链表表示）（son data brother）
  - son：指向第一个孩子结点
  - brother：指向该结点的下一个兄弟结点
- 双亲表示法
树、森林、二叉树之间转换
- 树->二叉树
  - 各兄弟之间加连线
  - 对任一结点，除最左孩子，抹掉该结点与其余孩子的各枝
  - 以根为轴心，将连线顺指针转 45 度
- 森林->二叉树
  - 将每棵树转换成相应的二叉树
  - 将（1）中得到的各颗二叉树的根结点看做是兄弟链接起来
- 二叉树->一般树
  - 从根结点起
  - 该结点左孩子和左孩子右枝上的结点一次作为该结点孩子
  - 重复（1）
树和森的遍历
- 树
  - 先序遍历：先序先访问根结点，然后一次先序遍历根的每A->B->C->D->E
  - 后序遍历：先依次后续遍历每棵子树，最后访问根结点B->D->C->E->A
  - 层次遍历：遍历每个兄弟结点A->B->C->E->D
```
graph TB;
A((A))
B((B))
C((C))
D((D))
E((E))
A-->B
A-->C
A-->E
C-->D
```
- 森林的遍历
  - 先序：访问森林中每棵树的根结点；先序遍历森林中第一棵树的根结点的子树组成的森林；先序遍历除去第一棵树之外其余的树组成的森林。
  - 中序：中序访问森林中第一棵树的根结点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的树组成的森林；

6 判定树和哈夫曼树

解题思路：先求哈夫曼树，再求哈夫曼编码
- 求哈夫曼树的口诀
  1. 构造森林全是根
  2. 选用两小造新树
  3. 删除两小添新人
  4. 重复，2，3 剩单根

7 小结

第五章图（重点）

邻接矩阵 、邻接表存储结构；深度优先和广度优先；求最小生成树的 prim 算法

1 图的基本概念

图的定义
- 图 G：是有集合 V 合成 E 组成，记成 G=(V,E)
  - v：顶点集（非空）
  - E：边集（可空），可只有顶点，没边
- 边是顶点的有序对或无序对（反映两点之间的关系）
  - 有向图：边顶点有序对的图（用箭头指明方向）
  - 无向同：边是顶点的无序对的图
- 网状结构（比线性（线性表）、层次（图））更复杂，多对多(N:N)
- 注意：
  - 集合可空
  - 边集中不允许出现相同的边
基本术语
- 顶点（Vertex）：图中的数据元素
- <Vi,Vj>：有向图中，顶点 Vi 到顶点 Vj 的边，也成弧
  - 弧头（终端点）箭头端
  - 弧尾（初始点）无箭头端
- 完全图（顶点数 n）
  - 无向完全图：边数=n*(n-1)/2的无向图
  - 有向完全图：边数=n*(n-1)的有向图
- 权：与图中的边相关的数
- 子图：图 G 和 G′,若有 V(G′)∈=V(G)和 E(G′)∈=E(G),则称 G′为图 G 的子图
- 邻接：若(Vi,Vj)∈E(G)，则称 Vi 和 Vj 互为邻接点
- 关联：若(Vi,Vj)∈E(G)，则称边(Vi,Vj)关联于顶点 Vi 和 Vj;
  - 注意
    1. 邻接是指顶点之间的关系，而关联是指边与顶点间的关系
    2. 若弧<Vi,Vj>∈E(G)，则称 Vj 是 Vi 的邻接点
- 度
  - 无向图：顶点 Vi 的度为与 Vi 相关联的边的个数；D(Vi)用（）表示
  - 有向图用< >表示
    - 出度：顶点 Vi 的出度为以 Vi 为尾的出边数
    - 入度：顶点 Vi 的入度为以 Vi 为头的入边数
    - 度：有向图的度=入度+出度
  - 一边带二度，两度组一边
- 路径：顶点 Vp 至顶点 Vq 的路径是顶点序列
- 路径长度：路径上边或弧的数目
- 简单路径：除第一个和最后一个外，其余的各个顶点均不相同的路径
- 回路：第一个和最后一个顶点相同的路径（也称环）
- 简单回路：第一个和最后一个顶点相同的简单路径
  
  回路中可以有多个圈，而简单回路只能有一个圈
- 连通：无向图中，若从顶点 Vi 到 Vj 顶点有路径，则称 Vi 和 Vj 是连通的
- 连通图和连同分量（针对无向图而言）
- 生成树：含有该连通图的全部顶点的一个极小连通子图。若连通图 G 的顶点个数为 n，则 G 的生成树的变数为 n-1
  - 边>n-1，一定有环
  - 边<n-1，一定不连同
- 生成森林：在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。
- 基本运算
  - 建立图 GreateGraph(G,V,E)
  - 取顶点信息 Getvex(G,u)
  - 取边信息 Getarc(G,u,v)
  - 查询第一个邻接点 FirstVex(G,u)
  - 查询下一个邻接点 NextVex(G,u,v)
  - 插入顶点 InsertVex(G,v)
  - 删除顶点 DeleteVex(G,v)
  - 插入边 InsertArc(G,v,w)
  - 删除边 DeleteArc(G,v,w)
  - 遍历图 Travers(G,tag)

2 图的存储结构

没有顺序存储结构，可以借助二维数组表示，也叫做邻接矩阵；共有邻接矩阵，邻接表，十字链表，邻接多重等存储结构….

邻接矩阵表示法（也叫二维数组）
- 图的邻接矩阵：表示图的各顶点之间关系的矩阵
  - 表示方法
    1. 有边 1 表示
    2. 无边 0 表示
    3. 实例：脑补无向图（1-2，1-3，1-4，2-3，3-4）
    1 2 3 4 5 1,2,3,4 1[0,1,1,1] 2[1,0,1,0] 3[1,1,0,1] 4[1,0,1,0]
  - 无向图的邻接矩阵是对称的
  - 从邻接矩阵容易判断任意两顶点间是否有边相联；容易求出各顶点的度
  - 无向图：顶点 Vi 的度 D(Vi)=矩阵中第 i 行的 1 总和
  - 有向图：OD(Vi)=矩阵中第 i 行的 1 总和，I D(Vi)=矩阵中第 i 列的 1 总和
- 带权图(网)的邻接矩阵
  - 有 n 个结点，对应就会有 n*n 的方阵
邻接表示法（连式）
- n 个顶点、e 条边的无向图，则其邻接表的表头结点数为 n，链表结点总数为 2e；
- 对于无向图，第 i 个链表的结点数为顶点 Vi 的度；
- 对于有向图，第 i 个链表的结点数为顶点 Vi 的出度；
- 在边稀疏时，邻接表比邻接矩阵省单元；
- 邻接表表示在检测边数方面比邻接矩阵表示效率要高。

3 图的遍历

从图 G 的某一顶点 V 出发，顺序访问各顶点一次

方法：为了克服顶点的重复访问，设立辅助数组（visited[n]）

visted[i]=\left\{
\begin{aligned}
1=&顶点i已被访问过 \\
0=&顶点i未被访问过\\
\end{aligned}
\right.

遍历分类
- 深度优先搜索发（DFS）必考
  - 为克服顶点的重复访问，设立一标识向量 visited[n] - 图可用邻接矩阵或邻接表表示
  - DFS 规则具有递归性，故需用到栈
  - 搜索到达某个顶点时(图中仍有顶点未被访问)，如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一未被访问的邻接点开始深度优先搜索。
  - 深度搜索的顶点的访问序列不是唯一的
- 广度优先搜索发（BFS）考点
  - 类似于树的层次遍历的过程（遍历所有的兄弟结点）
  - 过程：中某一点 Vi 出发，首先访问 Vi 的所有邻接点（w1，w2，…，wt），然后再顺序访问 w1，w2，…，wt 的所有未被访问过的邻接点…., 此过程直到所有顶点都被访问过
  - 图可用邻接矩阵或邻接表表示
  - 顶点的处理次序——先进先出，故需用到队列
  - 思想
    1. 所有结点标记置为”未被访问”标志；
    2. 访问起始顶点，同时置起始顶点”已访问”标记；
    3. 将起始顶点进队列
    4. 当队列不为空时重复执行以下步骤；
      1. 取当前队头顶点；
      2. 对与队头顶点相邻接的所有未被访问过的顶点依次做：
        
        访问该顶点
        
        置该顶点为”已访问”标记,并将它进队列；
      3. 当前队头元素顶点出队；
      4. 重复进行，直到队空时结束。
- 求图的连通分量
  - 判断连通性：调用一次 DFS 或 BFS 得到一顶点集合之后与 V(G)比较，若两集合相等，则图 G 是连通图，否则不连通
  - 求图的连通分量：图遍历的一种应用

4 图的应用

最小生成树：连通图 G=(V,E)，从任一顶点遍历，则图中边分成两部分：E(G) = T(G)+ B(G)
- T(G):遍历通过的边
- B(G):剩下的边（即遍历时未通过的边）
深度优先生成树：按照深度优先遍历而生成的树
广度优先生成树：按照广度优先遍历而生成的树
图的生成树不是唯一的
最小生成树也不是唯一的
最小生成树：给一个带权图，构造带权图的一颗生成树，使树中所有边权总和为最小
最小生成树的构造算法
- Prim 算法：适用于稠密最小生成树
- Kruskal 算法：构造的最小生成树不唯一，但权和相同，适合与求边稀疏的网的最小生成树
拓扑排序：拓扑有序序列的构造过程称
- AOV 网：对 AOV 网构造顶点线性序列（…i,…,k,…j,…）i 是 j 的前趋，则 i 在 j 之前，若 i、k 间无路径，则或 i 在 k 前，或 k 在 i 前。这样的线性序列称为拓扑有序序列
- 拓扑排序算法：避免重复查找，可将入度为 0 的顶点入度域串链成一个链式栈
  - 将全体入度为 0 的顶点入栈；
  - 链栈非空时，反复执行：
    - 弹出栈顶元素 Vj 并将其输出；
    - 检查 Vj 的出边表，将每条出边（Vj，Vk）的终点 Vk 的入度域减 1；
    - 若 Vk 的入度为 0，则 Vk 入栈。
  - 若输出的顶点数小于 N，则输出有回路；否则，拓扑排序结束。

5 小结

第六章查找

1 基本概念

查找表：是由同一类型的数据元素构成的集合，查找中的核心
查找：给定 K 值，寻找 K 的数据元素
静态查找表：进行的是引用型运算
- 基本运算
  - 建表
  - 查找
  - 读表中元素
动态查找表：进行的是加工型运算
- 基本运算
  - 初始化
  - 查找
  - 读表中元素
  - 插入
  - 删除
- 树查找（二分查找，B 树查找）
- 哈希查找
查找成功：在数据元素集合中找到了要查找的数据元素
查找不成功：在数据元素集合中没有找到要查找的数据元素

2 静态查找表

二分法查找
- 静态查找：二分查找，索引顺序表查找
- 动态查找：二叉排序树找，哈希查找
顺序表中查找：二分法查找法
- 从表中最后一个记录开始顺序进行查找，若当前记录的关键字=给定值，则查找成功；否则，继续查上一记录…；若直至第一个记录尚未找到需要的记录，则查找失败。包括”二分查找，索引顺序表查找”二种方法
- 优点：简单，对表无要求
- 缺点：比较次数多
- 算法
  - 设立岗哨
- 思想：：每次将处于查找区间中间位置上的数据元素与给定值 K 比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为 0（查找不成功）为止。可使下次查找范围缩小一半
分块查找：索引顺序查找
- 查找过程（把数据分为若干个块，然后在块中再查找）
  - 先建立最大（小）关键字表-索引表（有序）
  - 查找索引表，以确定所查找元素块号
  - 在相应的块中按顺序查找关键字为 K 的记录

3 二叉排序树

定义：是种特殊的、增加了限制条件的二叉树
条件
- 左子树上所有结点的值都小于它的根值，如左子树为空除外。
- 右子树上所有结点的值都大于它的根植，如右子树为空除外
- 每一个子树也要分别满足上二个条件，即一层一层都是这样条件
总结：二叉排序树上进行查找，如查找成功，则是从根结点出发走了一条从根结点到待查结点的路径；如查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。因些与二分查找类似，关键字比较的次数不超过二叉树的深度，对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态与深度也不同，含有 n 个结点的二叉排序树不是唯一的。也就是说，二叉排序树上的查找长度不仅与结点数 n 有关，也与二叉排序树的生成过程有关
插入原则：必须要保证插入一个新结点后，仍为一棵二叉排序树，这个结点是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子

4 散列表

哈希表
- 散列函数（哈希函数）：关键字与元素地址的函数
- 散列地址：由散列函数决定数据元素的存储位置，该位置称为散列地址
- 散列查找：关键字->散列函数转换->位置上有无元素
- 散列表：通过散列法建立的表称为散列表
冲突
- 散列表的实现：链池址法
- 优点：直接由关键字通过哈希函数计算出哈希地址，查找效率高
- 缺点：常发生冲突，影响查找效率

5 小结

第七章排序（重点）

1 概述

数据排序：一个文件记录按照关键字不减（不增）次序排列，是文件成为有序的文件，此过程称为排序
稳定排序：若排序后相同的关键字的记录保持原来相对次序
不稳定排序：反之稳定排序
排序类型
- 内部排序：全部数据存与内存只考
  - 插入排序：又分直接插入排序，折半插入（二分法）排序，表插入和希尔排序几种，我们重点掌握直接插入排序就可
  - 交换排序：又分冒泡排序，快速排序
  - 选择排序：又分直接选择排序，堆排序
  - 并归排序：它和和前几种完全不同的排序，它又分为有序序列合并，二路归并排序
- 外部排序：需要对外存进行访问的排序过程

2 插入排序

过程：对 R_1，…，R_i−1 已排好序，有 K_1≤K_2≤….≤K_i−1，现将 K_i 依次与 K_i−1，K_i−2，…进行比较，并移动元素，直到发现 R_i 应插在 R_j 与 R_j+1 之间(即有 K_j ≤ K_i ＜ K_j+1 )，则将 R_i 插到 j+1 号位置上，形成 i 个有序序列。（i 从 2 ～ n）

算法

存储空间 n+1；（1 为附加空间）
时间复杂度 O(n^2)

稳定性：稳定排序

        
      
void straightsort( list r );
{                                               /* 用直接插入排序法对r[1]…r[n]进行排序 */
  for ( i = 2; i <= n; i++ )                    /* n为表长，从第二个记录进行插入 */
  {
    r[0] = r[i];                         /* 第i个记录复制为岗哨 */
    j = i - 1;
    while ( r[0].key < r[j].key )            /* 与岗哨比较，直到健不大于岗哨键值 */
    {
      r[j + 1] = r[j];                 /* 将第j个记录赋值给第j+1个记录 */
      j  = j - 1;
    }
    r[j + 1] = r[0];                       /* 将第i个记录插入到序列中 */
  }
}

3 交换排序

冒泡排序

基本思想：通过多次重复比较、交换相邻记录而实现排序；每一趟的效果都是将当前键值最大的记录换到最后。它是对 n 个元素排序，所历经的趟数至少为 1，至多为 n-1

原理：通过两两数进行多次对比，把最大的数放在最后面，如下面多次比较才得到第一趟结果把 49 放在最后面，这就是冒泡的原理(21，25，49，25，16，08)

    第一趟：21，25，25，16，08，49
    第二趟：21，25，16，08，25，49
    第三趟：21，16，08，25，25，49
    第四趟：16，08，21，25，25，49
    第五趟：08，16，21，25，25，49

        
      
Void bubbleSort( list r, int n )
{                                                       /* 用冒泡排序法对r[1]…r[n]进行排序 */
  /* flag:标志文件是否已排好序 */
  for ( i = 1; i <= n - 1; i++ )
  {
    flag = 1;                               /* 若循环中记录未作交换,则说明序列已有序 */
    for ( j = 1; j <= n - i; j++ )
      if ( r[j + 1].key < r[j].key )
      {
        flag  = 0;    /* 排序前先为0，若在一趟起泡中交换了记录，则置为1 */
        p  = r[j]; r[j] = r[j + 1];
        r[j + 1] = p;
      }
    if ( flag )
      return;
  }
}

快速排序

基本思想：通过分部排序完成整个表的排序；首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置，使记录表分成两部分{其一（左边的）诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它}；然后对这两部分重新执行上述过程，依此类推，直至排序完毕

        
      
void  quickpass( list r, int h, int p )
{
  /* 对顺序表r中的子序列r[h]至r[p]进行快速排序 */
  i = h;    j = p;  /* 左右指针置初值 */
  x = r[h];         /* 取处理元素（即作为枢轴记录） */
  while ( i ＜ j  )       /* 左右指针未碰头则反复做： */
  {
    while ( r[j].key > x.key && i < j )
      --j;
    /*右边未找到小关键字，则右指针j继续左移*/
    if ( i < j )    /*右边找到比枢轴记录小的记录，则将其送到左边*/
    {
      r[i] = r[j];
      ++i;
    }
    while ( r[i].key <= x.key && i < j )
      ++i;
    /*边未找到大关键字，则左指针i继续右移*/
    if ( i < j )                    /*左边找到比枢轴记录大的记录，则将其送到右边*/
    {
      r[j] = r[i];
      - -j;
    }
  }
  r[i] = x;                               /*枢轴记录定位*/
  if ( h < i - 1 )
    quickpass( r, h, i - 1 );       /*对左子序列进行快速排序*/
  if ( j + 1 < high )
    quickpass( r, j + 1, p );       /*对右子序列进行快速排序*/
}

算法分析
- 空间：n+log2n; （log2n 为附加空间—栈）
- 时间：≤O(nlog2n);
  - 注：若初始记录表有序或基本有序，则快速排序将蜕化为冒泡排序，其时间复杂度为 O(n2)；
  - 即：快速排序在表基本有序时，最不利于其发挥效率。
- 稳定性：不稳定排序。

4 选择排序

直接选择：以重复选择的思想为基础进行排序

过程：设记录 R_1，R_2…，R_n，对 i=1，2，…，n-1，重复下列工作：

在 R_i，…，R_n 中选最小(或最大)关键字记录 R_j；
将 R_j 与第 i 个记录交换位置，即将选到的第 i 小的记录换到第 i 号位置上

        
      
void  select( list r, int n )
{
 /*用选择排序法对r[1]….r[n]进行排序*/
 for ( i = 1; i < = n - 1; ++i )
 {
  k = i;                                  /*选择第i小的记录，并交换位*/
  for ( j = i + 1; j <= n; j++ )
   if ( r[j].key < r[k].key )      /*在r.[i]…r.[n-1]中找最小者*/
    k = j;
  if ( k != i )                           /*交换记录*/
  {
   temp = r[i];
   r[i] = r[k];
   r[k] = temp;
  }
 }
}

分析
- 空间：n+1；（1 为附加空间）
- 时间：C 总=∑ni=1(n-i)=(n2-1)/2≈O(n2)
- 稳定性：不稳定排序；

堆排序
- 需要解决问题
  - 如何由一个初始序列建成一个堆？
  - 如何在输出堆元素之后调整剩余元素成为一个新堆？
- 分析
  - 空间：n+1；（仅需 1 个附加空间）
  - 时间：O（nlog2n)
  - 稳定性：不稳定排序；

5 并归排序

有序序列的合并：比较各个子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排序结果
二种并归排序
- 思路
  - n 个记录的表看成 n 个，长度为 1 的有序表
  - 两两归并成 n/2 个，长度为 2 的有序表（n 为奇数，则还有 1 个长为 1 的表）
  - 再两两归并为 n/2 /2 个，长度为 4 的有序表，再两两归并直至只剩 1 个，长度为 n 的有序表，共 log2n 趟
- 算法分析
  - 空间：n+n；（需 n 个附加空间）
  - 时间：O（nlogn)
  - 稳定性：稳定排序；

6 小结

排序方法	平均时间	最坏情况	辅助存储	稳定性
简单排序(插入、冒泡、直接选择)	O(n2)	O(n2)	O(1)	稳定排序(除直接选择是不稳定外)
快速排序	O(nlog2n)	O(n2)	O(log2n)	不稳定排序
堆排序	O(nlog2n)	O(nlog2n)	O(1)	不稳定排序
归并排序	O(nlog2n)	O(nlog2n)	O(n)	稳定排序

Cc, SelfStudy, ComputerBasics

SelfStudy

This post is licensed under CC BY 4.0 by the author.

数据结构导论（02142）

第一章 概论（重点）

1 引言

2 基本概念和术语

算法及描述

4 算法分析

5 小结

第二章 线性表（重点）

1 线性表的基本概念

2 线性表的顺序存储

3 线性表的链接存储

4、5 其它运算在单链表的实现、其他链表

6 顺序实现与链式实现的比较

7 小结

第三章 栈、队列和数组（重点）

1 栈

2 队列(Queue)

3 数组、应用

4 小结

第四章树和二叉树（重、难点）

1 树的基本概念

2 二叉树

3 二叉树的存储结构

4 二叉树的遍历

5 树和森林

6 判定树和哈夫曼树

7 小结

第五章 图（重点）

1 图的基本概念

2 图的存储结构

3 图的遍历

4 图的应用

5 小结

第六章查找

1 基本概念

2 静态查找表

3 二叉排序树

4 散列表

5 小结

第七章排序（重点）

1 概述

2 插入排序

3 交换排序

4 选择排序

5 并归排序

6 小结

Trending Tags

第一章概论（重点）

第二章线性表（重点）

第三章栈、队列和数组（重点）

第五章图（重点）