#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define maxboeken 30 /* maximum hoeveelheid boeken op een plank */
#define maxlen 20 /* maximum lengte van een titel */
/* De naam kast ten spijt, gaat het hier niet om de kasten in de opgave,
maar ja, de naam plankstruct is zo mogelijk nog waardelozer */
typedef struct kast {
char prefix[maxlen+1]; /* gebruikte prefix in de boom */
char grootste[maxlen+1]; /* prefix van alle boeken op deze plank */
unsigned int boeken;
char boek[maxboeken][maxlen+1]; /* De titels op deze plank */
struct kast *child;
struct kast *next;
int echt;
} kast;
unsigned int planken;
kast *plank=NULL;
unsigned int plankenperkast,boekenperplank;
int debug;
void Init(kast *pl,char *titel) {
strcpy(pl->prefix,""); /* prefix in deze ``boom'' is leeg */
strcpy(pl->grootste,titel); /* prefix op deze plank is de titel */
pl->boeken=1;
strcpy(pl->boek[0],titel); /* Dit boek STAAT op de plank */
pl->child=NULL;
pl->next=NULL;
pl->echt=1;
planken++;
}
void Print(kast *pl) {
static int tab=0;
unsigned int i;
/* if ((pl!=NULL) && (debug)) {
fprintf(stderr,"%*sprefix: ``%s'', grootste: ``%s''\n",
tab,"",pl->prefix,pl->grootste);
for (i=0;i<pl->boeken;i++) fprintf(stderr,"%*s%s\n",tab,"",pl->boek[i]);
tab+=3;
Print(pl->child);
tab-=3;
Print(pl->next);
} */
}
void Quit(kast **pl) {
if ((*pl)!=NULL) {
Quit(&((*pl)->child));
Quit(&((*pl)->next));
free(*pl);
(*pl)=NULL;
}
}
kast *Zoek(kast *pl,char *titel) {
/* Neem aan dat er tenminste 1 kind is */
kast *plch=pl->child,*pln;
if (strncmp(plch->prefix,titel,strlen(plch->prefix))>0) return(NULL);
pln=plch->next;
while ((pln!=NULL) && (strncmp(pln->prefix,titel,strlen(pln->prefix))<=0)) {
plch=pln;
pln=pln->next;
}
return(plch);
}
void Herverdeel(kast *pl) {
unsigned int i,j;
kast *nwpl,*zpl;
strcpy(pl->prefix,pl->grootste);
pl->echt=0;
/* Voor elk boek op deze plank moet een kind-plank gevonden worden */
for (i=0;i<pl->boeken;i++) {
zpl=Zoek(pl,pl->boek[i]);
if (zpl==NULL) {
nwpl=malloc(sizeof(kast));
Init(nwpl,pl->boek[i]);
for (j=0;pl->prefix[j]==pl->boek[i][j];j++) ;
strncpy(nwpl->prefix,pl->boek[i],j+1);
nwpl->prefix[j+1]='\0';
nwpl->next=pl->child;
pl->child=nwpl;
} else {
if (strncmp(zpl->prefix,pl->boek[i],strlen(zpl->prefix))<0) {
nwpl=malloc(sizeof(kast));
Init(nwpl,pl->boek[i]);
for (j=0;pl->prefix[j]==pl->boek[i][j];j++) ;
strncpy(nwpl->prefix,pl->boek[i],j+1);
nwpl->prefix[j+1]='\0';
nwpl->next=zpl->next;
zpl->next=nwpl;
} else {
/* Het boek hoort op deze plank thuis */
strcpy(zpl->boek[zpl->boeken++],pl->boek[i]);
for (j=0;zpl->grootste[j]==pl->boek[i][j];j++);
zpl->grootste[j]='\0';
}
}
/* Print(pl); */
}
pl->boeken=0;
planken--; /* pl is nu geen ``echte'' plank meer */
} /* Herverdeel() */
void VolgendeBoek(char *titel) {
kast *pl,*nwpl,*zpl;
unsigned int i;
if (plank==NULL) {
plank=malloc(sizeof(kast));
Init(plank,titel);
return;
}
pl=plank;
while (!pl->echt) { /* oftewel, er ZIJN kinderen */
zpl=Zoek(pl,titel);
if (zpl==NULL) {
/* Maak nieuwe plank vooraan in lijst van kinderen */
nwpl=malloc(sizeof(kast));
Init(nwpl,titel);
for (i=0;pl->child->prefix[i]==titel[i];i++) ;
strncpy(nwpl->prefix,titel,i+1);
nwpl->prefix[i+1]='\0';
nwpl->next=pl->child;
pl->child=nwpl;
return;
} else {
if (strncmp(zpl->prefix,titel,strlen(zpl->prefix))<0) {
nwpl=malloc(sizeof(kast));
Init(nwpl,titel);
for (i=0;pl->prefix[i]==titel[i];i++) ;
strncpy(nwpl->prefix,titel,i+1);
nwpl->prefix[i+1]='\0';
nwpl->next=zpl->next;
zpl->next=nwpl;
return;
} else {
pl=zpl;
}
}
}
/* We zijn nu aangekomen bij een ``echte'' plank. Het boek moet hierbij */
for (i=0;pl->grootste[i]==titel[i];i++);
pl->grootste[i]='\0';
if (pl->boeken<boekenperplank) {
/* boeken hoeven niet gesorteerd op de plank te staan */
strcpy(pl->boek[pl->boeken++],titel);
} else {
/* Leg de nieuwe titel vast op zijn eigen plank,
zodat Zoek gebruikt mag worden */
nwpl=malloc(sizeof(kast));
Init(nwpl,titel);
strncpy(nwpl->prefix,titel,strlen(pl->grootste)+1);
nwpl->prefix[strlen(pl->grootste)+1]='\0';
pl->child=nwpl;
Herverdeel(pl);
}
}
int main() {
unsigned int runs,r;
unsigned int boeken,b;
char titel[maxlen+1];
scanf("%d",&runs);
for (r=0;r<runs;r++) {
if (r!=9) debug=1; else debug=0;
planken=0;
plank=NULL;
scanf("%d %d %d",&plankenperkast,&boekenperplank,&boeken);
for (b=0;b<boeken;b++) {
scanf("%s",titel); /* Hoezo niet netjes maxlen tekens?
Die opmerking over spaties is slechts bedoeld om ambiguiteiten
in het probleem te vermijden :*/
VolgendeBoek(titel);
Print(plank);
}
printf("%d\n",(planken+plankenperkast-1)/plankenperkast);
Quit(&plank); /* This REALLY s*cks, maar 'k heb geen tijd meer om de echte fout op te zoeken */
}
return(0);
}
Generated by Java2Html