`
shinepengwei
  • 浏览: 45614 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

脱线MIN问题及源代码——Union-Find算法的应用与推广

阅读更多

脱线MIN问题:

指令Insert(i):把元素i插入集合s中。

指令Extract_min:从集合S中找出最小元并进行删除。

两种指令的简单表示法:用i表示Insert(i),用E表示Extract_min

例:7259E6EE3E14E

这种序列满足两个性质:

1 任一i (1<=i<=n)在序列中最多出现一次(元素之间互不相同);

2)从左起任意一段中,插入指令条数大于等于E指令条数。(否则无元素可删。)

算法结果:

给定一个InsertExtract_min的指令序列之后,对在序列中出现的每个i,算法要输出i是被第几条E指令删除的(对于序列中未出现的i,算法应输出相应信息。)

上例中有:1(5), 2(1), 3(4), 4(未被删除)5(2)6(3)794一样未被删除,8未出现。


脱线MIN算法思路:

算法开始之前,先把所有元素的所属集合名NAME[i]置为0O(n));再扫描指令序列,把由E隔开的每段中的元素组成若干个集合并命名(O(n)):

e.g.: 1={2,5,7,9}2={6}3=null4={3}5={1,4}6=null

用集合名(数字)来表示删除iE指令序号。

算法从i=1开始逐一检查,找到1所在的元素集合名(5),输出1是被第5E指令删除的;

输出后用UNION算法把集合5与其后的集合6合并为66={1,4}

下一步看i=2,找到2所在的元素集合名(1),输出2是被第1E指令删除的;

输出后用UNION算法把集合1与其后的2合并,得到2={2,5,6,7,9}

其次看i=3,找到3所在的元素集合名(4),输出3是被第4E指令删除的;

输出后用UNION算法把集合4与其后的集合6合并(此时集合5已经不存在了),得到6={1,3,4}

i=4时,找到4所在的元素集合名(6),但6>E指令条数(只有5条),故输出“4未被删除

i=5时,找到5所在的元素集合名(2),输出5是被第2E指令删除的;

输出后用UNION算法把集合2与其后的集合3合并,得3={2,5,6,7,9}

i=6时,找到6所在的元素集合名(3),输出6是被第3E指令删除的;

输出后用UNION算法把集合36合并,得6={1,2,3,4,5,6,7,9}其后的79执行Find后均得6,故与4一样未被删除,而8未在序列中出现,因Find(8)=0,故应输出“8未出现

为合并时方便地找到后继集合,引入PredSucc 2个数组:

Pred[j]记录了前一个集合的名称(数字),初始时为j-1

Succ[j]记录了后一个集合的名称(数字),初始时为j+1

 

 

Union-Find树结构的基础上,解决了脱线MIN问题。考虑了路径压缩。

测试数据:7259E6EE3E14E

运行截图:

输入:



 

输出:


算法:

for i=1 to n do

{

   j←Find(i); /*找到i所属集合名(数字)即删除i的E指令序号*/

   if j=0 then {输出“i未在序列中出现”}

   else if j>k then

    {输出“i未被删除”}

   else    /* i确实被删除了*/

    {

      输出“i是被第j条E指令所删除”;

      UNION(j,Succ[j],Succ[j]);

      Succ[Pred[j]]←Succ[j];/* 集合j不再存在*/

       Pred[Succ[j]]←Pred[j]

    }

}
 

 

算法的主要工作是执行O(n)Find指令,(其余工作在循环的每一轮都是常数时间)故该算法的时间复杂度为O(n*G(n))

因要对合并后的集合(树结构)进行强制命名,故采用可强制命名为kUNION(i,j,k)算法:

 

  • 数组元素ROOT[i]中存放集合名为i的根结点编号;
  • 数组元素COUNT[t]中存放编号t的结点为根的子树中的结点个数;
  • 数组元素FATHER [t]中存放编号t的结点的父结点编号;
  • 数组元素NAME[t]中存放t结点为根的树所对应的集合名。

 

wlg assume COUNT[ROOT[i]]<=COUNT[ROOT[j]]

  (otherwise interchange i and j in the following lines)

LARGE←ROOT[j];

SMALL←ROOT[i];

FATHER[SMALL]←LARGE;

COUNT[LARGE]←COUNT[LARGE]+ COUNT[SMALL];

NAME[LARGE]←k;

ROOT[k]←LARGE

由于该算法不执行Find,故在O(1)时间里即可完成。

 #include <stdio.h>

#include <malloc.h>
#define NUM 10
typedef struct Node//节点
{
	int name;//集合名
	int value;//value,和index数值相同
	int father;//父亲节点
	int rank;//秩
}TreeNode, *BiTree;
typedef struct Sets//集合
{
	int num;//集合的根结点
	int pre;//前面的集合名
	int suc;//后面的集合名
	int used;
}SetNode, *BiSet;
BiTree bt;
BiSet bs;
//创建集合
void creatSet(int assetNum){
	if (assetNum>1)
	{
		bs[assetNum-1].suc=assetNum;
		bs[assetNum].pre=assetNum-1;
	}
	bs[assetNum].used=1;
}
//插入操作
void insert(int i,int assetNum){
	if (bs[assetNum].num == 0)
	{
		bt[i].rank=0;
		bt[i].name=assetNum;
		bs[assetNum].num=i;
	}else{
		bt[bs[assetNum].num].rank=1;
	};
	bt[i].father=bs[assetNum].num;
}
//删除最小操作
int extract_min(int assetNum){
	assetNum++;
	creatSet(assetNum);
	return assetNum;
}
//初始化,输入及构造数据结构
int initializeNode()//返回构造了几个集合树
{
	bs=(BiSet)malloc(NUM*sizeof(SetNode));
	bt=(BiTree)malloc(NUM*sizeof(TreeNode));
	for (int i=0;i<NUM;i++)
	{
		bt[i].name=0;
		bt[i].value=0;
		bt[i].rank=0;
		bt[i].father=0;
		bs[i].pre=0;
		bs[i].suc=0;
		bs[i].num=0;
		bt[i].value=i;
		bs[i].used=0;
	}
	int r=-2;
	int assetNum=1;
	creatSet(assetNum);
	while(r!=-1){
		printf("请输入一个不重复正数字,作为insert操作。或者输入0表示一个extract_min操作,-1表示退出输入");
		scanf("%d",&r);
		if (r>0)
		{
			insert(r,assetNum);
		}
		else if (r==0)
		{
			assetNum=extract_min(assetNum);
		}
	}
	//assetNum=extract_min(assetNum);
	return assetNum;
}
/************************************************************************
找到某个节点的根节点
输入参数:

输出参数:
	index:根结点节点编号
************************************************************************/
int find(int value){
	BiTree t=&bt[value];
	if (t->father!=value)
	{
		t->father=find(bt[bt[value].father].value);
	}
	return t->father;
}
//返回节点所在的集合
//即返回节点的根节点的name
int find_setNum(int value){
	int t=bt[find(value)].name;
	return t;
}
//输入一个集合名,将这个集合和它的下一个集合合并,并命名为下一个集合名
void funion(int setNum){
	int index1=bs[setNum].num;
	int suc=bs[setNum].suc;
	int index2=bs[suc].num;
	if (bt[index1].rank>bt[index2].rank)//当
	{
		bt[index2].father=index1;
		bs[suc].num=index1;
		bt[index1].name=suc;
	}
	else if (bt[index1].rank ==bt[index2].rank)
	{
		bt[index1].father=index2;
		bt[index2].rank++;
	}
	else{
		bt[index1].father=index2;
	}
	bs[setNum].used=0;
	int pre=bs[setNum].pre;
	bs[pre].suc=suc;
	bs[suc].pre=pre;

}
//处理。输出
void deal(int setsCount){
	for (int i=1;i<NUM;i++)
	{
		if (bt[i].father==0)
		{
			printf("%d没有出现在序列中\n",i);
		}
		else{
			int setsNum=find_setNum(i);
			if (setsNum == setsCount)
			{
				printf("%d没有被删除\n",i);
			}
			else if (setsNum <setsCount)
			{
				printf("%d节点被第%d条指令删除\n",i,setsNum);
				funion(setsNum);
			}
			else
				printf("err:根据节点查找到一个错误的集合名\n");
		}
	}
}
void main(){
	//初始化、输入及构造数据结构
	int setsCount=initializeNode();
	//处理
	deal(setsCount);
	//打印
	for (int i=0;i<NUM;i++)
	{
		printf("index/value:%d, ",i);
		printf("name:%d, ",bt[i].name);
		printf("rank:%d, ",bt[i].rank);
		printf("father:%d\n ",bt[i].father);
	}
	printf("asset[name]:index\n");
	for (int i=0;i<NUM;i++)
	{
		printf("set num:%d, ",i);
		printf("use:%d, ",bs[i].used);
		printf("num:%d, ",bs[i].num);
		printf("pre:%d, ",bs[i].pre);
		printf("suc:%d\n",bs[i].suc);
	}
	//等待显示
	printf("\nprint end");
	int i;
	scanf("%d",&i);
}
 

 

  • 大小: 14.8 KB
  • 大小: 16 KB
1
1
分享到:
评论

相关推荐

    电子功用-架空电缆巡线机器人的搭脱线器及方法

    在电子工程领域,架空电缆巡线机器人的研发与应用是一项重要的技术,旨在提升电力设施的维护效率和安全性。本文将深入探讨“电子功用-架空电缆巡线机器人的搭脱线器及方法”这一主题,揭示其中蕴含的关键知识点。 ...

    行业资料-交通装置-一种机车、车辆脱线起复工具.zip

    行业资料-交通装置-一种机车、车辆脱线起复工具.zip

    行业分类-设备装置-一种金属线自动绕线脱线模架.zip

    在IT行业中,设备装置的设计与应用是至关重要的领域,尤其在制造业中,自动化设备的创新对于提高生产效率、降低成本有着显著作用。标题“行业分类-设备装置-一种金属线自动绕线脱线模架.zip”暗示了我们即将讨论的是...

    新前景——CAD基础上的测量软件可以对坐标测量仪进行脱机编程.pdf

    软件还具备模拟运行路径的功能,即可以在CAD模型上动画显示已编程的运行路径,并且能够识别并显示键控器与CAD模型之间的碰撞,从而帮助用户轻松找出并修正问题。 此外,Calypso支持一种特征曲线输入方案,可以从CAD...

    uc3845中文资料应用

    这些集成电路包括振荡器、温度补偿参考源、高增益误差放大器、电流检测比较器及一个适合于驱动MOS功率场效应晶体管(PFET)的理想的高电流图腾柱输出。 芯片还包括一系列保护特性,如具有滞后特性的输入和参考电压欠压...

    让机器人巡线不脱线.pdf

    机器人巡线是自动化领域一项重要的技术,广泛应用于生产线自动化、机器人竞赛以及智能导航等领域。本文档详细介绍了机器人通过颜色传感器沿黑线巡线的原理、遇到的问题以及解决这些问题的方法。 首先,巡线机器人的...

    TOPSwitch器件

    随着技术的进步,一种全新的设计理念——将PWM控制器与MOSFET功率开关集成于单一芯片上的趋势逐渐兴起,这种集成控制芯片成为新一代开关电源设计的重要标志。美国功率集成公司(Power Integrations Inc.)在这一领域...

    unstrip:ELF脱线工具

    ELF脱线工具 要求 顶点python绑定 pyelftools python-sqlite python-msgpack 生成数据库 确保最大文件打开限制&gt; = 65536,因为它将在生成db的过程中打开很多目标文件。 mkdir archobj 复制&lt;your&gt; ex: libc.a, ...

    一种基于TOP202Y的单片开关电源设计说明.doc

    TOPSwitch 系列器件仅用了三个管脚就将脱线式开关电源所必需的具有通态可控栅极驱动电路的高压 N 沟道功率的 MOS 场效应管、电压型 PWM 控制器、100kHz 高频振荡器、高压启动偏置电压、带隙基准、用于环路补偿的并联...

    行业分类-设备装置-切带装置及其应用该切带装置的肩带加工设备.zip

    同时,由于肩带对柔软度和边缘质量的要求较高,因此,切带装置往往需要具备良好的切割精度和边缘处理能力,以防止肩带在使用过程中出现脱线、磨损等问题。 此外,随着科技的发展,智能化和自动化技术也在切带装置上...

    松下伺服电机A5系列故障代码.pdf

    若听到电机有异常声音,可能是电磁制动器存在问题,检查其动作及连接部是否松弛。 当伺服电机出现故障,驱动器会显示错误代码,如控制电源不足(110)、过电压保护(120)、主电源不足电压保护(130)、过电流保护...

    德国自动化公司cts针对造纸行业推出浆板或废纸包自动化脱线技术.pdf

    德国自动化技术公司cts针对造纸行业推出了针对浆板或废纸包的自动化脱线技术,这项技术的核心是使用一种新型高效的自动化机器人解决方案。这种机器人解决方案特别适用于从进料到碎浆机与切碎机的自动化纸浆处理流程...

    电子政务-剑杆织机电动锁边废边装置.zip

    本资料聚焦于一个特定的技术领域——剑杆织机电动锁边废边装置,它在电子政务中扮演着不可或缺的角色。这种装置的应用,不仅提高了纺织行业的生产效率,也为政府的信息化管理提供了新的解决方案。 剑杆织机是一种...

    德国自动化公司cts针对造纸行业推出浆板或废纸包自动化脱线技术.rar

    标题中的“德国自动化公司cts针对造纸行业推出浆板或废纸包自动化脱线技术”指的是CTS(可能是Control Technology & Solutions或其他相关公司)这家德国自动化企业在造纸行业中推出的一项新技术,旨在优化浆板或废纸...

    机器视觉工业应用指南

    机器视觉在现代工业中的应用已经变得日益广泛与深入,尤其在汽车、半导体和食品等行业,其卓越的表现使得生产效率和质量控制达到了前所未有的高度。本文将深入探讨机器视觉在汽车工业中的具体应用案例,旨在为相关...

    daibutsu:8.4.1脱线

    大佛 8.4.1脱网(适用于32位iOS) 开发 覆盖libmis.dylib中的... (源代码仍仅适用于iPhone5,2-12H321) 帮手 用于加载基材。 脱口而出 老式越狱(适用于iPhone5,2-12H321)。 [init] 2021/04/07由dora2ios

    行业文档-设计装置-窗帘收放线装置绕线轮.zip

    本文档将深入探讨窗帘收放线装置的核心组件——绕线轮的设计与应用,旨在为相关领域的专业人士提供详尽的知识点。 1. 绕线轮的基本概念:绕线轮是窗帘收放线装置中的关键机械部件,负责缠绕和释放窗帘线,通过旋转...

    乐高EV3机器人单光循线技术的实现与改进.pdf

    这项研究的目的是解决单光循线技术在实际应用中出现的问题,如循线不稳、脱线、慢速等,进而提高EV3机器人的循线性能和效率。 首先,EV3机器人采用的单光循线技术是基于光电传感器来实现的。光电传感器能检测到光线...

    开关电源开关电源设计

    UC3842是一种高性能的固定频率电流型控制器,专门用于脱线式直流变换电路。其主要特点包括: 1. **可调整振荡器放电电流**:用于产生精确的占空比。 2. **最高开关频率**:可达500kHz,适用于需要较高开关频率的...

Global site tag (gtag.js) - Google Analytics