Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- a9.txt Page 1 of 4
- CPS-210, Assignment #9 20 points
- Due:
- Goal: Bit operations, bitmaps and implementation of fixed size sets.
- Statement:
- Recall/lookup the concept of a set(s) and associated operations.
- A set with no elements (members) is a valid set. The general operations of
- interest can be: create an empty set, add an element to set, remove an
- element form set, test if an element is a member of given set, print
- the elements of a set, find the union set of given sets, find the
- intersection set of given set, find the difference set of given sets.
- One way to implement set is using an ordered/un-ordered singly
- linked list (allows for set size to grow). Another way to implement a set is
- using a bitmap as mentioned in class. This method is used to implement fixed
- size sets. We want to implement the sets using bitmaps. A bitmap is a
- collection of fixed number of of contiguous bits where each bit can be 1
- corresponding element is in set) or 0 (element not in set).
- You have to write a well documented, structured C-program to
- implement a set of integers using the bitmap technique. Set size is limited
- to 256 elements (range of values 0..255). The elements will be made available
- at run time from stdin. All writes will be done to stderr.
- The data format of input line: count-of-elements list-of-elements:
- 5 12 3 45 110 239
- 6 3 12 45 115 221 239
- ...
- ---
- Sample output:
- { 5 elements in this set }
- Set A: 12 3 45 110 239
- Set B: 3 12 45 115 221 149
- A union B: 3 12 45 110 115 149 221 239
- A intersection B: 3 12 45
- A difference B: 110 239
- B difference A: 115 149 221
- ---
- Set A: 12 3 45 110 239
- Set B: empty
- A union B: 3 12 45 110 239
- A intersection B: empty
- A difference B: 3 12 45 110 239
- B difference A: empty
- ---
- Set A: empty
- Set B: empty
- ...
- ---- globals ----
- The set ADT:
- a9.txt
- #define SIZE 32
- struct set{
- char *data;
- int count;
- Page 2 of 4
- // 256 elements in a set
- // storage for 256 bits, allocated dynamically
- // count of elements/members
- };
- typedef struct set set;
- ----
- The program must use the following modules (write them):
- 01. void makeaset(set **s1); // 01 to 09 in file a8.c
- { allocates storage and makes the set s1 empty
- handle count of elements, use malloc() to allocate memory }
- 02. void clearaset(set *s2);
- { makes the set s2 empty: bits and count are cleared }
- 03. void addtoset(int elm, set *s1);
- { add elm to set s1, updates the count member }
- 04. int isinset(int elm, set *s1);
- { checks if elm is in s1, returns 1 on success, 0 otherwise..}
- 05. void setunion(set *s1, set *s2, set **s3);
- { s3 is a union of sets s1 and s2 }
- 06. void setintersect(set *s1, set *s2, set **s3);
- { s3 is an intersection set of sets s1 and s2 }
- 07. void setdiff(set *s1, set *s2, set **s3);
- { s3 contains elements that are in s1 and not s2 etc.. }
- 08. void dosetops(set *seta, set *setb);
- { perform the set operations and print results as needed.
- result will have to cleared after each operation }
- 09. void printaset(char *label, set *s1);
- { writes the label followed by members of s1 to stderr.. }
- 10. void buildaset(set *s1);
- { populates the set using values read stdin, also
- updates the count member }
- 11. void freeaset(set **s1);
- { returns storage allocated by malloc() back to system }
- 12. int main(void); // in file main.c
- { of course }
- Note: modify the Makefile as needed.
- Turn-in: A hardcopy print out using gmake print and also as an e-mail
- attached file (<global-id>-a8.tar.bz2).
- ----Jump start main()-----
- /* Documentation as required/needed.. */
- <include files>
- #define SIZE 32
- int main(void)
- {
- // 8 bytes needed for 256 element set
- set *seta, *setb;
- int i;
- // prototypes for the functions called by main go here
- makeaset(&seta); makeaset(&setb);
- if(!seta || !setb)
- { fprintf(stderr, "Malloc failed\n"); exit(1); }
- a9.txt Page 3 of 4
- for(i= 0; i < 3; i++) {
- buildaset(seta); buildaset(setb);
- printaset("Set A: ", seta); printaset("Set B: ",setb);
- dosetops(seta, setb);
- clearaset(seta); clearaset(setb);
- }
- if (seta) freeaset(&seta);
- if (setb) freeaset(&setb);
- exit(0);
- } ----
- 1. Storage allocation:
- char *ptr;
- ptr = malloc(100); /* allocates 100 byte chunk from heap and
- returns pointer to chunk, ptr is NULL on failure */
- 2. Storage deallocation:
- /* if ptr points to chunk of memory obtained vial malloc() then */
- free(ptr);
- /* will return the memory pointed by ptr back to heap */
- 3. Hint on bits (you have seen it before):
- int i, mask;
- char a;
- mask = 1;
- for(i=0; i<8; i++)
- if(a & (mask<<i)) { /* ith bit is set */ }
- 4. /* Allocates storage for the set, and initializes all bits to 0
- so that the set is empty at start. Since malloc() can and
- does fail, the caller must make sure that the address of set
- is defined -- that is not NULL. */
- void makeaset(set **s)
- {
- int i; set *ptr;
- ptr = NULL;
- ptr = malloc(sizeof(set));
- if(ptr) {
- ptr->data = malloc(SIZE);
- if(ptr->data){
- } }
- *s = ptr; }
- for(i=0; i<SIZE; i++) ptr->data[i] = 0;
- ptr->count = 0;
- 5. Use library function scanf() to read a value from stdin as:
- int val;
- scanf("%d", &val);
- { will read next value in val, note the address of operator }
- 6. /* Clears the bits in the set s1 and also resets the set count
- to 0 */
- void clearaset(set *s1)
- a9.txt Page 4 of 4
- {
- int i;
- s1->count = 0;
- for(i = 0; i < SIZE; i++)
- s1->data[i] = 0;
- }
- 7. /* Returns the dynamically allocates storage back to system
- using library function free(). s1 is NULL after the operation.
- */
- void freeaset(set **s1)
- {
- set *s2;
- s2 = *s1;
- if( s2 != NULL) {
- free((void *)s2);
- *s1 = NULL; }
- }
- 8. Algorithm for buildaset():
- read the count-of-elements from stdin
- make set count same as count-of-elements
- while more elements to read:
- ----
Add Comment
Please, Sign In to add comment