A. 常量定义
#define MAX 10 //运行最大值，用于限制状态和边的数量
#define INFINIT 32767 //特殊函数返回值
#define NumMaxChar 10 //最大字符数量
#define NumMAXTN 10 //最大结点数量
B. 数据结构定义
typedef struct edge
{//边
int dest; //
char cost; //代价
struct edge *link; //指向下一边
}*Edge;
typedef struct vertex
{//顶点
char data; //状态
Edge adj; //边
}*Vertex;
typedef struct graph
{//图
Vertex NodeTable;
int NumVertex; //顶点（状态）数量
int MaxNumVertex; //最大允许顶点（状态）数量
int NumEdge; //该图边数量
}*Graph;
//////////////////////////////////////////////////////////////////////
//////////////////////////状态转换表机构//////////////////////////////
typedef struct tablenode
{//转换表节点
char newname ;//状态集的新命名
char ch[MAX]; //顶点集合，如{1,2,3}
}*TableNode;
typedef struct tablequeue
{//转换表列
TableNode TN[MAX]; //转换表节点数组
char transword; //转换输入字符，即转换条件
int NumTn; //添加的顶点数
}*TableQueue;
typedef struct transmatrix
{//状态转换矩阵
TableQueue TQ; //转换表列组
int transnum; //转换表列数
}*TranMatrix;
/////////////////////////////////////////////////////////////////
C. 部分关键函数说明
int GraphEmpty(Graph g) /判断图是否为空
int GraphFull(Graph g) //判断图是否以满
char GetValue(Graph g,int i) //在图g中寻找下标为i的顶点
void Insert_Vertex(Graph g,char vertex) //向图g插入新顶点
void Insert_Edge(Graph g,int v1,int v2,char weight) //向图g插入新边
int GetVertexPos(Graph g,char v) //得到顶点在图中的下标
void Construct_Graph(Graph g) //构建图，要求输入每个边和每个顶点
void Destruct_Graph(Graph g) //销毁图
void Show_Graph(Graph g) //显示图
void Init_Matrix(TranMatrix TM)
//始化状态转换矩阵，要输入接受字符数和转换字符
void BubbleSort(char a[],int len)
//冒泡排序，为了显示状态集时让字符按升序排列
int CheckChar(char t[],char ti)
//检查数组t中是否有与ti相同的字符
int CheckTable(TranMatrix TM,char str[])
//检查转换矩阵的第一列中是否有与str相同的字符串
void Smove(Graph g,char t1[],char t2[],char transword)
//№根据NFA，将t1中的状态接受了transword后转为对应的t2中的状态
void E_Closure(Graph g,char t[])
//进行了Smove后的状态集合求闭包，并将结果按升序排列
void Show_TranMatrix(TranMatrix TM)
//显示转换矩阵
void NFA_to_DFA(Graph g,TranMatrix TM)
//实现从NFA转换为DFA,要求输入新状态名称
void Show_DFA(TranMatrix TM)
//根据状态转换表显示DFA图
#include
#include
#include
#define MAX 10
#define INFINIT 32767
#define NumMaxChar 10
#define NumMAXTN 10
typedef struct edge
{//边
int dest;
char cost;
struct edge *link; //指向下一边
}*Edge;
typedef struct vertex
{//顶点
char data; //状态
Edge adj; //边
}*Vertex;
typedef struct graph
{//图
Vertex NodeTable;
int NumVertex;
int MaxNumVertex;
int NumEdge;
}*Graph;
typedef struct tablenode
{//转换表节点
char newname;//新命名
char ch[MAX];//顶点集合
}*TableNode;
typedef struct tablequeue
{//转换表列
TableNode TN[MAX];//转换表节点数组
char transword;//转换条件
int NumTn;//添加的顶点数
}*TableQueue;
typedef struct transmatrix
{//状态转换矩阵
TableQueue TQ;//转换表列组
int transnum;//转换表列数
}*TranMatrix;
int GraphEmpty(Graph g)
{//图判空
return g->NumVertex==0;
}
int GraphFull(Graph g)
{//判图满
return g->NumVertex==g->MaxNumVertex;
}
char GetValue(Graph g,int i)
{//寻找下标为i的顶点
return (i>0 && i
}
void Insert_Vertex(Graph g,char vertex)
{//插入新的顶点
g->NodeTable[g->NumVertex].data=vertex;
g->NodeTable[g->NumVertex].adj=NULL;
g->NumVertex++;
}
void Insert_Edge(Graph g,int v1,int v2,char weight)
{//插入边
Edge p;
p=(Edge)malloc(sizeof(struct edge));
p->cost=weight;
p->dest=v2;
p->link=g->NodeTable[v1].adj;
g->NodeTable[v1].adj=p;
}
int GetVertexPos(Graph g,char v)
{//得到顶点在图中的下标
int i=0;
while(i
{
if(g->NodeTable[i].data==v)
return i;
i++;
}
return INFINIT;
}
void Construct_Graph(Graph g)
{//创建图
int k,j,i,vexn,edgen;
char head,tail,name;
char weight;
g->NumVertex=0;
g->NumEdge=0;
g->MaxNumVertex=MAX;
g->NodeTable=(Vertex)malloc((g->MaxNumVertex)*sizeof(struct vertex));
printf("输入NFA状态数:");
scanf("%d",&vexn);
printf("输入NFA状态名称:\n");
flushall();
//依次获取状态名称，并将这些顶点插入图中
for(i=0;i
{
scanf("%c",&name);
flushall();
Insert_Vertex(g,name);
}
printf("输入NFA的边数:");
scanf("%d",&edgen);
printf("输入 起始状态，接受字符 和 到达状态:\n");
flushall();
//依次获取边的信息（起始顶点，接受字符，到达的顶点），并将这些边插入图中
for(i=0;i
{
flushall();
scanf("%c %c %c",&tail,&weight,&head);
k=GetVertexPos(g,tail);
j=GetVertexPos(g,head);
Insert_Edge(g,k,j,weight);
}
}
void Destruct_Graph(Graph g)
{//销毁图
int i;
Edge p;
for(i=0;i
{
p=g->NodeTable[i].adj;
while(p!=NULL)
{
g->NodeTable[i].adj=p->link;
p->link=NULL;
free (p);
p=g->NodeTable[i].adj;
}
}
g->NumEdge=0;
g->NumVertex=0;
printf("图已销毁\n");
}
void Show_Graph(Graph g)
{//显示图
int i;
Edge p;
for(i=0;i
{
p=g->NodeTable[i].adj;
while(p!=NULL)
{
printf("(%c,%c):%c ",g->NodeTable[i].data,g->NodeTable[p->dest].data,p->cost);
p=p->link;
}
printf("\n");
}
}
void Init_Matrix(TranMatrix TM)
{
int i,j,k;
printf("输入接受字符数:");
scanf("%d",&TM->transnum);
TM->TQ=(TableQueue)malloc((TM->transnum+1)*sizeof(struct tablequeue));
//初始化转换矩阵的第一列
for(j=0;j
{
TM->TQ[0].TN[j]=(TableNode)malloc(sizeof(struct tablenode));
TM->TQ[0].TN[j]->newname='\0';
for(k=0;k
TM->TQ[0].TN[j]->ch[k]='\0';
}
TM->TQ[0].transword='I';
TM->TQ[0].NumTn=0;
//初始化转换矩阵的其它列
for(i=1;i<=TM->transnum;i++)
{
printf("输入第%d个转换字符:\n",i);
flushall();
scanf("%c",&TM->TQ[i].transword);
for(j=0;j
{
TM->TQ[i].TN[j]=(TableNode)malloc(sizeof(struct tablenode));
TM->TQ[i].TN[j]->newname='\0';
for(k=0;k
TM->TQ[i].TN[j]->ch[k]='\0';
}
TM->TQ[i].NumTn=0;
}
}
void BubbleSort(char a[],int len)
{//冒泡排序
int i,j;
char temp;
for(i=0;i
{
for(j=0;j
{
if(a[j]>a[j+1])
{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
}
int CheckChar(char t[],char ti)//检查数组t中是否有与ti相同的字符
{//0 有重复，1 无重复
int i;
for(i=0;i
{
if(t[i]==ti) return 0;
}
return 1;
}
int CheckTable(TranMatrix TM,char str[])//检查转换矩阵的第一列中是否有与str相同的字符串
{// i 有重复（并返回重复的位置），1 无重复
int i;
for(i=0;i
{
if(!strcmp(TM->TQ[0].TN[i]->ch,str))
return i;
}
return 1;
}
void Smove(Graph g,char t1[],char t2[],char transword)
{//根据NFA，将t1中的状态接受了transword后转为对应的t2中的状态
int i,j,k=0,check,len;
Edge p;
while(t2[k]!='\0') k++;
for(i=0;i
{
for(j=0;j
{
if(g->NodeTable[j].data==t1[i])
{
p=g->NodeTable[j].adj;
while(p!=NULL)
{
if(p->cost==transword)
{
check=CheckChar(t2,g->NodeTable[p->dest].data);
if(check==1)
{
t2[k]=g->NodeTable[p->dest].data;
k++;
}
p=p->link;
}
else
p=p->link;
}
}
}
}
len=k;
BubbleSort(t2,k);
}
void E_Closure(Graph g,char t[])
{//对进行了Smove后的状态集合求闭包，并将结果按升序排列
int i=0,j,k=0,check,len;
Edge p;
//找到字符数组中的最后一个字符的位置
while(t[k]!='\0') k++;
for(i=0;t[i]!='\0';i++)
{ //每个顶点都要查看一次
for(j=0;j
{ //
if(g->NodeTable[j].data==t[i])
{
p=g->NodeTable[j].adj;
while(p!=NULL)
{
if(p->cost=='*') //空输入
{
check=CheckChar(t,g->NodeTable[p->dest].data);
if(check==1)
{
t[k]=g->NodeTable[p->dest].data;
k++;
}
}
p=p->link;
}
}
}
}
len=k;
BubbleSort(t,k); //结果按升序排列
}
void Show_TranMatrix(TranMatrix TM)
{
int i,j,k;
printf("状态转换矩阵:\n");
for(j=0;j<=TM->transnum;j++)
printf("转换字符:%c ",TM->TQ[j].transword);
printf("\n");
for(k=0;k
{
for(j=0;j<=TM->transnum;j++)
{
if(TM->TQ[j].TN[k]->newname=='\0') printf("NULL ");
else printf("%c:",TM->TQ[j].TN[k]->newname);
for(i=0;TM->TQ[j].TN[k]->ch[i]!='\0';i++)
{
printf("%c",TM->TQ[j].TN[k]->ch[i]);
}
if(TM->TQ[j].TN[k]->ch[0]=='\0') printf("NULL");
printf("\t\t");
}
printf("\n");
}
}
void NFA_to_DFA(Graph g,TranMatrix TM)
{
int j=0,i,check;
char temp[2]={'\0','\0'};
TM->TQ[0].TN[0]->ch[0]=g->NodeTable[0].data;
for(i=1;i<=TM->transnum;i++)
E_Closure(g,TM->TQ[0].TN[0]->ch);
printf("输入新状态名:");
flushall();
scanf("%c",&TM->TQ[0].TN[0]->newname);
TM->TQ[0].NumTn++;
while(j
{
for(i=1;i<=TM->transnum;i++)
{
Smove(g,TM->TQ[0].TN[j]->ch,TM->TQ[i].TN[j]->ch,TM->TQ[i].transword);
E_Closure(g,TM->TQ[i].TN[j]->ch);
if (TM->TQ[i].TN[j]->ch[0]!='\0') //如果为空则可忽略，不记入结果状态
{
check=CheckTable(TM,TM->TQ[i].TN[j]->ch);
if(check==1)
{
printf("输入新状态名:");
flushall();
scanf("%c",&TM->TQ[i].TN[j]->newname);
strcpy(TM->TQ[0].TN[TM->TQ[0].NumTn]->ch,TM->TQ[i].TN[j]->ch);
TM->TQ[0].TN[TM->TQ[0].NumTn]->newname=TM->TQ[i].TN[j]->newname;
TM->TQ[0].NumTn++;
}
else TM->TQ[i].TN[j]->newname=TM->TQ[0].TN[check]->newname;
}
}
j++;
}
}
void Show_DFA(TranMatrix TM)
{
int i,j;
for(j=0;TM->TQ[0].TN[j]->newname!='\0';j++)
{
for(i=1;i<=TM->transnum;i++)
{
if (TM->TQ[i].TN[j]->newname!='\0')
printf("(%c,%c,%c) ",TM->TQ[0].TN[j]->newname,TM->TQ[i].transword,TM->TQ[i].TN[j]->newname);
}
printf("\n");
}
}
void main()
{
Graph g;
TranMatrix TM;
g=(Graph)malloc(sizeof(struct graph));
TM=(TranMatrix)malloc(sizeof(struct transmatrix));
Construct_Graph(g);
Init_Matrix(TM);
printf("\nNFA图:\n");
Show_Graph(g);
printf("\n(初始状态):\n");
Show_TranMatrix(TM);
NFA_to_DFA(g,TM);
printf("\n(转换过程):\n");
Show_TranMatrix(TM);
printf("\n转化后的DFA:\n");
Show_DFA(TM);
printf("\n程序结束，销毁图...\n");
Destruct_Graph(g);
Show_Graph(g);
}
本文来源：https://www.2haoxitong.net/k/doc/44dc6a4ecc1755270722086b.html
文档为doc格式