Homework SourseQuestion In C Programming In mathematics a set is a colle Sa
Question: In C Programming: In mathematics, a set is a colle...
Save
In C Programming:
In mathematics, a set is a collection of distinct elements (say integer numbers). For example,
A={2, 5, 7} and B={3, 5, 8, 10} are two different sets. There are several basic operations for constructing new sets from given two sets, but let\'s just consider three basic ones:
C = union(A,B); ---> C = A B={2, 5, 7, 8, 10} C = intersection(A,B); ---> C = A B={5}
C = difference(A,B); ---> C = A-B = A \\ B ={2, 7} also aka. complement
You are asked to develop a set library (using two different representations: array and link list) and then implement a driver program that gets two sets and one of the above operation as a command to apply, then it prints the resulting set...
Developing set library: For interface, create an interface file set.h which contains boiler plate and the followings:
typedef int setElementT;
typedef struct setCDT *setADT;
setADT setNew(); /* create a new empty set */
void setFree(setADT S); /* free the space allocated for the set S */
int setInsertElementSorted(setADT S, setElementT E);
/* if not successful, return 0; otherwise, return the num of elements after the insertion. Also note that the elements might be given in different orders, but your function should always keep the set in a sorted manner after each insertion */
setADT setUnion(setADT A, setADT B);
/* returns a new set containing A B */
setADT setIntersection(setADT A, setADT B);
/* returns a new set containing A B */
setADT setDifference(setADT A, setADT B);
/* returns a new set containing A \\ B */
int setCardinality(setADT S);
/* return the number of elements in S */
void setPrint(setADT S, char *name);
/* print elements of S, A = {2, 5, 7} */
For implementation, you will be asked to have two different implementations:
(40pt) First implement set library as setArrayImp.c which uses a constant size array to store set elements (suppose max set size is 100). [hint: see ch2 slides 72-78 ]
(40pt) Second implement this library as setLinkedListImp.c which uses a dynamic single linked list to store set elements.
Develop a driver.c program and compile it with two different imp of set library (20 pt)
1. Create two sets called A and B.
2. Ask user to enter positive integers for set A (end input when user enters -1)
3. Ask user to enter positive integers for set B (end input when user enters -1)
4. In a loop 4.1. Ask user to enter a command:
4.2 If Q is entered, quit from this loop.
4.3 If U, I, or D is entered, compute set C as union, intersection, or difference. setPrint(A, \"A\"); setPrint(A, \"B\"); setPrint(C, \"C\"); print the number of elements in C setFree(C);
5. free A and B
Compile/execute driver.c with setArrayImp.c as well as setListImp.c
//no include files needed
Solution
Create set.h first with the following
typedef int setElementT;
typedef struct setCDT *setADT;
setADT setNew(); /* Creates a new empty set */
void setFree(setADT S); /* Frees the space allocated for the set S */
int setInsertElementSorted(setADT S, setElementT E);
/* if not successful, returns 0; otherwise, returns the num of elements after the insertion. This function will always keep the set in a sorted manner after each insertion */
setADT setUnion(setADT A, setADT B);
/* returns a new set containing A B */
setADT setIntersection(setADT A, setADT B);
/* returns a new set containing A B */
setADT setDifference(setADT A, setADT B);
/* returns a new set containing A \\ B */
int setCardinality(setADT S);
/* returns the number of elements in S */
void setPrint(setADT S, char *name);
/* prints elements of S, A = {2, 5, 7} */
Next, create setArrayImp.c
#include \"set.h\"
#include <malloc.h>
typedef struct setCDT{
setElementT *setElements;
setElementT maxSize;
setElementT setNumElements;
} *setADT;
setADT setNew(){
setADT newSet = (setADT)malloc(sizeof(struct setCDT));
newSet->maxSize = 100;
newSet->setElements = (int *)calloc(newSet->maxSize,sizeof(int));
newSet->setNumElements = 0;
return newSet;
}
void setFree(setADT S){
free(S);
}
int setInsertElementSorted(setADT S, setElementT E){
int cntr,temp1,temp2;
for(cntr = 0;cntr<S->setNumElements;cntr++){
if(S->setElements[cntr] >= E){
temp1 = S->setElements[cntr];
break;
}
}
S->setElements[cntr++] = E;
for(;cntr<=S->setNumElements;cntr++){
temp2 = S->setElements[cntr];
S->setElements[cntr] = temp1;
temp1 = temp2;
}
S->setNumElements++;
return S->setNumElements;
}
setADT setUnion(setADT A, setADT B){
int cntr1,cntr2;
setADT U = setNew();
for(cntr1=0,cntr2=0;cntr1<A->setNumElements && cntr2<B->setNumElements;){
if(A->setElements[cntr1] == B->setElements[cntr2]){
setInsertElementSorted(U,A->setElements[cntr1]);
cntr1++;
cntr2++;
}
else if(A->setElements[cntr1] < B->setElements[cntr2]){
setInsertElementSorted(U,A->setElements[cntr1]);
cntr1++;
}
else if(A->setElements[cntr1] > B->setElements[cntr2]){
setInsertElementSorted(U,B->setElements[cntr2]);
cntr2++;
}
}
for(;cntr1<A->setNumElements;cntr1++){
setInsertElementSorted(U,A->setElements[cntr1]);
}
for(;cntr2<B->setNumElements;cntr2++){
setInsertElementSorted(U,B->setElements[cntr2]);
}
return U;
}
setADT setIntersection(setADT A, setADT B){
int cntr1,cntr2;
setADT I = setNew();
for(cntr1=0,cntr2=0;cntr1<A->setNumElements && cntr2<B->setNumElements;){
if(A->setElements[cntr1] == B->setElements[cntr2]){
setInsertElementSorted(I,A->setElements[cntr1]);
cntr1++;
cntr2++;
}
else if(A->setElements[cntr1] < B->setElements[cntr2]){
cntr1++;
}
else if(A->setElements[cntr1] > B->setElements[cntr2]){
cntr2++;
}
}
return I;
}
setADT setDifference(setADT A, setADT B){
int cntr1,cntr2;
setADT D = setNew();
for(cntr1=0,cntr2=0;cntr1<A->setNumElements && cntr2<B->setNumElements;){
if(A->setElements[cntr1] == B->setElements[cntr2]){
cntr1++;
cntr2++;
continue;
}
else if(A->setElements[cntr1] < B->setElements[cntr2]){
setInsertElementSorted(D,A->setElements[cntr1]);
cntr1++;
}
else if(A->setElements[cntr1] > B->setElements[cntr2]){
cntr2++;
}
}
for(;cntr1<A->setNumElements;cntr1++){
setInsertElementSorted(D,A->setElements[cntr1]);
}
return D;
}
void setPrint(setADT S, char *name){
int i;
printf(\"%d elements in Set %s, Elements are:\ \",S->setNumElements,name);
for(i=0;i<S->setNumElements;i++){
printf(\"%d \",S->setElements[i]);
}
printf(\"\ \");
}
int setCardinality(setADT S){
return S->setNumElements;
}
Run: gcc -o set.o -c setArrayImp.c. This would create a set.o in your folder.
Now, have the driver.c as follows
#include \"set.h\"
#include <stdlib.h>
#include <stdio.h>
void main(){
int setInput;
char option;
setADT A = setNew();
setADT C;
while(1){
printf(\"Enter Positive Values for Set A. Press -1 to End:\");
scanf(\"%d\",&setInput);
if(setInput < 0)
break;
setInsertElementSorted(A,setInput);
}
setADT B = setNew();
while(1){
printf(\"Enter Positive Values for Set B. Press -1 to End:\");
scanf(\"%d\",&setInput);
if(setInput < 0)
break;
setInsertElementSorted(B,setInput);
}
while(1){
printf(\"Options:\ \");
printf(\"Enter Q to quit!\ \");
printf(\"Enter U for A Union B!\ \");
printf(\"Enter I for A Intersection B!\ \");
printf(\"Enter D for A Difference B!\ \");
printf(\"Your option:\");
fflush(stdin);
fflush(stdout);
scanf(\" %c\",&option);
switch(option){
case \'U\':
C = setUnion(A,B);
setPrint(A,\"A\");
setPrint(B,\"B\");
setPrint(C,\"C\");
setFree(C);
break;
case \'I\':
C = setIntersection(A,B);
setPrint(A,\"A\");
setPrint(B,\"B\");
setPrint(C,\"C\");
setFree(C);
break;
case \'D\':
C = setDifference(A,B);
setPrint(A,\"A\");
setPrint(B,\"B\");
setPrint(C,\"C\");
setFree(C);
break;
default:
exit(0);
}
}
}
Sample Run Output:
gcc driver.c set.o
./a.out
Enter Positive Values for Set A. Press -1 to End:2
Enter Positive Values for Set A. Press -1 to End:5
Enter Positive Values for Set A. Press -1 to End:7
Enter Positive Values for Set A. Press -1 to End:-3
Enter Positive Values for Set B. Press -1 to End:3
Enter Positive Values for Set B. Press -1 to End:5
Enter Positive Values for Set B. Press -1 to End:8
Enter Positive Values for Set B. Press -1 to End:10
Enter Positive Values for Set B. Press -1 to End:-1
Options:
Enter Q to quit!
Enter U for A Union B!
Enter I for A Intersection B!
Enter D for A Difference B!
Your option:U
3 elements in Set A, Elements are:
2 5 7
4 elements in Set B, Elements are:
3 5 8 10
6 elements in Set C, Elements are:
2 3 5 7 8 10
Options:
Enter Q to quit!
Enter U for A Union B!
Enter I for A Intersection B!
Enter D for A Difference B!
Your option:I
3 elements in Set A, Elements are:
2 5 7
4 elements in Set B, Elements are:
3 5 8 10
1 elements in Set C, Elements are:
5
Options:
Enter Q to quit!
Enter U for A Union B!
Enter I for A Intersection B!
Enter D for A Difference B!
Your option:D
3 elements in Set A, Elements are:
2 5 7
4 elements in Set B, Elements are:
3 5 8 10
2 elements in Set C, Elements are:
2 7
Options:
Enter Q to quit!
Enter U for A Union B!
Enter I for A Intersection B!
Enter D for A Difference B!
Your option:Q
The process is similar with setListImp.c. No need to change anything, just use setListImp.c while generating set.o file, i.e. Run gcc -o set.o -c setListImp.c.
setListImp.c
#include \"set.h\"
#include <malloc.h>
struct setList{
setElementT data;
struct setList *next;
};
typedef struct setCDT{
struct setList *head;
setElementT setNumElements;
} *setADT;
setADT setNew(){
setADT newSet = (setADT)malloc(sizeof(struct setCDT));
newSet->setNumElements = 0;
return newSet;
}
void setFree(setADT S){
free(S);
}
int setInsertElementSorted(setADT S, setElementT E){
int cntr,temp1,temp2;
struct setList *temp,*prev;
struct setList *setElement = (struct setList *)malloc(sizeof(struct setList));
setElement->data = E;
setElement->next = NULL;
if(S->head == NULL){
S->head = setElement;
}
else{
temp = S->head;
prev = NULL;
while(temp!=NULL && temp->data < setElement->data){
prev = temp;
temp = temp->next;
}
if(prev == NULL){
setElement->next = S->head;
S->head = setElement;
}
else{
prev->next = setElement;
setElement->next = temp;
}
}
S->setNumElements++;
return S->setNumElements;
}
setADT setUnion(setADT A, setADT B){
setADT U = setNew();
struct setList *cntr1 = A->head, *cntr2 = B->head;
for(;cntr1!=NULL && cntr2!=NULL;){
if(cntr1->data == cntr2->data){
setInsertElementSorted(U,cntr1->data);
cntr1 = cntr1->next;
cntr2 = cntr2->next;
}
else if(cntr1->data < cntr2->data){
setInsertElementSorted(U,cntr1->data);
cntr1 = cntr1->next;
}
else if(cntr1->data > cntr2->data){
setInsertElementSorted(U,cntr2->data);
cntr2 = cntr2->next;
}
}
for(;cntr1!=NULL;cntr1=cntr1->next){
setInsertElementSorted(U,cntr1->data);
}
for(;cntr2!=NULL;cntr2=cntr2->next){
setInsertElementSorted(U,cntr2->data);
}
return U;
}
setADT setIntersection(setADT A, setADT B){
setADT I = setNew();
struct setList *cntr1 = A->head, *cntr2 = B->head;
for(;cntr1!=NULL && cntr2!=NULL;){
if(cntr1->data == cntr2->data){
setInsertElementSorted(I,cntr1->data);
cntr1 = cntr1->next;
cntr2 = cntr2->next;
}
else if(cntr1->data < cntr2->data){
cntr1 = cntr1->next;
}
else if(cntr1->data > cntr2->data){
cntr2 = cntr2->next;
}
}
return I;
}
setADT setDifference(setADT A, setADT B){
setADT D = setNew();
struct setList *cntr1 = A->head, *cntr2 = B->head;
for(;cntr1!=NULL && cntr2!=NULL;){
if(cntr1->data == cntr2->data){
cntr1 = cntr1->next;
cntr2 = cntr2->next;
}
else if(cntr1->data < cntr2->data){
setInsertElementSorted(D,cntr1->data);
cntr1 = cntr1->next;
}
else if(cntr1->data > cntr2->data){
cntr2 = cntr2->next;
}
}
for(;cntr1!=NULL;cntr1=cntr1->next){
setInsertElementSorted(D,cntr1->data);
}
return D;
}
void setPrint(setADT S, char *name){
struct setList *temp = S->head;
printf(\"%d elements in Set %s, Elements are:\ \",S->setNumElements,name);
while(temp != NULL){
printf(\"%d \",temp->data);
temp = temp->next;
}
printf(\"\ \");
}
int setCardinality(setADT S){
return S->setNumElements;
}
