3. ich peil garnix ...

ich peil garnix ...

  • V

    Original erstellt von Silke_verzweifelt:
    also was ich an code bisher habe???
    nix denn ich setz mich erst ran wenn ich genau weiss wie und was ich machen muss.

    fehler. man fummelt sich sowas langsam zurecht und lernt währenddessen. und man probiert viel aus. 20 stunden sind da schnell wech, das ist normal.

    event. mach ich mir vorher ne übersicht in pseudo-code.

    halt ich für hilfreich.

    ich poste einfach mal was mir alles klar is ...

    gut. dann kann ich besser widersprchen.

    Binär-Suche : weil die Suchzeit dann nich linear mit der Datei-Grösse ansteigt sondern nur in etwa logarithmus der Dateigrösse. Also wichtig in grossen Datensätzen.

    korrekt.

    Nur wie implementiere ich so ein Suchmuster?

    im internet eins finden. egal, welche sprache. und nach c++ übersetzen. wird zwar ne array-version sein, aber zu ner datei-version kannstes umbasteln.

    Die Datensätze müssen wohl durch ein Trennzeichen in die Datei geschrieben werden, in java würd ich da nen "token" für benutzen, in c++??

    nein. der kasper denkt bestimmt an direktzugriffsdateien. das heißt, du nimmst die ne feste datensatzlänge und kannst dann den 53. datensatz leicht lesen mit fseek(53*sizeof(Datensatz));read(&data,sizeof(Datensatz)); oder so.

    Primär/Index-Datei:die Primär und Index-Datei ist nach dem selben Feld sortiert. Die Indexdatei enthält dann einen Eintrag je Block aus der Primärdatei

    nein. hauptdatei ist gar nicht sortiert. beim eintragen wird einfach der datensatz hinten drangeklatscht. und in den sortierten index wird ein verweis drauf geschrieben. so muß nur der kleine index sortiert sein, was viel schneller geht, als die haupt-datei sortiert zu halten.

    vielleicht ne Struktur in der Art definieren:
    struct artikel_Eingabe { int art_Nr; char art_Bez; float art_Preis; };

    art_Bez sollte eher ein array of chars sein, nicht nur ein einzelner buchstabe. also char art_Bez[20]; oder so.

    0
  • E

    erstmal vorweg:
    ich bin mir sicher, dass dir hier niemand das programm schreiben
    wird; du wirst lediglich loesungsvorschlaege und antworten
    zu konkreten fragen erhalten.
    was dimah, dir versucht hat zu sagen: nimm dir ein buch ueber
    c++ (oder schau mal im internet nach tutorials, schon mal auf www.c-plusplus.net nachgesehen? -> tutorials, links, faq) und arbeite
    dich mal in die sprache ein, dass bringt dir mehr als eine feritge
    loesung von irgendjemandem.

    also, ich geb dir mal ein paar weiter dankanstoesse: 🙂
    die idee mit der struktur ist ok, aber da du ja c++ prog. sollst nimm eine
    klasse (fast wie in java). fuer die bezeichung kannst du, fast wie in java,
    die klasse string (kleingeschrieben!) benutzen (dazu musst du noch
    ein include <string> machen).
    das saehe dann so aus:

    #include <string>
using namespace std;
class Artikel
{
  public:
     Artikel( int nr, string& bez, double preis );

  private:
    int nr;
    string bez;
    double preis;
}
sieht fast wie in java aus :)

    binaere suche? google, buch?
    trennzeichen? ein char ( ' ', ';', '#',...)?
    dateien? tutorial, faq, buch?
    fuer die index-/primaer-datei schau dir die funktionen tellg, seekp
    der fstreams an, und wirf mal nen blick in die faq.

    0
  • V

    Original erstellt von entelechie:
    die klasse string (kleingeschrieben!) benutzen (dazu musst du noch
    ein include <string> machen).

    ich halte struct und ein char-array hier für angemessen. weils die direktzugriffe vereinfacht.

    0
  • S

    toll dass ihr mir überhaupt antwortet, ich mein ich hab 4 Leutz aus der Uni angerufen und die sagten ..keine Zeit ...

    @KingRuediger ...klar das muss n char-arry sein 😉 auch ne Klasse ist sicher gut(oop)

    @volkard ... solltest mir mal Unterricht geben *fg* ...Direktzugriffsdateien.. das heißt, du nimmst die ne feste Datensatzlänge... das klingt gut! thx und auch richtig dass die Primärdatei garnich sortiert wird sondern nur die Index-datei aus der ein Zeiger auf den Datensatz in der Primärdatei verweist , vielleicht in etwa so ? --> (sizeof( primarystruct) * pos)

    @entelechie ich schau mir die Funktionen an, thx.

    0
  • S

    ich überleg grad ...
    es wird ja nur in der Index-Datei gesucht. Diese hat die Zuordnung "art_Nr" => "offset", und beides könnte man als Integer darstellen . Also die Index-Datei einfach mit jeweils Integer-Paaren füllen. Ein Integer sind 4 Bytes d.h. es reicht, wenn man auf die Index-Datei einfach in 8-Byte-Schritten zugreift, ohne Trennzeichen.
    Ist so ein gedanklicher Ansatz gut?

    Silke

    0
  • ?

    Original erstellt von Silke_verzweifelt:
    **ich überleg grad ...
    es wird ja nur in der Index-Datei gesucht. Diese hat die Zuordnung "art_Nr" => "offset", und beides könnte man als Integer darstellen . Also die Index-Datei einfach mit jeweils Integer-Paaren füllen. Ein Integer sind 4 Bytes d.h. es reicht, wenn man auf die Index-Datei einfach in 8-Byte-Schritten zugreift, ohne Trennzeichen.
    Ist so ein gedanklicher Ansatz gut?

    Silke**

    ja, du solltest aber wg. der Portabilität nicht 8, sondern 2*sizeof(int) nehmen.

    0
  • V

    jo.

    0
  • K

    mit strings aus c++ wirds eklig, weil die ne variable länge haben, also würd ich eben solche char arrays nehmen. für 4 c++ vorlesungen isses schon bisschen happig...

    wieso steigt doe suchdauer bei binary search eigentlich nur logarithmisch im vgl. zur dateigröße an?

    0
  • ?

    Original erstellt von Korbinian:
    wieso steigt doe suchdauer bei binary search eigentlich nur logarithmisch im vgl. zur dateigröße an?

    Eingabe wird immer halbiert.

    0
  • K

    Original erstellt von <KingRuediger>:
    Eingabe wird immer halbiert.

    Weil nur alle 2*sizeof(int) gelesen wird, und nicht alles? (vermut mal ja :p)

    0
  • V

    Original erstellt von Korbinian:
    mit strings aus c++ wirds eklig, weil die ne variable länge haben, also würd ich eben solche char arrays nehmen. für 4 c++ vorlesungen isses schon bisschen happig...
    wieso steigt doe suchdauer bei binary search eigentlich nur logarithmisch im vgl. zur dateigröße an?

    wie sochste denn in nem worterbuch? ungefähr so (es hat 1000 seiten):
    //1000 kandidaten
    bei seite 500 aufschlagen. ah, es steht weiter hinten.
    //nur noch 500 kandidaten
    bei seite 750 aufschlagen. ah, es steht weiter vorne.
    //nur noch 250 kandidaten
    usw.
    nach 10 mal blättern nur noch 1 kandidat.

    für ein buch mit ner million seiten braucht man nur 20 mal blättern. bei ner milliare nur 30 mal.

    0
  • K

    ahjo. aber in genau diesem fall ist das doch eigentlich wurscht oder? ich mein, wenn die indexdatei eh sortierte werte in form von

    00000000 11001001
00000001 10001100
00000010 11100110
00000011 00011001
00000100 10011001
...      ...

    enthält, dann brauch ich doch auf diese datei kein binary search verwenden. wenn ich weis, dass die 2*x bytes groß ist, dann habe ich x datensätze. ist die zahl dann nächer bei 0, fang ich vorne mit dem durchgehen an, ist sie näher bei x, fang ich hinten an. problem dann nur: sind die artikelnummern belibige (eindeutige) zahlen, können z.b. 500 datensätze in der indexdatei sein (id 5000 - 5499), und meine methode fängt, wenn sie nach datensatz 5000 frägt, am ende der datei an.
    Binary search heist also immer, dass in der Mitte des [arrays/datei/xyz] angefangen wird?

    0
  • V

    die artikelnummern sind beliebige zahlen.

    und natürlich ist binäre suche gut bei großen mengen. nicht lachhafte 500 datensätze. die werden ja auf einmal gelesen. nein, 1000000 datensätze. also ne 8mb-datei nur der index. liest du die ganz durch, biste alt und grau, bis die zahl gefunden ist. machste aber binäre suche, brauchste nur 20 zugriffe. bei ner zugriffzeit von 10ms also ne lachhafte fünftel sekunde. une bei doppelt so vielen daten eben 21 zugriffe. würdest du die ganze indexdatei lesen, würdtest du bei doppelt so vielen daten doppelt so lange brauchen.

    0
  • K

    und wieso eigentlich 'binäre' suche? weil die daten binär verglichen/ausgelesen werden, aber wohl nicht wegen dem suchvorgang oder...

    0
  • B

    binäre Suche wie in binärer Baum. Hat nix mit Binärdarstellung zu tun.

    0
  • K

    Wieder was gelernt 🙂

    0
  • ?

    hastes jetzt hinbekommen?

    0
  • S

    so das hab ich mal bisher geschrieben ....danke für alle tipps bisher 😉

    das Problem is noch die Funktion binary_search(...) irgendwas ist an dem Zugriff(den Parametern) noch falsch.

    kann ich zum sortieren Einschreiben in die Index-Datei die Methode
    lower_bound(....) benutzen und wenn ja vielleicht ein kleine Hilfe???

    #include <iostream>
#include <algorithm>
#include <string>
#include <stdio>
using namespace std;

struct art_Eingabe{
    int art_Nr;
    char art_Name[50];
    double art_Preis;
};

void dat_Schreiben(){
    FILE *pDat;
    pDat = fopen("prim.dat","a+");
    if (pDat!=NULL){
        //....
        //code ........Datensatz einschreiben
        //....
        cout << "pDat geoeffnet"<<endl;

        FILE *iDat;
        iDat = fopen("index.dat","w");
        if (iDat!=NULL){
            // ..lower_bound
            cout << "iDat  geoeffnet"<<endl;
        }
        else{
            cerr << "Lese/Schreibfehler in iDat"<< endl;
        }
    }
    else cerr << "Lese/Schreibfehler in pDat"<< endl;
}
void dat_Suchen(int key){
    FILE *iDat;
    iDat = fopen("index.dat","r");
    if (iDat!=NULL){
        //if(binary_search(iDat.begin(),iDat.end(),key)){
        // OFFSET --> pDat
        // Ausgabe Datensatz
            cout<<"Datensatz gefunden"<<endl;
        //}
    }
    else cerr << "Lesefehler"<< endl;
}

void main() {
    bool ende = false;
    char antwort;
    int eingabe;
    cout << "Artikel.cpp\n"<<endl;
    cout <<"Artikel-Datensatz durchsuchen oder bearbeiten\n" << endl;
    while (!ende) {     // also erstmal true
        cout << "Suchen (1) oder Eingeben (2) : " ;
        cin >> eingabe ;
        if(eingabe ==1){
            int key;
            cout << "Artikelnummer eingeben: ";
            cin >> key;
            dat_Suchen(key);
        }
        else if (eingabe == 2){
           dat_Schreiben();
        }
        else cerr << "Fehler in main()"<<endl;

        cout << "Noch einmal (j/n) ? ";
        cin  >> antwort ;
        cout << endl;
        ende = (antwort != 'j');  //  ende = true oder false
    }
}

    bye Silke 🙂

    0
  • ?

    1. Warum nimmst du FILE und keinen fstream?
    2. (siehe Kommentare)

    dat_Suchen(int key){
    FILE *iDat;
    iDat = fopen("index.dat","r"); // Du öffnest die Datei doppelt!
    if (iDat!=NULL){
/*iDat ist keine Sequenz! Du musst erst iDat in einen vector<int> einlesen!*/
        //if(binary_search(iDat.begin(),iDat.end(),key)){
        // OFFSET --> pDat
        // Ausgabe Datensatz
            cout<<"Datensatz gefunden"<<endl;
        //}
    }
    else cerr << "Lesefehler"<< endl;
}
    0
  • S

    @KingRuediger bitte erklär mir das doch, wieso öffne ich die Datei 2mal??? ich dachte mit iDat = fopen("index.dat","r"); würde ich folgendes erreichen :
    index.dat wird lesend geöffnet bzw. neu erstellt falls nicht vorhanden.
    kannst du vielleicht noch kurz erklären warum ich fstream nehmen soll?
    Ich dachte, dass ich gerade nicht die iDat(Index-Dat) als eine Sequenz einlesen soll, kannst mir auch dazu was schreiben?
    Ich find das wirklich sehr nett von euch, dass ihr euch damit befasst und mir die nötigen Denkansätze liefert...
    🙂 Silke

    0
Anmelden zum Antworten