CSCI2100F/ESTR2102B 数据结构算法-526互联

CSCI2100F/ESTR2102B Data Structures (Spring 2023)
Lab Assignment #7
Schedule: Week 11
1. To familiarize the implementations of heap and disjoint set
2. To apply heap in different problems
Submission guideline (Online judge)
1. Name your program(s) according to the question (e.g. lab7-q1.c)
2. Write your programs under “Desktop/mywork/lab7”
3. Duplicate your programs before submission
4. Submit your programs under “Desktop/submission/lab7”
5. Check the submission folder for your grading report (Be patience, auto grading need
some time. You can F5 to update the browser.)
6. Resubmit your work if you cannot receive full score
7. Visit “Other Locations/Computer/2100share/lab7” in the VM to download the
starting programs
8. Version of the gcc compiler in the online judge: C99
9. Deadline: 28th March, 2023 (Tuesday)
10. Late penalty is 30%, and the judge for lab 7 is closed on 4th April, 2023 (Tuesday).
11. There will be 5 late days in total for all 10 labs. The late days will be used automatically
if your submission is beyond the deadline and achieve a better score.
Grading scheme (CSCI2100F)
1. Total score is 100%
2. The weighting of each question is marked on the question
3. Bonus score is at most 13%
Bonus score: Extra question (13%)
○ Mark given according to the number of correct answers of the question (13%)
Requirements for ESTR2102B: Non-zero scores for the extra question
Useful commands
1. Compile your program
gcc -o prog labX-q1.c labX-q1-tc1.c
gcc -o prog labX-q3.c
2. Run the program with arguments
./prog inputfile.txt outputfile.txt
1
Question 1: Max-Heap (40%)
You are going to implement the heap abstract data type using array implementation. The
header file “lab7-q1.h” and the description of the functions are as follows.
Your program should not contain main(). Name your program as “lab7-q1.c”.
// lab7-q1.h
// Cannot modify this file
typedef struct node {
int key; /* key of a node */
char value[100]; /* value of a node */
} Node;
typedef struct heap{
int maxsize; /* maximum size of the heap */
int count; /* number of nodes stored in the heap */
Node *data; /* storage of the heap */
}MaxHeap;
/* Init an empty heap with a given size #1 #2 */
void maxheap_init(MaxHeap **H, int maxsize);
/* Heapify a max-heap based on the input array S with size S_size */
/* The root of heap is stored at H->data[1] #1 #3 #4 */
/* init the max-heap based on the input S */
void maxheap_heapify(MaxHeap **H, Node* S, int S_size);
/* Insert the (key,value) pair into the max-heap H #1 #5 #6 #7 */
/* If key exist in the heap, update the value */
/* If key does not exist in the heap and heap is not full, */
/* perform the insertion of a max-heap */
/* If key does not exist in the heap but heap is full, do nothing */
/* Return 1 if insertion is successful */
/* Return 2 if update of value is successful */
/* Return 0 if heap is full and insertion cannot be proceeded */
int maxheap_insert(MaxHeap *H, int key, char* value);
/* Delete root of the max-heap #1 #8 #9 */
/* Update the heap accordingly */
/* Return the (key,value) of the deleted root */
/* Return NULL if the heap is empty */
Node *maxheap_delete(MaxHeap *H);
/* Free the max-heap #1 #10 */
/* Assign NULL pointer to *H */
void maxheap_free(MaxHeap **H);
2
Sample Test Case (lab7-q1-tc1.c):
// This file is named as lab7-q1-tc1.c
#include"lab7-q1.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
int main(int argc, char *argv[]){
FILE *fout;
MaxHeap *H;
Node list[5] = {1, "5", 2, "4", 3, "3", 4, "2", 5, "1"};
Node ans1[5] = {5, "1", 4, "2", 3, "3", 1, "5", 2, "4"};
Node ans2[5] = {4, "2", 2, "4", 3, "3", 1, "5"};
Node ans3[5] = {10, "0", 4, "2", 3, "3", 1, "5", 2, "4"};
int listsize = 5;
fout = fopen(argv[1], "w");
/* default, your program is correct */
isCorrect = 1;
/* check the function, maxheap_init() */
H = (MaxHeap*)1;
maxheap_init(&H, 15);
/* if H is not initialized appropriately */
if (H == NULL) {
isCorrect = 0;
} else if (H->maxsize != 15 || H->count != 0 || H->data == NULL) {
isCorrect = 0;
}
// output "WA" if the maxheap_init() is not correctly implemented
if (isCorrect != 1) {
fprintf(fout, "Heap: Wrong Answer\n");
fclose(fout);
return 0;
}
maxheap_heapify(&H, list, listsize);
for (i = 0; i < 5; i++) {
if (H->data[i+1].key != ans1[i].key) isCorrect = 0;
if (strcmp(H->data[i+1].value, ans1[i].value) != 0)
isCorrect = 0;
}
/* output "WA" if the maxheap_heapify() is not correctly
implemented */
if (isCorrect != 1) {
3
fprintf(fout, "Heap: Wrong Answer\n");
fclose(fout);
return 0;
}
Node *tmp = maxheap_delete(H);
if (tmp->key != 5 || strcmp(tmp->value, "1") != 0) isCorrect = 0;
for (i = 0; i < 4; i++) {
if (H->data[i+1].key != ans2[i].key) isCorrect = 0;
if (strcmp(H->data[i+1].value, ans2[i].value) != 0)
isCorrect = 0;
}
//output "WA" if the maxheap_delete() is not correctly implemented
if (isCorrect != 1) {
fprintf(fout, "Heap: Wrong Answer\n");
fclose(fout);
return 0;
}
maxheap_insert(H, 10, "0");
for (i = 0; i < 5; i++) {
if (H->data[i+1].key != ans3[i].key) isCorrect = 0;
if (strcmp(H->data[i+1].value, ans3[i].value) != 0)
isCorrect = 0;
}
maxheap_free(&H);
/* output "WA" if the maxheap_insert() or maxheap_free() is not
correctly implemented */
if (isCorrect == 1 && H == NULL) {
fprintf(fout, "Heap: Correct\n");
} else {
fprintf(fout, "Heap: Wrong Answer\n");
}
fclose(fout);
return 0;
}
4
Question 2: Disjoint Set (30%)
You are going to implement the disjoint set abstract data type using forest implementation.
The header file “lab7-q2.h” and the description of the functions are as follows.
Your program should not contain main().Name your program as “lab7-q2.c”.
// lab7-q2.h
// Cannot modify this file
typedef struct ds {
int size; /* size of disjoint set */
int *parent; /* parent of each element */
int *tree_size; /* size of a tree in the disjoint set */
} DS;
/* Init a disjoint set with a given size #1 #2 #3 */
/* All node should point to itself */
void ds_init(DS **S, int size);
/* Find the root of node x #1 #4 */
/* Path compression is needed */
/* Return the root of node x */
int ds_find_set(DS *S, int x);
/* Check if x and y belong to the same set #1 #5 */
/* Return 1 if they are belong to the same set */
/* Return 0 if they are not belong to the same set */
int ds_same_set(DS* S, int x, int y);
/* Union the set containing x and the set containing y #1 #6 #7 */
/* Put the set containing y as the subtree of the set of containing x */
/* You need to update tree_size */
void ds_union(DS *S, int x, int y);
/* Union the set containing x and the set containing y #1 #8 #9 */
/* Put the smaller set as the subtree of the larger set */
/* If both sets have the same set, put set containing y as the subtree
of set containing x */
/* Remember to update tree_size */
void ds_union_by_size(DS *S, int x, int y);
/* Free the disjoint set #1 #10 */
/* Assign NULL pointer to *S */
void ds_free(DS **S);
Sample Test Case (lab7-q2-tc1.c):
// This file is named as lab7-q2-tc1.c
#include"lab7-q2.h"
#include<stdio.h>
5
#include<stdlib.h>
#include<string.h>
#include<limits.h>
int main(int argc, char *argv[]){
FILE *fout;
DS *S;
int isCorrect, i;
fout = fopen(argv[1], "w");
/* default, your program is correct */
isCorrect = 1;
/* check the function, ds_init() */
S = (DS*)1;
ds_init(&S, 10);
/* if S is not initialized appropriately */
if (S == NULL) {
isCorrect = 0;
} else if (S->size != 10 || S->parent == NULL) {
isCorrect = 0;
} else for (i = 0; i < 10; i++) {
if (S->parent[i] != i) {
isCorrect = 0;
}
}
/* output "WA" if the ds_init() is not correctly implemented */
if (isCorrect != 1) {
fprintf(fout, "DS: Wrong Answer\n");
fclose(fout);
return 0;
}
ds_union(S, 1, 3);
ds_union(S, 2, 4);
result1 = ds_same_set(S, 1, 3);
result2 = ds_same_set(S, 1, 2);
result3 = ds_same_set(S, 2, 4);
if (result1 == 0 || result2 == 1 || result3 == 0) isCorrect = 0;
/* output "WA" if the ds_union() or ds_same_set() is not correctly
implemented */
if (isCorrect != 1) {
fprintf(fout, "DS: Wrong Answer\n");
fclose(fout);
return 0;
}
6
ds_union(S, 1, 5);
ds_union_by_size(S, 3, 4);
ds_union_by_size(S, 8, 3);
ds_union_by_size(S, 5, 3);
if (S->parent[1] != 1 || S->tree_size[1] != 6) isCorrect = 0;
ds_free(&S);
/* output "WA" if the ds_union_by_size() or ds_free() is not
correctly implemented */
if (isCorrect == 1 && S == NULL) {
fprintf(fout, "DS: Correct\n");
} else {
fprintf(fout, "DS: Wrong Answer\n");
}
fclose(fout);
return 0;
}
7
Question 3: Heap Sort (30%)
You are asked to sort a list of students in descending order. Output the results of
heapification, and the results of the heap after each delete_max().
Your program should read the input from the file, and output the answer to another file. The
first argument is the input file name, while the second argument is the output file name.
Name your program as “lab7-q3.c”.
Hint: Reuse the code in question 1.
Input file: First line shows an integer n (0 < n < 100), representing the number of students.
Following n line shows the list of students, in the format “<student ID> <Name of
student>”. You can assume student ID is a 10 digit number starting with 11, while the name
of the student consists of alphabets and space bars less than 99 characters.
Output file: First line shows the result of heap after heaplification. Following n-1 lines show
the results of the heap after each delete_max(). The output format of a student is “<student
ID>:<Name of student>”
Sample Input:
5
1155001234 Chan Tai Man
1155123456 Lily So
1155232323 Happy Wong
1155012012 Wong Tai Sin
1155171615 Chan Tai Man
Sample Output (Use two different colours to show different lines):
1155232323:Happy Wong 1155171615:Chan Tai Man 1155001234:Chan Tai Man
1155012012:Wong Tai Sin 1155123456:Lily So
1155171615:Chan Tai Man 1155123456:Lily So 1155001234:Chan Tai Man
1155012012:Wong Tai Sin
1155123456:Lily So 1155012012:Wong Tai Sin 1155001234:Chan Tai Man
1155012012:Wong Tai Sin 1155001234:Chan Tai Man
1155001234:Chan Tai Man
8
Question 4: Greatest Common Divisor Again? (Bonus 13%)
You are given array A. There are 4 types of operations associated with it:
1. 1 l r x: For each l ≤ i ≤ r, replace A[i] with the value of x.
2. 2 l r x: For each l ≤ i ≤ r, replace A[i] with the value of the gcd(A[i], x) function.
3. 3 l r: print the value of max A[i], where l ≤ i ≤ r.
4. 4 l r: print the value of A[l] + A[l+1] +...+ A[r]
A greatest common divisor (gcd(a, b)) of two positive integers a and b is equal to the biggest
integer d such that both integers a and b are divisible by d. Assume the index is 1-based.
You can assume 1 ≤ A[i] ≤ 10
9
.
Your program should read the input from the file, and output the answer to another file. The
first argument is the input file name, while the second argument is the output file name.
Name your program as “lab7-q4.c”.
Hint: This problem is about range updates and range queries on a segment tree.
Input file: The first line contains two space-separated integers n (1 ≤ n ≤ 100000) and m (1 ≤
m ≤ 100000) denoting the number of elements in array A and the number of queries
respectively. The second line contains n space-separated integers denoting the elements of
array A. Next m lines contain the description of the queries, one per line. Queries are
formatted the same way as in the problem statement above. It is guaranteed that 1 ≤ l ≤ r ≤
n.
Output file: For each type three and type four query, print the answer for this query in a
separate line.
Explanation:
Array before queries is [10,12,6,8]
Answer for queries 3 1 4 = 12, because max(10,12,6,8) = 12
Answer for queries 4 1 4 = 36, because 10 + 12 + 6 + 8 = 36
After queries-update 2 2 4 4 array is [10, 4, 2, 4]
Answer for queries 3 2 4 = 4, because max(4,2,4) = 4
After queries-update 1 1 4 2 array is [2, 2, 2, 2]
Answer for queries 4 1 4 = 36, because 2 + 2 + 2 + 2 = 8
WX：codehelp mailto: thinkita@qq.com