Hashtabelle mit verketteten Liste

Ich habe ein Problem mit einer übung für die Schule.

Muss ich implementieren Sie eine hash-Tabelle mit dieser Struktur :

struct Book {
char * title;
char * author;
int price;
struct Book * next;
}

Also ich muss eine Funktion erstellen initTable() die meine hash-Tabelle ist eine Tabelle der struct Buch der 1000 Elemente. Also meine Funktion ist :

struct Book* initTable(){
struct Book *tab = malloc(sizeof(struct Book) * 1000);
return tab;
}

Beachten Sie, dass die Funktion soll das erste element von meinem Tisch.
Aber ich weiß nicht, ob diese syntax korrekt ist.

Also meine Fragen sind :

Ist, dass eine richtige syntax ?
Wie kann ich navigieren in der Tabelle ? Zum Beispiel, wenn ich will, zu gehen, um die Zelle 50 für meine Tabelle, wie kann ich tun?

Dann, wenn es zu einer Kollision in meinem hash-Tabelle, die ich zum erstellen einer verknüpften Liste, wo ich meine Elemente in Konflikt. Aber die einzelnen Zellen meiner Tabelle sind eine Struktur, und nicht ein Zeiger von dieser Struktur, so verstehe ich nicht, wie kann ich mein link-Elemente.

Sind Sie sicher, dass Ihre Tabelle sein soll, eine Tabelle der Strukturen, und nicht die Tabelle von Zeigern auf Strukturen?
für die Klärung sind Sie wahrscheinlich erstellen Sie ein array[1000] von verketteten Listen. Diese Listen enthalten nur ein einziges element, aber auf die hash-Konflikt enthalten mehr
Eine Sache, die Ihnen fehlt, ist die Initialisierung der Tabelle Artikel. Man könnte hinzufügen memset Anruf nach malloc oder ersetzen malloc mit calloc (die Nullen der Speicher reserviert).
is that a correct syntax? - gut, warum fragst du? warum nicht Sie versuchen, kompilieren? wenn es kompiliert, ist die syntax korrekt ist.
Ich meine, ist, dass der gute Weg, um eine hash-Tabelle von struct Buch

InformationsquelleAutor | 2014-06-22

c hashtable linked-list

1

Einer hash-Tabelle ist gedacht zum nachschlagen einen Eintrag in einer Sammlung von Schlüssel in konstanter Zeit. In Bezug auf die Umsetzung dieses besteht in der Regel aus einem "versteckten" array Objekt Zeiger (nicht die Objekte selbst). Sie brauchen dann eine Hash-Funktion wandelt einen Schlüssel in ein array-lookup-index (integer). Als Beispiel:
```
ValueObjectType **createHashTable(int hashSize)
{
    ValueObjectType **table = malloc( sizeof(ValueObjectType *) * hashSize);
    return table;
}

void hashInsert(ValueObjectType **hashTable, KeyObjectType key, ValueObjectType *value)
{
    int arrayIndex = hashingFunction(key);
    if ( hashTable[arrayIndex] != NULL ) traverseLinkedListAndAdd(...);
    else hashTable[arrayIndex] = value;
}

ValueObjectType *lookupByKey(ValueObjectType **hashTable, KeyObjectType key)
{
    int arrayIndex = hashingFunction(key);
    return traverseLinkedListAndReturnObjectWithKey(...);        
}
```
Einer Hash-Funktion in der Regel beinhaltet die Einnahme eines oder mehrere Schlüssel-Elemente (die beliebigen Typs sein können) und konvertiert Sie zu einem einzigen integer-Wert und dann die Umwandlung, die zu einem array-index, indem die modulo der hash-array-Größe.

Den Zweck, für die verknüpfte Liste in Ihrem Buch struct ist die Auseinandersetzung mit hash-Kollisionen. Eine hash-Kollision tritt auf einfügen, weil der angegebene Schlüssel existiert bereits in der hash (in diesem Fall sollten Sie ersetzen Sie den Wert Objekt-Referenz auf das neue Objekt) oder aufgrund der nicht-Eindeutigkeit der Hash-Funktion. Wenn letzteres passiert, wird die verknüpfte Liste speichert mehrere Einträge mit unterschiedlichen Schlüsseln, dass hash, um die gleichen array-index (in der Regel durch Durchlaufen der Liste, ersetzen Sie ein element von der Liste, wenn Schlüssel der Geschlechter gesehen wird, und sonst Wende das neue Objekt am Ende).

Im Beispiel-code oben habe ich einen separaten Schlüssel-Objekt, aber um zu beurteilen, Gleichheit der Schlüssel muss entweder eingeschlossen in das Objekt selbst (ich vermute in Ihrem Fall der Schlüssel ist eine Kombination aus Titel und Autor), oder verpackt in eine meta-Struktur (z.B. eine "KeyValue" struct enthält einen Zeiger auf den Schlüssel und Wert, die Sie würde hash statt ValueObjectType). Sie müssen Logik zum auswerten der Gleichheit/Ungleichheit der beiden Tasten, um ordnungsgemäß zu behandeln die hash-Kollision zu Fall.

Habe ich Links die Hash-Funktion, verknüpfte Liste, Navigations-und Schlüssel-Geschlechter-Logik unbekannter, denn dies ist hier klar, was Ihr Lehrer möchte, dass Sie lernen, wie zu tun ist.

Mein Lehrer gab mir den hash-Funktion, die sich nur mit dem Titel des Buches. Der header der Funktion initTable() ist die gleiche, die mein Lehrer mir gab. Was stört mich ist, wenn ich zu tun haben mit der verlinkten Liste in meinem hash-Tabelle, so meine hash-Tabelle zu enthalten, die Zeiger auf Strukturen Buch und nicht nur die Struktur nicht ?
Wie ich schon sagte in der Antwort, die verkettete Liste ist, wie Sie befassen sich mit hash-Kollisionen (die passieren, wenn zwei verschiedene Schlüssel ergeben die gleiche array-lookup-index). Der Allgemeine Algorithmus für hashes, ist beschrieben in der Antwort oben - können Sie herausfinden, die Besonderheiten, die für Ihre Hausaufgaben-problem.

InformationsquelleAutor T3am5hark
0

du willst
```
malloc(sizeof(struct book) * 1000)
```
Was malloc tut, wird Speicher reserviert. Zuerst einen Zeiger für den start in das Objekt dann zusätzlichen Raum für irgendetwas anderes, werden in diesem Objekt gespeichert. In Ihrem Fall, dass Sie möchten, erstellen Sie ein array mit 1000 Objekten, so müssen Sie Speicher für diese Objekte nach dem ersten Zeiger.

für die Navigation in einem array zugewiesen schauen Sie in Zeiger-Arithmetik. Von wesentlicher Bedeutung was dies bedeutet ist, dass Sie sich für ein Objekt bei einem offset von dem ersten Zeiger.

für einen start auf den Zeiger arithmatic check-out http://www.eskimo.com/~scs/cclass/notes/sx10b.html

Danke für die Antwort.Aber entschuldigen Sie mich für diese Frage aber wie kann ich das tun, was Sie vorschlagen ? Ich sehe nicht ganz klar, wie ich das tun kann. Tut mir Leid für Sie zu stören.
was ist ein Livre in deinem code oben?
Sie sind mallocing ein array von Livre und speichern, array als Zeiger auf ein Livre
Sorry, dass ich einen Fehler gemacht habe, ist das Buch in der Funktion.
In der Tat, das Motiv, dass ich haben, sagt "eine Funktion zu erstellen, die eine hash-Tabelle, die eine Tabelle von struct Buch mit 1000 Elementen. Diese Funktion zuweisen eine Tabelle von 1000 struct Buch und gibt einen Zeiger auf das erste element der Tabelle"

InformationsquelleAutor pwilmot

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.