📄 mstscr.cpp
字号:
{
CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
if(ptrSet_C_Locate->UniteSort){
jcount = icount+1;
BOOL UnintOK = FALSE;
while(jcount < Set_C_Array.GetSize() )
{
CStruct_C * ptrSet_C_tmp=(CStruct_C *)Set_C_Array.GetAt(jcount);
if(ptrSet_C_tmp->UniteSort)
{
if( ptrSet_C_Locate->UniteSet( * ptrSet_C_tmp) )
{
Set_C_Array.RemoveAt(jcount);
UnintOK = TRUE;
break;
}else jcount++;
}else jcount++;
}
if( !UnintOK ) icount++;
}else icount++;
}
icount=0;
while(icount <Set_C_Array.GetSize()){
CStruct_C * ptrSet_C_Locate=(CStruct_C *)Set_C_Array.GetAt(icount);
if(ptrSet_C_Locate->UniteSort){
jcount=0;
while(jcount<Set_C_Array.GetSize()){
CStruct_C * ptrSet_C_tmp = (CStruct_C *)Set_C_Array.GetAt(jcount);
if( !ptrSet_C_tmp->UniteSort ){
if( ptrSet_C_tmp->UniteSet1(* ptrSet_C_Locate )){
Set_C_Array.RemoveAt(icount);
break;
}else jcount++;
}else jcount++;
}
if(jcount == Set_C_Array.GetSize()) icount ++;
}else icount++;
if( icount == Set_C_Array.GetSize() )
{
BOOL find_Not_Unite=FALSE;
for(index=0;index<Set_C_Array.GetSize();index++){
if( ((CStruct_C *)Set_C_Array.GetAt(index))->UniteSort ){
find_Not_Unite = TRUE; icount = index; break;
}
}
}
}
}
CStruct_C * ptrOK=(CStruct_C *)Set_C_Array.GetAt( 0 );
for(icount=0; icount<ptrOK->BorderArray.GetSize(); icount++)
{
int isTreeIndex=ptrOK->BorderArray.GetAt(icount);
((CPointCouple *)pointCoupleArray.GetAt(isTreeIndex))->isTree=TRUE;
}
for(icount=0; icount<pointCoupleArray.GetSize();icount++)
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(icount);
if(ptrCouple->isTree)
{
structPot * ptrCurPot;
ptrCurPot=(structPot *)PointArray.GetAt(ptrCouple->indexpoint1);
for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
{
border Border=ptrCurPot->neighborhood.GetAt(jcount);
if( Border.index == ptrCouple->indexpoint2 )
{
Border.isTree=TRUE;
ptrCurPot->neighborhood.SetAt(jcount,Border);
}
}
ptrCurPot=(structPot *)PointArray.GetAt(ptrCouple->indexpoint2);
for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
{
border Border=ptrCurPot->neighborhood.GetAt(jcount);
if( Border.index == ptrCouple->indexpoint1 )
{
Border.isTree=TRUE;
ptrCurPot->neighborhood.SetAt(jcount,Border);
}
}
}
}
do{
if(pointCoupleArray.GetSize())
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
pointCoupleArray.RemoveAt(0);
delete ptrCouple;
ptrCouple=NULL;
}else break;
}while(1);
do{
if(Set_C_Array.GetSize())
{
CStruct_C * ptrPot=(CStruct_C *)Set_C_Array.GetAt(0);
Set_C_Array.RemoveAt(0);
delete ptrPot;
ptrPot=NULL;
}else break;
}while(1);
Invalidate();
}
void CMSTScr::WorkMST1()
{
if( !PointArray.GetSize() ) return; //网络图中没有顶点
int icount=0,jcount=0,index=0;
//构造点对集合pointCoupleArray，包含点对的两个点和权重
CPtrArray pointCoupleArray;
for(icount=0;icount<PointArray.GetSize();icount++)
{
structPot *ptrPot=(structPot *)PointArray.GetAt(icount);
if( ! ptrPot->neighborhood.GetSize() )
{
MessageBox("网络中存在孤立点！","Input Error!",MB_OK|MB_ICONINFORMATION);
do{
if(pointCoupleArray.GetSize())
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
pointCoupleArray.RemoveAt(0);
delete ptrCouple;
ptrCouple=NULL;
}else break;
}while(1);
return;
}
for(jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++){
//icount当前顶点的索引，
//ptrPot->neighborhood.GetAt(jcount).index,从当前节点出发的边的另一个顶点的索引
CPointCouple * ptrCouple=new CPointCouple(icount,
ptrPot->neighborhood.GetAt(jcount).index,ptrPot->neighborhood.GetAt(jcount).value);
for(index=0; index<pointCoupleArray.GetSize(); index++ )
if( ( * ( (CPointCouple *)pointCoupleArray.GetAt(index) ) ) == ( * ptrCouple) ) break;
if( index == pointCoupleArray.GetSize() ) pointCoupleArray.Add(ptrCouple);
else delete ptrCouple;
}
}
UndoTree();
//构造集合U，包含最小支撑树的节点。初始化时只包含节点1
CPtrArray Pot_Array;
Pot * ptrPot=new Pot(0,-1);
Pot_Array.Add(ptrPot);
for(icount=1; icount<PointArray.GetSize(); icount++)
{
ptrPot=new Pot(icount,0);
Pot_Array.Add(ptrPot);
}
//程序主体。判断当U==V时，循环推出。
do{
int min=-1,minInVindex=-1,minIntreeindex=-1;
index=0;//循环索引
int numindex=0; //计数索引；
do{
if( ( (Pot *)Pot_Array.GetAt(index) )->NearDistance != -1 )//判断当前点是否属于V－U
{
//构造点对
Pot * tmpPot=(Pot *)Pot_Array.GetAt(index);
CPointCouple pointcouple(tmpPot->index,tmpPot->NearDistance,-1);
//带入到点对集合pointCoupleArray中进行查找。
//如果找到该点，则minIntreeindex参数返回该点在点对集合中的位置。
int Intreeindex=0;
int retValue=ComparePointCouple(pointCoupleArray,pointcouple,Intreeindex);
if( retValue != -1 )//网络中存在该点对
{
if(min == -1){ min = retValue; minInVindex = index; minIntreeindex = Intreeindex; }
else if( min > retValue && min != -1 )
{ min = retValue; minInVindex = index; minIntreeindex = Intreeindex; }
}
}
else numindex++;
index++;
}while( index < Pot_Array.GetSize() );
if( numindex == Pot_Array.GetSize() ) break;//表示所有的点都加入到了U集合。
( (Pot *)Pot_Array.GetAt(minInVindex) )->NearDistance=-1;
(*( (CPointCouple* )pointCoupleArray.GetAt(minIntreeindex))).isTree=TRUE;
index=0;
do{ //minInVindex
if( ( (Pot *)Pot_Array.GetAt(index) )->NearDistance != -1 )//判断当前点是否属于V－U
{
int findindex1=0,findindex2=0;
Pot * tmpPot=(Pot *)Pot_Array.GetAt(index);
CPointCouple pointcouple1(tmpPot->index,tmpPot->NearDistance,-1);
CPointCouple pointcouple2(tmpPot->index,minInVindex,-1);
int retValue1=ComparePointCouple(pointCoupleArray,pointcouple1,findindex1);
int retValue2=ComparePointCouple(pointCoupleArray,pointcouple2,findindex2);
if( retValue2 != -1 )
if( retValue1 ==-1 || retValue2 < retValue1 )
tmpPot->NearDistance = minInVindex;
}
index++;
}while( index < Pot_Array.GetSize() );
}while(1);
for(icount=0; icount<pointCoupleArray.GetSize();icount++)
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(icount);
if(ptrCouple->isTree)
{
structPot * ptrCurPot;
ptrCurPot=(structPot *)PointArray.GetAt(ptrCouple->indexpoint1);
for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
{
border Border=ptrCurPot->neighborhood.GetAt(jcount);
if( Border.index == ptrCouple->indexpoint2 )
{
Border.isTree=TRUE;
ptrCurPot->neighborhood.SetAt(jcount,Border);
}
}
ptrCurPot=(structPot *)PointArray.GetAt(ptrCouple->indexpoint2);
for( jcount=0; jcount < ptrCurPot->neighborhood.GetSize(); jcount++)
{
border Border=ptrCurPot->neighborhood.GetAt(jcount);
if( Border.index == ptrCouple->indexpoint1 )
{
Border.isTree=TRUE;
ptrCurPot->neighborhood.SetAt(jcount,Border);
}
}
}
}
//结束释放内存。
do{
if(pointCoupleArray.GetSize())
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
pointCoupleArray.RemoveAt(0);
delete ptrCouple;
ptrCouple=NULL;
}else break;
}while(1);
do{
if(Pot_Array.GetSize())
{
Pot * ptrPot=(Pot *)Pot_Array.GetAt(0);
Pot_Array.RemoveAt(0);
delete ptrPot;
ptrPot=NULL;
}else break;
}while(1);
Invalidate();
}
int CMSTScr::ComparePointCouple(CPtrArray & ptrArray,CPointCouple & pointcouple,int & findIndex)
{
int retValue=0;
for(int icount=0;icount<ptrArray.GetSize();icount++)//在网络中寻找该点对
{
CPointCouple Couple= * ( (CPointCouple* )ptrArray.GetAt(icount));
int valueCouple = Couple.Compare(pointcouple);
if( valueCouple != -1){
retValue = valueCouple;
findIndex = icount;
break;
}
}
if( icount != ptrArray.GetSize() ) return retValue;//找到了，返回权值。
else return -1;//没有找到
}
void CMSTScr::UndoTree()
{
int icount=0,jcount=0;
for(icount=0;icount<PointArray.GetSize();icount++){
structPot *ptrPot=(structPot *)PointArray.GetAt(icount);
for(jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++){
//icount当前顶点的索引，
//ptrPot->neighborhood.GetAt(jcount).index,从当前节点出发的边的另一个顶点的索引
border Border=ptrPot->neighborhood.GetAt(jcount);
if(Border.isTree)
{
Border.isTree=FALSE;
ptrPot->neighborhood.SetAt(jcount,Border);
}
}
}
}
void CMSTScr::ClearPanel()
{
do{
if(PointArray.GetSize())
{
structPot * ptrPot=(structPot *)PointArray.GetAt(0);
PointArray.RemoveAt(0);
delete ptrPot;
ptrPot=NULL;
}else break;
}while(1);
ReDraw = true;
Invalidate();
}
void CMSTScr::WorkStep1()
{
AfxBeginThread(Step1_Proc,this);
}
void CMSTScr::WorkStep2()
{
AfxBeginThread(Step2_Proc,this);
}
UINT Step2_Proc( LPVOID pParam )
{
CMSTScr * ptrView=(CMSTScr *)pParam;
if( !ptrView->PointArray.GetSize() ) return 0; //网络图中没有顶点
int icount=0,jcount=0,index=0;
//构造点对集合pointCoupleArray，包含点对的两个点和权重
CPtrArray pointCoupleArray;
CPtrArray Set_C_Array;
for(icount=0;icount<ptrView->PointArray.GetSize();icount++)
{
CStruct_C * ptrSet_C=new CStruct_C;
ptrSet_C->PotArray.Add(icount);
Set_C_Array.Add(ptrSet_C);
structPot *ptrPot=(structPot *)ptrView->PointArray.GetAt(icount);
if( ! ptrPot->neighborhood.GetSize() )
{
ptrView->MessageBox("网络中存在孤立点！","Input Error!",MB_OK|MB_ICONINFORMATION);
do{
if(pointCoupleArray.GetSize())
{
CPointCouple * ptrCouple=(CPointCouple *)pointCoupleArray.GetAt(0);
pointCoupleArray.RemoveAt(0);
delete ptrCouple;
ptrCouple=NULL;
}else break;
}while(1);
do{
if(Set_C_Array.GetSize())
{
CStruct_C * ptrPot=(CStruct_C *)Set_C_Array.GetAt(0);
Set_C_Array.RemoveAt(0);
delete ptrPot;
ptrPot=NULL;
}else break;
}while(1);
return 0;
}
for(jcount=0;jcount<ptrPot->neighborhood.GetSize();jcount++){
//icount当前顶点的索引，
//ptrPot->neighborhood.GetAt(jcount).index,从当前节点出发的边的另一个顶点的索引
CPointCouple * ptrCouple=new CPointCouple(icount,
ptrPot->neighborhood.GetAt(jcount).index,ptrPot->neighborhood.GetAt(jcount).value);
for(index=0; index<pointCoupleArray.GetSize(); index++ )
if( ( * ( (CPointCouple *)pointCoupleArray.GetAt(index) ) ) == ( * ptrCouple) ) break;
if( index == pointCoupleArray.GetSize() ) pointCoupleArray.Add(ptrCouple);
else delete ptrCouple;
}
}
if( ! ptrView->PointArray.GetSize() ) return 0;//网络图中没有边
ptrView->UndoTree();
while( Set_C_Array.GetSize() > 1 )
{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -