dfa最小化，上一个版本采用的是moore的打表法，这个版本采用的是hopcroft的方法，但是实现中采用链表而不是栈来优化。

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表
     //这里需要确定哪些是开始节点，那些是结束节点,并做好标注
     //具体代码就不详细写了，太尼玛累了
 }