Guest User

Untitled

a guest
Jul 20th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.08 KB | None | 0 0
  1. a9.txt Page 1 of 4
  2. CPS-210, Assignment #9 20 points
  3. Due:
  4. Goal: Bit operations, bitmaps and implementation of fixed size sets.
  5. Statement:
  6. Recall/lookup the concept of a set(s) and associated operations.
  7. A set with no elements (members) is a valid set. The general operations of
  8. interest can be: create an empty set, add an element to set, remove an
  9. element form set, test if an element is a member of given set, print
  10. the elements of a set, find the union set of given sets, find the
  11. intersection set of given set, find the difference set of given sets.
  12. One way to implement set is using an ordered/un-ordered singly
  13. linked list (allows for set size to grow). Another way to implement a set is
  14. using a bitmap as mentioned in class. This method is used to implement fixed
  15. size sets. We want to implement the sets using bitmaps. A bitmap is a
  16. collection of fixed number of of contiguous bits where each bit can be 1
  17. corresponding element is in set) or 0 (element not in set).
  18. You have to write a well documented, structured C-program to
  19. implement a set of integers using the bitmap technique. Set size is limited
  20. to 256 elements (range of values 0..255). The elements will be made available
  21. at run time from stdin. All writes will be done to stderr.
  22. The data format of input line: count-of-elements list-of-elements:
  23. 5 12 3 45 110 239
  24. 6 3 12 45 115 221 239
  25. ...
  26. ---
  27. Sample output:
  28. { 5 elements in this set }
  29. Set A: 12 3 45 110 239
  30. Set B: 3 12 45 115 221 149
  31. A union B: 3 12 45 110 115 149 221 239
  32. A intersection B: 3 12 45
  33. A difference B: 110 239
  34. B difference A: 115 149 221
  35. ---
  36. Set A: 12 3 45 110 239
  37. Set B: empty
  38. A union B: 3 12 45 110 239
  39. A intersection B: empty
  40. A difference B: 3 12 45 110 239
  41. B difference A: empty
  42. ---
  43. Set A: empty
  44. Set B: empty
  45. ...
  46. ---- globals ----
  47. The set ADT:
  48. a9.txt
  49. #define SIZE 32
  50. struct set{
  51. char *data;
  52. int count;
  53. Page 2 of 4
  54. // 256 elements in a set
  55. // storage for 256 bits, allocated dynamically
  56. // count of elements/members
  57. };
  58. typedef struct set set;
  59. ----
  60. The program must use the following modules (write them):
  61. 01. void makeaset(set **s1); // 01 to 09 in file a8.c
  62. { allocates storage and makes the set s1 empty
  63. handle count of elements, use malloc() to allocate memory }
  64. 02. void clearaset(set *s2);
  65. { makes the set s2 empty: bits and count are cleared }
  66. 03. void addtoset(int elm, set *s1);
  67. { add elm to set s1, updates the count member }
  68. 04. int isinset(int elm, set *s1);
  69. { checks if elm is in s1, returns 1 on success, 0 otherwise..}
  70. 05. void setunion(set *s1, set *s2, set **s3);
  71. { s3 is a union of sets s1 and s2 }
  72. 06. void setintersect(set *s1, set *s2, set **s3);
  73. { s3 is an intersection set of sets s1 and s2 }
  74. 07. void setdiff(set *s1, set *s2, set **s3);
  75. { s3 contains elements that are in s1 and not s2 etc.. }
  76. 08. void dosetops(set *seta, set *setb);
  77. { perform the set operations and print results as needed.
  78. result will have to cleared after each operation }
  79. 09. void printaset(char *label, set *s1);
  80. { writes the label followed by members of s1 to stderr.. }
  81. 10. void buildaset(set *s1);
  82. { populates the set using values read stdin, also
  83. updates the count member }
  84. 11. void freeaset(set **s1);
  85. { returns storage allocated by malloc() back to system }
  86. 12. int main(void); // in file main.c
  87. { of course }
  88. Note: modify the Makefile as needed.
  89. Turn-in: A hardcopy print out using gmake print and also as an e-mail
  90. attached file (<global-id>-a8.tar.bz2).
  91. ----Jump start main()-----
  92. /* Documentation as required/needed.. */
  93. <include files>
  94. #define SIZE 32
  95. int main(void)
  96. {
  97. // 8 bytes needed for 256 element set
  98. set *seta, *setb;
  99. int i;
  100. // prototypes for the functions called by main go here
  101. makeaset(&seta); makeaset(&setb);
  102. if(!seta || !setb)
  103. { fprintf(stderr, "Malloc failed\n"); exit(1); }
  104. a9.txt Page 3 of 4
  105. for(i= 0; i < 3; i++) {
  106. buildaset(seta); buildaset(setb);
  107. printaset("Set A: ", seta); printaset("Set B: ",setb);
  108. dosetops(seta, setb);
  109. clearaset(seta); clearaset(setb);
  110. }
  111. if (seta) freeaset(&seta);
  112. if (setb) freeaset(&setb);
  113. exit(0);
  114. } ----
  115. 1. Storage allocation:
  116. char *ptr;
  117. ptr = malloc(100); /* allocates 100 byte chunk from heap and
  118. returns pointer to chunk, ptr is NULL on failure */
  119. 2. Storage deallocation:
  120. /* if ptr points to chunk of memory obtained vial malloc() then */
  121. free(ptr);
  122. /* will return the memory pointed by ptr back to heap */
  123. 3. Hint on bits (you have seen it before):
  124. int i, mask;
  125. char a;
  126. mask = 1;
  127. for(i=0; i<8; i++)
  128. if(a & (mask<<i)) { /* ith bit is set */ }
  129. 4. /* Allocates storage for the set, and initializes all bits to 0
  130. so that the set is empty at start. Since malloc() can and
  131. does fail, the caller must make sure that the address of set
  132. is defined -- that is not NULL. */
  133. void makeaset(set **s)
  134. {
  135. int i; set *ptr;
  136. ptr = NULL;
  137. ptr = malloc(sizeof(set));
  138. if(ptr) {
  139. ptr->data = malloc(SIZE);
  140. if(ptr->data){
  141. } }
  142. *s = ptr; }
  143. for(i=0; i<SIZE; i++) ptr->data[i] = 0;
  144. ptr->count = 0;
  145. 5. Use library function scanf() to read a value from stdin as:
  146. int val;
  147. scanf("%d", &val);
  148. { will read next value in val, note the address of operator }
  149. 6. /* Clears the bits in the set s1 and also resets the set count
  150. to 0 */
  151. void clearaset(set *s1)
  152. a9.txt Page 4 of 4
  153. {
  154. int i;
  155. s1->count = 0;
  156. for(i = 0; i < SIZE; i++)
  157. s1->data[i] = 0;
  158. }
  159. 7. /* Returns the dynamically allocates storage back to system
  160. using library function free(). s1 is NULL after the operation.
  161. */
  162. void freeaset(set **s1)
  163. {
  164. set *s2;
  165. s2 = *s1;
  166. if( s2 != NULL) {
  167. free((void *)s2);
  168. *s1 = NULL; }
  169. }
  170. 8. Algorithm for buildaset():
  171. read the count-of-elements from stdin
  172. make set count same as count-of-elements
  173. while more elements to read:
  174. ----
Add Comment
Please, Sign In to add comment