002-数据结构和算法探索

作者: 千转军师 | 来源:发表于2021-03-09 13:32 被阅读0次

时间：2021年3月9日13:43:06
作者：along

参考1：
https://www.runoob.com/data-structures/data-structures-tutorial.html
参考2：
https://weread.qq.com/web/reader/f66323605a0426f66836979ka87322c014a87ff679a21ea

c语言的特点是面向过程，有它的应用领域，但也有局限性：在编写某些类型的大程序是，没有高级语言快捷和方便。

一、绪论

由来

由现实问题引申而来。人们发明计算机，起初的目的就是为计算数值提供便利。
数学理论可以抽象一般的生活问题，从而建立“模型”；根据数学模型，我们可以设计数据结构，并配套相应的算法（可以探讨优化）；最后确定数据类型，编写对应的程序流程、结构（顺序、判断、循环、跳转等），由此达到解决实际问题的目的。
所以这个过程描述为：

现实问题,抽象为===>
数学模型（解题思路），设计===>
数据结构（算法），编码===>
数据类型（程序），运行===>
结果

描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构

1.1 概念

数据
数据元素
一个数据元素可由若干个数据项（Data Item）组成。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等；
数据项
数据项（Data Item）指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段（field）或域；
数据结构
数据元素都不会是孤立的，在它们之间存在着这样或那样的关系，这种数据元素之间存在的关系称为数据的逻辑结构；
数据类型
在高级程序设计语言中用以限制变量取值范围和可能进行的操作的总和称为数据类型；
抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

1.2 数据结构的分类

（1）集合结构：在集合结构中，数据元素之间的关系是“属于同一个集合”。数据元素之间除了同属一个集合外，不存在其他关系。
（2）线性结构：在该结构中，数据元素除了同属于一个集合外，数据元素之间还存在着一对一的顺序关系。
（3）树形结构：该结构的数据元素之间存在着一对多的层次关系。（4）图状结构：该结构的数据元素之间存在着多对多的任意关系，图状结构也称为网状结构。
（4）图状结构：该结构的数据元素之间存在着多对多的任意关系，图状结构也称为网状结构。

数据结构有两个要素：一是数据元素，二是数据元素之间的关系。

1.3 逻辑存储和物理存储

数据的逻辑结构可以看做从具体问题抽象出来的数学模型，它与数据的存储无关；
数据的逻辑结构在计算机中的存储表示（又称映像）称为数据的物理结构，数据的存储方法包括顺序存储和链式存储。

1.4 算法

1.4.1 特性

有穷性
确定性
可行性
输入
输出

1.4.2 要求

确定性
可读性
健壮性
高效性

1.4.3 基本操作

查找
读取
插入
删除
更新

1.4.4 算法描述

自然语言
框图
伪代码
高级程序语言

1.4.5 算法分析

硬件的速度。即主机本身运行速度，主要与CPU的主频和字长有关，也与主机系统采用的技术有关，如多机系统的运算速度一般比单机系统要快。
实现算法的程序设计语言。实现算法的语言的级别越高，其执行效率相对就越低。
编译程序所生成目标代码的质量。代码优化较好的编译程序所生成的程序质量较高。
算法所采用的策略。采用不同设计思路与解题方法，其时空代价是不同的，一般情况下时间指标与空间指标常常是矛盾的两个方面。
问题的规模。例如，求100以内的素数与求1 000以内的素数的执行时间必然不同。

（1）时间复杂度
同一问题的不同的算法，通常的做法是：

从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数为算法的时间度量；
一般情况下，算法中原操作重复执行的次数是该算法所处理问题的规模n的某个函数T(n)。
公式定义
定义（大Ο记号）：如果存在两个正常数c和n0，使得对所有的n（n≥n0），有：
T(n) ≤ c*f (n)
则T(n)＝Ο( f (n))。
例如，一个程序的实际执行时间为T(n)＝2.7n3+3.8n2+5.3，则T(n)＝Ο(n3)。使用大Ο记号表示的算法的时间复杂度称为算法的渐进时间复杂度（AsymptoticTimeComplexity）。
Ο(1)表示常数级时间复杂度，表明这样的算法执行时间是恒定的，不随问题规模的扩大而增长；
O(log2n)，对数级复杂度；
Ο(n)，线性复杂度；
Ο(n2)和Ο(n3)，分别为平方级和立方级复杂度；
Ο(2n)，指数级复杂度；
增长速度的快慢次序为：Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)

（2）空间复杂度
空间复杂度一个程序的空间复杂度（Space Complexity）是指程序运行从开始到结束所需的存储量与问题规模的对应关系，记做：S(n)=Ο(f(n))

二、线性表

线性表（Linear List）是一种线性结构

三、栈和队列

栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。
栈：先进后处的受限线性表
队列：先进先出的受限线性表

3.1 栈

栈（Stack）是限制在表的一端进行插入和删除操作的线性表；
允许进行插入、删除操作的这一端称为栈顶（Top）；
固定端称为栈底；
当表中没有元素时称为空栈。
也称作FILO（First-In Last-Out）表

3.1.1 顺序栈

利用顺序存储方式实现的栈称为顺序栈。
（1）例子：

#define MAX_NUM 100
typedef struct stack{
  int ele[MAC_NUM];
  int top;
}stack_t;

序号为0的元素为栈底，top记录的时栈顶元素的序号。
（2）顺序栈初始化

stack_t *init_stack(void)
{
  stack_t *p;
  p = (stack_t *)malloc(sizeof(stack_t ));
  p->top = -1;
  return p;
}

3.1.2 链栈

用链式存储结构实现的栈称为链栈。
用单链表来实现。
应用：

十进制数转换为任意进制数
表达式求值
表达式求值是程序设计语言编译中一个最基本的问题。
一个表达式是由运算数（operand）、运算符（operator）和界限符（delimiter）组成的有意义的式子。

运算符按优先级排列优先级为：（）→ ^ → *、/、%→ +、-

3.1.3 栈与递归

例子：

数学里的阶乘
递归的数据结构的处理
Hanoi塔问题
假设有三个分别命名为X、Y、Z的塔座，在塔座X上叠放着n个直径大小各不相同、小盘压在大盘之上的圆盘堆。现要求将塔座X上的n个圆盘移至塔座Z上，并仍按同样的顺序叠放。移动圆盘时必须遵循下列规则：
（1）每一次只能够移动一个圆盘；
（2）圆盘可以插放在X、Y和Z中任何一个塔座上；
（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
递归问题特点
（1）原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小；（2）规模最小的子问题具有直接解，即不需要再调用自身。
二阶菲波那切数列

3.2 队列

“先进先出”（First-In First-Out，FIFO）的数据结构
插入在表一端进行，而删除在表的另一端进行，这种数据结构被称为队或队列（Queue）；
允许插入的一端称为队尾（rear）；
允许删除的一端称为队头（front）。

3.2.1 顺序队

用顺序存储结构来存储数据。

typedef int data_type 
#define MAX_SIZE 10
typedef struct queue{
    data_type data[MAX_SIZE];
    int front, rear;    //队头和队尾
    int num;    //元素个数
}queue_t;

队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”；
解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。

3.2.2 链队列

队列采用带头结点的链表结构

3.3 队列的应用

键盘输入事件处理

四、串和数组

串线性表：以字符串为数据元素的线性表
数组线性表：以数组为数据元素的线性表

4.1 串

串（String）是由零个或多个任意字符组成的字符序列；
串中任意连续的字符组成的子序列称为该串的子串；
包含子串的串相应地称为主串。

4.1.1 顺序存储结构（定长）

#define MAX_SIZE 256
typedef struct str{
    char data[MAX_SIZE];
    int len;
}str_t;

//或者
char s[MAXP_SIZE];

子串的定位操作通常称做串的模式匹配。
基本运算：

串连接
求子串
串比较
串定位

4.1.2 对分配存储结构

typedef struct str{
    char *data_p;
    int len;
}str_t;

动态分配内存，更加灵活，解决了可能“溢出”的问题。

4.2 数组

数组是一个具有固定格式和数量的数据有序集，即，一旦定义了数组的维数和每维的上、下限，数组的元素个数就固定了，而且数组中的每一个元素也由唯一的一组下标来标识。因此，在数组上一般不能做插入、删除数据元素的操作。对数组的操作只有取值和赋值。

4.2.1 存储结构

存储二维数组时，存储二维数组时，一般有两种存储方式；
一种是以行序为主序（或先行后列）的顺序存储方式，即从第一行开始存放，一行存放完了接着存放下一行，直到最后一行为止，如BASIC、PASCAL、COBOL、C等程序设计语言中都是以行序为主序的；
另一种是以列序为主序（先列后行）的顺序存储方式，即一列一列地存储，如FORTRAN语言就是采用以列序为主序的存储分配。

4.2.2 稀疏矩阵

稀疏矩阵（Sparse Matrix）是指矩阵中大多数元素为零元素的矩阵。

15  0   0   22  0   -15
0   11  3   0   0   0
0   0   0   6   0   0
0   0   0   0   0   0
91  0   0   0   0   0
0   0   0   0   0   0

三元组表

    | i i   v
------------------
1   | 1 1   15
2   | 1 4   22
3   | 1 6   -15
4   | 2 2   11
5   | 2 3   3
6   | 3 4   6
7   | 5 1   91

五、树与二叉树

典型的非线性结构。

线性结构中结点具有唯一前趋和唯一后继的关系，而非线性结构中结点之间的关系不再具有这种唯一性；
树形结构中结点间的关系是前趋唯一而后继不唯一，即元素之间是一对多的关系；
在图结构中结点之间的关系是前趋、后继均不唯一，因此也就无所谓前趋、后继了

5.1 树的基本概念

树（Tree）是n（n≥0）个结点的有限集合
当n=0时，称这棵树为空树；
当n>0时，该集合满足以下条件：
（1）有且只有一个特殊的结点称为树的根（root），根结点没有直接前趋结点，但有零个或多个直接后继结点；（这里的前趋、后继暂时沿用线性表中的概念，在树中，前趋、后继其实是另外的术语）。
（2）除根结点之外的其余n-1个结点被分成m（m>0）个互不相交的集合T1, T2,…, Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1, T2, …, Tm称为根结点的子树；
树的二元组的形式：T=(D, R)
其中，D为树T中结点的集合，R为树中结点之间关系的集合。
当树T为空树时，即D=Φ；
当树T不为空树时，有：D={Root}∪DF其中，Root为树T的根结点，DF为树T的根Root的子树集合；

术语：
（1）结点：包含一个数据元素及若干指向其他结点的分支信息的数据结构。
（2）结点的度：结点所拥有的子树的个数称为该结点的度。
（3）叶子结点：度为0的结点称为叶子结点，或者称为终端结点。
（4）分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的结点都是分支结点。
（5）孩子结点、双亲结点、兄弟结点：树中一个结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点。具有同一个双亲结点的孩子结点互称为兄弟结点。
（6）路径、路径长度：设n1, n2, …, nk为一棵树的结点序列，若结点ni是ni+1的双亲结点（1≤i <k），则把n1, n2, …, nk称为一条由n1至nk的路径。这条路径的长度是k-1。
（7）祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的
（8）结点的层次：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
（9）树的深度（高度）：树中所有结点的层次的最大数称为树的深度。（10）树的度：树中所有结点的度的最大值称为该树的度。
（11）有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。
（12）森林：m（m≥0）棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林；反之，给森林增加一个统一的根结点，森林就变成了一棵树。

操作：

初始化
获取根节点
获取父节点
获取兄弟节点
插入节点
删除节点
遍历树中的所有节点

5.2 二叉树

每个结点只能含有0、1或2个孩子结点，而且其孩子结点有左右之分的树。

5.2.1 二叉树的五种形态

空二叉树
只有根节点的二叉树
只有左子二叉树的二叉树
只有右子二叉树的二叉树
左、右子二叉树都存在的二叉树

5.2.2 概念

满二叉树
如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。
完全二叉树
完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
二叉树性质
（1）性质1
一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
（2）性质2
一棵深度为k的二叉树中，最多具有2k-1个结点。
（3）性质3
对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有：n0=n2+1。
（4）性质4
具有n个结点的完全二叉树的深度[log 2 n] + 1（[]符号表示取整）。
（5）性质5
对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的编号为i的结点，有：
a：如果i > 1，则该结点i的双亲结点的编号为[插图]；如果i=1，则该结点是根结点，无双亲结点。
b：如果2i≤n，则该结点i的左孩子结点的编号为2i；如果2i >n，则该结点i无左孩子。
c：如果2i+ 1≤n，则该结点i的右孩子结点的编号为2i+1；如果2i+ 1>n，则该结点i无右孩子。

5.2.3 二叉树的存储结构

顺序存储结构
用一组连续的存储单元存放二叉树中的结点。
完全二叉树和满二叉树采用顺序存储的话，可以利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系。
链式存储结构
二叉链表存储。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;

三叉链表存储：每个结点由四个域组成，具体结构为：其中，data、lchild及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;   //指向左子节点
    struct node *r_child;   //指向有子节点
    struct node *parent;    //指向父节点
}node_t;

5.2.4 二叉树的基本操作

建立空二叉树
由根节点和左右子二叉树合成新的二叉树
插入左二叉树
插入右二叉树
删除左二叉树
删除有二叉树
查找节点
遍历二叉树的节点

5.2.5 二叉树的遍历

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。- - 由于左右具有对称性，因此可以限定先左后右，则只有前三种方式，即DLR（称为前序遍历或先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。

5.2.6 先序遍历（DLR）及其算法

访问过程
（1）访问根结点；
（2）先序遍历根结点的左子树；
（3）先序遍历根结点的右子树
可见这个过程包含递归形式。例子：

//二叉树测试
#include <stdio.h>
#include <stdlib.h>
//二叉链表
typedef int data_type;
typedef struct node{
    data_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;
//创建根节点
node_t *node_creat_root(void)
{
    node_t *ret = (node_t*)malloc(sizeof(node_t));
    ret->l_child = NULL;
    ret->r_child = NULL;
    return ret;
}
//向节点插入左节点
node_t *tree_insert_l(node_t *node_p)
{
    node_t *l = (node_t *)malloc(sizeof(node_t));
    l->l_child = NULL;
    l->r_child = NULL;
    node_p->l_child = l;
    return l;
}
//向节点插入左节点
node_t *tree_insert_r(node_t *node_p)
{
    node_t *r = (node_t *)malloc(sizeof(node_t));
    r->l_child = NULL;
    r->r_child = NULL;
    node_p->r_child = r;
    return r;
}
//先序遍历二叉树节点，打印数据（用递归方法比较合适）
void tree_scan_dlr(node_t *root)
{
    printf("%c\n", root->data);
    if(root->l_child != NULL)
    {
        tree_scan_dlr(root->l_child);
    }
    
    if(root->r_child != NULL)
    {
        tree_scan_dlr(root->r_child);
    }
}
int main()  
{     
    node_t *tree_p;
    tree_p = node_creat_root();
    tree_p->data = 'a';
    node_t *l = tree_insert_l(tree_p);
    l->data = 'b';
    node_t *r = tree_insert_r(tree_p);
    r->data = 'c';
    node_t *n1 = tree_insert_l(l);
    n1->data = 'd';
    node_t *n2 = tree_insert_r(l);
    n2->data = 'e';
    node_t *n3 = tree_insert_l(r);
    n3->data = 'f';
    node_t *n4 = tree_insert_r(r);
    n4->data = 'g';
    tree_scan_dlr(tree_p);  
    return 0;    
}

也有非递归先序遍历的方式（通过“辅助栈”的思想实现）

5.2.6 中序遍历（LDR）及其算法

中序遍历（LDR）的递归过程为：若二叉树为空，遍历结束。否则：
（1）中序遍历根结点的左子树；
（2）访问根结点；
（3）中序遍历根结点的右子树。

5.2.7 后续遍历（LRD）及其算法

后序遍历（LRD）的递归过程为：若二叉树为空，遍历结束。否则：
（1）后序遍历根结点的左子树；
（2）后序遍历根结点的右子树；
（3）访问根结点。

5.2.8 层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
算法实现：
二叉树以二叉链表存储，一维数组用以实现队列。
注意应用队列的头和尾的移动。

5.2.9 二叉树的其他操作

查找元素
统计叶子结点个数
求二叉树的深度

5.3 树与森林

5.3.1 树的表示方法

树的存储方式有顺序存储、链式存储，表示的方法也有多种：
（1）双亲表示法
树中的每个结点（除根结点外）都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息及该结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。
（2）孩子表示法

（3）孩子兄弟表示法

5.3.2 树、二叉树和森林的转换

将一棵树转换为二叉树的方法是：
（1）树中所有相邻兄弟之间加一条连线；
（2）对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线；
（3）以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。

【待续：森林转换为二叉树、二叉树转换为树和森林】

5.3.3 树遍历

先根遍历：
（1）访问根结点；
（2）按照从左到右的顺序先根遍历根结点的每一棵子树。
后根遍历：
（1）按照从左到右的顺序后根遍历根结点的每一棵子树；
（2）访问根结点。

5.3.4 森林的遍历

前序遍历：
（1）0 访问森林中第一棵树的根结点；
（2）前序遍历第一棵树的根结点的子树；
（3）前序遍历去掉第一棵树后的子森林。
中序遍历：
（1）0 中序遍历第一棵树的根结点的子树；
（2）访问森林中第一棵树的根结点；
（3）中序遍历去掉第一棵树后的子森林。

5.4 哈夫曼树（最优二叉树）

最优二叉树也称哈夫曼（Huffman）树，是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树；
权值是指一个与特定结点相关的数值。
对权值和节点路径长度乘积进行累加，得到的和为最小值。
带权路径长度（Weighted Path Length）
思想：根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

5.4.1 哈夫曼树的构造方法

（1）由给定的n个权值{w1, w2, …, wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1, T2, …, Tn}；
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

5.4.2 哈夫曼树的构造算法

【待续】

5.4.3 哈夫曼数的编码

利用哈夫曼树来构造编码方案，就是哈夫曼树的典型应用。

六、图

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的。

6.1 图的基本概念

6.1.1 术语

（1）无向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。如图6.1所示是一个无向图G1。
（2）有向图：在一个图中，如果任意两个顶点构成的偶对<vi, vj>∈E是有序的（有序对常常用尖括号“< >”表示），即顶点之间的连线是有方向的，则称该图为有向图。
（3）顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；(vi,vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对(vi, vj)来表示，称顶点vi和顶点vj互为邻接点，边(vi, vj)依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi, vj>来表示，有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。
（4）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。
（5）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。
（6）顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD (v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。有TD (v)=ID (v)＋OD (v)。
可以证明，对于具有n个顶点、e条边的无向图，顶点vi的度TD(vi)与顶点的个数及边的数目满足关系：

图片.png

（8）路径、路径长度：顶点vp到顶点vq之间的路径（Path）是指顶点序列vp, vi1,vi2, …, vim, vq。其中，(vp, vi1), (vi1, vi2), …, (vim, vq)分别为图中的边。路径上边的数目称为路径长度。图6.1所示的无向图G1中，v1→v4→v3→v5与v1→v2→v5是从顶点v1到顶点v5的两条路径，其路径长度分别为3和2。
（9）简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。在图6.1中，前面提到的v1到v5的两条路径都为简单路径。路径中第一个顶点与最后一个顶点相同的路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图6.2中的v1→v3→v4→v1。
（10）子图：对于图G=(V, E)，G′=(V′, E′)，若存在V′是V的子集、E′是E的子集，则称图G′是G的一个子图。图6.4给出了图6.2(G2)和图6.1(G1)的两个子图G′和G″。
（11）连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。
（12）强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj(i≠j)均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。图6.2中有两个强连通分量，分别是{v1, v3, v4}和{v2}，如图6.6所示。
（13）生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。图6.4（b）中的G″给出了图6.1中G1的一棵生成树。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。
（14）生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

6.1.2 图的操作

（1）CreatGraph(G)：输入图G的顶点和边，建立图G的存储。（2）DestroyGraph(G)：释放图G占用的存储空间。
（3）GetVex(G, v)：在图G中找到顶点v，并返回顶点v的相关信息。（4）PutVex(G, v, value)：在图G中找到顶点v，并将value值赋给顶点v。
（5）InsertVex(G, v)：在图G中增添新顶点v。
（6）DeleteVex(G, v)：在图G中，删除顶点v及所有和顶点v相关联的边或弧。
（7）InsertArc(G, v, w)：在图G中增添一条从顶点v到顶点w的边或弧。
（8）DeleteArc(G, v, w)：在图G中删除一条从顶点v到顶点w的边或弧。
（9）DFSTraverse(G, v)：在图G中，从顶点v出发深度优先遍历图G。
（10）BFSTtaverse(G, v)：在图G中，从顶点v出发广度优先遍历图G。在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图还有以下的基本操作。
（11）LocateVex(G, u)：在图G中找到顶点u，返回该顶点在图中位置。（12）FirstAdjVex(G, v)：在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。（13）NextAdjVex(G, v, w)：在图G中，返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。

6.2 图的存储结构

6.2.1 邻接矩阵

所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。
用矩阵表示图中各顶点之间的邻接关系。假设图G=(V, E)有n个确定的顶点，即V={v0, v1, …, vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵元素下标i、j代表点，元素值用1表示连接，0标志未连接。

特点：
（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。
（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。
（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。
（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

6.2.2 邻接表

邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表

一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成；
另一种是边表（即邻接表）结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成；
对于网的边表需再增设一个存储边上信息（如权值等）的域（info）。

在邻接表上容易找到任意顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需查找第i个或第j个链表，因此，不如邻接矩阵方便。

6.3 图的遍历

图的遍历是指从图中的任意顶点出发，对图中的所有顶点访问一次且只访问一次。

6.3.1 深度优先搜索（Depth-First Search，DFS）

类似于树的先根遍历，是树的先根遍历的推广。

假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点；
然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点；
重复上述过程，直至图中所有顶点都被访问到为止。

6.3.2 广度优先搜索（Breadth-First Search，BFS）

类似于树的按层次遍历的过程。

假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点；
然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止；
换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1, 2, …的顶点。

6.4 图的应用

6.4.1 最小生成树

如果无向连通图是一个网，那么，它的所有生成树中必有一棵生成树的边的权值总和最小，称这样一棵生成树为最小代价生成树（Minimum Cost SpanningTree），简称最小生成树（MST）。一棵生成树的代价就是树中所有边的代价之和。

构造最小生成树的Prim算法和Kruskal算法
【待续】

6.4.2 最短路径

在网中求点A到点B的所有路径中边的权值之和最短的那一条路径，这条路径就是两点之间的最短路径
【待续】

6.4.3 拓扑排序

一个无环的有向图称为有向无环图（Directed Acycline Graph，DAG）。
有向无环图是描述工程或系统进程的有效工具。

七、查找

（1）关键码

关键码（Key）是数据元素（记录）中某个项或组合项的值，可以用它标识一个数据元素（记录）；
能唯一确定一个数据元素（记录）的关键码称为主关键码；
不能唯一确定一个数据元素（记录）的关键码称为次关键码。
（2）查找表
具有同一类型（属性）的数据元素（记录）组成的集合称为查找表。
静态查找表：仅对查找表进行前两种所谓的“查找”操作，而不能被改变的表；
动态查找表：对查找表除进行“查找”操作外，可能还要向表中插入数据元素或删除表中数据元素，因而动态查找表在查找过程中可以被改变。
（3）查找
按给定的某个值kx，在查找表中查找关键码为给定值kx的数据元素（记录）。
（4）平均查找长度ASL
定义：在查找成功时，平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键码比较次数的期望值

7.2 静态表查找

7.2.1 静态表查找结构

静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。

7.2.2 顺序查找

顺序查找又称线性查找，是最基本的查找方法之一。其查找过程为：从表的一端开始，向另一端逐个将其关键码与给定值kx进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息。

7.2.3 有序表查找

有序表是表中数据元素按关键码升序或降序排列。对于有序表，若按顺序存储结构存储，可以用折半查找来实现查找操作。

7.2.4 分块查找

分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找要求将查找表分成若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。

7.3 动态表查找

二叉排序树就是一种常见的动态查找表

7.3.1 二叉排序树定义

二叉排序树（Binary Sort Tree）或者是一棵空二叉树，或者是具有下列性质的二叉树。
（1）若左子树不空，则左子树上所有结点的关键码值均小于根结点的关键码值；若右子树不空，则右子树上所有结点的关键码值均大于根结点的关键码值。
（2）左、右子树也都是二叉排序树。
左子节点键值 < 父节点键值 < 右子节点键值

7.3.1 二叉排序树查找算法

7.3.1 二叉排序树构造和插入

7.4 哈希表

建立关键码与数据元素间的一一对应关系，通过这个关系，能很快地由关键码值得到对应的数据元素位置。而哈希方法就是试图建立这样的对应关系。

选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比较，确定查找是否成功，这就是哈希（Hash）方法（又称为散列法、杂凑法或关键字地址计算法）；哈希方法中使用的转换函数称为哈希（Hash）函数（散列函数）。