/***********************************************************
Copyright (c) 2004, RM.RYT. All rights reserved.
Developed in Microsoft Visual C++ 6.0 Enterprise Edition.
***********************************************************/
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
/////////////////////////////////////////////////
#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 = startVert
- 1
- 2
- 3
- 4
- 5
- 6
前往页