脱线MIN问题及源代码——Union-Find算法的应用与推广
脱线MIN问题：
指令Insert(i)：把元素i插入集合s中。
指令Extract_min：从集合S中找出最小元并进行删除。
两种指令的简单表示法：用i表示Insert(i)，用E表示Extract_min。
例：7，2，5，9，E，6，E，E，3，E，1，4，E
这种序列满足两个性质：
1）?任一i （1<=i<=n）在序列中最多出现一次（元素之间互不相同）；
2）从左起任意一段中，插入指令条数大于等于E指令条数。（否则无元素可删。）
算法结果：
给定一个Insert与Extract_min的指令序列之后，对在序列中出现的每个i，算法要输出i是被第几条E指令删除的（对于序列中未出现的i，算法应输出相应信息。）
上例中有：1(5), 2(1), 3(4), 4(未被删除)，5(2)，6(3)，7，9与4一样未被删除，8未出现。
脱线MIN算法思路：
算法开始之前，先把所有元素的所属集合名NAME[i]置为0（O(n)）；再扫描指令序列，把由E隔开的每段中的元素组成若干个集合并命名（O(n)）：
e.g.: 1={2,5,7,9}，2={6}，3=null，4={3}，5={1,4}，6=null
用集合名（数字）来表示删除i的E指令序号。
算法从i=1开始逐一检查，找到1所在的元素集合名（5），输出1是被第5条E指令删除的;
输出后用UNION算法把集合5与其后的集合6合并为6：6={1,4}。
下一步看i=2，找到2所在的元素集合名（1），输出2是被第1条E指令删除的;
输出后用UNION算法把集合1与其后的2合并,得到2={2,5,6,7,9}。
其次看i=3，找到3所在的元素集合名（4），输出3是被第4条E指令删除的；
输出后用UNION算法把集合4与其后的集合6合并（此时集合5已经不存在了），得到6={1,3,4}。
i=4时，找到4所在的元素集合名（6），但6>E指令条数（只有5条），故输出“4未被删除”。
i=5时，找到5所在的元素集合名（2），输出5是被第2条E指令删除的；
输出后用UNION算法把集合2与其后的集合3合并，得3={2,5,6,7,9}。
i=6时，找到6所在的元素集合名（3），输出6是被第3条E指令删除的；
输出后用UNION算法把集合3与6合并，得6={1,2,3,4,5,6,7,9}其后的7，9执行Find后均得6，故与4一样未被删除，而8未在序列中出现，因Find(8)=0，故应输出“8未出现”。
为合并时方便地找到后继集合，引入Pred和Succ 2个数组：
Pred[j]记录了前一个集合的名称（数字），初始时为j-1，
Succ[j]记录了后一个集合的名称（数字），初始时为j+1。
?
?
在Union-Find树结构的基础上，解决了脱线MIN问题。考虑了路径压缩。
测试数据：7，2，5，9，E，6，E，E，3，E，1，4，E
运行截图：
输入：
?
输出：
算法：
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))。
因要对合并后的集合（树结构）进行强制命名，故采用可强制命名为k的UNION(i,j,k)算法：
?
数组元素ROOT[i]中存放集合名为i的根结点编号；数组元素COUNT[t]中存放编号t的结点为根的子树中的结点个数；数组元素FATHER [t]中存放编号t的结点的父结点编号；数组元素NAME[t]中存放t结点为根的树所对应的集合名。?
wlg assume COUNT[ROOT[i]]<=COUNT[ROOT[j]]
??(otherwiseinterchange 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 10typedef 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;}//返回节点所在的集合//即返回节点的根节点的nameint 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);}elseprintf("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);}??