0

hi all

i have an assignment in which i have to use object-oriented programming to read from an input file(say: input.txt), use prim's algorithm and calculate the weight of a minimun spanning tree and then save the output to a file(output.txt).

the problem with my code is that the program closes as soon as i compile and run it, however, the output is correctly printed and saved in the output file.

can anyone please help me with this.

this is the content of input.txt :

*9 13
1 2 10
1 9 60
1 3 30
2 9 50
2 3 20
3 9 40
3 4 70
4 5 110
3 5 120
3 6 100
5 6 130
6 8 90
6 7 80*

and this the program that i have:

```
#include <memory.h>
#include <stdio.h>
#include <iostream.h>
// Create the edge type
struct Edge
{
int from;
int to;
int weight;
bool inTheCut;
};
typedef Edge* pEdge;
// adjacency list
struct ListIt
{
int value;
ListIt *p_next;
};
// typedef for the pointer type
typedef ListIt* pListIt;
pEdge edges;
pEdge edgesPr;
int n,m;
int *tree;
int *ancient;
int **distanceMatrix;
FILE *fp;
pListIt* adjacencyList; // 100000 is the maximum vertexes
void read();
int Prim(int at);
bool add(pListIt &dest, int val);
int compareEdges(const void* el1, const void* el2);
int min_vag();
int main()
{
read();
cout<<"\n";
cout<<"\n\n The edges and weights of the MST: \n\n";
Prim(1);
fclose(fp);
system("PAUSE");
return 0;
}
//Read in the data from the same folder as the code being compiled in
void read()
{
fp = freopen("input.txt", "r", stdin);
if(fp == NULL) {
cout<<"failed to open input.txt \n";
system("PAUSE");
}
scanf("%d", &n);
scanf("%d", &m);
fp = freopen("outfile.txt", "w", stdout);
if(fp == NULL) {
cout<<"failed to open out.txt \n";
system("PAUSE");
}
tree = (int*) calloc(n+1, sizeof(int));
ancient = (int*) calloc(n+1, sizeof(int));
edges = (pEdge)malloc(m*sizeof(Edge));
adjacencyList = (pListIt*) calloc(n+1,sizeof(pListIt));
distanceMatrix = (int**) calloc(n+1, sizeof(int*));
for (int j = 1; j <=n; ++j)
{
distanceMatrix[j] = (int*) calloc(n+1, sizeof(int));
}
int from,to,distance;
for(int i =0; i< m; ++i)
{
scanf("%d%d%d", &from, &to, & distance);
add(adjacencyList[from], to);
add(adjacencyList[to], from);
edges[i].from = from;
edges[i].to = to;
edges[i].weight = distance;
}
}
//Compare two edge types according to their weight
int compareEdges(const void* edge1, const void * edge2)
{
pEdge first = (pEdge)edge1;
pEdge second = (pEdge)edge2;
return first->weight - second->weight;
}
//Prims Algoritm to create the minimal spanning tree
int Prim(int at)
{
int i = 0;
memset(tree, 0, (n+1)*sizeof(int));
tree[at] = 1;
ancient[at] = 0 ;
// sort the edge list
qsort((void*)edges,m,sizeof(Edge),compareEdges);
// build up the tree
for (i = 0; i < m; ++i)
{
distanceMatrix[edges[i].from][edges[i].to ] = i;
distanceMatrix[edges[i].to ][edges[i].from] = i;
if (edges[i].from == at || edges[i].to == at)
{
edges[i].inTheCut = true;
}
else
{
edges[i].inTheCut = false;
}
}
int overallWeight = 0;
int curent = 0;
int addedVertex = 1;
int neighborVertex = 0;
int neighborEdge = 0;
pListIt p = NULL;
int j = 0;
for(i = 1; i < n; ++i)
{
for ( j =0 ; j < m; ++j)
{
if (edges[j].inTheCut)
{
curent = j;
break;
}
}
printf( " %d) %d - %d -> %d \n",i, edges[curent].from,edges[curent].to, edges[curent].weight);
overallWeight += edges[curent].weight;
if (tree[edges[curent].from] == 1)
{
addedVertex = edges[curent].to;
ancient[addedVertex] = edges[curent].from;
}
tree[addedVertex] = 1;
for (p = adjacencyList[addedVertex]; p != NULL; p = p -> p_next)
{
neighborVertex = p->value;
neighborEdge = distanceMatrix[addedVertex][neighborVertex];
if (tree[neighborVertex] == 1)
edges[neighborEdge].inTheCut = false; // reset if both ends are there
else
edges[neighborEdge].inTheCut = true; // set if only one is there
}
}
printf( "\n\n Size of the MST: %d " , overallWeight);
cout<<"\n\n";
}
// Check for correct order
bool add(pListIt &dest, int val)
{
//create the item
pListIt p;
p = (pListIt) malloc(sizeof(ListIt));
p -> value = val;
if(!dest) // first item addition
{
p -> p_next = NULL;
dest = p;
}
else
{
pListIt find = dest;
pListIt at = NULL;
// first find the first greater number, insert before
while(find && find->value <= val)
{
if( find->value == val) // do not add a duplicate
{
free(p);
return false;
}
at = find;
find = find->p_next;
}
// insert at
if (at) // insert at a valid point
{
p->p_next = at->p_next;
at->p_next = p;
}
else // insert at the start
{
p->p_next = dest;
dest = p;
}
}
return true;
}
```

i know the code is very long but i would be very grateful if anyone would please help me.