Makefile, Modular Design, File I/O, Pointers, Dynamic Memory Allocation, Command Line Interpretation
This is your first programming project. It should be implemented in C++, on a Linux platform such as general.asu.edu. Your program will be graded on Gradescope, which uses a Linux platform. You will perform modular design, provide a Makefile to compile various modules to generate the executable le named run. Among other things, you need to have
1. a main program, which coordinates all other modules;
2. a module that provides utility services including command line interpretation;
3. a module that implements the heap data structure (not all heap functions yet);
4. a Make le which compiles all modules and link them into the executable.
For each module other than the main program, you should have a header le which specifies the data structures and the prototypes of the functions in the module, and an implementation le which implements all of the functions specified in the header le. All programs will be compiled and graded on Gradescope. If your program works well on general.asu.edu, there should not be much problems. You will need to submit it electronically on Gradescopevia the link on Canvas. Submission details have been posted as of 02/23/2021. If your program does not compile and work on Gradescope, you will receive 0 on this project.
Data Types Definition
You need to define the following data types.
ELEMENT is a struct that contains aeld named key, which is of type int. In later assign-ments, you will add other elds to ELEMENT, without having to change the functions. Notethat ELEMENT should not be of type int.
HEAP is a data type that contains three elds named capacity (of type int), size (of type int), and H (of type **ELEMENT). H will be pointing to an array of capacity + 1 of pointers of type *ELEMENT. Note that the size of HEAP should be equal to 12, regardless of the capacity or the size of the heap. In other words, sizeof(HEAP)should always return12.
Functions Implementation
The functions that you are required to implement are:
Initialize(n) which creates an object of type HEAP with capacity n, size 0, and H points to a dynamically allocated array of n + 1 pointers. It then returns a pointer to this object. This function requires you to perform dynamic memory allocation, given the demand n.
printHeap(heap) which prints out the information of the heap pointed to by heap, including capacity, size, and the key elds of the elements in the array with index going from 1 to size.
Module Implementation
You should implement a module that takes the following commands from stdin and feeds to the main program:
S C n R W P
The main program should react to each of the above command in the following way.
S: On reading S, the program
1. Writes the following line to stdout:
COMMAND: S
where S is the character S.
2. Stops.
C: On reading C n, the program
1. Writes the following line to stdout: COMMAND: C n
where C is the character C and n is replaced by the value of n.
2. Calls a function in the heap module to create a heap with capacity equal to n and size equal to 0, and return a pointer to this heap object to the caller.
3. Waits for the next command from stdin.
R: On reading R, the program
1. Writes the following line to stdout:
COMMAND: R
where R is the character R.
2. Opens the le "HEAPinput.txt" in read mode. If the le is not opened successfully, writes the following line to stdout:
Error: cannot open file for reading and waits for the next command from stdin.
3. Reads in the rst integer n from the le opened.
If heap is NULL or heap->capacity is smaller than n, writes the following line to stdout: Error: heap overflow
and waits for the next command from stdin.
4. Reads in the next n integers key1; key2, : : :, keyn from the le, dynamically allocates memory for an ELEMENT, sets it key to keyj , and let heap->H[j] points to this ELEMENT, for j = 1; 2; : : : ; n.
5. Waits for the next command from stdin.
P: On reading P, the program
1. Writes the following line to stdout:
COMMAND: P
where P is the character P.
2. If heap is NULL, writes the following line to stdout: Error: heap is NULL
and waits for the next command from stdin.
3. Writes the information of the heap pointed to by heap to stdout. Refer to the posted test cases for the output format.
4. Waits for the next command from stdin.
W: On reading W, the program
1. Writes the following line to stdout:COMMAND: W:
where W is the character W.
2. Opens the le "HEAPout.txt" in write mode. If the le is not opened successfully, writes the following line to stdout:
Error: cannot open file for writing and waits for the next command from stdin.
3. If heap is NULL, writes the following line to stdout: Error: heap is NULL
and waits for the next command from stdin.
4. Writes the information of the heap pointed to by heap to the le "HEAPoutput.txt". "HEAPoutput.txt" should have exactly the same format as "HEAPinput.txt".
5. Waits for the next command from stdin.
The le HEAPinput.txt is a text le. The rst line of the le contains an integer n, which indicates the number of array elements. The next n lines contain n integers, one integer per line. These integers are the key values of the n array elements, from the rst element to the nth element. Refer to the posted test cases for the exact format of "HEAPinput.txt".
Requirements
(5 pts) You should provide a Makefile that can be used to compile your project on Gradescope. The executable le should be named run. If your program does not pass this step, you will receive 0 on this project.
(5 pts) Modular design: You should have ale named util.cpp and its corresponding header le util.h, where the header le de nes the prototype of the functions, and the implementation le implements the functions. You should have a le named heap.cpp and its corresponding header le heap.h. This module implements (some of) the heap functions.
(5 pts) Documentation: You should provide a README.txtle that clearly species the le and line numbers where dynamic memory allocation is used.
(5 pts) Your program should use dynamic memory allocation correctly. You should document thisclearly both in the README.txt le and in the implementation le(s), indicating the le name(s) and line number(s) where dynamic memory allocation is implemented.
(50 pts) You will earn 5 points for each of the 10 posted test cases your program passes on Gradescope.
(10 pts) You will earn 5 points for each of the 2 unposted test cases your program passes on Gradescope.
NOTE: For test case #5, the le output.txt was produced by the following bash script:
./run < input.txt > output.txt
cat HEAPoutput.txt >> output.txt
We use this to check the content of your output le.
You should try to make your program as robust as possible. A basic principle is that your program can complain about bad input, but should not crash.
As an aid, the following is a partial program for reading in the commands from the keyboard.
You need to understand it and to expand it.
typedefstruct TAG_ELEMENT{
int key;
}ELEMENT;
typedef ELEMENT *ElementT;
typedefstruct TAG_HEAP{
int capacity; /* max size of the heap */
int size; /* current size of the heap */
ElementT *H; /* pointer to pointers to elements */ }HEAP;
#include "util.h"
//=============================================================================
intnextCommand(int *n, int *f)
{
char c;
while(1){
scanf("%c", &c);
if (c == ’ ’ || c == ’\t’ || c == ’\n’){ continue;
}
if (c == ’S’){
break;
}
if (c == ’C’ || c == ’c’){
scanf("%d", n);
break;
}
if (...){
...
}
}
return c;
}
//=============================================================================
The following is a partial program that calls the above program.
//=============================================================================
#include
#include
#include "util.h"
int main()
{
// variables for the parser...
char c; inti, v; while(1){
c = nextCommand(&n, &f); switch (c) {
case ’s’:
case ’S’: printf("COMMAND: %c\n", c); exit(0);
case ’c’:
case ’C’: printf("COMMAND: %c %d\n", c, n); heap = heapInit(n);
break;
case ’r’:
case ’R’: printf("COMMAND: %c\n", c);
ifile = fopen("HEAPinput.txt", "r");
if (!ifile){
}
fscanf(ifile, "%d", &n);
...
default: break;
}
}
exit(0);
}
//=============================================================================
The following is a partial Make le.
EXEC = run
CC = g++
CFLAGS = -c -Wall
# $(EXEC) has the value of shell variable EXEC, which is run.
# run depends on the files main.outil.oheap.o
$(EXEC) :main.outil.oheap.o
# run is created by the command g++ -o run main.outil.o
# note that the TAB before $(CC) is REQUIRED...
$(CC) -o $(EXEC) main.outil.oheap.o
# main.o depends on the files main.h main.cpp main.o:main.h main.cpp
# main.o is created by the command g++ -c -Wall main.cpp
# note that the TAB before $(CC) is REQUIRED...
$(CC) $(CFLAGS) main.cpp
util.o :util.h util.cpp
$(CC) $(CFLAGS) util.cpp
heap.o :heap.h heap.cpp
$(CC) $(CFLAGS) heap.cpp
clean :
rm *.o
C++ Code Solution
/*
* Project1.cpp
*
* Created on: Mar 1, 2021
* Author: thanh
*/
#include
#include "main.h"
using namespace std;
int main(intargc, char **argv) {
// variable for the parser...
int c;
inti, n, f, key, j;
HEAP *heap = NULL;
FILE *ifile, *ofile;
intisrunning = 1;
while (isrunning) {
c = nextCommand(&n, &f);
switch (c) {
case 's':
case 'S':
fprintf(stdout, "COMMAND: %c\n", c);
exit(EXIT_SUCCESS);
break;
case 'c':
case 'C':
fprintf(stdout, "COMMAND: %c %d\n", c, n);
heap = initialize(n);
break;
case 'r':
case 'R':
fprintf(stdout, "COMMAND: %c\n", c);
ifile = fopen("HEAPinput.txt", "r");
if (!ifile) {
fprintf(stdout, "Error: cannot open file for reading\n");
break;
}
fscanf(ifile, "%d", &n);
if(!heap || heap->capacity < n) {
fprintf(stdout, "Error: heap overflow\n");
break;
}
// Read next key from file
j = 1;
while(fscanf(ifile, "%d", &key) && j <= n) {
// Dynamic allocate the ELEMENT
heap->H[j] = (ELEMENT*)calloc(1, sizeof(ELEMENT));
if(!heap->H[j]) {
fprintf(stderr, "CAN NOT ALLOCATED MEMORY!\n");
break;
}
heap->H[j++]->key = key;
heap->size++;
}
fclose(ifile);
break;
case 'w':
case 'W':
// Handler for W command
fprintf(stdout, "COMMAND: %c\n", c);
ofile = fopen("HEAPout.txt", "w");
if(!ofile) {
fprintf(stdout, "Error: cannot open file for writing\n");
break;
}
if(!heap) {
fprintf(stdout, "Error: heap is NULL");
}
// Write to file
// Write the n first.
fprintf(ofile, "%d\n", heap->size);
// Write the key
for(i = 1; i<= heap->size; i++) {
fprintf(ofile, "%d\n", heap->H[i]->key);
}
fclose(ofile);
break;
case 'p':
case 'P':
// Handle for P command
fprintf(stdout, "COMMAND: %c\n", c);
if(!heap) {
fprintf(stdout, "Error: heap is NULL\n");
break;
}
printHeap(heap);
break;
case EOF:
isrunning = 0;
break;
default:
break;
}
}
if(heap) {
for(i = 0; i< heap->capacity; i++) {
free(heap->H[i]);
}
free(heap->H);
free(heap);
}
return 0;
}