grand.c file:

#include

#include

#include

#include

#include

#include "random.h"

void create_random_ints(FILE *fp, int size, int mod)

{

int i;

seed();

for (i = 0; i

fprintf(fp, "%d ", nrand(mod));

}

}

int main(int argc, char **argv)

{

/* create a file of random integers */

int size = 0;

int mod = 0;

FILE *fp = NULL;

int c = 0;

if (argc == 1) {

printf("usage: ./grand -n [NUM] -m [MAX] -f [FILE] ");

printf("[NUM] is the number of random integers to create ");

printf("create random numbers between [0, [MAX]) ");

printf("[FILE] is the name of the file the data is written to ");

exit(EXIT_SUCCESS);

}

/* pass a string of options to getopt

* the colon after a letter signifies that the option expects an argument

* leading colon lets you distinguish between invalid option and missing argument cases

*/

while((c = getopt(argc, argv, ":hn:m:f:")) != -1)

switch(c) {

case 'n':

size = atoi(optarg);

break;

case 'm':

mod = atoi(optarg);

break;

case 'f':

errno = 0; /* set to 0 so can process it if an error occurs */

fp = fopen(optarg, "w");

if (fp == NULL) {

/* strerror */

fprintf(stderr, "%s: argument to option '-f' failed: %s ", argv[0], strerror(errno));

exit(EXIT_FAILURE);

}

break;

case 'h': /* help */

if (fp != NULL)

fclose(fp);

printf("usage: ./grand -n [NUM] -m [MAX] -f [FILE] ");

printf("[NUM] is the number of random integers to create ");

printf("create random numbers between [0, [MAX]) ");

printf("[FILE] is the name of the file the data is written to ");

exit(EXIT_SUCCESS);

case ':':

/* missing option argument */

/* optopt contains the option */

/* argv[0] is the programs name */

/* stderr is 1 of 3 files open for you -- stdin, stdout, stderr. By default stdout and stderr are mapped to the same location */

if (fp != NULL)

fclose(fp);

fprintf(stderr, "%s: option '-%c' reguires an argument ", argv[0], optopt);

exit(EXIT_FAILURE);

case '?': /* getopt default invalid option */

default:

if (fp != NULL)

fclose(fp);

printf("illegal option %c - ignored ", optopt);

break;

}

/* all options are required, check to make sure they are valid */

if (fp == NULL) {

printf("the option -f [FILE] is required ");

printf("usage: ./grand -n [NUM] -m [MAX] -f [FILE] ");

exit(EXIT_FAILURE);

}

if (size

printf("the option -m [MAX] is required ");

printf("usage: ./grand -n [NUM] -m [MAX] -f [FILE] ");

if (fp == NULL)

fclose(fp);

exit(EXIT_FAILURE);

}

if (mod

printf("the option -m [MAX] is required ");

printf("usage: ./grand -n [NUM] -m [MAX] -f [FILE] ");

if (fp == NULL)

fclose(fp);

exit(EXIT_FAILURE);

}

create_random_ints(fp, size, mod);

fclose(fp);

return 0;

}

random.c

#include

#include

#include

#include "random.h"

/**

* returns a uniform random number between 0

* @param int range, defines the range of the random number [0,range)

* @return int, the generated random number

*/

int nrand(int range)

{

return rand() % range;

}

/**

* call this to seed the random number generator rand()

* uses a simple seed -- the number of seconds since the epoch

* call once before using nrand and similar functions that call rand()

*/

void seed(void)

{

srand((unsigned int)time(NULL));

}

random.h

#ifndef RANDOM_H_

#define RANDOM_H_

int nrand(int range);

void seed();

#endif

heap.c

#include

#include

#include

#include

#define LEN 4096

struct heap_t {

int last; /* index of last heap element in data array */

int size; /* number of elements in array */

int max; /* allocated size of array */

int *data; /* the data array */

};

enum {INIT = 1, GROW = 2};

int main(int argc, char **argv)

{

char buf[LEN];

FILE *fp = NULL;

int i = 0;

if (argc != 2) {

printf("error in input ");

printf("usage: ./heap [FILE] ");

printf("[FILE] is a list of integers one per line ");

exit(EXIT_FAILURE);

}

else {

fp = fopen(argv[1], "r");

assert(fp);

}

struct heap_t *heap = malloc(sizeof(struct heap_t));

heap->last = 0;

heap->size = INIT;

heap->max = INIT;

heap->data = NULL;

while (fgets(buf, LEN, fp)) {

/* read in data from file */

/* assign to heap->data */

/* grow the array as necessary */

if (heap->size > heap->max) {

heap->data = realloc(heap->data, GROW * heap->max *sizeof(int));

assert(heap->data);

heap->max = GROW * heap->max;

}

else if (heap->data == NULL) {

heap->data = malloc(INIT * sizeof(int));

assert(heap->data);

}

*(heap->data + i) = atoi(buf);

heap->size++;

i++;

}

/* size is off by one */

heap->size--;

/* todo - sort data with a heap sort */

/* build heap */

/* sort is in-place -- delete root and place at end of array */

/* send data to stdin -- if you correctly built a heapsort

* this will print the data in ascending order */

for (i = 0; i size; i++) {

printf("%d ", *(heap->data + i));

}

/* cleanup */

free(heap->data);

free(heap);

fclose(fp);

return 0;

}

Problem - Heapsort 2. Write an integer heapsort program. The program grand generates random integers one per line. The heap program takes an integer data file (one integer per line) and sorts it using a heapsort with a max heap. The files grand.c, random.c, random.h and heap.c are provided to help get you started grand.c is a complete program, you just have to compile and run it to create integer data sets that you feed the heap program to sort. heap.c is incomplete. heap.c currently reads in a file and dynamically allocates an array which holds the data of the file. Your task is to write the heapsort. You are not allowed to modify the structure heap t as it contains everything you need. Use its members in your code. Your first task is to build a heap and the second step is to delete the elements. You are creating a max heap. You are required to build and sort the heap using only the existing storage heap->data. That is, you build the heap and sort it in place. Important: do not allocate another array to build or to sort your heap as that is waste of storage space. Sample Input $ ./grand -n 5-m 3 -f data $ ./heap data Sample Output 0 1 1 1 2 Make sure you free all memory that is allocated. Check with valgrind