arrayset.cpp

来自「I implement Dijkstra s Single Source Sho」· C++ 代码 · 共 89 行

#include "ArraySet.h"

/*
 *Constructor, Initialize the array to store the medium state
 *during the Dijkstra.
 *int size:the max size of the array.
 */
ArraySet::ArraySet(int size)
{
	maxSize = size;
	initial();
}

void ArraySet::initial()
{
	currentSize = 0;
	dists = new int[maxSize];
	nodes = new int[maxSize];
}

/*
 *Destructor
 */
ArraySet::~ArraySet(void)
{
	delete [] dists;
	delete [] nodes;
}

/*
 *find the node with min dist and delete it from array.
 *return the ID of the node.
 */
int ArraySet::deleteMin()
{
	int i, min;
	if(currentSize<=0){
		cout<<"No Elements!"
		<<endl;
		return -1;
	}

	min = INT_MAX;
	for(i=0; i<currentSize; i++){
		if(dists[i]<min){
			min = dists[i];
		}
	}

	i--;

	if(currentSize>1){
		nodes[i] = nodes[currentSize-1];
		dists[i] = dists[currentSize-1];
	}
	currentSize = currentSize-1;
	return nodes[i];
}

/*
 *Decrease the dist of a node to a new value
 *int node: the node to decrease value.
 *int newDist: new value of the dist of the node
 */
int ArraySet::decreasDist(int node, int newDist)
{
	for(int i=0; i<currentSize; i++){
		if(nodes[i] == node && newDist<dists[i]){
				dists[i] = newDist;
				return 1;
			}
	}
	return 0;
}

/*
 *insert a new (node, dist) pair into the array
 *return the current size of the array.
 */
int ArraySet::insert(int node, int dist){
	for(int i=0; i<maxSize; i++){
		if(nodes[i]!=-1){
			nodes[currentSize] = node;
			dists[currentSize] = dist;
		}
	}
	currentSize++;
	return currentSize;
}