list.cpp

使用DIJKSTAR算法解决多点最短路径,还带文字解说

/*  list.cpp - Robert Ollington - 1/8/05
    (based upon Mike Cameron Jones' C implementation for KXA251)
    
    This code illustrates the use of pointers to implement a linked list,
    with a dummy header node. The last node's next will be NULL. (The use of
    the dummy header node simplifies some of the code as it ensures that there
    is always a node before every node containing an item, even the first
    one.)
*/


#include <iostream.h>
#include "list.h"

node::node(){
	next = NULL;
}

node::node(connection n){
	data_item.setIndex_start(n.getIndex_start());
	data_item.setIndex_end(n.getIndex_end());
	data_item.setKm(n.getkm());
	next = NULL;
}

/* Function to create an empty list 
   (the void argument list indicates that it takes no arguments) */
list::list()
{
    first = new node();
    first->data_item.setIndex_end(0);  /* superfluous initialisation */
	first->data_item.setIndex_start(0);
	first->data_item.setKm(0);
    first->next = NULL; /* necessary initialisation to indicate last node */
}

/* Function to return dynamically allocated memory in list */
list::~list()
{
    /* Note that we don't really need to have the variable "current" here,
       as we could just advance list itself if we preferred. (Some of the other
       list functions also make use of an additional such variable.) */
    node* current = first;

    while(current)
    {
			node* to_free = current;
			current = current->next;
			delete to_free;
			/* Note that the simpler: 
			   delete current; 
			   current = current->next;
			   makes the mistake of using dynamically allocated memory after
			   it's been freed */
    }
}

/* Function to insert n at front of list */
void list::insert_at_front(connection n)
{
    node* new_node = new node(n);
    new_node->next = first->next;
    first->next = new_node;
}

/* Function to print list */
void list::print()
{
    node* current = first->next;

    while(current)
    {
			//printf("%d ", current->data_item);
			cout<<current->data_item.getIndex_start()<<" "
				<<current->data_item.getIndex_end()<<" "
				<<current->data_item.getkm()<<endl;
			current = current->next;
    }
    cout<<endl;
}

/* Function to insert n in (non-decreasing) order in list - assuming list 
   items are already in (non-decreasing) order. */
void list::insert_in_order(connection n)
{
    node* before = first;
    node* new_node = new node(n);

    /* Move along list until right place is found, looking for node after
       which new node should go */
    while(before->next && (before->next->data_item.getIndex_end() < n.getIndex_end()))
    {
        before = before->next;
    }

    new_node->next = before->next;
    before->next = new_node;
}

connection* list::getConnection(int index)
{
	int i = 0;
    node* current = first->next;
    connection* con = NULL;
    while(current)
    {
		    if(i == index)
				break;
			current = current->next;
			i++;
    }
    if(i == index)
	{
        con = &current->data_item;
	}
	return con;
    
}