3.21Code
基于二叉链表的二叉树最大宽度的计算
#include<iostream>#define MAXSIZE 1000using namespace std;int k=0;
int m=0; //记录层数 typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;m++; T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;m++;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void Traverse(BiTree T,int n[]){if(T){//k代表当前遍历到的层数! k++;n[k]++;Traverse(T->lchild,n);Traverse(T->rchild,n);k--;}
}void Width(int n[]){int max=n[1];for(int i=2;i<=m;i++)if(max<n[i])max=n[i];cout<<max<<endl;
} int main(){while(true){char ch;int n[100]={0};cin>>ch;if(ch=='0')break;BiTree T;CreateBiTree(T,ch);Traverse(T,n);Width(n); }return 0;
}
【思路】每创建一个结点,m++,m维护节点数。
遍历的时候,每进入一层,k++,n[k]++,k维护层数。注意在找完左右子树时,要k--,方便向上层递归
n[i]代表第i个结点对应层的结点个数
最后遍历n数组,找到最大值即可
基于二叉链表的二叉树叶子结点到根结点的路径的求解
#include<iostream>#define MAXSIZE 1000using namespace std;int maxi=0;
int m=0,n=0;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;m++; T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;m++;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void Traverse(BiTree T){if(T){m++;Traverse(T->lchild);Traverse(T->rchild);m--;}
}void FindRoad(BiTree T,char path[],int pathlen){if(T){if(T->lchild==NULL && T->rchild==NULL){//叶子节点cout<<T->data;for(int i=pathlen-1;i>=0;i--) cout<<path[i];cout<<endl;}else{path[pathlen]=T->data;pathlen++;FindRoad(T->lchild,path,pathlen);FindRoad(T->rchild,path,pathlen);pathlen--; //很重要 }}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch); Traverse(T);FindRoad(T,path,pathlen);m=0;}return 0;
}
【思路】重点在于FindRoad函数,参数是path数组和当前path数组应储存的下标
遇到叶子结点时输出整个数组内容,否则存入当前结点名称,进入左右孩子的递归
由以上两题,注意形参是数组时,可以写成int n[ ]的形式
基于二叉链表的二叉树的遍历
#include<iostream>#define MAXSIZE 1000using namespace std;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T){if(T){cout<<T->data;PreTraverse(T->lchild);PreTraverse(T->rchild);}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch); PreTraverse(T);cout<<endl;MidTraverse(T);cout<<endl;LastTraverse(T);cout<<endl;}return 0;
}
基于二叉链表的二叉树结点个数的统计
#include<iostream>#define MAXSIZE 1000using namespace std;int n0=0,n1=0,n2=0;typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T){if(T){if(T->lchild && T->rchild)n2++;else if(T->lchild && !T->rchild)n1++;else if(!T->lchild && T->rchild)n1++;else n0++;PreTraverse(T->lchild);PreTraverse(T->rchild);}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch); PreTraverse(T);cout<<n0<<" "<<n1<<" "<<n2<<endl;n0=n1=n2=0;}return 0;
}
基于二叉链表的二叉树高度的计算
#include<iostream>#define MAXSIZE 1000using namespace std;int maxd=0;
typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild;
}BiNode,*BiTree;void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void CreateBiTree(BiTree &T,char ch){if(ch=='0')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }
}void PreTraverse(BiTree T,int &nowd){if(T){nowd++;maxd=max(nowd,maxd);PreTraverse(T->lchild,nowd);PreTraverse(T->rchild,nowd);nowd--;}
}void MidTraverse(BiTree T){if(T){MidTraverse(T->lchild);cout<<T->data;MidTraverse(T->rchild);}
}void LastTraverse(BiTree T){if(T){LastTraverse(T->lchild);LastTraverse(T->rchild);cout<<T->data;}
}int main(){while(true){char ch;cin>>ch;char path[100];int pathlen=0;if(ch=='0')break;BiTree T;CreateBiTree(T,ch); int d=0; PreTraverse(T,d);cout<<maxd<<endl;maxd=0;}return 0;
}
【注意】最大高度应该用一个全局变量来维护,而每次遍历到的深度则用临时变量来存储和递归传参,在递归前nowd++了,在这一层最终还要nowd--,以便向上回溯!
————————————华丽的分界线————————————————
————————以下是图及应用相关习题————————————————
基于Dijsktra算法的最短路径求解
【Dijkstra算法】
#include <iostream>
#include <cstring>
#define MVNum 100
#define MaxInt 999
using namespace std;typedef struct
{char vexs[MVNum];//点集 int arcs[MVNum][MVNum];//边的邻接矩阵 int vexnum,arcnum;//点数&边数
}AMGraph;int LocateVex(AMGraph G,char u){//存在则返回u在顶点表中的下标;否则返回-1int i;for(i=0;i<G.vexnum;++i)if(u==G.vexs[i])return i;return -1;}void InitAM(AMGraph &G)
{//初始化图 memset(G.vexs,0,sizeof(G.vexs));//初始化顶点集 for(int i=0;i<MVNum;i++)for(int j=0;j<MVNum;j++)G.arcs[i][j]=MaxInt;return;
}void CreateUDN(AMGraph &G)
{int i,j,k; //G.vexnum++;for(i=0;i<G.vexnum;i++)cin>>G.vexs[i];for(k=0;k<G.arcnum;k++)//将边录入邻接矩阵,顺便将顶点录入 {char v1,v2;int w;cin>>v1>>v2>>w;//边的端点i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];G.arcs[i][j]=w;G.arcs[k][k]=0;}
}void ShortestPath_DIJ(AMGraph G){ //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 char v0,v1;int S[MVNum];int D[MVNum];int Path[MVNum];cin>>v0>>v1;int v00=LocateVex(G,v0);int n=G.vexnum; int v; //n为G中顶点的个数 for( v = 0; v<n; ++v){ //n个顶点依次初始化 S[v] = false; //S初始为空集 D[v] = G.arcs[v00][v]; //将v0到各个终点的最短路径长度初始化 if(D[v]< MaxInt) Path [v]=v00; //v0和v之间有弧,将v的前驱置为v0 else Path [v]=-1; //如果v0和v之间无弧,则将v的前驱置为-1 }//for S[v00]=true; //将v0加入S D[v00]=0; int w; int i; //源点到源点的距离为0
/*―开始主循环,每次求得v0到某个顶点v的最短路径,将v加到S集―*/ for(i=1;i<n; ++i){ //对其余n?1个顶点,依次进行计算 int min= MaxInt; for(w=0;w<n; ++w) if(!S[w]&&D[w]<min) {v=w; min=D[w];} //选择一条当前的最短路径,终点为v S[v]=true; //将v加入S for(w=0;w<n; ++w) //更新从v0出发到集合V?S上所有顶点的最短路径长度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path [w]=v; //更改w的前驱为v }//if }//for w=LocateVex(G,v1);cout<<D[w]<<endl; char road[G.vexnum];road[0]=G.vexs[w];int t=w;i=0;while(1){ i++;if(t==-1||t==v00)break;road[i]=G.vexs[Path[t]];t=Path[t]; }while(i){if(road[i])cout<<road[i]<<" ";i--;} cout<<road[0];cout<<endl;
}int main()
{ while(1){AMGraph G;InitAM(G);cin>>G.vexnum>>G.arcnum;if(G.vexnum==0&&G.arcnum==0)break;CreateUDN(G);ShortestPath_DIJ(G);}
}
相关文章:
3.21Code
基于二叉链表的二叉树最大宽度的计算 #include<iostream>#define MAXSIZE 1000using namespace std;int k0; int m0; //记录层数 typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree;void CreateBiTree(BiTree &T){cha…...

学习总结2
解题思路 用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出. 代码 #include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #in…...

【LeetCode】--- 动态规划 集训(一)
目录 一、1137. 第 N 个泰波那契数1.1 题目解析1.2 状态转移方程1.3 解题代码 二、面试题 08.01. 三步问题2.1 题目解析2.2 状态转移方程2.3 解题代码 三、746. 使用最小花费爬楼梯3.1 题目解析3.2 状态转移方程3.3 解题代码 一、1137. 第 N 个泰波那契数 题目地址:…...
【数据结构与算法】(18):树形选择排序:按照锦标赛的思想进行排序
🤡博客主页:Code_文晓 🥰本文专栏:数据结构与算法 😻欢迎关注:感谢大家的点赞评论关注,祝您学有所成! ✨✨💜💛想要学习更多数据结构与算法点击专栏链接查看&…...
统计单词数
统计单词数 题目描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。 现在,请你编程实现这一功能,具体要求是:给定一个单词࿰…...
c++pair的用法
pair简单来说就是可以存储两种类型数据的一个类,其内部是使用模板实现的,所以可以指定其内部的类型。 pair在#include <utility> pair的构造 pair<int, string> p1({ 1,"张三" });pair<int, string> p2;pair<int, str…...

石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型
石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型。在石油炼化行业,5G智能制造工厂数字孪生可视化平台的出现,为行业的数字化转型注入了新的活力。石油炼化行业作为传统工业的重要领域,面临着资源紧张、环境压力、安…...

IP代理技术革新:探索数据采集的新路径
引言: 随着全球化进程不断加深,网络数据采集在企业决策和市场分析中扮演着愈发重要的角色。然而,地域限制和IP封锁等问题常常给数据采集工作带来了巨大挑战。亿牛云代理服务凭借其强大的网络覆盖和真实住宅IP资源,成为解决这些问…...

流畅的 Python 第二版(GPT 重译)(一)
前言 计划是这样的:当有人使用你不理解的特性时,直接开枪打死他们。这比学习新东西要容易得多,不久之后,活下来的程序员只会用一个容易理解的、微小的 Python 0.9.6 子集来编写代码 。 Tim Peters,传奇的核心开发者&am…...

Vue+jquery+jquery.maphilight实现图片热区高亮以及点击效果
//鼠标悬浮效果 mounted() {this.setCurrentTask(0); //对于id为mapAll的热区图,设置鼠标放置在上面有一个颜色 fillColor填充颜色 strokeColor边框颜色 strokeWidth边框宽度 fillOpacity 是设置热区填充颜色的不透明度的属性。 alwaysOn:true 保持常量$(function(…...

靠谱!朋友圈一键转发和自动转发好友朋友圈
微信朋友圈在生活和工作中扮演着重要的社交和信息传播角色。尤其是对于一些企业来说,朋友圈是不可或缺的推广渠道。 今天就给大家分享一个能够实现一键转发和自动转发好友朋友圈的工具——微信管理系统,让大家都能有效的管理朋友圈。 1、定时发圈&…...

线性顺序表算法库
list.cpp 具体函数实现 #include <stdio.h> #include "list.h" #include <malloc.h>/************************************************** ①函数名: CreateList 功 能: 用数组构建顺序表 参 数: ①SqList *&L:传入的线性表 ②ElemType a[]:使用…...

java分割等和子集(力扣Leetcode416)
分割等和子集 力扣原题链接 给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] …...
383. 赎金信
给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 func canConstruct(ransomNote …...

【二】【单片机】有关独立按键的实验
自定义延时函数Delay 分别用Delay.c文件存储Delay函数。用Delay.h声明Delay函数。每次将这两个文件复制到工程中,直接使用。 //Delay.c void Delay(unsigned int xms) //11.0592MHz {while(xms--){unsigned char i, j;i 2;j 199;do{while (--j);}…...

AJAX踩坑指南(知识点补充)
JWT JSON Web Token是目前最为流行的跨域认证解决方案 如何获取:在使用JWT身份验证中,当用户使用其凭据成功登录时,将返回JSON Web Token(令牌) Token本质就是一个包含了信息的字符串 如何获取Token:登录成功之后,服务…...
备战蓝桥杯Day29 - 拼接最大数字问题
问题描述 有n个非负整数,将其按照字符串拼接的方式拼接为一个整数如何拼接可以使得得到的整数最大? 例: 32,94,128,1286,6,71可以拼接除的最大整数为 94716321286128。 问题思路 1.比较两个字符串的第一个数字,数值大的在前面,数值小的在…...

基于springboot的mysql实现读写分离
前言: 首先思考一个问题:在高并发的场景中,关于数据库都有哪些优化的手段?常用的有以下的实现方法:读写分离、加缓存、主从架构集群、分库分表等,在互联网应用中,大部分都是读多写少的场景,设置两个库,主库和读库,主库的职能是负责写,从库主要是负责读…...

Python爬虫之Scrapy框架系列(24)——分布式爬虫scrapy_redis完整实战【XXTop250完整爬取】
目录: 每篇前言:1.使用分布式爬取豆瓣电影信息(1)settings.py文件中的配置:(2)spider文件的更改:(3)items.py文件(两个项目一致!&…...

提升效率,稳定可靠:亚信安慧AntDB的企业价值
亚信安慧AntDB分布式数据库凭借平滑扩展、高可用性和低成本三大核心优势,在业界获得了极高的评价和认可。这些优点不仅为AntDB提供了巨大的市场发展潜力,也使其成为众多企业在数据管理上的首选解决方案。 AntDB的平滑扩展特性极大地提升了企业的灵活性和…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙
WebGL:在浏览器中解锁3D世界的魔法钥匙 引言:网页的边界正在消失 在数字化浪潮的推动下,网页早已不再是静态信息的展示窗口。如今,我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室,甚至沉浸式的V…...

goreplay
1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具,可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长,测试它所需的工作量也会呈指数级增长。GoRepl…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学
一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件,其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时,价带电子受激发跃迁至导带,形成电子-空穴对,导致材料电导率显著提升。…...