(Abstract Data Type - Library) Background see http://en.wikipedia.org/wiki/Set (
ID: 3724261 • Letter: #
Question
(Abstract Data Type - Library) Background see http://en.wikipedia.org/wiki/Set (mathematics) 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-intersection(A,B); C- difference(A,B); >C=AUB={2, 3, 5, 7, 8, 10} > C = A-B =AY B = 12, 7} also aka. complement What to do: You are asked to develop a set library (using two different representations: array and linlk list). So you will have setArrayImp.c and setLinkedListImp.c 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 (); void setFree (setADT S); /* create a new empty set */ *free the space allocated for the set S */ int setInsertElementSorted(setADT S, setElementT E); /* if not successful, return 0; otherwise, return the number of elements in the set (including the element just inserted). 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 AU B setADT setIntersection (setADT A, setADT B); /* returns a new set containing AnB setADT setDifference (setADT A, setADT B); /* returns a new set containing ABExplanation / Answer
//set.h
typedef int setElementT;
typedef struct setCDT *setADT;
setADT setNew();
void setFree(setADT S);
int setInsertElementSorted(setADT S, setElementT E);
setADT setUnion (setADT, setADT B);
setADT setIntersection(setADT A, setADT B);
setADT setDIfference(setADT A, setADT B);
int setCardinality(setADT S);
void setPrint(setADT S, char *name);
//setArrayImp.c
#include "set.h"
#define MAX_ELEMENTS 100
typedef struct setCDT
{
setElementT val;
} * ADT;
setADT setNew()
{
setADT list = (setADT)malloc(MAX_ELEMENTS * sizeof(setADT));
int i = 0;
while (i < MAX_ELEMENTS)
{
(list + i)->val = -999;
i++;
}
return list;
}
void setFree(setADT S)
{
free(S);
}
int setInsertElementSorted(setADT S, setElementT E)
{
int n = setCardinality(S);
if (n < MAX_ELEMENTS)
{
int i = 0;
while ((S + i)->val < E && i < n)
{
i++;
}
int j = n;
while (j >= i)
{
(S + j)->val = (S + j - 1)->val;
j--;
}
(S + i)->val = E;
return n + 1;
}
else
{
return 0;
}
}
setADT setUnion(setADT A, setADT B)
{
setADT new = setNew();
int i = 0;
while ((A + i)->val != -999)
{
setInsertElementSorted(new, (A + i)->val);
i++;
}
i = 0;
while ((B + i)->val != -999)
{
int j = 0, exists = 0;
while ((A + j)->val != -999)
{
if ((B + i)->val == (A + j)->val)
exists = 1;
j++;
}
if (!exists)
setInsertElementSorted(new, (B + i)->val);
i++;
}
return new;
}
setADT setIntersection(setADT A, setADT B)
{
setADT new = setNew();
int i = 0;
while ((A + i)->val != -999)
{
int j = 0, exists = 0;
while ((B + j)->val != -999)
{
if ((A + i)->val == (B + j)->val)
{
setInsertElementSorted(new, (A + i)->val);
break;
}
j++;
}
i++;
}
return new;
}
setADT setDifference(setADT A, setADT B)
{
setADT new = setNew();
int i = 0;
while ((A + i)->val != -999)
{
int j = 0, exists = 0;
while ((B + j)->val != -999)
{
if ((A + i)->val == (B + j)->val)
{
exists = 1;
break;
}
j++;
}
if (!exists)
{
setInsertElementSorted(new, (A + i)->val);
}
i++;
}
return new;
}
void setPrint(setADT S, char *name)
{
int i = 0;
printf("Set Name is: %s ", name);
printf("Elements are: ");
while ((S + i)->val != -999)
{
printf("%d ", (S + i)->val);
i++;
}
printf(" ");
}
int setCardinality(setADT S)
{
int i = 0;
while ((S + i)->val != -999)
{
i++;
}
return i;
}
//setLinkedListImp.c
#include "set.h"
#define MAX_ELEMENTS 100
typedef struct setCDT
{
setElementT val;
setADT next;
} * ADT;
setADT setNew()
{
setADT node = (setADT)malloc(sizeof(setADT));
return node;
}
void setFree(setADT S)
{
setADT temp = S, prev;
while(temp!=NULL){
prev = temp;
temp = temp->next;
free(prev);
}
}
int setInsertElementSorted(setADT S, setElementT E)
{
setADT new = setNew();
new->val = E;
setADT temp = S;
if (temp->next == NULL)
{
new->next = NULL;
temp->next = new;
}
else
{
setADT temp = S, prev;
while (temp->next != NULL && temp->val < E)
{
prev = temp;
temp = temp->next;
}
if (temp->next == NULL)
{
new->next = NULL;
temp->next = new;
}
else
{
prev->next = new;
new->next = temp;
}
}
return 1;
}
setADT setUnion(setADT A, setADT B)
{
setADT new = setNew(), temp = A->next, temp1 = B->next;
while (temp != NULL)
{
setInsertElementSorted(new, temp->val);
temp = temp->next;
}
while (temp1 != NULL)
{
temp = A->next;
int exists = 0;
while (temp != NULL)
{
if (temp1->val == temp->val)
exists = 1;
temp = temp->next;
}
if (!exists)
setInsertElementSorted(new, temp1->val);
temp1 = temp1->next;
}
return new;
}
setADT setIntersection(setADT A, setADT B)
{
setADT new = setNew(), temp = A->next, temp1 = B->next;
while (temp != NULL)
{
temp1 = B->next;
int exists = 0;
while (temp1 != NULL)
{
if (temp->val == temp1->val)
{
setInsertElementSorted(new, temp->val);
break;
}
temp1 = temp1->next;
}
temp = temp->next;
}
return new;
}
setADT setDifference(setADT A, setADT B)
{
setADT new = setNew(), temp = A->next, temp1 = B->next;
while (temp != NULL)
{
temp1 = B->next;
int exists = 0;
while (temp1 != NULL)
{
if (temp->val == temp1->val)
{
exists = 1;
break;
}
temp1 = temp1->next;
}
if (!exists)
{
setInsertElementSorted(new, temp->val);
}
temp = temp->next;
}
return new;
}
void setPrint(setADT S, char *name)
{
printf("Set Name is: %s ", name);
printf("Elements are: ");
setADT temp = S->next;
while (temp != NULL)
{
printf("%d ", temp->val);
temp = temp->next;
}
printf(" ");
}
int setCardinality(setADT S)
{
int i = 0;
setADT temp = S->next;
while (temp != NULL)
{
temp = temp->next;
i++;
}
return i;
}
//driver.c
#include <stdio.h>
#include <stdlib.h>
#include "setLinkedListImp.c"
int main()
{
//Initilize ADT's
setADT A = setNew();
setADT B = setNew();
//Insertin elements
int in;
printf("Enter Elements for A(-1 to exit): ");
scanf("%d", &in);
while (in != -1)
{
setInsertElementSorted(A, in);
scanf("%d", &in);
}
printf("Enter Elements for B(-1 to exit): ");
scanf("%d", &in);
while (in != -1)
{
setInsertElementSorted(B, in);
scanf("%d", &in);
}
char choice;
setADT C;
do
{
printf("************ MENU *********** ");
printf("U - Union I - Intersection D - Difference Q - Quit ");
printf("Enter choice: ");
scanf(" %c", &choice);
switch (choice)
{
case 'U':
//Union
C = setUnion(A, B);
setPrint(A, "A");
setPrint(B, "B");
setPrint(C, "Union");
printf("number of ELements: %d ", setCardinality(C));
setFree(C);
break;
//InterSection
case 'I':
C = setIntersection(A, B);
setPrint(A, "A");
setPrint(B, "B");
setPrint(C, "Intersection");
printf("number of ELements: %d ", setCardinality(C));
setFree(C);
break;
//Difference
case 'D':
C = setDifference(A, B);
setPrint(A, "A");
setPrint(B, "B");
setPrint(C, "Difference");
printf("number of ELements: %d ", setCardinality(C));
setFree(C);
break;
case 'Q':
printf("Thank you! ");
exit(1);
break;
default:
printf("Invlaid Choice: ");
}
} while (choice != 'Q');
//Cardinality
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.