005
17.11.2005, 10:48 Uhr
0xdeadbeef
Gott
(Operator)
|
Wichtig ist die Verarbeitung des Index. Im Grunde ist die Indexdatei selbst nicht besonders kompliziert, ich würde vorschlagen, sie einfach space-padded so aufzubauen, dass sie dem Format "Offset Datum" entspricht, im Fall von Namen also
| Code: |
102 Hindenburg
0 Meier
50 Müller
|
Wichtig zu beachten dabei ist, bei der Suche wird das Datum, nicht das Offset als Schlüssel benutzt. Je nachdem, wie du den Index nachher verarbeiten willst, kann es also Sinn machen, die Indexdatei nach dem Datum zu sortieren (wie ich es oben getan habe). In dem Fall könnte man sie zum Beispiel einfach in ein Array einlesen und dann binär suchen. Wenn du mit einem Baum arbeiten willst, ist das Sortieren eher ungünstig, weil du dann die ganze Zeit am Ausbalancieren bist. Die Deluxe-Lösung ist natürlich eine Hashtable, der ist das je nach Hashfunktion herzlich egal, ob die Datei sortiert ist oder nicht.
Ich nehme aber an, dass in der Aufgabenstellung das Einlesen in ein Array gemeint ist, da sich sowohl Baum als auch Hashtable locker auch ohne spezielle Indexdatei direkt aus den Datensätzen generieren ließen.
Als weitere Verfeinerung würde ich darüber nachdenken, am Anfang der Datei die Anzahl der enthaltenen Datensätze zu speichern und evtl. die Länge des Datums, um nicht zu viel Speicher anfordern zu müssen. Das sähe dann so aus:
| Code: |
3
102 10 Hindenburg
0 5 Meier
50 6 Müller
|
und ließe sich in folgender Form verarbeiten:
| C++: |
#include <stdio.h>
#include <stdlib.h>
struct name_index_data {
char *name;
long offset;
};
int main(int argc, char *argv[]) {
struct name_index_data *name_index;
int name_index_len, data_len, i;
long offset;
FILE *fd = fopen("name.idx", "r");
fscanf(fd, "%d", &name_index_len);
name_index = calloc(name_index_len, sizeof(struct name_index_data));
for(i = 0; i < name_index_len; ++i) {
fscanf(fd, "%ld %d ", &offset, &data_len);
name_index[i].offset = offset;
name_index[i].name = malloc(data_len + 1);
fread(name_index[i].name, sizeof(char), data_len, fd);
}
for(i = 0; i < name_index_len; ++i) {
printf("%s %ld\n", name_index[i].name, name_index[i].offset);
free(name_index[i].name);
}
free(name_index);
return 0;
}
|
Natürlich würdest du name_index irgendwo in geeigneter Form aufbewahren und nicht gleich wieder freigeben, und ein paar Zugriffsfunktionen empfehlen sich auch, aber das grobe Prinzip sollte klar werden.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra |
