NFA转DFA，并将DFA最小化

#include <iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> using namespace std; #define NULL 0 #define LStack LinkedStack // 链式栈类的前视定义 template <class T> class LinkedStack; // 定义链式栈结点类 template <class T> class StackNode { friend class LinkedStack<T>; private: T data; StackNode<T> *next; StackNode(T item = 0, StackNode<T> *p = NULL) { data = item; next = p; } }; // 定义链式栈类 template <class T> class LinkedStack { private: StackNode<T> *top; public: LinkedStack(); ~LinkedStack(); bool IsEmpty(void) const; int Length(void) const; void Push(const T &item); T Pop(void); T GetTop(void); void Clear(void); }; // 构造函数 template <class T> LinkedStack<T>::LinkedStack() { top = NULL; } // 析构函数 template <class T> LinkedStack<T>::~LinkedStack() { Clear(); } // 判断栈是否为空 template <class T> bool LinkedStack<T>::IsEmpty(void) const { return (!top); } // 获取队列的长度 template <class T> int LinkedStack<T>::Length(void) const { StackNode<T> *temp = new StackNode<T>(); temp = top; int length = 0; while (temp) { temp = temp->next; length++; } return length; } // 压入数据(入栈) template <class T> void LinkedStack<T>::Push(const T &item) { top = new StackNode<T>(item, top); } // 抽出数据(出栈) template <class T> T LinkedStack<T>::Pop(void) { if (!IsEmpty()) { StackNode<T> *temp = top; top = top->next; T value = temp->data; delete temp; return value; } else { cout << "Stack Already Empty!" << endl; _getch(); exit(1); } } // 获取栈头数据 template <class T> T LinkedStack<T>::GetTop(void) { if (!IsEmpty()) { return top->data; } else { cout << "Stack Already Empty!" << endl; _getch(); exit(1); } } // 设置栈为空栈 template <class T> void LinkedStack<T>::Clear(void) { StackNode<T> *temp = new StackNode<T>(); while (top) { temp = top; top = top->next; delete temp; } } // 定义邻接表的边表类 class Edge { public: int number; int position; char weight; Edge *link; Edge(); Edge(int num, int pos, char ch); }; Edge::Edge() { number = -1; position = -1; link = NULL; } Edge::Edge(int num, int pos, char ch) { number = num; position = pos; weight = ch; link = NULL; } // 定义邻接表的顶点类 class Vertex { public: int number; Vertex *next; Edge *out; Vertex(); Vertex(int num); }; Vertex::Vertex() { number = -1; next = NULL; out = NULL; } Vertex::Vertex(int num) { number = num; next = NULL; out = NULL; } // 用邻接表定义的图类 class AdjacentTable { private: Vertex *startVertex; int numOfVertices; int numOfEdges; public: AdjacentTable(); ~AdjacentTable(); int GetValueByPos(int pos) const; int GetPosByValue(int value) const; char GetWeightByPos(int v1, int v2) const; char GetWeightByValue(int value1, int value2) const; void SetValue(int value, int pos); void InsertVertex(int value); void InsertEdgeByPos(int v1, int v2, char weight); void InsertEdgeByValue(int value1, int value2, char weight); void RemoveAllEdges(void); void Clear(void); int* Closure(int *T); int* Move(int *T, char ch); void OutputNFA(void); }; // 构造函数 AdjacentTable::AdjacentTable() { numOfVertices = 1; numOfEdges = 0; startVertex = new Vertex(); } // 析构函数 AdjacentTable::~AdjacentTable() { Vertex *p; Edge *q; p = startVertex; for (int i = 0; i<numOfVertices; i++) { q = p->out; while (q) { p->out = q->link; delete q; q = p->out; } p = p->next; } } // 按顶点位置获取顶点的值 int AdjacentTable::GetValueByPos(int pos) const { if ((pos >= 0) && (pos < numOfVertices)) { Vertex *p = startVertex; for (int i = 0; i<pos; i++) { p = p->next; } return p->number; } return -1; } // 按顶点值获取顶点的位置 int AdjacentTable::GetPosByValue(int value) const { Vertex *p = startVertex; for (int i = 0; i<numOfVertices; i++) { if (p->number == value) { return i; } p = p->next; } return -1; } // 按顶点位置获取边的权 char AdjacentTable::GetWeightByPos(int v1, int v2) const { if ((v1 >= 0) && (v2 >= 0) && (v1 < numOfVertices) && (v2 < numOfVertices)) { Vertex *p = startVertex; for (int i = 0; i<v1; i++) { p = p->next; } Edge *q = p->out; while (q) { if (q->position == v2) { return (q->weight); } else { q = q->link; } } } return '#'; } // 按顶点值获取边的权 char AdjacentTable::GetWeightByValue(int value1, int value2) const { return GetWeightByPos(GetPosByValue(value1), GetPosByValue(value2)); } // 设置顶点的值 void AdjacentTable::SetValue(int value, int pos) { if ((pos < 0) || (pos >= numOfVertices)) { cout << "Illegal setting: The vertex doesn't exist!" << endl; _getch(); exit(1); } Vertex *p = startVertex; for (int i = 0; i<pos; i++) { p = p->next; } p->number = value; } // 插入顶点 void AdjacentTable::InsertVertex(int value) { int pos = GetPosByValue(value); if ((pos >= 0) && (pos < numOfVertices)) { cout << "Illegal insertion: The same vertex has existed!" << endl; _getch(); exit(1); } Vertex *p = startVertex; while (p->next) { p = p->next; } Vertex *newVertex = new Vertex(value); p->next = newVertex; numOfVertices++; } // 按顶点位置插入边表 void AdjacentTable::InsertEdgeByPos(int v1, int v2, char weight) { if ((v1 < 0) || (v1 >= numOfVertices) || (v2 < 0) || (v2 >= numOfVertices)) { cout << "Illegal insertion: The vertex doesn't exist!" << endl; _getch(); exit(1); } Vertex *p = startVertex; for (int i = 0; i<v1; i++) { p = p->next; } Edge *q = p->out; Edge *newEdge = new Edge(GetValueByPos(v2), v2, weight); if (!q) { p->out = newEdge; numOfEdges++; return; } while ((q->position != v2) && (q->link)) { q = q->link; } if (q->position == v2) { cout << "Illegal insertion: The Edge has existed!" << endl; _getch(); exit(1); } if (!q->link) { q->link = newEdge; numOfEdges++; } } // 按顶点值插入边表 void AdjacentTable::InsertEdgeByValue(int value1, int value2, char weight) { int v1 = GetPosByValue(value1), v2 = GetPosByValue(value2); InsertEdgeByPos(v1, v2, weight); } // 删除所有的边表 void AdjacentTable::RemoveAllEdges(void) { Vertex *p = startVertex; for (int i = 0; i<numOfVertices; i++) { Edge *q = p->out; while (q) { p->out = q->link; delete q; q = p->out; } p = p->next; } numOfEdges = 0; } // 清空邻接表 void AdjacentTable::Clear(void) { RemoveAllEdges(); Vertex *p = startVertex->next; while (p) { startVertex->next = p->next; delete p; p = startVertex->next; } numOfVertices = 1; } // 闭包函数 int* AdjacentTable::Closure(int *T) { int i = 0, j, k = 0, l, len = 0; int *temp = new int[128]; Vertex *p; Edge *q; while (T[len] != -1) { len++; } while (T[i] != -1) { for (l = 0; l<k; l++) { if (T[i] == temp[l]) { break; } } if (l == k) { temp[k] = T[i]; k++; } int pos = GetPosByValue(T[i]); p = startVertex; for (j = 0; j<pos; j++) { p = p->next; } q = p->out; while (q) { if (q->weight == '~') { for (l = 0; l<k; l++) { if (q->number == temp[l]) { break; } } if (l == k) { temp[k] = q->number; k++; T[len++] = q->number; T[len] = -1; } } q = q->link; } i++; } temp[k] = -1; return temp; } // 移动函数 int* AdjacentTable::Move(int *T, char ch) { int i = 0, j, k = 0, l; int *temp = new int[128]; Vertex *p; Edge *q; while (T[i] != -1) { int pos = GetPosByValue(T[i]); p = sta