Datenstrukturen zum Thema Voxel, Hashing, Komprimierung, einfach-verkettete Liste

Hallo!

Es ist zwar immer blöd HA's von anderen lösen zu lassen, aber ich seh hier nicht richtig durch Es wäre cool, wenn mir jemand nen Tipp geben könnte, oder ne WebSite die das Problem betrifft oder irgendwelche Ansätze der Programmierung, das wäre sehr gut. Also hier erst mal die Aufgaben:

(a) Gegeben sei Ihnen ein dreidimensionales Binärbild der Auflösung N×N×N. Darin seien durchschnittlich nur O(N²) Voxel gesetzt, die genaue Anzahl kann jedoch auch größer oder kleiner sein und soll sich zur Laufzeit ändern können (Setzen oder Löschen von Voxeln). Wie kann man das 3D-Bild unter Ausnutzung von Hashing komprimieren, aber gleichzeitig noch in konstanter Zeit einen wahlfreien Zugriff gewährleisten, z. B. um zu klären, ob ein Voxel gefüllt ist oder nicht? Es reicht also nicht, die Vordergrundvoxel der Reihe nach in eine Liste zu schreiben! Gehen Sie insbesondere auf die Größe der Hashtabelle, die Art des Hashverfahrens, die Schlüsselproblematik und den Komprimierungsfaktor ein!

(b) Implementieren Sie eine Funktion CSingleList::Search(keytype key), die nach einer erfolgreichen Suche in einer einfach verketteten selbstorganisierenden Liste das gefundene Element auskettet und an den Listenanfang schreibt. Gemeint ist nicht der Tausch mit dem Kopfelement! Die Funktion soll außerdem einen Zeiger auf das gefundene Element zurückgeben bzw. NULL, wenn es nicht enthalten war.

Ich finde die Aufgaben bissl schwierig und kann diese nicht so recht mit meinen Kenntnissen lösen, wäre echt toll, wenn mir da jemand weiterhelfen könnte.

Viele Grüße und Dank!

SideWinder

Crosspostings sind hier unerwünscht.

MfG SideWinder

BorisDieKlinge

wie ist den der zugriff auf ein Voxel bisher? ein voxel besteht aus 3 Koordinaten und einem Wert oder? Normalerweise wäre das jetzt eine 3-dim Array. Man könnte dise aber in eine 1-dim liste speichern und hätte einen sqeuentiellen zugriff. Statt 3 koordinaten werte pro Voxel bräuchte man dann nur einen wert, welcher die Koodrinaten repräsentiert

statt:
3-dim

int Array[10][10[10];
Val= Array[x][y][z]

1-dim

int Array [1000];
Val= (x*100-100)+(y*10-10)+z;

Voxel mit kleinen werten, könntest du nun gruppieren und dir den Koordinatwert speichern..

BorisDieKlinge schrieb:

wie ist den der zugriff auf ein Voxel bisher? ein voxel besteht aus 3 Koordinaten und einem Wert oder? Normalerweise wäre das jetzt eine 3-dim Array. Man könnte dise aber in eine 1-dim liste speichern und hätte einen sqeuentiellen zugriff. Statt 3 koordinaten werte pro Voxel bräuchte man dann nur einen wert, welcher die Koodrinaten repräsentiert

statt:
3-dim
int Array[10][10[10];
Val= Array[x][y][z]
1-dim
int Array [1000];
Val= (x*100-100)+(y*10-10)+z;
Voxel mit kleinen werten, könntest du nun gruppieren und dir den Koordinatwert speichern..

In der Aufgabenstellung steht doch schon, dass es mit Hashing gemacht werden soll, was du da schreibst ist doch quatsch und hat garnix damit zu tun.

BorisDieKlinge

DS'er schrieb:

Es reicht also nicht, die Vordergrundvoxel der Reihe nach in eine Liste zu schreiben! Gehen Sie insbesondere auf die Größe der Hashtabelle, die Art des Hashverfahrens, die Schlüsselproblematik und den Komprimierungsfaktor ein!

ups... das hab ich übersehen... ^^

naja jetzt weis er wenigsten wie man das ganze in eine liste schreibt;)

dankte mein schlauer bub für die aufklärung...

Sorry, das ich jetzt erst das Thema wieder aufgreife, aber wie funktioniert das denn nun mit dem Hashing auf diesem Problem?