HC Search (File I/O and Malloc Example)
HC Search
File I/O and Malloc Example
<![CDATA[
/* This program may or may not meet your coding standards.
* Please don't use it as a guide for your prgrams format.
* Below is a short desciption of the programs purpose but
* for this class pay attention to the File I/O and Memory
* Allocation segments.
*
* HC Search is a program which takes a file name containing
* an int (representing the number of "cities" in the file)
* on the first line and floating point pairs separated by
* a comma (the first number represents the city's x-coordinate
* the second its y-cooridinate).
*
* The cities after being read in are sorted with an algorithm
* similar to Selection Sort in an attempt to find the shortest
* Hamilton Circuit visiting all the cities only once.
*
* Program written by Margot McKinney in October 2000.
* Last edited 17 April 2001.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct coords {
int num; /* City's number (acts as a name) */
float x;
float y;
} COORDS;
main() {
int i, num, curr;
char ofile[10];
float leastDist, currDist, totalDist = 0, xDist, yDist;
COORDS *cities, *cityPtr, temp;
FILE *fptr;
/* Read the name of the file from the user's input and
* attempt to open it. If unopenable, print msg and exit. */
printf("Please enter the name of the data file: ");
scanf("%s", ofile);
fptr = fopen(ofile, "r") ;
if (fptr == NULL)
{
printf ("Error opening %s.\n", ofile);
exit (-1);
}
/* Read in the first number in the open file. Attempt to
* allocate an array of COORDS to hold the cities. Check
* for NULL. If so print msg and exit. */
fscanf(fptr, "%d", &num) ;
cities = (COORDS *)(malloc(sizeof(COORDS) * num));
if (cities == NULL){
printf ("Error allocating memory.\n");
exit (-2);
}
/* Read in each of the cites from the file and assign them
* into the array. Give each city a number (in the order they
* are read here) and print the city to the screen. */
for( i = 0; i < num; i++) {
fscanf(fptr, "%f, %f", &cities[i].x, &cities[i].y);
cities[i].num = i + 1;
printf("\nCity %d Co-Oridinates: %.2f, %.2f",
cities[i].num, cities[i].x, cities[i].y);
}
fclose(fptr) ; /* Close the user's file. */
printf("\n\nStarting with City 1... ");
/* Assign curr 0 becuse no visits have been made. */
curr = 0;
/* While there are still unvisited cities. */
while( curr < num - 1 ) {
/* Initialize leastDist to 10 - no cities are this far apart. */
leastDist = 10;
for( i = curr + 1; i < num; i++) {
/* Compute the distance between the curr city and each of the
* remaining cities. */
xDist = cities[curr].x - cities[i].x;
yDist = cities[curr].y - cities[i].y;
currDist = sqrt((xDist * xDist) + (yDist * yDist));
/* If currDist is 0, we are visiting ourselves. Continue
* with the next iteration of the loop. */
if( currDist == 0 ) {
continue;
}
/* If the leastDist is less than the currDist then assign the
* currDist to the least and point the the current city, since
* it is now the closeest. */
if( leastDist > currDist ) {
leastDist = currDist;
cityPtr = &cities[i];
}
}
/* Increment curr since we are visiting another city. */
curr++;
/* Swap the closest city (from the previous) into the current
* current position. */
temp = cities[curr];
cities[curr] = *cityPtr;
*cityPtr = temp;
/* Add the distance between the two cities to totalDist. */
totalDist += leastDist;
}
/* Compute the distance from the last city visited to the first
* in order to complete our tour of all the cities. */
xDist = cities[0].x - cities[num - 1].x;
yDist = cities[0].y - cities[num - 1].y;
totalDist += sqrt((xDist * xDist) + (yDist * yDist));
/* Print the results to the screen. */
for( i = 0; i < num; i++) {
printf("\n\tVisit to City %d (%.2f, %.2f)",
cities[i].num, cities[i].x, cities[i].y);
if( i < num - 1 ) {
printf(" followed by");
}
}
printf("\nTotal Distance Traveled: %f\n", totalDist);
free(cities); /* Free the memory allocated for cities. */
}
]]>
Main Page