Mulitple file compilation, etc. Notice that sset.c contains no main function. Th
ID: 669392 • Letter: M
Question
Mulitple file compilation, etc. Notice that sset.c contains no main function. This is because it is a set of utility functions (implementing a Sorted Set ADT). These functions can be used by "client" programs much in the same way that programs you've written use the standart C library functions. There are three files here: - sset.h defines the interface (functions) to the SSET ADT. It also has a typedef for SSET which is "incompletely specified" -- the actual struct is hidden in the file sset.c In principle, a client program only needs to know the set of functions available, not their actual implementation. - sset.c contains the actual implementations of the functions. Some of these are currently empty "stubs" which you are to complete. It also contains the specification of struct sset_struct referred to in the .h file. - toy.c is a trivial client program. You will write a similar program for testing pourposes. Compilation: Step 1: compile sset.c. Remember this does not become an executable. % gcc -c sset.c This produces an "object file" sset.o Step 2: % gcc toy.c sset.o -o toy This compiles the program toy.c and links it with the object file sset.o. It produces the executable toy.
#include "sset.h" #include "stdlib.h" #include "stdio.h" #define DEBUG struct sset_struct{ int val; struct sset_struct *next; }; /** * Function: sset_create * Status: DONE * Returns an empty set */ SSET *sset_create(){ return NULL; } /** * Function: sset_singleton * Status: DONE * Returns the set {x} */ SSET *sset_singleton(int x) { SSET *p; p = malloc(sizeof(SSET)); p->val = x; p->next = NULL; return p; } /** * Used for the sset_from_array function */ static int int_cmp(const void *a, const void *b) { int *pa = (int *)a; int *pb = (int *)b; return (*pa - *pb); } /** * Function: from_sorted_array (helper) * * Status: TODO * Parameters: * * a: the base address of an array of integers * n: the length of array a. * * Returns: * A sorted set populated with the n elements in the * given array. * * Precondition: array a[] is assumed to be sorted in * ascending order and have no duplicates. * * Requirement: linear time * Recommendation: recursion */ static SSET *from_sorted_array(int *a, int n) { } /** * Function: print_arr (helper) * * Description: helper function for debugging. */ static void print_arr(int *a, int n) { int i; printf("[ "); for(i=0; i<n; i++) printf("%i ", a[i]); printf("] "); } /** * Fuction: sset_from_array * * Status: DONE (but subroutine from_sorted_array needs * implementation) * * Parameters: * * a: base address of an array of integers * n: array length * * Returns the SSET * representation of the elements. * * Notes: given array not necessarily sorted and * may have duplicates. */ SSET *sset_from_array(int *a, int n) { int *b, *c; int i, j, x; SSET *s; b = malloc(n*sizeof(int)); c = malloc(n*sizeof(int)); for(i=0; i<n; i++) b[i] = a[i]; qsort(b, n, sizeof(int), int_cmp); i=0; j=0; // copy elements w/o duplicates from b[] to c[] (retaining // sorted order while(i < n) { x = b[i]; c[j] = x; i++; j++; while(i < n && b[i] == x) i++; } #ifdef DEBUG printf("---start debug--- "); printf("sset_from_array: "); printf(" a: "); print_arr(a, n); printf(" b: "); print_arr(b, n); printf(" c: "); print_arr(c, j); printf("---end debug--- "); #endif s = from_sorted_array(c, j); free(b); free(c); return s; } /** * Function: sset_free * Status: TODO * * Description: de-allocates all memory associated with the * parameter set. * * Requirements: linear time * recursive */ void sset_free(SSET *s) { } /** * Function: sset_isempty * Status: DONE * * Description: self-evident */ int sset_isempty(SSET *s) { return s==NULL; } /** * Function: sset_size * Status: DONE * * Description: returns the cardinality of the * given set. */ int sset_size(SSET *s) { if(s == NULL) return 0; return 1 + sset_size(s->next); } /** * Function: sset_display * Status: DONE * * Description: prints the contents of the set s in * curly-brace style. */ void sset_display(SSET *s) { printf(" { "); while(s != NULL) { printf("%i ", s->val); s = s->next; } printf("} "); } /** * Function sset_contains * Status: TODO * * Description: Returns 0 or 1 accordingly * * Requirement: linear time * Recommendation: recursion */ int sset_contains(SSET *s, int x) { } /** * Function: sset_clone * Status: DONE * * Description: creates and returns a clone of the set s. * Afterwards, there are two distinct sets which happen * to have the same contents. */ SSET *sset_clone(SSET *s) { SSET *p; if(s == NULL) return NULL; p = malloc(sizeof(struct sset_struct)); p->val = s->val; p->next = sset_clone(s->next); return p; } /** * Function: sset_union * Status: DONE * * Description: * * self evident (?) */ SSET *sset_union(SSET *a, SSET *b) { SSET *p; if(a == NULL) return sset_clone(b); if(b == NULL) return sset_clone(a); p = malloc(sizeof(SSET)); if(a->val < b->val){ p->val = a->val; p->next = sset_union(a->next, b); } else if(a->val > b->val){ p->val = b->val; p->next = sset_union(a, b->next); } else { p->val = a->val; p->next = sset_union(a->next, b->next); } return p; } /** * Function: sset_intersection * Status: TODO * * Description: returns a new sorted set which is the * intersection of the given sets a and b. * * Requirements: linear time * recursive */ SSET *sset_intersection(SSET *a, SSET *b) { return NULL; // placeholder } /** * Function: sset_diff * Status: TODO * * Description: constructs and returns the difference * of set a with set b. * Recall that A - B = {x in A s.t. x NOT-IN B} * * Example: {3, 7, 11, 14} - {3, 5, 11, 20} = {7, 14} * * Requirements: linear time * recursive * */ SSET *sset_diff(SSET *a, SSET *b) { return NULL; } /** * Function sset_toarray * Status: TODO * Description: allocates and returns an array containing the * elements of the given set. * * Requirement: linear time */ int *sset_toarray(SSET *a) { return NULL; } /** * Function: sset_cmp * Status: TODO * * Compares sets a and b lexicographically (essentially like alphabetical). * Sets a and b are given via void pointers instead of SSET pointers so the * function can be utilized by qsort * * If "a < b", a negative number is returned. * if "a > b", a positive number is returned. * if a and b are identical, zero is returned. * * Lex rules: * The empty set precedes all other sets * For non-empty A={a0, ...}, B={b0, ...}, compare a0 and b0 * * - if a0 != b0 set with smallest first elem "wins" * - otherwise, compare A-{a0} with B-{b0} * * Example: * A = {2, 3, 5, 8, 10, 11} * B = {2, 3, 5, 7, 1000, 2000, 30000} * * we have ties on frst 3 elements; then 7<8 so B < A. * * Example: * A = {2, 3, 5} * B = {2, 3, 5, 7, 1000 } * * Again, ties on first three elements; then we are comparing {} with * {7, 1000} so A < B * * Note: you will use this function to complete the sset_sort_sets * function (which will use qsort). * * Requirements: linear time * recursive */ int sset_cmp(const void *a, const void *b){ return 0; // placeholder } /** * Function: sset_sort_sets * Status: TODO * Description: Takes an array of sets (array element type: * SSET *) and sorts the sets according to the lexicographic * rules of the sset_cmp function. * * This should be a very short function!! It really just act as * a "wrapper" function which calls the qsort library routine. * * Hint: you need to get sset_cmp working first */ void sset_sort_sets(SSET * sets[], int n) { } // File: sset.h // Note: struct sset_struct is "hidden" in // sset.c typedef struct sset_struct SSET; /** * Function: sset_create * Status: DONE * Returns an empty set */ extern SSET *sset_create(); /** * Function: sset_singleton * Status: DONE * Returns the set {x} */ extern SSET *sset_singleton(int x); /** * Fuction: sset_from_array * * Status: DONE (but subroutine from_sorted_array needs * implementation) * * Parameters: * * a: base address of an array of integers * n: array length * * Returns the SSET * representation of the elements. * * Notes: given array not necessarily sorted and * may have duplicates. */ extern SSET *sset_from_array(int *a, int n); /** * Function: sset_isempty * Status: DONE * * Description: self-evident */ extern int sset_isempty(SSET *s); /** * Function: sset_size * Status: DONE * * Description: returns the cardinality of the * given set. */ extern int sset_size(SSET *s); /** * Function: sset_display * Status: DONE * * Description: prints the contents of the set s in * curly-brace style. */ extern void sset_display(SSET *s); /** * Function sset_contains * Status: TODO * * Description: Returns 0 or 1 accordingly * * Requirement: linear time * Recommendation: recursion */ extern int sset_contains(SSET *s, int x); /** * Function: sset_clone * Status: DONE * * Description: creates and returns a clone of the set s. * Afterwards, there are two distinct sets which happen * to have the same contents. */ extern SSET *sset_clone(SSET *s); /** * Function: sset_free * Status: TODO * * Description: de-allocates all memory associated with the * parameter set. * * Requirements: linear time * recursive */ extern void sset_free(SSET *s); /** * Function: sset_union * Status: DONE * * Description: * * self evident (?) */ extern SSET *sset_union(SSET *a, SSET *b); /** * Function: sset_intersection * Status: TODO * * Description: returns a new sorted set which is the * intersection of the given sets a and b. * * Requirements: linear time * recursive */ extern SSET *sset_intersection(SSET *a, SSET *b); /** * Function: sset_diff * Status: TODO * * Description: constructs and returns the difference * of set a with set b. * Recall that A - B = {x in A s.t. x NOT-IN B} * * Example: {3, 7, 11, 14} - {3, 5, 11, 20} = {7, 14} * * Requirements: linear time * recursive * */ extern SSET *sset_diff(SSET *a, SSET *b); /** * Function sset_toarray * Status: TODO * Description: allocates and returns an array containing the * elements of the given set. * * Requirement: linear time */ extern int *sset_toarray(SSET *a); /** * Function: sset_cmp * Status: TODO * * Compares sets a and b lexicographically (essentially like alphabetical). * * If "a < b", a negative number is returned. * if "a > b", a positive number is returned. * if a and b are identical, zero is returned. * * Lex rules: * The empty set precedes all other sets * For non-empty A={a0, ...}, B={b0, ...}, compare a0 and b0 * * - if a0 != b0 set with smallest first elem "wins" * - otherwise, compare A-{a0} with B-{b0} * * Example: * A = {2, 3, 5, 8, 10, 11} * B = {2, 3, 5, 7, 1000, 2000, 30000} * * we have ties on frst 3 elements; then 7<8 so B < A. * * Example: * A = {2, 3, 5} * B = {2, 3, 5, 7, 1000 } * * Again, ties on first three elements; then we are comparing {} with * {7, 1000} so A < B * * Note: you will use this function to complete the sset_sort_sets * function (which will use qsort). * * Requirements: linear time * recursive */ extern int sset_cmp(const void *set_a, const void *set_b); /** * Function: sset_sort_sets * Status: TODO * Description: Takes an array of sets (array element type: * SSET *) and sorts the sets according to the lexicographic * rules of the sset_cmp function. * * This should be a very short function!! It really just act as * a "wrapper" function which calls the qsort library routine. * * Hint: you need to get sset_cmp working first */ extern void sset_sort_sets(SSET * sets[], int n); extern void sset_sort_sets(SSET * sets[], int n); #include "sset.h" int main(){ SSET *s; int a[] = {2, 8, 1, 3, 1, 8, 0, 4}; s = sset_from_array(a, 8); }
Explanation / Answer
toy.c
#include "sset.h"
#include <stdlib.h>
#include <stdio.h>
int main(){
SSET *s1, *s2, *s3, *s4;
int n, *c;
int a[] = {2, 8, 1, 3, 1, 8, 0, 4};
int b[] = {5, 4, 3, 2, 1, 0, 9, 8, 7, 6};
int d[] = {30, 4, 13, 2, 6, 47, 345, 5};
printf("Sorting... ");
s1 = sset_from_array(a, 8);
s2 = sset_from_array(b, 10);
s4 = sset_from_array(d, 8);
printf("sset_intersection ");
sset_display(s2);
sset_display(s4);
s3 = sset_intersection(s2, s4);
sset_display(s3);
printf("comparing... ");
if(sset_contains(s1, 3)) {
sset_display(s1);
c = sset_toarray(s2);
n = 10;
}
else {
sset_display(s2);
c = sset_toarray(s1);
n = 6;
}
printf("freeing... ");
sset_free(s2);
printf("sset_from_array ");
s3 = sset_from_array(c, n);
sset_display(s3);
sset_display(s1);
printf("sset_diff ");
s2 = sset_diff(s1, s3);
sset_display(s2);
printf("sset_cmp ");
s3 = s2;
s2 = s1;
s1 = s3;
int x = sset_cmp(s1, s2);
if(x == 1) {
printf("s1:");
sset_display(s1);
printf("is larger. ");
}
else if(x == -1) {
printf("s2:");
sset_display(s2);
printf("is larger. ");
}
else {
printf("The sets are equal. ");
}
return 0;
}
sset.h
// Note: struct sset_struct is "hidden" in
// sset.c
typedef struct sset_struct SSET;
/**
* Returns an empty set
* DONE
*/
extern SSET *sset_create();
/**
* Returns a set containing just x.
* DONE
*/
extern SSET *sset_singleton(int x);
/**
* takes an array of integers in arbitrary order (and
* maybe containing duplicates) and returns an SSET
* of the set
* sets *a and *b;
* sets a and b are unchanged.
* TODO: function complete but you have to write
* helper function from_sorted_array()
*/
extern SSET *sset_from_array(int *a, int n);
/**
* DONE
*/
extern int sset_isempty(SSET *s);
/**
* DONE
*/
extern int sset_size(SSET *s);
/**
* DONE
*/
extern void sset_display(SSET *s);
/*
* TODO
*/
extern int sset_contains(SSET *s, int x);
/*
* TODO
*/
extern void sset_free(SSET *s);
/**
* returns a sorted set representing the UNION of
* sets *a and *b;
* sets a and b are unchanged.
* DONE
*/
extern SSET *sset_union(SSET *a, SSET *b);
/**
* TODO
* returns a sorted set representing the INTERSECTION of
* sets a and b;
* sets a and b are unchanged.
*/
extern SSET *sset_intersection(SSET *a, SSET *b);
/**
* TODO
* returns a sorted set representing the set DIFFERENCE of
* a - b (the set of elements in *a which are NOT in *b)
* sets a and b are unchanged.
*
* Example: {3, 7, 11, 14} - {3, 5, 11, 20} = {7, 11}
*
*/
extern SSET *sset_diff(SSET *a, SSET *b);
/**
* TODO
* allocates and returns an array containing the elements of *a
* in sorted order.
*/
extern int *sset_toarray(SSET *a);
/**
* TODO
* Compares sets a and b "lexicographically" and returns
* a negative number if "a < b";
* a positive number if "a > b"
* zero if they are identical
*
*/
extern int sset_cmp(SSET *a, SSET *b);
sset.c
#include "sset.h"
#include "stdlib.h"
#include "stdio.h"
#define DEBUG
struct sset_struct{
int val;
struct sset_struct *next;
};
/**
* DONE
* Returns an empty set
*/
SSET *sset_create(){
return NULL;
}
SSET *sset_singleton(int x) {
SSET *p;
p = malloc(sizeof(SSET));
p->val = x;
p->next = NULL;
return p;
}
/**
* Used by qsort
*/
static int int_cmp(const void *a, const void *b) {
int *pa = (int *)a;
int *pb = (int *)b;
return (*pa - *pb);
}
/**
* TODO
* Requirement: linear time
* Recommendation: recursion
*/
static SSET *from_sorted_array(int *a, int n) {
SSET *s = sset_singleton(a[0]);
if(a[0] == a[n-1]) {
return s;
}
else {
s->next = from_sorted_array(&a[1],n-1);
return s;
}
}
static void print_arr(int *a, int n) {
int i;
printf("[ ");
for(i=0; i<n; i++)
printf("%i ", a[i]);
printf("] ");
}
SSET *sset_from_array(int *a, int n) {
int *b, *c;
int i, j, x;
SSET *s;
b = malloc(n*sizeof(int));
c = malloc(n*sizeof(int));
for(i=0; i<n; i++)
b[i] = a[i];
qsort(b, n, sizeof(int), int_cmp);
i=0; j=0;
// copy elements w/o duplicats from b[] to c[] (retaining
// sorted order
while(i < n) {
x = b[i];
c[j] = x;
i++; j++;
while(i < n && b[i] == x)
i++;
}
#ifdef DEBUG
printf("---start debug--- ");
printf("sset_from_array: ");
printf(" a: ");
print_arr(a, n);
printf(" b: ");
print_arr(b, n);
printf(" c: ");
print_arr(c, j);
printf("---end debug--- ");
#endif
s = from_sorted_array(c, j);
free(b);
free(c);
return s;
}
/**
* TODO
* Requirements: linear time
* recursive
*/
void sset_free(SSET *s) {
if(s->next != NULL) {
sset_free(s->next);
s->next = NULL;
}
free(s);
}
/**
* DONE
*/
int sset_isempty(SSET *s) {
return s==NULL;
}
/**
* DONE
*/
int sset_size(SSET *s) {
if(s == NULL) return 0;
return 1 + sset_size(s->next);
}
/**
* DONE
*/
void sset_display(SSET *s) {
printf(" { ");
while(s != NULL) {
printf("%i ", s->val);
s = s->next;
}
printf("} ");
}
/**
* TODO
* Returns 0 or 1 accordingly
* Requirement: linear time
* Recommendation: recursion
*/
int sset_contains(SSET *s, int x) {
if(s->val == x) {
return 1;
}
else
{
if(s->next != NULL) {
return sset_contains(s->next, x);
}
else {
return 0;
}
}
}
/**
* DONE
*/
SSET *sset_clone(SSET *s) {
SSET *p;
if(s == NULL)
return NULL;
p = malloc(sizeof(struct sset_struct));
p->val = s->val;
p->next = sset_clone(s->next);
return p;
}
/**
* DONE
*/
SSET *sset_union(SSET *a, SSET *b) {
SSET *p;
if(a == NULL)
return sset_clone(b);
if(b == NULL)
return sset_clone(a);
p = malloc(sizeof(SSET));
if(a->val < b->val){
p->val = a->val;
p->next = sset_union(a->next, b);
}
else if(a->val > b->val){
p->val = b->val;
p->next = sset_union(a, b->next);
}
else {
p->val = a->val;
p->next = sset_union(a->next, b->next);
}
return p;
}
/**
* TODO
* Requirements: linear time
* recursive
*/
SSET *sset_intersection(SSET *a, SSET *b) {
SSET *p;
if(a == NULL || b == NULL) {
return NULL;
}
p = malloc(sizeof(SSET));
if(a->val > b->val) {
p = sset_intersection(a, b->next);
}
else if(b->val > a->val) {
p = sset_intersection(a->next, b);
}
else {
p->val = a->val;
p->next = sset_intersection(a->next, b->next);
}
return p;
}
/**
* TODO
* Requirements: linear time
* recursive
*
* A - B = {x in A s.t. x NOT-IN B}
*
* Example: {3, 7, 11, 14} - {3, 5, 11, 20} = {7, 11}
*/
SSET *sset_diff(SSET *a, SSET *b) {
SSET *p;
if(a == NULL) {
return sset_clone(b);
}
if(b == NULL) {
return sset_clone(a);
}
p = malloc(sizeof(SSET));
if(a->val < b->val) {
p->val = a->val;
p->next = sset_diff(a->next, b->next);
}
else if(b->val < a->val) {
p->val = b->val;
p->next = sset_diff(a, b->next);
}
else {
p = sset_diff(a->next, b->next);
}
return p;
}
/**
* TODO
* allocates and returns an array containing the elements of *a
* in sorted order.
* Requirement: linear time
*/
int *sset_toarray(SSET *a) {
int i, n;
n = sset_size(a);
int *b = malloc(n * sizeof(int));
for(i = 0; i < n; i++) {
b[i] = a->val;
a = a->next;
}
return b;
}
int sset_cmp(SSET *a, SSET *b){
if(a == NULL && b == NULL) {
return 0;
}
else if(a == NULL && b != NULL) {
return -1;
}
else if(a != NULL && b == NULL) {
return 1;
}
if(a->val > b->val) {
return 1;
}
else if(b->val > a->val) {
return -1;
}
else {
return sset_cmp(a->next, b->next);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.