我使用C++来创建Hopcroft的DFA最小化算法。
Hopcroft算法的一部分是对两个集合(P有接受状态和非接受状态,q只有非接受状态)进行初步划分。我已经有了P组,我试图从P中提取Q值,我使用以下代码来实现它:
for(int i=0; i<groupP.size(); i++)
if(groupP[i]->final)
groupQ.push_back(groupP[i]);
其中groupP和groupQ是:
vector<node*> groupQ;
vector<node*> groupP;
节点是我为表示自动机的一个节点而创建的一个结构。它保证布尔属性" final“已经正确设置(非最终状态为false,最终状态为true )。
最后,我的问题是:通过执行我所做的工作,将一个元素从一个向量复制到另一个元素是否正确?如果我从groupP修改复制的元素的内容,这个元素也会在groupQ中被修改吗?
发布于 2015-05-29 13:40:30
现在,你有指针的向量。当您从一个向量复制到另一个向量时,您复制的是指针,而不是元素本身。
由于您有两个指向同一个节点的指针,对一个节点所做的任何修改都将在另一个组中可见--也就是说,如果您更改了groupP[i]->foo
,那么相同的更改将在groupQ[j]->foo
中可见(前提是groupP[i]
是从groupP
复制到groupQ
的元素之一)。
如果你不想那样,你有几个选择。一种方法是将groupP
和groupQ
保留在同一个向量中,但是根据元素的final
成员的状态对该向量进行分区:
auto P_end = std::partition(groupP.begin(), groupQ.end(),
[](node *n) { return n->final;});
然后[groupP.begin(),P_begin)是groupP (即final==true
),而[P_begin,groupP.end()]是groupQ (即final==false
)。
这会移动指针(并给出一个迭代器,使您知道这两个元素之间的分界线),因此您有一个指向每个元素的指针,但是它们被分离成两个相关的组。
最后一种可能是,您可能希望将元素从groupP
实际复制到groupQ
,并且在此过程中创建一个新元素,因此在您将项目从groupP
复制到groupQ
之后,您复制的每个项目现在在两个位置存在--即groupP
中有一个元素,groupQ
中有一个元素。任何一个都可以修改,但它们是分开的,所以两者都可以修改,但是对其中一个的修改对另一个没有影响。
要做到这一点,最明显的方法是只使用节点的向量:
vector<node> groupQ;
vector<node> groupP;
这样,当您从一个组复制到另一个组时,您将复制节点本身,而不是指向节点的指针,因此每个副本创建一个新的独立节点,其值与现有节点的值相同。
https://stackoverflow.com/questions/30538803
复制相似问题