4. lexikographisches Sortieren

lexikographisches Sortieren

  • B

    Hallo,

    Ich habe Probelem mit folgender Aufgabe:

    Es soll ein Programm geschrieben werden, dass zufällige Zeichenketten nach einem vorgegebenen Alphabet erzeugt, sortiert und ausgibt.

    Das Alphabet a soll die Länge n haben (n wird zur Laufzeit eingegeben, 1<=n<=95), aus druckbaren Zeichen bestehen und es sollen keine Zeichen doppelt vorkommen. (Das Alphabet wird zur Laufzeit zeichenweise eingelesen)
    Dann sollen zwei Zahlen k und m eingegeben werden, und k Zeichenketten aus den Zeichen des Alphabets mit zufälliger Länge (aber maximaler Länge m) erzeugt werden. (und ausgegeben)
    Zum Schluss sollen die Zeichenketten nach der Reihenfolge des Alphabets a sortiert und das Ergebnis ausgegeben werden. (Sortieren durch Vergleichen zweier Zeichenketten und bei Bedarf Vertauschen)
    Für Ausgabe, Vergleich und Sortierung sollen die Funktionen print(), vgl() und sort geschrieben werden
    Die zum Sortieren benötigte Zeit soll mithilfe der Systemuhr gemessen und zum Schluss ausgegeben werden.

    Ich habe folgendes Programm geschrieben:

    #include <time.h>
    #include <conio.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    void print(char**,int);
    int vgl(char*,char*,char*);
    void sort(char**,int,char*);

    int main(void) {
    char c;
    int i,j;
    int k,m,n;

    // Alphabet erzeugen
    printf("Laenge des Alphabets:\t");
    do
    scanf("%d",&n);
    while(n<1||n>95);

    char a[n];
    for(i=0;i<n;i++) {
    printf("%02d. Zeichen: ",i+1);
    do
    c=getch();
    while(c<32||c>127||strchr(a,c)!=NULL);
    a[i]=c;
    printf("%c\n",a[i]);
    }
    a[i]='\0';

    printf("Anzahl Zeichenketten:\t");
    scanf("%i",&k);
    printf("maximale Laenge:\t");
    scanf("%i",&m);

    // zweidimensionales Array erzeugen (m x n)
    charz;
    int l;
    srand(time(NULL));
    z=(char    )calloc(k,sizeof(char*));
    for(i=0;i<k;i++) {
    l=1+rand()%m;
    z[i]=(char*)calloc(l,sizeof(char));
    for(j=0;j<l;j++)
    z[i][j]=a[rand()%(n-1)];
    z[i][j]='\0';
    }

    printf("\nUnsortiert:\n");
    print(z,k);

    sort(z,k,a);
    printf("\nSortiert: ");
    print(z,k);

    system("PAUSE");
    return 0;
    }

    void print(char**arrarr,int strings) {
    int i;
    for(i=0;i<strings;i++)
    printf("\n%s",arrarr[i]);
    putchar('\n');
    }

    //Vergleicht die ZK miteinander
    int vgl(char*s,char*t,char*alphabet){
    int minlaenge,laenge1,laenge2,poslex1,poslex2,i,k;
    if(strlen(s)<strlen(t)) {
    minlaenge=strlen(s);
    }
    else {
    minlaenge=strlen(t);
    }
    for(i=0;i<minlaenge;i++)
    {
    k=0;
    while(s[i]!=alphabet[k])
    k++;
    poslex1=k;
    k=0;
    while(t[i]!=alphabet[k])
    k++;
    poslex2=k;
    if(poslex1<poslex2){
    return 1;
    }
    if(poslex2<poslex1){
    return 2;
    }
    }
    if(laenge1==laenge2){
    return 0;
    }
    if(laenge1<laenge2){
    return 1;
    }
    return 2;
    }

    void sort(char**stringArray,int k,char*alphabet) {
    int i=k-1,l;

    do {
    for(l=0;l<i;l++) {
    char tauschstring[strlen(stringArray[l])];
    switch(vgl(stringArray[l],stringArray[l+1],alphabet)){
    case 2:
    strcpy(tauschstring,stringArray[l]);
    strcpy(stringArray[l],stringArray[l+1]);
    strcpy(stringArray[l+1],tauschstring);
    break;
    case 1:
    default:
    break;
    }
    }
    i--;
    } while(i>0);
    }

    Es gibt aber noch ein paar Probleme:
    wenn ich bspw. Das Alphabet (Länge 10) „abcdefghij“ eingebe und 10 Zeichenketten mit max. Länge 10 erzeugen lassen will, stürzt das Programm(fast) immer ab
    Beim Erzeugen der Strings wird das Ende nicht erkant, sodass ich die ASCII-NULL manuell anfügen muss
    Das Sortieren dauert bei mir weniger als eine Sekunde - ansich kein Problem, aber ich weiss nicht, wie ich die Zeit mit ausreichender Genauigkeit stoppen kann

    Wäre lieb, wenn mir jemand helfen würde 😉

    0

  • Ich bin ja net so der Ansi C Profi, aber

    char a[n];
for(i=0;i<n;i++)
{
   ...

    Wenn 10 Zeichen erwünscht sind und eingegeben werden, ist kein Platz mehr für '\0' drum solltest du hier Eingabe + 1 Zeichen reservieren.

    Mich wundert, dass es compiliert, da die Groesse deines Array's zur Kompilierzeit unbekannt ist. a[n] << n wird doch noch eingegeben.

    Codatags find ich schön 😉

    Zur Messung würde ich spontan mal auf die time.h hinweissen. Da sollte es
    bestimmt was geben. So suche im Internet mal nach time.h + Zeitmessung.

    PS: fuer super genaue Zeitmessungen fallen mir spontan nur WinAPI-Funktionen ein

    0
  • B

    hi, erstmal vielen Dank für die schnelle Antwort 😉

    Ich dachte, bei a[10] wären die Elemente 0 bis 9 für die Zeichen 1 bis 10 und für die ASCII-Null ist das 10. Element vorgesehen (oder täusch ich mich da?)

    Könntest Du mir bitte ein ppar Beispiele für die erwähnten WINAPI-Funktionen zur genauen Zeitmessung nennen? (und könnteich die auch bei einer Konsolenanwendung benutzen?)

    Grüße Bianca

    0

  • char a[10] sagt aus, dass du 10 Zeichen Speicher reservierst.
    Also von 0 - 9. Das Nullterminierungszeichen ist dort leider nicht automatisch dabei. Das musst du mit berücksichtigen.

    char a[10] = {'a','b','c','d','e','f','g','h','i','\0'};

    zum Messen bevorzuge ich gern folgendes Beispiel:

    LONGLONG freq;
        LONGLONG startFrame;
        LONGLONG endFrame;

        QueryPerformanceFrequency((LARGE_INTEGER*) &freq);
        QueryPerformanceCounter((LARGE_INTEGER*) &startFrame);

        // Code, dessen Laufzeit gemessen werden soll bitte hier einfuegen 

        QueryPerformanceCounter((LARGE_INTEGER*) &endFrame);
        printf("%d\t", endFrame-startFrame);

    Allerdings brauchst du hier die <windows.h> Wie es bei Linux aussieht, weiß ich wohl garnet 😃

    0

  • Vielleicht noch ein kleiner Nachtrag:

    printf("%f", (endFrame-startFrame) / (long double)freq);

    sollte dir die Anzahl der Sekunden liefern, falls du von den Werten, die rauskommen, irritiert sein solltest

    0
  • B

    danke Dir nochmal 🙂

    Die Zeit wird denke ich in Millisekunden (ms) ausgegeben, richtig?

    P.S. hab Deinen Nachtrag erst jetzt bemwerkt

    0

  • Der Nachtrag liefert in Sekunden 😉 (0.000002)
    wenn du das mit 1000 multiplizierst, dann hast Millisekunden (0.002)
    Und weil du ja so genau Messen willst multiplizierst du wieder mit 1000 (2) und hast dann Nanosekunden.

    in freq steht die Anzahl der "Ticks" pro Sekunde, die dein Prozessor so schafft.

    0
  • ?

    BasicMan01 schrieb:

    Mich wundert, dass es compiliert, da die Groesse deines Array's zur Kompilierzeit unbekannt ist. a[n] << n wird doch noch eingegeben

    Das sind die Arrays mit variabler Länge, die von C99 eingeführt wurden. Mancher alte oder MS-Compiler versteht das nicht.

    Wenn ihr so kleine Codesnippets zeitmessen wollt, müsst ihr noch aufpassen, dass der Grossteil in eurer Ergebnis-Zeit nicht vom Overhead aller Art erzeugt wird.
    🙂

    0
Anmelden zum Antworten