读书人

毗邻法算系统树节点距离求大神们帮忙

发布时间: 2013-04-02 12:35:26 作者: rapoo

邻接法算系统树节点距离,求大神们帮忙
这个是我用的算法
毗邻法算系统树节点距离,求大神们帮忙

我写了第一次循环的过程,准备完成后用for循环或者什么命令循环计算直到最后N-2=0跳出,但是在最后合并时出现了问题。代码中注释掉的那部分有问题?我找不出来啊。
那部分的功能是将AB合并为U,将x和y vector里面的A都替换为U,里面的B都删除,而且B对应的其他两个VECTOR里面的值也要一起删除。因为3个VECTOR没有关联,所以我就很笨的用计数的方式。
求大神们解释,最好能帮忙完成循环实现功能,下面是代码:


// CS614 HW3.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <stdlib.h>
using namespace std;

template <class T>
void print_map (const T& m)
{
T::const_iterator p = m.begin();
for (; p!=m.end(); ++p)
{
cout << (p->first) << " : " << (p->second) << endl;
}
}

int main()
{
string filename, q, tmp;
//cout<<"input filename: ./infNJTree ";
//cin>>filename;
ifstream file("dist.txt"); //(filename.c_str());//直接读dist.txt文件
if(!file)
{
cout<<"Not found!"<<endl;
return 0;
}
double sum =0.0, M, Ms, M1, M2, Dij;
int N;
string dist, node1, node2, U, Ufirst, Usecond;
double distance;
vector <string> count;
vector <string> x; //放横行元素
vector <string> y; //放纵行元素
vector <double> z; //放这两个元素的距离
vector <int> pos1, pos2;
map <string, double> s;

while(getline(file, q))
{
node1 = q.substr(0,q.find_first_of(' '));
node2 = q.substr(q.find_first_of(' ')+1, q.find_last_of(' ')-q.find_first_of(' ')-1);
dist = q.substr(q.find_last_of(' ')+1);
stringstream ss(dist);
ss>>distance;

x.push_back(node1);
y.push_back(node2);
x.push_back(node2);
y.push_back(node1);
z.push_back(distance);
z.push_back(distance);
count.push_back(node1);
count.push_back(node2);
}

sort(count.begin(),count.end());
count.erase( unique(count.begin(), count.end()), count.end());
N=count.size()-2; //计算一共有多少个不重复的元素,求出N
Ms=z[0];
for(int i=0; i<x.size(); i++)
{
for(int j=0; j<x.size();j++)
{
if(x[j] == x[i])
sum = sum +z[j];
}
s.insert(make_pair(x[i], (sum/N)));
sum = 0.0;
}
cout<<"The nodes are: ";
for(int i=0;i<count.size();i++)
{
cout<<count[i]<<" ";
}
cout<<endl;
cout<<"The S values are: "<<endl;
print_map(s);

map<string, double>::iterator it;
for(int i=0; i<z.size();i=i+2)
{
M=z[i] - (s.find(x[i])->second) - (s.find(x[i+1])->second);


if(M<Ms)
{
Dij = z[i];
Ms = M;
Ufirst = x[i];
Usecond = x[i+1];
}
cout<<"M"<<" "<<x[i]<<"-"<<x[i+1]<<" is "<<M<<endl;
}
cout<<"The M value of the smallest pair is: "<<Ms<<endl;
cout<<"The M pair is '"<<Ufirst<<"-"<<Usecond<<"' (always get the first pair)"<<endl;
U = Ufirst+Usecond;
M1 = ((s.find(Ufirst)->second) - (s.find(Usecond)->second))/2 + Dij/2;
M2 = ((s.find(Usecond)->second) - (s.find(Ufirst)->second))/2 + Dij/2;
cout<<"S values of U joins node1 and node2 are: "<<M1<<" "<<M2<<endl;
//到这里第一次计算基本就完成了,下面要开始合并找出的两个元素为U,做为一个新的元素再进行运算
int mm = 0;
for(vector<string>::iterator str = x.begin(); str!=x.end();str++)
{
mm=mm+1;
if(*str == Ufirst)
{
*str = U;
pos1.push_back(mm);
}
else if(*str == Usecond)
{
str = x.erase(str);
pos2.push_back(mm);
str --;
}
else continue;
if(str == x.end())
break;
}
//就是下面这里出问题了,和上面的code是一样的,不明白为什么运行时要报错,貌似是overload
mm=0;
/*for(vector<string>::iterator vir = y.begin(); vir!=y.end(); vir++)
{
mm=mm+1;
if(*vir == Ufirst)
{
*vir = U;
pos1.push_back(mm);
}
else if(*vir == Usecond)
{
vir = y.erase(vir);
vir --;

}
else continue;
if(vir == y.end())
break;
}*/

sort(pos1.begin(),pos1.end());
pos1.erase( unique(pos1.begin(), pos1.end()), pos1.end());
sort(pos2.begin(),pos2.end());
pos2.erase( unique(pos2.begin(), pos2.end()), pos2.end());

for(vector<double>::iterator dou = z.begin(); dou!= z.end(); dou++)
{
if(dou!=z.end())
{
for(int j=0; j<pos1.size(); j++)
z[j] = z[j] - M1;
for(int i=0; i<pos2.size(); i++)
{
z.erase(z.begin()+pos2[i]);
}
}
break;
}

//这里观察3个vector在操作之后的结果

cout<<"--------------------------------------------"<<endl;
cout<<"--------------------------------------------"<<endl;
for(int i=0;i<x.size();i++)
{
cout<<x[i]<<" ";
}
cout<<endl;
cout<<"--------------------------------------------"<<endl;
cout<<"--------------------------------------------"<<endl;
for(int i=0;i<y.size();i++)
{
cout<<y[i]<<" ";
}
cout<<endl;
cout<<"--------------------------------------------"<<endl;
cout<<"---------------------------------------------"<<endl;
for(int i=0;i<z.size();i++)
{
cout<<z[i]<<" ";
}
cout<<endl;
cout<<"----------------------------------------------"<<endl;
cout<<"---------------------------------------------"<<endl;

count.clear();
s.clear();
for(vector<string>::iterator p=x.begin();p!=x.end();++p)


{
count.push_back(*p);
}
sort(count.begin(),count.end());
count.erase( unique(count.begin(), count.end()), count.end());

if(count.size()-2 == 0)
{
cout<<"finished.............."<<endl;
return 0;
}
else N=count.size()-2;
system("pause");
return 0;
}



这里是dist.txt的内容:
A B 5
A C 4
A D 7
A E 6
A F 8
B C 7
B D 10
B E 9
B F 11
C D 7
C E 6
C F 8
D E 5
D F 9
E F 8

谢谢大家! vector iterator c++ 邻接法 neigbhor?joining
[解决办法]
第140行:
vir = y.erase(vir); // vector里第一个元素被删除后,vir重新成为第一个元素
vir --; // vir-- 肯定就要报错了。
[解决办法]
如果删除操作的条件一致,可以,但不建议这样操作。
理由如下:
1, 同时删除3个vector里的某个元素操作肯定是可以,但她们同时删除某个元素的条件是否都一致?
2, 她们删除的是否都是第n(0<= n < x.size())个元素?
3, 效率问题,3个for循环分别做3个删除操作与1个循环做3个删除操作的效率上,如果数据量不是超大影响可忽略。

读书人网 >C++

热点推荐