Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Datenstrukturen
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
04.06.2003, 11:21 Uhr
~Mexa
Gast


Eimal etwas Theorie hoffe es stört euch nicht!
Mir geht es um Datenstrukturen und ihren Einsatz bzw Verwendung in Programmen. Mein Chef hat gemeint ich soll mal ein bischen auf die Verwendung von verschiedenen Strukturen schauen!
So nun meine Frage wann verwendet ihr welche Struktur?
Hashtabell
verkettete Liste
Binärer Baum
Array
bezüglich Grösse, Suchen.....
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
05.06.2003, 16:17 Uhr
Bruder Leif
dances with systems
(Operator)


Moin!

Kommt drauf an, was Du machen willst. Faustregel:

Array: Wenn Du 1. Weißt, wie viele Elemente Du speichern willst, 2. Über ihre Nummer sehr schnell darauf zugreifen willst und 3. diese Nummer im Idealfall einfach hochgezählt wird. Und Du keine Lust hast, die STL zu verwenden oder eigene Algos zu programmieren ;-)

Hashtabelle: Wie Array, aber mit "beliebigem" Index statt Ganzzahl. Praktisch, wenn Du einen String als Indexer benutzen willst, oder wenn Du relativ wenige Werte speichern mußt und deren "gedachte Indexwerte" sich stark unterscheiden oder einen wesentlich größeren Speicherbereich abdecken würden.

Mal ein Beispiel aus meinem Studium: Ein Krankenhaus weist jedem Patienten eine "I-Zahl" als eindeutige Patientennummer zu. Die setzt sich nach dem Muster TTMMJJNNGM zusammen, wobei:

TTMMJJ = Geburtsdatum (das Prinzip stammt aus den 70ern, über Y2k hat damals noch niemand nachgedacht)
NN = "Verschlüsselung" des Namens nach den Anfangsbuchstaben
G = Geschlecht, 0/1
M = Mehrfachbelegung, falls mehrere Patienten des selben Geschlechts am selben Tag Geburtstag haben und den selben Namenscode bekommen. Ab 10 ist also Schicht

Das Problem dabei ist, wenn Du jetzt, sagen wir, 10'000 Patienten, also etwa so viel, wie ein durchschnittliches Krankenhaus in einem Monat aufnimmt, in einem Array speichern wolltest, wobei die I-Zahl (für den Begriff gehört der Prof geschlagen *grummel*) den Index im Array angibt, wären das 7,3 * 10^7 Einträge. In einer Hash-Tabelle mit der I-Zahl als Indexer sind es "nur" 1 * 10^4 Einträge. Nachteil: In der Regel (!) hast Du keine Chance, den Einträgen eine Reihenfolge zuzuweisen.

Verkettete Liste: Wenn Du beim Programmieren noch nicht weißt, wie viele Einträge Du speichern mußt. Oder die Einträge sortiert wieder ausgeben willst. Nachteil: Wenn Du NUR das 5073. Element in der Liste haben willst, mußt Du erst durch die 5072 davor iterieren. Und das Sortieren dauert ne Weile...

Binärbaum:: Im Prinzip eine spezielle verkettete Liste, besonders praktisch, wenn Du Deine Daten vorsortiert halten willst und sehr schnell auf einzelne Elemente zugreifen willst. Bessere Implementierung für eine Hash-Tabelle als die verkettete Liste.
Wenn ein Baum über längere Zeit bestehen soll, besser einen rot/schwarz-Baum oder gleich einen B(*)-Baum verwenden, sonst degeneriert er allmählich zur verketteten Liste und der Geschwindigkeitsvorteil ist dahin...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
05.06.2003, 16:36 Uhr
~0xdeadbeef
Gast


Ergänzend dazu (aus meiner Sicht)

Array: Wenn du

- abschätzen kannst, wieviele Elemente es geben wird
- du den Index, auch ohne den Inhalt des Arrays zu kennen, sinnvoll dem Inhalt des Arrays zuweisen kannst. Dazu zählen zum Beispiel Vektoren und Matrizen.

Anstelle eines Arrays kannst du in C++ auch die Template-Klasse vector benutzen.

Hastable: Die Idee hinter einer Hastable ist, dass du dir ein Array begrenzter Größe nimmst, und außerdem eine Funktion hernimmst, die einem Objekt eine Zahl - einen sogenannten Hashwert - zuweist, der dann als Index benutzt wird. Das Problem ist, dass keine Hash-Funktion perfekt ist, das heißt, die Funktion wird mehreren Objekten den gleichen Wert zuweisen (man nennt das Kollision). Es gibt verschiedene Methoden, damit zurechtzukommen, welche gerade die sinnvollste ist, muss im Einzelfall entschieden werden.

Liste: Du kannst mit Tricks wie doppelt verketteten Listen, Head- und Tailpointern, Skip-Listen und Dummies auch aus Listen Performance rausholen, aber Leif hat schon recht. Die Dinger sind im wesentlichen als FIFOs und LIFOs brauchbar. Wenn du schnell an die Daten ranwillst, nimmst du nen Baum.

Bäume: Bäume degenerieren ziemlich selten zu Listen, aber wenn man Gegenmaßnahmen ergreift, kann man die Zugriffszeit auf die Blätter schon deutlich verkürzen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
28.10.2004, 21:27 Uhr
~kamicat
Gast


hi
ich hab ein problem! und zwar weis ich nicht wie man listen sortieren kann! ich brauch das aber ganz dringend, also wenn jemand eine idee hat bitte antworten!!!!
ich bin sonst echt arm dran!! es muss nur eine lineare liste sein, keine verkettete!
danke
kamicat
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
29.10.2004, 07:24 Uhr
derphilipder



 Du meinst eine einfach verkettete?! Verkettet ist eine Liste immer.

Du könntest z.B. den Bubble Sort verwenden. Dabei wird die Liste durchlaufen, jedes Listenelement mit seinem Nachbarn verglichen und ggf. ausgetauscht. Dabei musst Du Dir merken, ob Du in einem Durchlauf mindestens einmal getauscht hast. Ist das nicht der Fall, bist Du fertig.


Zitat von Bruder Leif:

Das Problem dabei ist, wenn Du jetzt, sagen wir, 10'000 Patienten, also etwa so viel, wie ein durchschnittliches Krankenhaus in einem Monat aufnimmt, in einem Array speichern wolltest, wobei die I-Zahl (für den Begriff gehört der Prof geschlagen *grummel*) den Index im Array angibt, wären das 7,3 * 10^7 Einträge. In einer Hash-Tabelle mit der I-Zahl als Indexer sind es "nur" 1 * 10^4 Einträge. Nachteil: In der Regel (!) hast Du keine Chance, den Einträgen eine Reihenfolge zuzuweisen.


Wieso 7,3*10^7
Das versteht der Philip nicht.
--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
29.10.2004, 16:57 Uhr
~kamicat
Gast


also muss ich die gesamte liste durchlaufen und dann in dieser procedure die sortierprocedure aufrufen???
in die liste sollen nur wenige einträge eingetragen werden, also funktioniert das mit bubble sort schon!!
Danke schon mal
kamicat
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
29.10.2004, 19:03 Uhr
derphilipder



 Ein kleines Beispiel

C++:
#include <iostream>
using namespace std;

int main()
{
    struct listel//Listenelement
    {
        int data;
        listel* next;
    };

    listel *root = NULL, *hlp = NULL;

    root = new listel;    //Liste fuellen
    hlp = root;
    hlp->data = 0;
    for(int i = 1; i < 10; i++)
    {
        hlp->next = new listel;
        hlp = hlp->next;
        hlp->data = i;
        hlp->next = NULL;
    }

    hlp = root;
    while(hlp != NULL)//Ausgabe vorher
    {
        cout << hlp->data << endl;
        hlp = hlp->next;
    }

    bool finished = false; //Ab hier wird sortiert
    listel* prev, *lptr;

    while(!finished)
    {
        hlp = root;
        finished = true;

        if(root != NULL && root->next != NULL)//Was zum sortieren da
        {
            while(hlp->next != NULL)
            {
                if(hlp == root)//Listenanfang?
                {
                    hlp = hlp->next;
                    prev = root;
                    if(prev->data < hlp->data)//Listenelemente vergleichen
                    {
                        root = hlp;
                        prev->next = hlp->next;
                        hlp->next = prev;
                        hlp = prev;
                        prev = root;
                        finished = false;
                    }
                    else
                    {
                        prev = hlp;
                        hlp = hlp->next;
                    }

                }
                else
                {
                    lptr = hlp->next;
                    if(hlp->data < lptr->data)//Listenelemente vergleichen
                    {
                        prev->next = lptr;
                        hlp->next = lptr->next;
                        lptr->next = hlp;
                        prev = hlp;
                        hlp = lptr;
                        finished = false;
                    }
                    else
                    {
                        prev = hlp;
                        hlp = hlp->next;
                    }
                }


            }
        }
    }

    hlp = root;
    while(hlp != NULL)//Ausgabe danach
    {
        cout << hlp->data << endl;
        hlp = hlp->next;
    }
    return 0;
}


Geht vermutlich auch einfacher...hab mir ganzschön einen abgewürgt mit der einfach-Verkettung
--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
01.11.2004, 21:20 Uhr
~kamicat
Gast


Vieltausend dank dass du dir solche mühe gemacht hast!!!
Damit hast du mir praktisch mein leben gerettet!!!
Ich war leider das ganze wochenende nicht zu Hause und hatte mit einer so schnellen antwort auch ehrlich gesagt nicht gerechnet!!!
Also noch mal danke!!
kamicat
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
02.11.2004, 07:17 Uhr
Bruder Leif
dances with systems
(Operator)



Zitat von derphilipder:
Zitat Bruder Leif:
Das Problem dabei ist, wenn Du jetzt, sagen wir, 10'000 Patienten, also etwa so viel, wie ein durchschnittliches Krankenhaus in einem Monat aufnimmt, in einem Array speichern wolltest, wobei die I-Zahl (für den Begriff gehört der Prof geschlagen *grummel*) den Index im Array angibt, wären das 7,3 * 10^7 Einträge. In einer Hash-Tabelle mit der I-Zahl als Indexer sind es "nur" 1 * 10^4 Einträge. Nachteil: In der Regel (!) hast Du keine Chance, den Einträgen eine Reihenfolge zuzuweisen.
Zitat Ende

Wieso 7,3*10^7
Das versteht der Philip nicht.


Moin!

Ganz einfach: Die "I-Zahl" (und der Prof gehört immer noch geschlagen ) hat folgende Struktur:


Code:
TTMMJJNNGM
TTMMJJ: Geburtsdatum des Patienten. Um Y2k hat sich damals noch niemand Gedanken gemacht...
NN    : "Verschlüsselung" des Namens nach den häufigsten Anfangsbuchstaben (Tabelle, Werte 00-99)
G     : Geschlecht (0/1)
M     : Mehrfachbelegungen, normalerweise 0, wird hochgezählt, wenn mehrere Patienten ansonsten den gleichen Eintrag hätten


Daraus ergibt sich:
- 365 mögliche Werte für TTMM (naja, SINNVOLLE Werte)
- 100 mögliche Werte für JJ
- 100 mögliche Werte für NN
- 2 mögliche Werte für G
- 10 mögliche Werte für M

Alles zusammen: 73'000'000 mögliche Werte, also 7,3*10^7


Edit: Wie verschachtelt man eigentlich quote-Tags?
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.
Dieser Post wurde am 02.11.2004 um 07:19 Uhr von Bruder Leif editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
02.11.2004, 08:23 Uhr
derphilipder



 Das versteht der Philip
--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: