ultrakabel.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
* Het begin van deze voorbeeldoplossing is een licht aangepaste hashtabel (zie lesvideo 14c.)
* De keys van de hashtabel zijn strings die steden voorstellen, de waardes zijn drie potentieel
* lege strings die rechtstreeks verbonden steden met de key voorstellen.
*
* Het algoritme dat deze hashtabel gebruikt is te vinden vanaf lijn 190.
*/

#define NAAMLENGTH 100

typedef struct {
  char naam[NAAMLENGTH];
} Key;

typedef struct {
  char stad1[NAAMLENGTH];
  char stad2[NAAMLENGTH];
  char stad3[NAAMLENGTH];
} Waarde;

void printKeyWaarde(Key k, Waarde w) { printf("%s -> %s %s %s", k.naam, w.stad1, w.stad2, w.stad3); }

unsigned int hash(Key k) {
  // gebaseerd op http://www.cse.yorku.ca/~oz/hash.html
  unsigned char* s = k.naam;
  unsigned int hash = 5381; // priemgetal
  while (*s) {
    hash = ((hash << 5) + hash) + *s++; /* hash * 33 + karakter */
  }
  return hash;
}

int equals(Key k1, Key k2) { return strcmp(k1.naam, k2.naam) == 0; }

typedef struct elem {
  Key key;
  Waarde waarde;
  struct elem* volgende;
} Element;

Element* createEl(Key k, Waarde w) {
  Element* el = malloc(sizeof(Element));
  el->key = k;
  el->waarde = w;
  el->volgende = NULL;
  return el;
}

void destroyEl(Element* el) {
  if (el != NULL) {
    destroyEl(el->volgende);
    free(el);
  }
}

typedef struct {
  int lengte;
  int gevuld;
  Element** elementen;
} HashTabel;

HashTabel create() {
  HashTabel t = {0, 0, NULL};
  return t;
}

void destroy(HashTabel* t) {
  if (t->lengte > 0) {
    assert(t->elementen != NULL);
    for (int i = 0; i < t->lengte; ++i) {
      destroyEl(t->elementen[i]);
    }
    free(t->elementen);
    t->elementen = NULL;
    t->lengte = 0;
    t->gevuld = 0;
  }
}

void print(HashTabel* t) {
  printf("lengte %d gevuld %d\n", t->lengte, t->gevuld);
  for (int i = 0; i < t->lengte; ++i) {
    printf("index %3d", i);
    Element* el = t->elementen[i];
    while (el != NULL) {
      printf(" | ");
      printKeyWaarde(el->key, el->waarde);
      el = el->volgende;
    }
    printf("\n");
  }
}

Element* vind(HashTabel* t, Key k) {
  if (t->lengte == 0) {
    return NULL;
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  while (el != NULL) {
    if (equals(el->key, k)) {
      return el;
    }
    el = el->volgende;
  }
  return NULL;
}

void groei(HashTabel* t);

void voegToe(HashTabel* t, Key k, Waarde w) {
  if (t->lengte == 0) {
    groei(t);
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  if (el == NULL) {
    t->elementen[index] = createEl(k, w);
  } else if (equals(el->key, k)) {
    return; // zit al in tabel
  } else {
    while (el->volgende != NULL) {
      el = el->volgende;
      if (equals(el->key, k)) {
        return; // zit al in tabel
      }
    }
    el->volgende = createEl(k, w);
  }
  t->gevuld += 1;
  if (t->lengte <= t->gevuld) {
    groei(t);
  }
}

void groei(HashTabel* t) {
  HashTabel nieuw = create();
  nieuw.lengte = 2 * t->lengte + 1; // 0,1,3,7,15, enz.
  nieuw.elementen = malloc(sizeof(Element*) * nieuw.lengte);
  for (int i = 0; i < nieuw.lengte; ++i) {
    nieuw.elementen[i] = NULL;
  }
  for (int i = 0; i < t->lengte; ++i) {
    Element* el = t->elementen[i];
    while (el != NULL) {
      voegToe(&nieuw, el->key, el->waarde);
      el = el->volgende;
    }
  }
  destroy(t);
  t->lengte = nieuw.lengte;
  t->gevuld = nieuw.gevuld;
  t->elementen = nieuw.elementen;
}

int verwijder(HashTabel* t, Key k) {
  if (t->lengte == 0) {
    return 0;
  }
  int index = hash(k) % t->lengte;
  Element* el = t->elementen[index];
  if (el == NULL) {
    return 0;
  }
  if (equals(el->key, k)) {
    Element* tmp = el->volgende;
    free(el);
    t->elementen[index] = tmp;
    t->gevuld -= 1;
    return 1;
  }
  while (el->volgende != NULL) {
    if (equals(el->volgende->key, k)) {
      Element* tmp = el->volgende->volgende;
      free(el->volgende);
      el->volgende = tmp;
      t->gevuld -= 1;
      return 1;
    }
    el = el->volgende;
  }
  return 0;
}

// BEGIN VAN EIGENLIJKE OPLOSSING

void voegKabelToe(HashTabel* rechtstreeks, char* van, char* naar){
  Key k = {""};
  strcpy(k.naam,van);
  Element* e = vind(rechtstreeks,k);
  if(e==NULL){
    Waarde w = {"", "", ""};
    strcpy(w.stad1,naar);
    voegToe(rechtstreeks,k,w);
  }else{
    if(strlen(e->waarde.stad2)==0){
      strcpy(e->waarde.stad2,naar);
    }else{
      strcpy(e->waarde.stad3,naar);
    }
  }
}

void initialiseerRechtstreeks(HashTabel* rechtstreeks, char** van, char** naar, int n){
  for(int i=0; i<n; ++i){
    voegKabelToe(rechtstreeks, van[i],naar[i]);
    voegKabelToe(rechtstreeks, naar[i],van[i]);
  }
}

void verwijderRecursief(HashTabel* rechtstreeks, char* teVerwijderen){
  if(teVerwijderen==NULL || strlen(teVerwijderen)==0){
    return;
  }else{
    Key k;
    strcpy(k.naam,teVerwijderen);
    Element* e = vind(rechtstreeks,k);
    if(e!=NULL){
      Waarde w = e->waarde;
      verwijder(rechtstreeks,k);
      verwijderRecursief(rechtstreeks,w.stad1);
      verwijderRecursief(rechtstreeks,w.stad2);
      verwijderRecursief(rechtstreeks,w.stad3);
    }
    // else: teVerwijderen al verwijderd
  }
}

int isVolledigVerbonden(char** van, char** naar, int n){
  HashTabel rechtstreeks = create();
  initialiseerRechtstreeks(&rechtstreeks, van,naar,n);
  print(&rechtstreeks);

  verwijderRecursief(&rechtstreeks, van[0]);
  print(&rechtstreeks);

  int result = rechtstreeks.gevuld==0;
  destroy(&rechtstreeks);

  return result;
}

#define INPUTLENGTH 5

int main(){
  char* van[INPUTLENGTH] = {"Brussel","Leuven","Antwerpen","Brugge","Gent"};
  char* naar[INPUTLENGTH] = {"Leuven","Antwerpen","Brussel","Gent","Kortrijk"};

  return isVolledigVerbonden(van,naar,INPUTLENGTH);
}