Advertisement
Guest User

ultrakabel.c

a guest
May 20th, 2021
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.93 KB | None
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. /**
  7. * Het begin van deze voorbeeldoplossing is een licht aangepaste hashtabel (zie lesvideo 14c.)
  8. * De keys van de hashtabel zijn strings die steden voorstellen, de waardes zijn drie potentieel
  9. * lege strings die rechtstreeks verbonden steden met de key voorstellen.
  10. *
  11. * Het algoritme dat deze hashtabel gebruikt is te vinden vanaf lijn 190.
  12. */
  13.  
  14. #define NAAMLENGTH 100
  15.  
  16. typedef struct {
  17. char naam[NAAMLENGTH];
  18. } Key;
  19.  
  20. typedef struct {
  21. char stad1[NAAMLENGTH];
  22. char stad2[NAAMLENGTH];
  23. char stad3[NAAMLENGTH];
  24. } Waarde;
  25.  
  26. void printKeyWaarde(Key k, Waarde w) { printf("%s -> %s %s %s", k.naam, w.stad1, w.stad2, w.stad3); }
  27.  
  28. unsigned int hash(Key k) {
  29. // gebaseerd op http://www.cse.yorku.ca/~oz/hash.html
  30. unsigned char* s = k.naam;
  31. unsigned int hash = 5381; // priemgetal
  32. while (*s) {
  33. hash = ((hash << 5) + hash) + *s++; /* hash * 33 + karakter */
  34. }
  35. return hash;
  36. }
  37.  
  38. int equals(Key k1, Key k2) { return strcmp(k1.naam, k2.naam) == 0; }
  39.  
  40. typedef struct elem {
  41. Key key;
  42. Waarde waarde;
  43. struct elem* volgende;
  44. } Element;
  45.  
  46. Element* createEl(Key k, Waarde w) {
  47. Element* el = malloc(sizeof(Element));
  48. el->key = k;
  49. el->waarde = w;
  50. el->volgende = NULL;
  51. return el;
  52. }
  53.  
  54. void destroyEl(Element* el) {
  55. if (el != NULL) {
  56. destroyEl(el->volgende);
  57. free(el);
  58. }
  59. }
  60.  
  61. typedef struct {
  62. int lengte;
  63. int gevuld;
  64. Element** elementen;
  65. } HashTabel;
  66.  
  67. HashTabel create() {
  68. HashTabel t = {0, 0, NULL};
  69. return t;
  70. }
  71.  
  72. void destroy(HashTabel* t) {
  73. if (t->lengte > 0) {
  74. assert(t->elementen != NULL);
  75. for (int i = 0; i < t->lengte; ++i) {
  76. destroyEl(t->elementen[i]);
  77. }
  78. free(t->elementen);
  79. t->elementen = NULL;
  80. t->lengte = 0;
  81. t->gevuld = 0;
  82. }
  83. }
  84.  
  85. void print(HashTabel* t) {
  86. printf("lengte %d gevuld %d\n", t->lengte, t->gevuld);
  87. for (int i = 0; i < t->lengte; ++i) {
  88. printf("index %3d", i);
  89. Element* el = t->elementen[i];
  90. while (el != NULL) {
  91. printf(" | ");
  92. printKeyWaarde(el->key, el->waarde);
  93. el = el->volgende;
  94. }
  95. printf("\n");
  96. }
  97. }
  98.  
  99. Element* vind(HashTabel* t, Key k) {
  100. if (t->lengte == 0) {
  101. return NULL;
  102. }
  103. int index = hash(k) % t->lengte;
  104. Element* el = t->elementen[index];
  105. while (el != NULL) {
  106. if (equals(el->key, k)) {
  107. return el;
  108. }
  109. el = el->volgende;
  110. }
  111. return NULL;
  112. }
  113.  
  114. void groei(HashTabel* t);
  115.  
  116. void voegToe(HashTabel* t, Key k, Waarde w) {
  117. if (t->lengte == 0) {
  118. groei(t);
  119. }
  120. int index = hash(k) % t->lengte;
  121. Element* el = t->elementen[index];
  122. if (el == NULL) {
  123. t->elementen[index] = createEl(k, w);
  124. } else if (equals(el->key, k)) {
  125. return; // zit al in tabel
  126. } else {
  127. while (el->volgende != NULL) {
  128. el = el->volgende;
  129. if (equals(el->key, k)) {
  130. return; // zit al in tabel
  131. }
  132. }
  133. el->volgende = createEl(k, w);
  134. }
  135. t->gevuld += 1;
  136. if (t->lengte <= t->gevuld) {
  137. groei(t);
  138. }
  139. }
  140.  
  141. void groei(HashTabel* t) {
  142. HashTabel nieuw = create();
  143. nieuw.lengte = 2 * t->lengte + 1; // 0,1,3,7,15, enz.
  144. nieuw.elementen = malloc(sizeof(Element*) * nieuw.lengte);
  145. for (int i = 0; i < nieuw.lengte; ++i) {
  146. nieuw.elementen[i] = NULL;
  147. }
  148. for (int i = 0; i < t->lengte; ++i) {
  149. Element* el = t->elementen[i];
  150. while (el != NULL) {
  151. voegToe(&nieuw, el->key, el->waarde);
  152. el = el->volgende;
  153. }
  154. }
  155. destroy(t);
  156. t->lengte = nieuw.lengte;
  157. t->gevuld = nieuw.gevuld;
  158. t->elementen = nieuw.elementen;
  159. }
  160.  
  161. int verwijder(HashTabel* t, Key k) {
  162. if (t->lengte == 0) {
  163. return 0;
  164. }
  165. int index = hash(k) % t->lengte;
  166. Element* el = t->elementen[index];
  167. if (el == NULL) {
  168. return 0;
  169. }
  170. if (equals(el->key, k)) {
  171. Element* tmp = el->volgende;
  172. free(el);
  173. t->elementen[index] = tmp;
  174. t->gevuld -= 1;
  175. return 1;
  176. }
  177. while (el->volgende != NULL) {
  178. if (equals(el->volgende->key, k)) {
  179. Element* tmp = el->volgende->volgende;
  180. free(el->volgende);
  181. el->volgende = tmp;
  182. t->gevuld -= 1;
  183. return 1;
  184. }
  185. el = el->volgende;
  186. }
  187. return 0;
  188. }
  189.  
  190. // BEGIN VAN EIGENLIJKE OPLOSSING
  191.  
  192. void voegKabelToe(HashTabel* rechtstreeks, char* van, char* naar){
  193. Key k = {""};
  194. strcpy(k.naam,van);
  195. Element* e = vind(rechtstreeks,k);
  196. if(e==NULL){
  197. Waarde w = {"", "", ""};
  198. strcpy(w.stad1,naar);
  199. voegToe(rechtstreeks,k,w);
  200. }else{
  201. if(strlen(e->waarde.stad2)==0){
  202. strcpy(e->waarde.stad2,naar);
  203. }else{
  204. strcpy(e->waarde.stad3,naar);
  205. }
  206. }
  207. }
  208.  
  209. void initialiseerRechtstreeks(HashTabel* rechtstreeks, char** van, char** naar, int n){
  210. for(int i=0; i<n; ++i){
  211. voegKabelToe(rechtstreeks, van[i],naar[i]);
  212. voegKabelToe(rechtstreeks, naar[i],van[i]);
  213. }
  214. }
  215.  
  216. void verwijderRecursief(HashTabel* rechtstreeks, char* teVerwijderen){
  217. if(teVerwijderen==NULL || strlen(teVerwijderen)==0){
  218. return;
  219. }else{
  220. Key k;
  221. strcpy(k.naam,teVerwijderen);
  222. Element* e = vind(rechtstreeks,k);
  223. if(e!=NULL){
  224. Waarde w = e->waarde;
  225. verwijder(rechtstreeks,k);
  226. verwijderRecursief(rechtstreeks,w.stad1);
  227. verwijderRecursief(rechtstreeks,w.stad2);
  228. verwijderRecursief(rechtstreeks,w.stad3);
  229. }
  230. // else: teVerwijderen al verwijderd
  231. }
  232. }
  233.  
  234. int isVolledigVerbonden(char** van, char** naar, int n){
  235. HashTabel rechtstreeks = create();
  236. initialiseerRechtstreeks(&rechtstreeks, van,naar,n);
  237. print(&rechtstreeks);
  238.  
  239. verwijderRecursief(&rechtstreeks, van[0]);
  240. print(&rechtstreeks);
  241.  
  242. int result = rechtstreeks.gevuld==0;
  243. destroy(&rechtstreeks);
  244.  
  245. return result;
  246. }
  247.  
  248. #define INPUTLENGTH 5
  249.  
  250. int main(){
  251. char* van[INPUTLENGTH] = {"Brussel","Leuven","Antwerpen","Brugge","Gent"};
  252. char* naar[INPUTLENGTH] = {"Leuven","Antwerpen","Brussel","Gent","Kortrijk"};
  253.  
  254. return isVolledigVerbonden(van,naar,INPUTLENGTH);
  255. }
Advertisement
RAW Paste Data Copied
Advertisement