C programming assignment. The assignment should: Read in one filename as input i
ID: 3676909 • Letter: C
Question
C programming assignment.
The assignment should:
Read in one filename as input in the command line. The file is going to represent an input to the program. Do not hard-code any filenames in your program – doing so will result in a zero – no exceptions.
The input file is going to store an undirected graph as follows. The first line of the file will represent the total number of vertices, and the remaining lines will be vertex pairs representing edges. We will assume that vertices are numbered as 1,2, …. An edge between two vertices numbered as x and y will be represented as (x,y) (with no whitespaces). In the input file, edges shall be separated by newlines. A sample input file can be found at the end of this assignment.
The output will be written to stdout. Write a procedure that outputs each vertex and it’s distance from vertex 1. More specifically, the output should be formatted with the vertex number, followed by a single whitespace, then the distance to vertex 1 and a newline. If the vertex is unreachable from 1, please write -1 for the distance. The vertices should be listed in increasing order, that is the first line should list vertex 1 and its distance from vertex 1, the second line should list vertex 2 and its distance from vertex 1 and so on. A sample output file can be found at the end of this assignment.
Constraints:
The assignment must be completed in C.
Built-in data structures and external libraries must not be used for this assignment. If the program requires a stack, linked list, or any other structure, it is up to you to provide it. If you have any doubt on whether or not any technique you wish to use is acceptable, do not hesitate to ask.
A moderate amount of error checking and resource management is required. Even if you do some error recovery, you must report errors in the input files. Your application should ensure that each line from the input file is properly formatted, that the file is successfully opened, the file is successfully closed upon reading of the file and that all allocated space is de-allocated at the exit.
For reporting input format error, please use the enum type provided in input_error.h. Please do not alter the files input_error.h. You need to include input_error.h in your main program. The file input_error.h contains documentation of how to use input_error.h.
A moderate amount of formatting and documentation is required. Comments should be descriptive and used to illustrate the purpose and inner workings of an algorithm or function; they should not be used to annotate each line or self-evident logic.
The assignment must be submitted via Blackboard. Please compress the folder before submitting using zip or tar. Please do not submit a rar file.
The input size is unknown, and the input range is 0 to UINT_MAX. This means that your program should not make any assumptions about the range or size of the input. Assuming an input size will result in a grade of zero – no exceptions.
Timing Constraints
A good algorithm for this homework should run in O(n+m) where n is the total number of vertices and m the total number of edges in the input graph. While we shall not be grading the exact time complexity of your solution, we shall be timing your solution and grading efficiency. As a guideline, on input files each consisting of a million integers, your program should run in under a minute of system time to receive full credit for efficiency.
Sample input graph:
5
(2,3)
(1,4)
(1,3)
(3,4)
(4,5)
Sample output
1 0
2 2
3 1
4 1
5 2
input_error.h
Explanation / Answer
#include <ctype.h>
#include <limits.h>
#include "input_error.h"
#include "vector.h"
void read_file(char* filename, Vector* v);
void quicksort(int* x, int first, int last);
void search_arrays(int* a1, int* a2, int size1, int size2);
int main(int argc, char** argv) {
if (argc != 3)//Incorrect commandline arguments
{
exit(INCORRECT_NUMBER_OF_COMMAND_LINE_ARGUMENTS);
}
Vector v1;
Vector v2;
init_vector(&v1);
read_file(argv[1], &v1);//Read in file 1 & load vector1
init_vector(&v2);
read_file(argv[2], &v2);//read in File 2 & load vector 2
quicksort(vector_get_ptr(&v1), 0, vector_size(&v1)-1);//Sort arrays inside vectors
quicksort(vector_get_ptr(&v2), 0, vector_size(&v2)-1);
search_arrays(vector_get_ptr(&v1), vector_get_ptr(&v2), vector_size(&v1), vector_size(&v2));//Find items in common and print
free_vector(&v1);//Got to prevent memory leaks!
free_vector(&v2);
return (EXIT_SUCCESS);
}
void read_file(char* filename, Vector* v)
{
FILE* fp = fopen(filename, "r");
if(!fp)//File doesn't open
{
exit(FILE_FAILED_TO_OPEN);
}
if(feof(fp))//File is empty
{
fclose(fp);//Just in case
exit(PARSING_ERROR_EMPTY_FILE);
}
int newNum;
while (!feof(fp)) //Parse file data
{
if(fscanf(fp, "%d ", &newNum) != 1)//Checks for weird stuff read in
{
exit(PARSING_ERROR_INVALID_CHARACTER_ENCOUNTERED);
}
else if (newNum >= 0 && newNum < INT_MAX)//Check if read in value is a possible number
{
insert_element_vector(v, newNum);//Insert into vector
}
else if (isspace(newNum))
{
continue;//Do nothing and go to next line
}
else
{
exit(PARSING_ERROR_INVALID_CHARACTER_ENCOUNTERED);
}
}
if (fclose(fp) == EOF)//FIle doesn't close
{
exit(FILE_FAILED_TO_CLOSE);
}
return;
}
void quicksort(int* x, int first, int last)
{
int pivot, j, temp, i;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
void search_arrays(int* a1, int* a2, int size1, int size2)//Finds the intersection of two data sets
{
int i = 0, j = 0;//Counters
Vector v;
init_vector(&v);
while(i < size1 && j < size2)
{
if (a1[i] < a2[j])
{
i++;
}
else if(a2[j] < a1[i])
{
j++;
}
else // if the current elements are equal, print out
{
printf("%d ", a1[i]);
i++;
j++;
}
}
return;
}
input_error.h
#ifndef H_ERRORS_H
#define H_ERRORS_H
enum error {
INCORRECT_NUMBER_OF_COMMAND_LINE_ARGUMENTS = 1,
FILE_FAILED_TO_OPEN,
FILE_FAILED_TO_CLOSE,
PARSING_ERROR_INVALID_CHARACTER_ENCOUNTERED,
PARSING_ERROR_EMPTY_FILE,
};
#endif
vector.h
#ifndef H_VECTOR_H
#define H_VECTOR_H
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define INIT_VECTOR_SIZE 512
enum vector_errors
{
OUT_OF_BOUNDS = 0,
};
typedef struct vector
{
int* data;
int size;
int capacity;
}Vector;
void init_vector(struct vector* v);
int access_element_vector(struct vector* v, size_t index);
void insert_element_vector(struct vector* v, int element_to_insert);
void free_vector(struct vector* v);
void printVector(Vector v);
int* vector_get_ptr(struct vector* v);
int vector_size(Vector* v);
#endif
vector.c
#include "vector.h"
void init_vector(struct vector* v)
{
v->data = malloc(sizeof(int) * INIT_VECTOR_SIZE);
v->size = 0;
v->capacity = INIT_VECTOR_SIZE;
}
int access_element_vector(struct vector* v, size_t index)
{
if(index >= v->size)
exit(OUT_OF_BOUNDS);
return v->data[index];
}
void insert_element_vector(struct vector* v, int element_to_insert)
{
if(v->capacity == v->size)
{
v->data = realloc(v->data, sizeof(int) * v->capacity * 2);
v->capacity *= 2;
}
v->data[v->size] = element_to_insert;
v->size += 1;
}
int* vector_get_ptr(struct vector* v)
{
return v->data;
}
void free_vector(struct vector* v)
{
free(v->data);
v->size = 0;
}
int vector_size(Vector* v)
{
return v->size;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.