夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 101 页PDF · 949.1KB
下载

文档在线预览

公开展示前 10 页
100%
1
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《012-第十二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 101 页 剩余 91 页未展示,请下载后查阅

下载

文档文本内容

第十一讲:高阶应用
主讲人:刘财政
B站:@计算机考研刘财政考点框架CON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用CON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用【二叉树的基本算法】考点二:二叉树的应用
// 递归先序遍历 typedef char ElemType;
typedef struct BTNode {
void PreOrderVisit(BiTree t, void (*visit)(BiTree)) {
ElemType data;
if (!t) return;
struct BTNode *lchild, *rchild;
visit(t);
} BTNode, *BiTree;
PreOrderVisit(t->lchild, visit);
PreOrderVisit(t->rchild, visit);
}
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机
L R考点二:二叉树的应用
// 递归中序遍历 typedef char ElemType;
typedef struct BTNode {
void InOrderVisit(BiTree t, void (*visit)(BiTree)) {
ElemType data;
if (!t) return;
struct BTNode *lchild, *rchild;
InOrderVisit(t->lchild, visit);
} BTNode, *BiTree;
visit(t);
InOrderVisit(t->rchild, visit);
}
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机
L R考点二:二叉树的应用
// 递归后序遍历 typedef char ElemType;
typedef struct BTNode {
void PostOrderVisit(BiTree t, void (*visit)(BiTree))
ElemType data;
{
struct BTNode *lchild, *rchild;
if (!t) return;
} BTNode, *BiTree;
PostOrderVisit(t->lchild, visit);
PostOrderVisit(t->rchild, visit);
visit(t);
}
按照先左后右的方式扫描二叉树,
区别仅在于访问结点的时机
L R考点二:二叉树的应用
// 非递归先序遍历 typedef char ElemType;
void PreOrderVisit2(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
stack<BiTree> s;
ElemType data;
while (t || !s.empty()) {
struct BTNode *lchild, *rchild;
if (t) {
} BTNode, *BiTree;
visit(t); // 先访问当前子树的根结点
s.push(t); // 将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
L R
s.pop(); // 弹出最近访问子树的根结点
t = t->rchild; // 访问当前子树的右子树
}
}
}考点二:二叉树的应用
// 非递归中序遍历 typedef char ElemType;
void InOrderVisit2(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
stack<BiTree> s;
ElemType data;
while (t || !s.empty()) {
struct BTNode *lchild, *rchild;
if (t) {
} BTNode, *BiTree;
s.push(t); // 先将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
s.pop(); // 弹出最近访问子树的根结点
L R
visit(t); // 访问当前子树的根结点
t = t->rchild; // 访问当前子树的右子树
}
}
}考点二:二叉树的应用
// 非递归后序遍历 typedef char ElemType;
void PostOrderVisit2(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
stack<BiTree> s;
ElemType data;
BiTree last = NULL; // 记录最近访问过的结点
struct BTNode *lchild, *rchild;
while (t || !s.empty()) {
} BTNode, *BiTree;
if (t) {
s.push(t); // 先将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
L R
if (t->rchild && t->rchild != last) {
t = t->rchild; // 当前子树的右子树存在且未被访问过,
访问当前子树的右子树考点二:二叉树的应用
// 非递归后序遍历 typedef char ElemType;
void PostOrderVisit2(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
stack<BiTree> s;
ElemType data;
BiTree last = NULL; // 记录最近访问过的结点
struct BTNode *lchild, *rchild;
while (t || !s.empty()) {
} BTNode, *BiTree;
else {
s.pop(); // 弹出最近访问子树的根结点
visit(t); // 访问当前子树的根结点
last = t; // 记录最近访问过的结点
t = NULL; // 置空,继续弹出栈顶结点
L R
}
}
}
}考点二:二叉树的应用
// 层次遍历
typedef char ElemType;
void LevelOrderVisit(BiTree t, void (*visit)(BiTree)) {
typedef struct BTNode {
if (!t) { return; }// 空树直接返回
ElemType data;
queue<BiTree> q;
q.push(t); // 根结点入队 struct BTNode *lchild, *rchild;
while (!q.empty()) {
} BTNode, *BiTree;
BiTree p = q.front();
q.pop(); // 队头结点出队
visit(p); // 访问队头结点
if (p->lchild) {
q.push(p->lchild); // 如果有左孩子,将左孩子入队
} L R
if (p->rchild) {
q.push(p->rchild); // 如果有右孩子,将右孩子入队
}
}
}【高阶应用】考点二:二叉树的应用
1、求二叉树的叶子结点数: 直接利用先序遍历二叉树算法求二叉树的叶子结点
数。只要将先序遍历二叉树算法中vist()函数简单地进行修改就可以。考点二:二叉树的应用
1、求二叉树的叶子结点数: 直接利用先序遍历二叉树算法求二叉树的叶子结点
数。只要将先序遍历二叉树算法中vist()函数简单地进行修改就可以。
void CountLeaf(BitTree T,int& count) {//累加和存储于变量count中,
其初值为0
if(T){ //二叉树T如果为空,则什么都不做;不为空时往下执行
if((!T->lchild)&&(!T->rchild))
count++;
CountLeaf(T->lchild,count);//遍历左子树叶子节点个数
CountLeaf(T->rchild,count);//遍历右子树叶子节点个数
}
}考点二:二叉树的应用
1、求二叉树的叶子结点数: 直接利用先序遍历二叉树算法求二叉树的叶子结点
数。只要将先序遍历二叉树算法中vist()函数简单地进行修改就可以。
int cnt = 0;
// 统计叶子节点个数的函数
void LeafCnt(BiTree t) {
if (!t->lchild && !t->rchild) {
++cnt;
}
}
PreOrderVisit(root, LeafCnt);
InOrderVisit(root, LeafCnt);
PostOrderVisit(root, LeafCnt);
LevelOrderVisit(root, LeafCnt);考点二:二叉树的应用
2、求二叉树的高度考点二:二叉树的应用
2、求二叉树的高度
利用递归方法可以直接求得二叉树的深度。
int treeDepth(binTree *rootNode) {
if(rootNode==NULL)
return 0;
else{
int lH=treeDepth(rootNode->lNode);
int rH=treeDepth(rootNode->rNode);
if(lH>rH) return lH+1;
return rH+1;
}
}考点二:二叉树的应用
2、求二叉树的高度
利用递归方法可以直接求得二叉树的深度。
int Depth(BiTree t) {
if (!t) {
return 0;
}
return max(Depth(t->lchild), Depth(t->rchild)) + 1;
}考点二:二叉树的应用
3、求二叉树的宽度考点二:二叉树的应用
3、求二叉树的宽度
所谓二叉树的宽度是指:二叉树各层节点个数的最大值。
算法思想:要求的是对于特定某一层的节点的个数,因此我们需要从头结点开
始,记录每一层的个数,对于当前层的每一个节点,在弹出自身之后把其左右
子树压入deque,当把当前层全部弹出队列之后,在队列中剩下的就是下一层
的节点。然后比较队列的size和之前得到的maxWidth,取最大值即为队列的
宽度。最终队列为空,得到的maxWidth就是二叉树的宽度。考点二:二叉树的应用
int Width(BiTree t) {
if (!t) {return 0;}
int width = 1; // t不为空时,宽度至少为1
BiTree last = t; // 记录当前层的最后一个节点
queue<BiTree> q;
q.push(t); // 根节点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 对头结点出队
if (p->lchild) q.push(p->lchild); // 如果有左孩子,将左孩子入队
if (p->rchild) q.push(p->rchild); // 如果有右孩子,将右孩子入队
if (p == last) { // 如果p是当前层的最后一个节点
width = max(width, (int)q.size()); // 更新宽度
last = q.back(); // 更新last为下一层的最后一结点
}
}
return width;
}考点二:二叉树的应用
4、交换二叉的左右子树考点二:二叉树的应用
4、交换二叉的左右子树
// root是根节点
BiNode * temp, * root1;
void swap(BiNode root1){
if(root1 == NULL) return;
else{
temp = root1->lchild;
root1->lchild = root1->rchild;
root1->rchild = temp;
swap(root1->lchild);
swap(root1->rchild);
}
}考点二:二叉树的应用
4、交换二叉的左右子树
void Exchange(BiTree t) { swap(t->lchild, t->rchild); }
PreOrderVisit(root, Exchange);
PostOrderVisit(root, Exchange);考点二:二叉树的应用
5、二叉树的最小深度:给定一个二叉树,求解二叉树的最小的深度。最小深
度是从根节点到最近的叶节点的最短路径上的节点数。考点二:二叉树的应用
5、二叉树的最小深度:给定一个二叉树,求解二叉树的最小的深度。最小深
度是从根节点到最近的叶节点的最短路径上的节点数。
// 思路:根据左右孩子的不同情况分别返回不同的相应深度,在左右孩子均存
在时,返回深度较小的那一边,以获得最小深度。
int minDepth(TreeNode *root){
if(root==nullptr)
return 0;
int heightOfLeft = minDepth (root->left);
int heightOfRight = minDepth (root->right);
return min(heightOfLeft,heightOfRight)+1;
}考点二:二叉树的应用
5、二叉树的最小深度:给定一个二叉树,求解二叉树的最小的深度。最小深
度是从根节点到最近的叶节点的最短路径上的节点数。
利用递归方法可以直接求得二叉树的最小深度。
int Depth(BiTree t) {
if (!t) {
return 0;
}
return min(Depth(t->lchild), Depth(t->rchild)) + 1;
}考点二:二叉树的应用
6、对称树考点二:二叉树的应用
6、对称树
// 判断两棵树是否互为镜像
bool Mirror(BiTree t1, BiTree t2) { bool Symmertric(BiTree t) {
if (!t) {
if (!t1 && !t2) {
return true;
return true; }
return Mirror(t, t);
}
}
if (!t1 || !t2) {
return false;
}
return t1->data == t2->data && Mirror(t1->lchild, t2->rchild) &&
Mirror(t1->rchild, t2->lchild);
}考点二:二叉树的应用
7、一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一
个算法求二叉树的繁茂度。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。考点二:二叉树的应用
int Width(BiTree t) {
if (!t) {return 0;}
int width = 1; // t不为空时,宽度至少为1
BiTree last = t; // 记录当前层的最后一个节点
queue<BiTree> q;
q.push(t); // 根节点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 对头结点出队
if (p->lchild) q.push(p->lchild); // 如果有左孩子,将左孩子入队
if (p->rchild) q.push(p->rchild); // 如果有右孩子,将右孩子入队
if (p == last) { // 如果p是当前层的最后一个节点
width = max(width, (int)q.size()); // 更新宽度
last = q.back(); // 更新last为下一层的最后一结点
}
}
return width;
}考点二:二叉树的应用
int Depth(BiTree t) {
if (!t) {
return 0;
}
return max(Depth(t->lchild), Depth(t->rchild)) + 1;
}
int Lush(BiTree t) { return Width(t) * Depth(t); }考点二:二叉树的应用
8、设计一个求结点x在二叉树中的双亲结点算法考点二:二叉树的应用
//非递归先序搜索(DFS)
BiTree PreOrderSearch(BiTree t, ElemType e, bool (*cmp)(BiTree, ElemType)) {
stack<BiTree> s;
while (t |I !s.empty()) {
if (t) {
if ( cmp(t, e)) { return t;}//找到目标结点,返回了
s. push(t) ;//将当前子树的根结点入栈
t=t->lchild;//优先搜索当前子树的左子树}
else {
t = s. top();
s. pop)();//弹出最近搜索子树的根结点
t=t->rchild;//搜索当前子树的右子树
}
}
return NULL;
}考点二:二叉树的应用
// 判断t的左右孩子是否包含有e元素
bool HasChild(BiTree t, ElemType e) {
if ((t->lchild && t->lchild->data == e) ||
(t->rchild && t->rchild->data == e)) {
return true;
}
return false;
}
PreOrderSearch(t,e,HasChild)考点二:二叉树的应用
9、假定用两个一维数组L[1:n]和R[1:n]作为有n个节点二叉树的存储结构,
L[i]和R[i]分别指示节点i的左儿子和右儿子,0表示空。试写一个算法判断节点
u是否为节点v的子孙。考点二:二叉树的应用
bool Dencendant(int l[], int r[], int n, int u, int v) {
if (v > n) {
return false; // v超出范围
}
if (v == 0) {
return false; // v为空,没有子孙
}
if (l[v] == 0 && r[v] == 0) {
return false; // v是叶子结点,没有子孙
}
if (l[v] == u || r[v] == u) {
return true; // v的左孩子或右孩子是u,u是v的子孙
}
return Dencendant(l, r, n, u, l[v]) ||
Dencendant(l, r, n, u, r[v]); // 递归搜索v的左子树和右子树
}考点二:二叉树的应用
10、请设计一个算法判断二叉树T是否为一棵完全二叉树,若是,返回1;否
则返回0。考点二:二叉树的应用
// 判断是否为完全二叉树
bool CompleteBiTree(BiTree t) {
queue<BiTree> q;
q.push(t); // 根结点入队
while (!q.empty()) {
BiTree p = q.front();
q.pop(); // 队头结点出队
if (!p) { break; } // 发现第一个空结点,跳出循环
q.push(p->lchild); // 左孩子入队
q.push(p->rchild); // 右孩子入队
}
// 判断队列中是否还有非空结点
while (!q.empty()) {
BiTree p = q.front();
q.pop();
if (p) {
return false; // 发现非空结点,不是完全二叉树
}
}
return true;
}考点二:二叉树的应用
11、设二叉树采用链式存储结构,定义结点结构为(leftchild,data,
rightchild),其中data为元素的值,leftchild和rightchild分别表示指向左子
结点的指针和指向右子结点的指针,root为指向根的指针,p所指的节点为任
一给定的节点,编写算法,求从根节点到p所指节点之间路径。考点二:二叉树的应用
// 求从根结点到目标结点的路径,结果保存到路径栈path中
bool Path(BiTree& t, BiTree& node, stack<BiTree>& path) {
if (!t) {
return false; // 空树,没有路径
}
if (t == node) {
path.push(t); // 找到目标结点,将其入栈
return true;
}
if (Path(t->lchild, node, path)) {
path.push(t); // 左子树中找到目标结点,将其入栈
return true;
}
if (Path(t->rchild, node, path)) {
path.push(t); // 右子树中找到目标结点,将其入栈
return true;
}
return false; // 没有找到目标结点,路径不存在
}THANKSCON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用【图的基本算法】考点三:图的高阶应用
#define MAXSIZE 100 // 最大顶点数
#define INF 65535 // 无穷大,用于表示两个顶点之间没有边
typedef char VertexInfo; // 顶点相关信息,这里表示顶点名称
typedef int ArcInfo; // 边相关信息,这里表示权值
typedef struct {
ArcInfo edges[MAXSIZE][MAXSIZE]; // 邻接矩阵
VertexInfo vexs[MAXSIZE]; // 存放顶点信息
int n, e; // 图的顶点数和边数
} MGraph;
typedef struct {
int src; // 边的起点
int dest; // 边的终点
ArcInfo weight; // 边的权值
} Edge;考点三:图的高阶应用
// 以src为源点,深度优先遍历图g,visited为访问标记数组,visit为访问函数
void DFS(MGraph& g, int src, bool visited[], void (*visit)(VertexInfo)) {
if (src >= g.n) {
return; // 超出范围
}
visited[src] = true; // 标记src已访问
visit(g.vexs[src]); // 访问src
for (int i = 0; i < g.n; ++i) {
if (!visited[i] && g.edges[src][i] != INF) {
DFS(g, i, visited, visit); // 遍历未访问的邻接点
}
}
}考点三:图的高阶应用
// 深度优先遍历图g,visit为访问函数
void DFSTraverse(MGraph& g, void (*visit)(VertexInfo)) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
for (int i = 0; i < g.n; ++i) {
if (!visited[i]) {
DFS(g, i, visited, visit); // 若未访问,则递归访问该顶点
}
}
}考点三:图的高阶应用
#define MAXSIZE 100 // 最大顶点数
#define INF 65535 // 无穷大,用于表示两个顶点之间没有边
typedef char VertexInfo; // 顶点相关信息,这里表示顶点名称
typedef int ArcInfo; // 边相关信息,这里表示权值
typedef struct {
ArcInfo edges[MAXSIZE][MAXSIZE]; // 邻接矩阵
VertexInfo vexs[MAXSIZE]; // 存放顶点信息
int n, e; // 图的顶点数和边数
} MGraph;
typedef struct {
int src; // 边的起点
int dest; // 边的终点
ArcInfo weight; // 边的权值
} Edge;考点三:图的高阶应用
// 以src为源点,广度优先遍历图g,visited为访问标记数组,visit为访问函数
void BFS(MGraph& g, int src, bool visited[], void (*visit)(VertexInfo)) {
if (src >= g.n) { return; } // 超出范围
queue<int> q;
q.push(src); // 将src入队
visited[src] = true; // 标记src已访问
visit(g.vexs[src]); // 访问src
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i < g.n; ++i) {
if (!visited[i] && g.edges[v][i] != INF) {
q.push(i); // 将未访问的邻接点入队
visited[i] = true; // 标记邻接点已访问
visit(g.vexs[i]); // 访问邻接点
}
}
}
}考点三:图的高阶应用
// 广度优先遍历图g,visit为访问函数
void BFSTraverse(MGraph& g, void (*visit)(VertexInfo)) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
for (int i = 0; i < g.n; ++i) {
if (!visited[i]) {
BFS(g, i, visited, visit); // 若未访问,则递归访问该顶点
}
}
}考点三:图的高阶应用
#define MAXSIZE 100 // 最大顶点数
typedef int ArcInfo; // 边相关信息,这里表示权值
typedef struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
struct ArcNode* nextarc; // 指向下一条边的指针
ArcInfo info; // 边相关信息,这里表示权值
} ArcNode; // 表结点(边结点)定义
typedef char VertexInfo; // 顶点相关信息,这里表示顶点名称
typedef struct VNode {
VertexInfo info; // 顶点相关信息,这里表示顶点名称
ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode; // 表头结点(顶点结点)定义
typedef struct {
VNode adjlist[MAXSIZE]; // 邻接表的表头结点数组
int n, e; // 图中的顶点数n和边数e
} ALGraph; // 图的邻接表定义
typedef struct {
int src; // 边的起点
int dest; // 边的终点
ArcInfo weight; // 边的权值
} Edge;考点三:图的高阶应用
// 以src为源点,深度优先遍历图g,visited为访问标记数组,visit为访问函数
void DFS(ALGraph& g, int src, bool visited[], void (*visit)(VNode)) {
if (src >= g.n) {
return; // 超出范围
}
visited[src] = true; // 标记src已访问
visit(g.adjlist[src]); // 访问src
for (ArcNode* arc = g.adjlist[src].firstarc; arc; arc = arc->nextarc) {
if (!visited[arc->adjvex]) {
DFS(g, arc->adjvex, visited, visit); // 遍历未访问的邻接点
}
}
}考点三:图的高阶应用
// 深度优先遍历图g,visit为访问函数
void DFSTraverse(ALGraph& g, void (*visit)(VNode)) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
for (int i = 0; i < g.n; ++i) {
if (!visited[i]) {
DFS(g, i, visited, visit); // 若未访问,则递归访问该顶点
}
}
}考点三:图的高阶应用
#define MAXSIZE 100 // 最大顶点数
typedef int ArcInfo; // 边相关信息,这里表示权值
typedef struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
struct ArcNode* nextarc; // 指向下一条边的指针
ArcInfo info; // 边相关信息,这里表示权值
} ArcNode; // 表结点(边结点)定义
typedef char VertexInfo; // 顶点相关信息,这里表示顶点名称
typedef struct VNode {
VertexInfo info; // 顶点相关信息,这里表示顶点名称
ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode; // 表头结点(顶点结点)定义考点三:图的高阶应用
typedef struct {
VNode adjlist[MAXSIZE]; // 邻接表的表头结点数组
int n, e; // 图中的顶点数n和边数e
} ALGraph; // 图的邻接表定义
typedef struct {
int src; // 边的起点
int dest; // 边的终点
ArcInfo weight; // 边的权值
} Edge;考点三:图的高阶应用
// 以src为源点,广度优先遍历图g,visited为访问标记数组,visit为访问函数
void BFS(ALGraph& g, int src, bool visited[], void (*visit)(VNode)) {
if (src >= g.n) {
return; // 超出范围
}
queue<int> q;
q.push(src); // 将src入队
visited[src] = true; // 标记src已访问
visit(g.adjlist[src]); // 访问src
while (!q.empty()) {
int v = q.front();
q.pop();
for (ArcNode* arc = g.adjlist[v].firstarc; arc; arc = arc->nextarc) {
if (!visited[arc->adjvex]) {
q.push(arc->adjvex); // 将未访问的邻接点入队
visited[arc->adjvex] = true; // 标记邻接点已访问
visit(g.adjlist[arc->adjvex]); // 访问邻接点
}
}
}
}考点三:图的高阶应用
// 广度优先遍历图g,visit为访问函数
void BFSTraverse(ALGraph& g, void (*visit)(VNode)) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
for (int i = 0; i < g.n; ++i) {
if (!visited[i]) {
BFS(g, i, visited, visit); // 若未访问,则递归访问该顶点
}
}
}【图的高阶应用】考点三:图的高阶应用
1、假设图采用邻接表表示,采用深度优先遍历和广度优先遍历,判断结点i和
结点j之间是否存在路径考点三:图的高阶应用
1、假设图采用邻接表表示,采用深度优先遍历和广度优先遍历,判断结点i和
结点j之间是否存在路径
// 以src为源点,深度优先遍历图g,visited为访问标记数组,visit为访问函数
void DFS(ALGraph& g, int src, bool visited[], void (*visit)(VNode)) {
if (src >= g.n) {
return; // 超出范围
}
visited[src] = true; // 标记src已访问
visit(g.adjlist[src]); // 访问src
for (ArcNode* arc = g.adjlist[src].firstarc; arc; arc = arc->nextarc) {
if (!visited[arc->adjvex]) {
DFS(g, arc->adjvex, visited, visit); // 遍历未访问的邻接点
}
}
}考点三:图的高阶应用
1、假设图采用邻接表表示,采用深度优先遍历和广度优先遍历,判断结点i和
结点j之间是否存在路径
void DoNothing(VNode v) {}
// 以src为源点,dest为终点,判断src和dest之间是否存在路径
bool HasPath(ALGraph& g, int src, int dest) {
if (src == dest) {
return true; // 找到路径
}
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
DFS(g, src, visited, DoNothing); // 标记以src为源点的所有目的点
return visited[dest]; // 判断dest是否已访问
}考点三:图的高阶应用
// 以src为源点,广度优先遍历图g,visited为访问标记数组,visit为访问函数
void BFS(ALGraph& g, int src, bool visited[], void (*visit)(VNode)) {
if (src >= g.n) {
return; // 超出范围
}
queue<int> q;
q.push(src); // 将src入队
visited[src] = true; // 标记src已访问
visit(g.adjlist[src]); // 访问src
while (!q.empty()) {
int v = q.front();
q.pop();
for (ArcNode* arc = g.adjlist[v].firstarc; arc; arc = arc->nextarc) {
if (!visited[arc->adjvex]) {
q.push(arc->adjvex); // 将未访问的邻接点入队
visited[arc->adjvex] = true; // 标记邻接点已访问
visit(g.adjlist[arc->adjvex]); // 访问邻接点
}
}
}
}考点三:图的高阶应用
2、假设图采用邻接表表示,设计一个算法,判断无向图是否是连通图考点三:图的高阶应用
2、假设图采用邻接表表示,设计一个算法,判断无向图是否是连通图
void NodeCnt(VNode t) { ++cnt; }
// 判断图g是否连通
bool Connected(ALGraph& g) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
BFS(g, 0, visited, NodeCnt); // 广度优先遍历,统计结点数
return cnt == g.n;
}考点三:图的高阶应用
2、假设图采用邻接表表示,设计一个算法,判断无向图是否是连通图
void NodeCnt(VNode t) { ++cnt; }
// 判断图g是否连通
bool Connected(ALGraph& g) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
DFS(g, 0, visited, NodeCnt); // 深度优先遍历,统计结点数
return cnt == g.n;
}考点三:图的高阶应用
3、假设图采用邻接表表示,设计一个算法,求解距离结点U最远的结点V;考点三:图的高阶应用
int visited[MaxVertex];
int maxDist(Graph G, int U){
ArcNode *p;
Int queue[MaxVertex], front = rear = 0, j, k;
rear ++; queue[rear] = U;
visited[U] = 1
while(rear != front) {
front = (front +1) % MaxVertex;
V = queue[front];
P = V -> adjList[V].firstArc;
while(p != NULL) {
j = p -> adjvex;
if( visited[j] == 0) {
visited[j] = 1;
rear = (rear + 1) % MaxVetex;
queue[rear] = j
}
P = P -> nextArc;
}
}
return V;
}考点三:图的高阶应用
3、假设图采用邻接表表示,设计一个算法,求解距离结点U最远的结点V;
void Record(VNode t) { farthest = t; }
// 求图g中以src为源点的最远距离的结点
void FarthestNode(ALGraph& g, int src) {
bool visited[MAXSIZE] = {false}; // 初始化访问标记数组
BFS(g, src, visited, Record); // 广度优先遍历,记录最远距离的结点
}考点三:图的高阶应用
4、拓扑排序
void PrintNode(VertexInfo v) { printf("%c ", v); }
// 统计各顶点的入度
void CountInDegree(MGraph& g, int indegree[]) {
// 初始化入度数组
for (int i = 0; i < g.n; ++i) {
indegree[i] = 0;
}
for (int i = 0; i < g.n; ++i) {
for (int j = 0; j < g.n; ++j) {
if (g.edges[i][j] != INF) {
++indegree[j];
}
}
}
}考点三:图的高阶应用
// 拓扑排序
// 若图G无回路,返回true,并通过topo返回G的一个拓扑序列
// 否则,返回false
bool TopologicalSort(MGraph& g, VertexInfo topo[]) {
int indegree[MAXSIZE];
CountInDegree(g, indegree);
queue<int> q;
for (int i = 0; i < g.n; ++i) {
if (indegree[i] == 0) {
q.push(i); // 将入度为0的顶点入队
}
}考点三:图的高阶应用
bool TopologicalSort(MGraph& g, VertexInfo topo[]) {
int cnt = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
topo[cnt++] = g.vexs[v];
for (int i = 0; i < g.n; ++i) {
if (g.edges[v][i] != INF &&
--indegree[i] == 0) { // 将v的邻接点的入度减1
q.push(i); // 将入度为0的顶点入队
}
}
}
return cnt == g.n;
}考点三:图的高阶应用
4、拓扑排序
// 统计各顶点的入度
void CountInDegree(ALGraph& g, int indegree[]) {
// 初始化入度数组
for (int i = 0; i < g.n; ++i) {
indegree[i] = 0;
}
for (int i = 0; i < g.n; ++i) {
for (ArcNode* p = g.adjlist[i].firstarc; p; p = p->nextarc) {
++indegree[p->adjvex];
}
}
}考点三:图的高阶应用
// 拓扑排序
// 若图G无回路,返回true,并通过topo返回G的一个拓扑序列
// 否则,返回false
bool TopologicalSort(ALGraph& g, VNode topo[]) {
int indegree[MAXSIZE];
CountInDegree(g, indegree);
queue<int> q;
for (int i = 0; i < g.n; ++i) {
if (indegree[i] == 0) {
q.push(i); // 将入度为0的顶点入队
}
}考点三:图的高阶应用
// 拓扑排序
// 若图G无回路,返回true,并通过topo返回G的一个拓扑序列
// 否则,返回false
bool TopologicalSort(ALGraph& g, VNode topo[]) {
int cnt = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
topo[cnt++] = g.adjlist[v];
for (ArcNode* p = g.adjlist[v].firstarc; p; p = p->nextarc) {
if (--indegree[p->adjvex] == 0) { // 将v的邻接点的入度减1
q.push(p->adjvex); // 将入度为0的顶点入队
}
}
}
return cnt == g.n;
}考点三:图的高阶应用
5、已知某图的邻接矩阵为A, 若从顶点i到顶点j有边, 则A[i, j]=1, 否则A[i, j]=0。
试编写一算法求矩阵A的传递包C:使得若从顶点i到顶点j有一条或多条路径,
则C[i,j]=1, 否则C[i, j]=0。
typedef int adjmatrix [maxvtxnum][maxvtxnum];
void Change(adjmatrix A, adjmatrix C, int n)考点三:图的高阶应用
如果顶点i与顶点j存在直接路径,则顶点i、j联通;若顶点i存在到顶点k的路径,
而顶点k存在到顶点j的路径,则顶点i、j同样联通。表达式为:
C[i][j] = C[i][j] or (C[[i][k] and C[k][j]] //C为传递包
用三层循环遍历即可求出传递包C。描述如下:
for 间接通过每个节点k
for 每个节点i
for 每个节点j
C[i][j] = C[i][j] or (C[[i][k] and C[k][j]];考点三:图的高阶应用
typedef int AdjMatrix[MAXSIZE][MAXSIZE];
void Change(AdjMatrix& A, AdjMatrix& C, int n);
// 已知邻接矩阵A,求A的传递闭包C
void Change(AdjMatrix& A, AdjMatrix& C, int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C[i][j] = A[i][j]; // 将C初始化为邻接矩阵A
}
}
for (int k = 0; k < n; ++k) { // 遍历中间点k
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// 如果结点i可以间接通过结点k到达结点j,则将C[i][j]置为1
if (C[i][k] && C[k][j]) {
C[i][j] = 1;
}
}
}
}
}THANKSCON T EN T S
目录
考点一 线性表的高阶应用
考点二 二叉树的应用
考点三 图的高阶应用
考点四 其他高阶应用考点四:其他高阶应用
1、若查找表用哈希表存储,哈希函数为H(key)=key MOD n,70<n<100,
用链地址法处理冲突,设计哈希表的初始化、插入元素和删除元素的算法。
typedef struct{ // 元素类型
keytype key;
char info[20];
}elemtype;
typedef struct hnode{ // 哈希表链结点类型
elemtype data;
hnode *next;
}hnode,*head;
typedef head HT[100]; // HT为哈希表类型
void InitHT(HT ht, int n)
void InsertHT(HT ht, int n, elemtype x)
int DeleteHT(HT ht, int n, keytype K) // 删除成功返回1,否则返回0考点四:其他高阶应用
1、初始化定义
typedef int KeyType;
typedef int ValueType;
typedef struct {
KeyType key; // 关键字
ValueType val; // 值
} ElemType;
typedef struct HNode {
ElemType data; // 数据元素
struct HNode* next;
} HNode;考点四:其他高阶应用
1、初始化定义
typedef struct HashTable {
HNode* slots[MAXSIZE]; // 哈希表的数组
int (*hash)(struct HashTable&, KeyType); // 哈希函数
int size; // 哈希表的大小
} HashTable;考点四:其他高阶应用
1、初始化
bool InitHashTable(HashTable& ht, int n, int (*hash)(struct HashTable&, KeyType)) {
ht.hash = hash; // 设置哈希函数
ht.size = n; // 设置哈希表的大小
for (int i = 0; i < n; ++i) {
ht.slots[i] = (HNode*)malloc(sizeof(HNode)); // 为每个哈希槽分配链表头
if (!ht.slots[i]) {
return false;
}
ht.slots[i]->next = NULL;
}
return true;
}考点四:其他高阶应用
bool InsertHashTable(HashTable& ht, ElemType e) {
int idx = ht.hash(ht, e.key); // 计算哈希值
for (HNode* p = ht.slots[idx]; p->next; p = p->next) {
if (p->next->data.key == e.key) {
return false; // 元素已存在,插入失败
}
}
HNode* node = (HNode*)malloc(sizeof(HNode));
if (!node) {
return false;
}
node->data = e;
node->next = ht.slots[idx]->next;
ht.slots[idx]->next = node; // 头插法插入元素
return true;
}考点四:其他高阶应用
bool SearchHashTable(HashTable& ht, KeyType key, ValueType& val) {
int idx = ht.hash(ht, key); // 计算哈希值
for (HNode* p = ht.slots[idx]; p->next; p = p->next) {
if (p->next->data.key == key) {
val = p->next->data.val; // 找到元素,返回值
return true;
}
}
return false;
}考点四:其他高阶应用
bool DeleteHashTable(HashTable& ht, KeyType key) {
int idx = ht.hash(ht, key); // 计算哈希值
for (HNode* p = ht.slots[idx]; p->next; p = p->next) {
if (p->next->data.key == key) {
HNode* node = p->next;
p->next = node->next;
free(node); // 释放内存
return true;
}
}
return false;
}考点四:其他高阶应用
2. 排序算法单链表实现归并排序。
通过快慢指针找到链表的中点。以中点为分界将链表切分为两个子链表,并对
两个子链表分别进行归并排序。最后合并两个有序子链表从而得到有序链表。考点四:其他高阶应用
LinkList MergeList(LinkList a, LinkList b) {
// head为合并后链表的头结点,tailp为合并后链表的尾结点指针
LinkList head = NULL, *tailp = &head;
while (a && b) {
if (a->data < b->data) {
*tailp = a;
a = a->next;
} else {
*tailp = b;
b = b->next;
}
tailp = &(*tailp)->next;
}
*tailp = a ? a : b;
return head;
}考点四:其他高阶应用
LinkList MergeSort(LinkList head) {
if (!head || !head->next) {
return head;
}
// 快慢指针找中点
LinkList slow(head);
for (LinkList fast = head->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
LinkList mid = slow->next;
slow->next = NULL;
// 合并将切分后的有序链表
return MergeList(MergeSort(head), MergeSort(mid));
}考点四:其他高阶应用
3、设计算法 Search Insert: 在一棵非空二叉排序树(按各元素的key值建立)上
查找元素值为e的结点, 若该结点存在, 返回其指针; 若该结点不存在, 则插入元
素值为e的新结点, 并返回新结点的指针。
typedef int ElemType;
typedef struct BSTNode {
ElemType key;
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;
bitptr Search_Insert( bitptr T, elemtype e)考点四:其他高阶应用
// 在二叉排序树t中插入一个关键字为key的结点,非递归实现
BSTree SearchInsertBST(BSTree& t, ElemType key) {
BSTree* p = &t;
while (*p) {
if ((*p)->key == key) {
return *p; // 如果关键字已存在,返回该结点
}
if ((*p)->key > key) {
p = &(*p)->lchild; // 在左子树中查找
} else {
p = &(*p)->rchild; // 在右子树中查找
}
}
*p = (BSTree)malloc(sizeof(BSTNode)); // 申请新结点
if (!*p) {
return NULL;
}
(*p)->key = key;
(*p)->lchild = (*p)->rchild = NULL; // 初始化新结点
return *p;
}考点四:其他高阶应用
4、给定一个二叉树,判断其是否是一个有效的二叉排序树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉排序树。考点四:其他高阶应用
bool GreaterThanLast(BiTree t) {
if (last && last->data > t->data) {
return false;
}
last = t;
return true;
}考点四:其他高阶应用
bool InOrderSearch(BiTree t, bool (*cmp)(BiTree))
{
stack<BiTree> s;
while (t || !s.empty()) {
if (t) {
s.push(t); // 先将当前子树的根结点入栈
t = t->lchild; // 优先访问当前子树的左子树
} else {
t = s.top();
s.pop(); // 弹出最近访问子树的根结点
if (!cmp(t)) { // 访问当前子树的根结点
return false;
}
t = t->rchild; // 访问当前子树的右子树
}
}
return true;
}考点四:其他高阶应用
if (InOrderSearch(root, GreaterThanLast)) {
printf("是BST\n");
} else {
printf("不是BST\n");
}考点四:其他高阶应用
5、二叉排序树以二叉链表存储,设计一个高效算法,找出二叉树中所有结点
数据域的最大值,并返回。
二叉树以二叉链表存储,其存储结构为:
typedef struct BiTNode{
TElem Type data;
struct BiTNode *lchild, * rehild;
} BiTNode,BiTree;考点四:其他高阶应用
int getMaxValue(BiTree T){ //求最大(递归算法)
if(T==NULL)
return 0;
if(T!=NULL) {
if(T->data>tmax)
tmax=T->data;
getMaxValue(T->lchild);
getMaxValue(T->rchild);
}
return tmax;
}考点四:其他高阶应用
BiTree maxNode;
void UpdateMaxNode(BiTree t) {
if (t->data > maxNode->data) {
maxNode = t;
}
}
maxNode = t;
PreOrderVisit(t, UpdateMaxNode);
InOrderVisit(t, UpdateMaxNode);
PostOrderVisit(t, UpdateMaxNode);
LevelOrderVisit(t, UpdateMaxNode);THANKS