求高手帮忙看个程序，编译通过运行不了
//邻接表图，寻找最短路径，Dij法#include<iostream>
using namespace std;
#define INFINITY 65535
typedef enum{UNVISITED,VISITED};
/****************************************************************************************************************/
template <class Type>
class MinHeap
{
private:
Type * heapArr;
int heapCurrentSize;
int heapMaxSize;
void FilterDown(const int start);
void FilterUp(int p);
public:
MinHeap(int maxSize);
MinHeap(Type a [], int n);
~MinHeap()
{
delete []heapArr;heapArr=NULL;
}
int Insert(const Type & d);
Type RemoveMin();
Type GetTop() const
{
return heapArr[0];
}
int IsEmpty()
{
return heapCurrentSize == 0;
}
int IsFull() const
{
return heapCurrentSize == heapMaxSize;
}
int SizeofHeap() const
{
return heapCurrentSize;
}
void SetEmpty()
{
heapCurrentSize = 0;
}
};
//最小值堆构造函数
template <class Type>
MinHeap<Type>::MinHeap(int maxSize)
{
if (maxSize <= 0)
{
cerr << "The size of heap cannot be less than 1" << endl;
exit(1);
}
heapMaxSize = maxSize;
heapArr = new Type[heapMaxSize];
heapCurrentSize = 0;
}
//向下调整
template <class Type>
void MinHeap<Type>::FilterDown(const int start)
{
int i = start, j;
Type temp = heapArr[i];
j = 2 * i + 1;
while (j <= heapCurrentSize - 1)
{
if ((j < heapCurrentSize - 1) && (heapArr[j].length > heapArr[j+1].length))
j++;
if (temp.length <= heapArr[j].length)
break;
else
{
heapArr[i] = heapArr[j];
i = j;
j = 2 * j + 1;
}
}
heapArr[i] = temp;
}
//向上调整
template <class Type>
void MinHeap<Type>::FilterUp(int p)
{
int j = p, i;
Type temp = heapArr[j];
i = (j - 1) / 2;
while (j > 0)
{
if (heapArr[i].length <= temp.length)
break;
else
{
heapArr[j] = heapArr[i];
j = i; i = (j - 1) / 2;
}
}
heapArr[j] = temp;
}
//插入
template <class Type>
int MinHeap<Type>::Insert(const Type & d)
{
if (IsFull())
{
cout << "The heap is full" << endl; return 0;
}
heapArr[heapCurrentSize] = d;
FilterUp(heapCurrentSize);
heapCurrentSize++;
return 1;
}
//删除堆顶最小元素
template <class Type>
Type MinHeap<Type>::RemoveMin()
{
if (IsEmpty())
{
cout << "The heap is empty" << endl;
}
else
{
Type temp = heapArr[0];
heapArr[0] = heapArr[heapCurrentSize - 1];
heapCurrentSize--;
FilterDown(0);
return temp;
}
}
/****************************************************************************************************************/
class Edge
{
public:
int from,to,weight;
Edge()
{
from = -1;to = -1;weight = 0;
}
Edge(int f,int t,int w)
{
from = f;to = t;weight = w;
}
};
class Graph
{
public:
int numVertex;
int numEdge;
int * Mark;
int * Indegree;
int * VertexName;
Graph(int numVert)
{
numVertex = numVert;
numEdge = 0;
Mark = new int[numVertex];
Indegree = new int[numVertex];
VertexName = new int[numVertex];
for(int i = 0;i < numVertex;i ++)
{
Mark[i] = UNVISITED;
Indegree[i] = 0;
VertexName[i] = -1;
}
}
~Graph()
{
delete[] Mark;
delete[] Indegree;
delete[] VertexName;
}
bool IsEdge(Edge oneEdge)
{
if((oneEdge.weight > 0)&&(oneEdge.weight < INFINITY)&&(oneEdge.to >= 0))
return true;
else return false;
}
void setVertex(Graph & G)
{
for(int i = 0;i <= 9;i++)
G.VertexName[i] = i;
}
};
struct listUnit
{
int end_point;
int weight;
};
template<class Elem>
class Link
{
public:
Elem element;
Link * next;
Link(const Elem& elemval,Link *nextval = NULL)
{
element = elemval;
next = nextval;
}
Link(Link * nextval = NULL)
{
next = nextval;
}
};
template<class Elem>
class LList
{
public:
Link<Elem> * head;
LList()
{
head = new Link<Elem>();
}
};
class Graphl:public Graph
{
private:
LList<listUnit> * graList;
public:
Graphl(int numVert):Graph(numVert)
{
graList = new LList<listUnit>[numVertex];
}
int ToVertex(Edge currEdge)
{
return currEdge.to;
}
Edge FirstEdge(int oneVertex)
{
Edge myEdge;
myEdge.from = oneVertex;
Link<listUnit> * temp = graList[oneVertex].head;
if(temp -> next != NULL)
{
myEdge.to = temp -> next -> element.end_point;
myEdge.weight = temp -> next -> element.weight;
}
return myEdge;
}
Edge NextEdge(Edge preEdge)
{
Edge myEdge;
myEdge.from = preEdge.from;
Link<listUnit> * temp = graList[preEdge.from].head;
while((temp -> next != NULL)&&(temp -> next -> element.end_point <= preEdge.to))
temp = temp -> next;
if(temp -> next != NULL)
{
myEdge.to = temp -> next -> element.end_point;
myEdge.weight = temp -> next ->element.weight;
}
return myEdge;
}
void setEdge(int from,int to,int weight)
{
Link<listUnit> * temp = graList[from].head;
while((temp -> next != NULL)&&(temp -> next ->element.end_point < to))
temp = temp -> next;
if(temp -> next == NULL)
{
temp -> next = new Link<listUnit>;
temp -> next -> element.end_point = to;
temp -> next -> element.weight = weight;
numEdge ++;
Indegree[to] ++;
return;
}
if(temp -> next -> element.end_point == to)
{
temp -> next -> element.weight = weight;
return;
}
if(temp -> next -> element.end_point > to)
{
Link<listUnit> * other = temp -> next;
temp -> next = new Link<listUnit>;
temp -> next -> element.end_point = to;
temp -> next -> element.weight = weight;
temp -> next -> next = other;
numEdge ++;
Indegree[to] ++;
return;
}
}
void setAllEdge(Graphl & G)
{
G.setEdge(0,1,5);G.setEdge(0,2,6);
G.setEdge(1,3,3);
G.setEdge(2,3,6);G.setEdge(2,4,3);
G.setEdge(3,4,3);G.setEdge(3,5,4);G.setEdge(3,6,5);
G.setEdge(4,6,1);G.setEdge(4,7,4);
G.setEdge(5,9,4);
G.setEdge(6,8,5);
G.setEdge(7,8,2);
G.setEdge(8,9,2);
}
class Dist
{
public:
int index;
int length;
int pre;
};
int Dijkstra(Graphl & G , int s , int end)
{
Dist * D = new Dist[G.numVertex];
for(int i = 0;i < G.numVertex;i ++)
{
G.Mark[i] = UNVISITED;
D[i].index = i;
D[i].length = INFINITY;
D[i].pre = s;
}
D[s].length = 0;
MinHeap<Dist>H(G.numEdge);
H.Insert(D[s]);
for(int i = 0;i < G.numVertex;i ++)
{
bool FOUND = false;
Dist d;
while(!H.IsEmpty())
{
d = H.Remove();
if(G.Mark[d.index] == UNVISITED)
{
FOUND = true;
break;
}
}
if(!FOUND)
break;
int v = d.index;
G.Mark[v] = VISITED;
for(Edge e = G.FirstEdge(v);G.IsEdge(e);e = G.NextEdge(e))
if(D[G.ToVertex(e)].length > (D[v].length) + e.weight)
{
D[G.ToVertex(e)].length = (D[v].length) + e.weight;
D[G.ToVertex(e)].pre = v;
H.Insert(D[G.ToVertex(e)]);
}
}
return D[end].length;
}
};
void main(Graphl & G)
{
int start=-1;int end=-1;
cin>>start>>end;
G.Dijkstra(G,start,end);
return;
}
