CIS2520 Data Structures
Assignment 4
Dr. Charlie Obimbo, Modified by Yukun Due: November 26, 2022
1 Heaps
1. (100%) Write a C program. It reads 200 2-digit integers from text file “f.dat” and stores the
integers in an a
ay of 20 rows and 10 columns. The program treats each row of the a
ay as
an object, with the sum of the first three integers being the key, and the other seven integers
eing the information content. The program then creates a heap with a node containing an
object. You are required to use an a
ay representation of heap, and apply the parental node
downheap algorithm in the a
ay representation. The program finally displays the heap as a
20× 10 a
ay, a row for an object.
2 Assignment 4 Guidelines
Assignment 4 is due on Nov 26, 2022.
• Write a makefile that can be used to generate executables, same as the one for Assignment 2.
• The information in readme file is the same as before. Other requirements are also the same.
• The file name is f.dat (can hard coding) and it contains exactly 200 2-digit integers (20 rows
and 10 columns).
Hints:
• The 2D a
ay can be considered as an extension of the 1D a
ay for representing heaps.
• The heap will contain a total of 20 objects.
• Each object holds a row of 10 integers.
• The first three integers are used to derive the key. The key is the sum of the first three
integers.
• The last seven integers are the content of the object. For example:
typedef struct Node{
int sum_key;
int key[3];
int content[7];
} node;
Due time: 11:59 pm Nov 26, 2022.
1
3 Test case
f.dat:
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
./A4
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
2
Explanation:
In test case f.dat:
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
Node.sum_key: XXXXXXXXXX)
After apply the parental node downheap algorithm:
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
3
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
Node.sum_key after downheap: XXXXXXXXXX)
4