hopcroft法的复杂度，他们说是nlogn，可是都没有严格的证明。难得找到一篇讲的详细点的论文，却又啰里啰唆的，不过那篇论文里面采用的是颜色树这个结构，有点意思。
前面的那个算法是n的平方复杂度，虽然这个复杂度计算都是建立在一些操作为单位时间操作的基础上。可是这些被认为的单位时间操作在我的实现中却有着平方复杂度，情何以堪，万恶的理论计算机科学家。
hopcroft实现的代码，太长了，还没写完。不过核心的子集分割已经完成了，剩下的就是分配节点及重新构建邻接表。明天再说吧。
#include "dfa_to_dfa.h"
pdfa_edge* rev_dfa_table;//作为dfa的反转表
int* belong_to;//这个是用来标记每个节点所在的群的标号
int** group_table;//这个是用来串联所有的群
int group_index;//这个用来表明使用了多少号的群
typedef struct _group_list
//这个结构用来把所有的当前在使用的群的标号串联起来
//这样就可以用来替代掉栈，而且也有利于遍历
{
struct _group_list* next;
int group_number;
}group_list,*pgroup_list;
pgroup_list group_list_begin=NULL;//这个是链表的专用头节点
void insert_group(int in_group_number)//将一个新的群号加入到群列表中，这里默认已经经过参数检查了
{
pgroup_list temp_list;
temp_list=malloc(sizeof(struct _group_list));
temp_list->group_number=in_group_number;
temp_list->next=group_list_begin->next;
group_list_begin->next=temp_list;
} void reverse_dfa(void)//构建反转表
{
int for_travel;//遍历变量
pdfa_edge temp_add;//作为反转表的增加边的变量
pdfa_edge temp_travel;//用来遍历原来的dfa表的邻接表的变量
int temp_dest;//增加边用的临时起始编号
rev_dfa_table=malloc(sizeof(struct _dfa_edge)*(dfa_node_number+));//分配表的内存，注意加1
for(for_travel=;for_travel<=dfa_node_number;for_travel++)
{
rev_dfa_table[for_travel]=NULL;//初始化为空
}
for(for_travel=;for_travel<=dfa_node_number;for_travel++)
{
temp_travel=current_dfa_table[for_travel].begin;
while(temp_travel!=NULL)
{
temp_add=malloc(sizeof(struct _dfa_edge));
temp_add->destination_number=for_travel;
temp_add->label=temp_travel->label;
temp_dest=temp_travel->destination_number;
temp_add->next=rev_dfa_table[temp_dest];
rev_dfa_table[temp_dest]=temp_add;
}
}//现在已经完全构建好了反转表
} typedef struct _rev_hash
{
int in_use;//0表示未使用，1表示正在使用，2表示已经删除
char* name;
int dfa_group_index;
}rev_hash;
rev_hash rev_hash_table[];
int insert_rev_hash(char* input_name，int dfa_group_pointer)//插入hash表
{
int for_i;
unsigned int result;
int counter;
int byte_of_table;
char* hash_name;
byte_of_table=(dfa_node_number+)/;
result=;
for(for_i=;for_i<byte_of_table;for_i++)
{
result+=(unsigned int) input_name[for_i];
}
result=result%;
counter=;
while(counter<)
{
if(rev_hash_table[result].in_use!=)
{
rev_hash_table[result].dfa_group_index=dfa_group_pointer;
rev_hash_table[result].in_use=;
hash_name=malloc(sizeof(char)*(byte_of_table+));
for(for_i=;for_i<byte_of_table;for_i++)
{
hash_name[for_i]=input_name[for_i];
}
hash_name[for_i]='\0';
rev_hash_table[result].name=hash_name;
return result;
}
result=(result+)%;
counter++;
}
return -;
}
int search_rev_hash(char* input_name)//根据名字来搜索hash表，如果存在则返回群标号
{
int for_i;
unsigned int result;
int counter;
int byte_of_table;
char* hash_name;
int compare_result;
byte_of_table=(dfa_node_number+)/;
result=;
for(for_i=;for_i<byte_of_table;for_i++)
{
result+=(unsigned int) input_name[for_i];
}
result=result%;
counter=;
while(counter<)
{
if(rev_hash_table[result].in_use==)
{
compare_result=;
for(for_i=;for_i<byte_of_bitmap;for_i++)
{
compare_result+=!((rev_hash_table[result].name)[for_i]==input_name[for_i]);
}
if(compare_result==)
{
return rev_hash_table[result].dfa_group_index;
}
else
{
result=(result+)%;
counter++;
}
}
else
{
if(rev_hash_table[result].in_use==)
{
result=(result+)%;
counter++;
}
else
{
return -;
}
}
}
return -;
} void map_name(char* output,int group_number)//将一个群转换为字符串
{
int for_i,for_j;
for(for_i=;for_i<=(dfa_node_number+)/;for_i++)
{
output[for_i]='\0';
}
for(for_i=;for_i<dfa_node_number;for_i++)
{
if(*(*(group_table+group_number)+for_i)==)
{
output[(for_i+)/]=BYTE_MASK>>(for_i%)|output[(for_i+)/];
}
}
}
void delete_rev_hash(char* input_name)//从hash表中删除一个节点
{
int for_i;
unsigned int result;
int counter;
int byte_of_table;
char* hash_name;
int compare_result;
byte_of_table=(dfa_node_number+)/;
result=;
for(for_i=;for_i<byte_of_table;for_i++)
{
result+=(unsigned int) input_name[for_i];
}
result=result%;
counter=;
while(counter<)
{
if(rev_hash_table[result].in_use==)
{
compare_result=;
for(for_i=;for_i<byte_of_bitmap;for_i++)
{
compare_result+=!((rev_hash_table[result].name)[for_i]==input_name[for_i]);
}
if(compare_result==)
{
rev_hash_table[result].in_use=;
}
else
{
result=(result+)%;
counter++;
}
}
else
{
if(rev_hash_table[result].in_use==)
{
result=(result+)%;
counter++;
}
}
}
} char* group_transition(int group_number,char input_label)//处理一个群在一个字母上的转移,结果以一个字符串来表示
{
char* result_return;
int for_i,for_j,for_k;
int temp_destination;
pdfa_edge temp_edge;
result_return=malloc(sizeof(char)*((dfa_node_number+)/+));
for(for_i=;for_i<=(dfa_node_number+)/;for_i++)
{
result_return[for_i]='\0';
}
for(for_i=;for_i<dfa_node_number;for_i++)
{
if(*(*(group_table+group_number)+for_i)==)
{
temp_edge=current_dfa_table[for_i+].begin;
while((temp!=NULL)&&(temp->label!=input_label))
{
temp=temp->next;
}
if(temp!=NULL)
{
temp_destination=temp->destination_number;
temp_destination--;//注意这里要减1
result_return[(temp_destination+)/]=result_return[(temp_destination+)/]|BYTE_MASK>>(temp_destination%);
}
}
}
return result_return;
} void intersect_group(int dest_group,int origin_group,char in_label)
{
int for_i,for_j,for_k;
char* dest;//最后用来注册hash表的名字
int* dest_number;//用来表示哪些是目标地址
pdfa_edge temp_edge;//用来遍历邻接表
int temp_dest_number;
dest=malloc(sizeof(char)*((dfa_node_number+)/+));
dest_number=malloc(sizeof(int)*dfa_node_number);
*(group_table+group_index)=dest_number;//复制目标地址
for(for_i=;for_i<dfa_node_number;for_i++)
{
dest_number[for_i]=;
}//初始化
for(for_i=;for_i<=(dfa_node_number+)/;for_i++)
{
dest[for_i]='\0';
}//初始化为0
group_index++;//建立一个新的群
for(for_i=;for_i<dfa_node_number;for_i++)
{
if(*(*(group_table+origin_group)+for_i)==)
{
temp_edge=rev_dfa_table[for_i=];//注意加1
while(temp_edge!=NULL)
{
if(temp_edge->label==in_label)
{
temp_dest_number=temp_edge->destination_number;
temp_dest_number--;
dest_number[temp_dest_number]=;
}
temp_edge=temp_edge->next;
}
}
}//遍历邻接表完成
//然后取交集
for(for_i=;for_i<dfa_node_number;for_i++)
{
if(*(*(group_table+dest)+for_i)==)
{
dest_number[temp_dest_number]=;
}
}//交集处理完成
for(for_i=;for_i<dfa_node_number;for_i++)
{
if(dest_number[for_i]==)
{
dest[for_i/]=dest[for_i/]|(BYTE_MASK>>for_i%);
belong_to[for_i]=group_index;
}
}//名字及相应的群建立完成
insert_rev_hash(dest,group_index);//插入hash表中
free(dest);//释放内存空间
} void group_min_dfa(void)
{
char* temp_name;
int for_i,for_j;
pgroup_list before,current;//用来遍历整个群链表
int is_group_changed;//用来标志当前是否生成了新的群号，如果没有生成，则可以结束集合分割了
int* is_already_tackled=malloc(sizeof(int)*dfa_node_size;//这个是用来标志在处理分割集的时候哪些点已经用过了
belongto=malloc(sizeof(int)*dfa_node_number);
group_table=malloc(sizeof(int)*);//这里可能有点小，但是就这么着吧，不够用了自己改
group_index++;
*(group_table+group_index)=malloc(sizeof(int)*dfa_node_number);//这个是用来标识属于接受节点的那些点
for(for_i=;for_i<=dfa_node_number;for_i++)//初始化那些属于开始节点的群
{
if(current_dfa_table[for_i].is_end==)
{
*(*(group_table+group_index)+for_i-)=;//注意这里要减一
*(belong_to+for_i-)=group_index;
}
else
{
*(*(group_table+group_index)+for_i-)=;
}
}
temp_name=malloc(sizeof(char)*((dfa_node_number+)/+));
map_name(temp_name,group_index);
insert_rev_hash(temp_name,group_index);
insert_group(group_index);
group_index++;
*(group_table+group_index)=malloc(sizeof(int)*dfa_node_number);//这个是用来标识属于非接受节点的那些点
for(for_i=;for_i<=dfa_node_number;for_i++)//初始化那些不是接受节点所在的群
{
if(current_dfa_table[for_i].is_end==)
{
*(*(group_table+group_index)+for_i-)=;//注意这里要减一
*(belong_to+for_i-)=group_index;
}
else
{
*(*(group_table+group_index)+for_i-)=;
}
}
temp_name=malloc(sizeof(char)*((dfa_node_number+)/+));
map_name(temp_name,group_index);
insert_rev_hash(temp_name,group_index);
insert_group_index;
//初始化工作完成
is_group_changed=;
while(is_group_changed!=)//现在开始遍历工作
{
is_group_changed=;
before=group_list_begin;
current=before->next;
while(current!=NULL)//现在开始遍历整个群链表
{
int label_traverse;
char* name_for_transition;
for(label_traverse=;label_traverse<alpha_size;label_traverse++)
{
name_for_transition=group_transition(current->group_number,mini_alpha_set[label_traverse]);
//这里进行边的转换，并为目标集合生成一个名字
int search_hash_result=search_rev_hash(name_for_transition);//搜索这个名字是不是已经在群里面了
if(search_hash_result==-)//如果这个名字当前不存在，则需要分割
{
is_group_changed=;//标志为已经改变
//记录这个name里面包含的群，然后每个群再通过反向调整，并与当前群相交来建立新的群
for(int for_k=;for_k<dfa_node_number;for_k++)
{
is_already_tackled[for_k]=;//初始化为未使用
}
for(int for_k=;for_k<dfa_node_number;for_k++)//处理每一位
{
if(is_already_tackled[for_k]==)
{
is_already_tackled[for_k]=;
if(name_for_transition[(for_k+)/]&(BYTE_MASK>>(for_k%)))//如果这里被置位了
{
int temp_group_number=belong_to[for_k];
for(int for_m=for_k;for_m<dfa_node_number;for_m++)
{
if(belong_to[for_m]==temp_group_number)
{
is_already_tackled[for_m]=;
}
}//把属于一个群的全都标记为已经处理
//然后在对这个群与当前群来处理
intersect_group(current->group_number,temp_group_number,mini_alpha_set[label_traverse]);
//前面的函数来处理交集，并生成一个新的群，自动增加到hash中
if(before==group_list_begin)//插入群的时候需要考虑这个情况
{
pgroup_list temp_group_add=malloc(sizeof(struct _group_list));
temp_group_add->group_number=group_index;
temp_group_add->next=group_list_begin->next;
group_list_begin=temp_group_add;
before=temp_group_add;
}
else
{
pgroup_list temp_group_add=malloc(sizeof(struct _group_list));
temp_group_add->group_number=group_index;
temp_group_add->next=group_list_begin->next;
group_list_begin=temp_group_add;
} }//相交群处理完成
}//这个位处理完成
}//所有位处理完成
delete_hash(current->group_number);//从hash表中取消这个群名字的注册
free(*(group_table+current->group_number);//释放这个名字所占的全局表空间
*(group_table+current->group_number)=NULL;//一定要列为空
current=current->next;//处理下一个群
free(before->next);//释放空间
before->next=current;//这样就把当前处理的群从当前链表中删去了
break;//下面的字符就不需要处理了，直接跳出循环，处理下一个群标号
}//当前群分割完成
free(name_for_transition);//释放临时申请的内存
}//当前群处理完成
}//当前遍历完成
}//没有额外的群加入，所有的处理完成 //现在所有的群都建造完成了
//现在的任务是重新建立dfa表
//这里需要确定哪些是开始节点，那些是结束节点,并做好标注
//具体代码就不详细写了，太尼玛累了
}