00 Sprint 12:05 PM 77%-, cs.utsa.edu CS 2123 Data Structures Recitation 3 Due Fr
ID: 3672064 • Letter: 0
Question
00 Sprint 12:05 PM 77%-, cs.utsa.edu CS 2123 Data Structures Recitation 3 Due Friday February 26 Difficulty(out of 5) 1. (100 pts) Write a program to read a two dimensional array from a file and compute the sum of the elemeuts in a rectangular area specified by the user efliciently in O(1) time without using loops Input file format is as follows. norcva Bocola rowo rou norova-1 Consider the following input file a.trt as an example 4 5 In this representation, cach element represents a single value and Ao0 is the top left entry in the matrix. To compute the sum of elements in a rectangular area in O(1) time, use a new representation where an element Ble] denotes the sum of all the elemenats Aly] wlere 0 si and 0 y : j. Convert the array read from the file into this representation, with this new representation the value of the array elements for the above array are as follows 12 3 45 24 6 8 10 3 6 9 12 15 4 8 12 16 20 Using this new representation the sum of a rectangular area can be computed without using a loop. Consider the diagram in Figure1. We are interested in Area As and this can be computed using Al-A2. A3As Try to find the expression to find the sum of elements in area A. Note that each entry BilD stores the su of al the eleents A here 0SISi and 0SSi Get the coordinates of a rectangular area from the user and compute the sum of the elements in that area using the above technique. Sample execution for the file a.tat is given belowExplanation / Answer
/*C program for max sum of rectangular table */ /*Inputs: */ /* - txt file for table */ /*Outputs: */ /* - Print to screen sum and right,left coordinates */ /*########################################################################### */ /*----------------------------------------------------------------------------*/ /* Includes */ /*----------------------------------------------------------------------------*/ #include /*----------------------------------------------------------------------------*/ /* Defines */ /*----------------------------------------------------------------------------*/ #define COL_COUNT 8 #define ROW_CAP 10 typedef struct{ int x; int y; } Point_t; typedef struct{ Point_t left_up; Point_t right_down; double sum; } Rectangle_t; /*########################################################################### */ /* Function Prototypes */ /*########################################################################### */ Point_t construct_point(int x, int y); Rectangle_t construct_rectangle(Point_t left_up, Point_t right_down); void print_rectangle(const Rectangle_t *rectangle); void getArray(FILE* inFile, double table[][COL_COUNT], int* nRow);/*Reads the table from a file into a 2D array*/ void getSum(double table[][COL_COUNT], Rectangle_t *rectangle);/*Returns the sum inside a given rectangular*/ Rectangle_t maxSumConstPoint(double table[][COL_COUNT], int nRow, Point_t left_up);/*Finds the rectangular left uppper point of which is specified having the max sum inside*/ Rectangle_t maxSumRec(double table[][COL_COUNT], int nRow);/*Finds the maximum sum of the rectangular*/ int main() { double table[ROW_CAP][COL_COUNT];/*define 2D array*/ FILE* inFile;/*define file*/ int nRow; double maxSum; int lUY, lUX, rDY, rDX; Rectangle_t rectangle; rectangle.left_up.x=0; rectangle.left_up.y=0; inFile=fopen("Table1.txt", "r");/*open file*/ getArray(inFile, table, &nRow);/*fill array*/ rectangle=maxSumConstPoint(table, nRow,rectangle.left_up);/*call function and return rectangle*/ print_rectangle(&rectangle);/*print rectangle*/ rectangle=maxSumRec(table, nRow);/*call function and return rectangle*/ print_rectangle(&rectangle);/*print rectangle*/ fclose(inFile);/*close file*/ return 0; } Point_t construct_point(int x, int y)/*construct the Point_t type elements*/ { Point_t point; point.x=x; point.y=y; return point; } Rectangle_t construct_rectangle(Point_t left_up, Point_t right_down)/*construct the Rectangle_t type elements*/ { Rectangle_t cons_rec; cons_rec.left_up=left_up; cons_rec.right_down=right_down; return cons_rec; } void print_rectangle(const Rectangle_t *rectangle)/*takes a rectangle pointer and prints all information about it in a reasonable format.*/ { printf("left_up=(y=%d,x=%d) right_down=(y=%d x=%d) sum= %lf ",rectangle-> left_up.y, rectangle->left_up.x,rectangle->right_down.y, rectangle->right_down.x, rectangle->sum); } /*Reads the table from a file into a 2D array*/ void getArray(FILE* inFile, double table[][COL_COUNT], int* nRow){ int row=0; int col; int status=EOF+1;/*Different from EOF*/ /*one more row will be read but the values will not be recorded into the table therefore, it is safe to use a table having just enough capasity to hold the data*/ while(status!=EOF){ for(col=0; colleft_up.y; rowright_down.y; ++row) for(col=rectangle->left_up.x; colright_down.x; ++col) sum+=table[row][col]; rectangle->sum=sum; } /*Finds the rectangular left uppper point of which is specified having the max sum inside*/ Rectangle_t maxSumConstPoint(double table[][COL_COUNT], int nRow, Point_t left_up){ int rDX; /*x coordinate of the right down corner of the rec*/ int rDY; /*y coordinate of the right down corner of the rec*/ int rightDownY,rightDownX; Point_t right_down; Rectangle_t rectangle,temp; /*initialize the rectangular with the one including only one point*/ double sum=table[left_up.x][left_up.y]; rightDownY=left_up.y; rightDownX=left_up.x; /*Try all feasible rectangulars by changing the right down corner*/ for(rDY=left_up.y; rDYRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.