String mit alphabetisch geordneten Substring



  • Guten Tag,
    ich habe mal wieder eine Frage zu einer Programmieraufgabe.

    Die Aufgabe lautet:
    Schreib ein Programm das in einem Buchstabensalat z. B. "sakdeidpoidweoidowijk" den längsten Substring in alphabetisch-korrekter Reihenfolge findet.
    z. B. "kotafgovlav" -> "Der längste alphabetische Substring ist: afgov"
    gibt es 2 gleichlange Kandidaten, soll der erste genommen werden.

    Diese Aufgabe habe ich von meinem Mentor bekommen, sie ist auch von der Webseite: programmieraufgaben.ch. Auch wenn dort Lösungen in C stehen sind diese für mich zu kompliziert gestaltet. Ich möchte es ja selbst Programmieren und nicht irgendwie kopieren.

    Deshalb benötige ich ein paar Denkanstöße.
    Wie kann ich vom str jedes einzelne Element abfragen?
    Und wie kann ich den Substring in meinem Falle ziel ausgeben?

    Ich danke euch für jegliche Hilfe.
    Ingmar

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    //alphabets funktion man müsste es später nu auf 26 begrenzen.
    /*void abc(int nummer) {
        return (64 + nummer);
    }
    */
    int folgensuche(char* str, char* ziel)
    {
        int i=0,j;
        int len = sizeof(str);
      //  abc(nummer);
        //ist die array stelle im alphabet
        while(str[i]==isalpha);
        {
            //kleiner gleich die länge des strings
            for(j=0; j<=len;j++)
            {
    
                    //ist [0] = k <=[1]
                    if(str[i]<=str[i+1])
                    {
                        //ergebnisse in einen Substring kopieren
                        strcpy(ziel[i], str[i]);
                    }
                    if(str[i]>str[i+1])
                    {
                        j+=len;
                        i+=26;
                    }
    
    
            }
        i++;
        }
    
        return ziel;
    }
    int main()
    {
       // abc(nummer);
        char str="kotafgovlav";
    
    
        char ziel;
    
        folgensuche(str,ziel);
        printf("%s", ziel);
    
        return 0;
    }
    

  • Mod

    Da ist leider noch viel grundlegendes zur Stingverarbeitung falsch. Und zwar auf eine Art und Weise falsch, dass man sieht, dass du das Konzept von Zeichenketten in C noch nicht verstanden hast. Die Aufgabe ist in dieser Form daher noch zu schwer für dich. Die übliche Art und Weise, um mit Zeichenketten in C fit zu werden, ist das Nachprogrammieren der Standardfunktionen. Eine gute Reihenfolge wäre beispielsweise strlen, memcpy, strcpy, strcat, strcmp, strchr, strstr. Vielleicht noch strtok, wenn du etwas Interessantes möchtest.

    Du magst vielleicht lachen über den Tipp, so etwas einfaches wie strlen zu programmieren, aber du hast es prompt falsch in deinem Programm hier. Daher: Teste auch jede deiner nachgeschriebenen Funktionen gründlichst(!) inklusive aller möglichen Sonderfälle durch.



  • @Luckyingmar Ein charkann genau ein Zeichen aufnehmen.

    Wenn du mehrere brauchst, musst du in C ein Array nehmen.

    Ein Array funktioniert in C aber anders als eine "normale" Variable.

    Zudem ist es in C extrem wichtig, bei Arrays die (in einer Funktion) beschrieben werden sollen, die (maximale) Größe mitzugeben.
    Das sizeof() funktioniert da nicht (bzw. anders)

    Das sind grundlegende Grundlagen, die muss dir dein Mentor vermitteln.

    Hier ist noch eine Onlinereferenz zur C-Standard-Library:
    http://www.cplusplus.com/reference/cctype/isalpha/?kw=isalpha
    http://www.cplusplus.com/reference/cstring/strlen/?kw=strlen (Das Example nicht beachten)



  • Ich muss mir alles selbstständig beibringen, daher kann es vorkommen, dass ich ein paar Sachen noch nicht zu 100% beherrsche.
    sizeof() habe ich schon ersetzt, danke!
    Ich werde ein Array verwenden, danke für den Tipp!


  • Mod

    @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    Ich werde ein Array verwenden, danke für den Tipp!

    Das klingt leider sehr danach, als hättest du es falsch verstanden. Du musst die Grundlagen zuerst lernen! Und prüfen, dass du diese wirklich verstanden hast. Der Eindruck ist, dass du denkst, die Grundlagen zu beherrschen, was aber eigentlich gar nicht der Fall ist.



  • @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    Wie kann ich vom str jedes einzelne Element abfragen?

    per subscript operator [], wie du es schon selbst machst

    Und wie kann ich den Substring in meinem Falle ziel ausgeben?

    mit puts

    Das Anhängen EINES Zeichens hinten an einen String passiert z.B. mit

    strncat(zielpointer,quellpointer,1);
    

    wobei der Zielbereich ausreichend groß dimensioniert und initial vollständig ausgenullt sein muss.

    Prinzip ist hier wie auch bei allen Aufgabenstellungen:
    separiere die größte sinnvoll zusammengehörige Teilfunktionalität in eine separate Funktion und wähle dabei minimale Parameteranzahl, hier also sub() und folgensuche().
    Die Musterlösung ist:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    char *sub(const char*s,char *z)  /* substring mit ausschließlich aufsteigender ASCII-Zeichenfolge ab 1. Position */
    {
    	while(*s)
    	{
    		if(*z)
    		{
    			if(z[strlen(z)-1]<*s)
    			strncat(z,s,1);
    			else
    			break;
    		}
    		else
    		*z=*s;
    		++s;
    	}
    	return z;
    }
    
    char *folgensuche(const char* str, char* ziel)
    {
    	while(*str) /* ab jeder Position suchen und mit bisher längstem Substring vergleichen */
    	{
    		char z[64000]="";
    		if(strlen(sub(str++,z))>strlen(ziel))
    		strcpy(ziel,z);
    	}
    	return ziel;
    }
    
    int main()
    {
        const char *str="kotafgovlav";
    
        char ziel[64000]="";
    
        puts(folgensuche(str,ziel));
    
        return 0;
    }
    

    https://ideone.com/xDjqbP



  • @Wutz sagte in String mit alphabetisch geordneten Substring:

    while(str) / ab jeder Position suchen und mit bisher längstem Substring vergleichen */

    Warum willst du das denn machen?

    Wenn an Position 1 5 Zeichen in alphabetischer Reihenfolge folgen, dann brauche ich nicht bei Position 2,3,... suchen, sondern kann danach gleich neu bei Position 1 + 5 = 6 starten. Und ich brauche auch nicht in jedem sub neu in z zu kopieren. Es reicht doch, wenn sub die Anzahl der alphabetisch aufsteigeden Zeichen liefert. Im calling code entscheide ich dann, ob das länger ist als der bisherige String. Wenn ja, kann ich mir pos+länge merken. Erst ganz am Ende kopiert man dann einmalig den gefundenen String heraus.



  • @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    Deshalb benötige ich ein paar Denkanstöße.

    du überprüfst für jedes element der zeichenkette, ob das nächste element größer ist (ascii-code, '0' ist kleiner als '9', 'A' ist kleiner als 'Z', 'a' ist kleiner als 'z', usw. programm entwickeln, dass dir alle chars von 0 bis 255 ausgibt und ansehen!). wenn ja, erhöhst du den längenzähler und überprüfst, ob das übernächste, überübernächste element auch größer ist, wenn nein, fängst du von vorne an. flussdiagramm erstellen, in c-code umwandeln, für beliebige (mindestens 20) zeichenketten überprüfen.

    Wie kann ich vom str jedes einzelne Element abfragen?

    mit str[i] bzw. *(str + i)

    Und wie kann ich den Substring in meinem Falle ziel ausgeben?

    indem du den substring in einen puffer kopierst bzw. die position des 1. und des letzten elements des substrings irgendwo abspeicherst.

    Ich danke euch für jegliche Hilfe.

    gern geschehen!


  • Mod

    Da bin ich ehrlich gesagt, tiefst enttäuscht, dass Wutzs Vorschlag künstliche Längenbegrenzungen drin hat. Einerseits massiv Stackspeicher verschwenden für nichts, andererseits ohne Vorwarnung abschmieren, wenn die unausgesprochenen Annahmen nicht eingehalten werden. Das ist doch nicht der vielbeschworene Proficode.

    PS: Hier auch mein Senf dazu. Nur einmal durchgehen, kein unnötiges Zwischenspeichern und keine Beschränkungen. Man kann aber bestimmt hier und da noch einzelne Zugriffe wegoptimieren:

    #include <stdio.h>
    #include <string.h>
    
    size_t first_ordered_subsequence_length(const char *sequence)
    {
      char previous_char = *++sequence;
      size_t length = 1;
      while(*sequence)
        {
          char current_char = *sequence;
          if (current_char >= previous_char)
            length += 1;
          else
            return length;
          previous_char = current_char;
          ++sequence;
        }
      return length;
    }
    
    
    void get_longest_ordered_subsequence(const char *sequence, char *result)
    {
      size_t longest_subsequence_length = 0;
      const char * longest_subsequence_pos = sequence;
    
      while(*sequence)
        {
          size_t next_subsequence_length = first_ordered_subsequence_length(sequence);
          if (next_subsequence_length > longest_subsequence_length)
            {
              longest_subsequence_length = next_subsequence_length;
              longest_subsequence_pos = sequence;
            }
          sequence += next_subsequence_length;
        }
      memcpy(result, longest_subsequence_pos, longest_subsequence_length);
      result[longest_subsequence_length] = 0;
    }
    
    int main()
    {
      char char_salad[] = "dehnijwdfbre4oto4tmpfe3TaacejkzREHY$%edft3GTE$HTSATSSERgdg";
      char result[sizeof(char_salad)];
      get_longest_ordered_subsequence(char_salad, result);
      puts(result);
    }
    


  • @SeppJ
    Oder unter Berücksichtigung der Groß/Kleinschreibung dann so, oder nicht?

    #include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    
    size_t step_subsequence( const char *sequence )
    {
      if( sequence )
      {
        char previous_char = 0x0;
        size_t length = 0;
        while( *sequence )
        {
          char current_char = toupper( *sequence );
          if( current_char >= previous_char ){ length += 1; }
          else { return length;  }
          previous_char = current_char;
          ++sequence;
        }
        return length;
      }
      return 0;
    }
    
    void get_longest_alpha_sequence( const char *sequence, char *result )
    {
      if( !sequence || !result ){ return; }
      size_t longest_subsequence_length = 0;
      const char *start_longest_subsequence = sequence;
      while( *sequence )
      {
        size_t subsequence_length = step_subsequence( sequence );
        if( subsequence_length > longest_subsequence_length )
        {
          longest_subsequence_length = subsequence_length;
          start_longest_subsequence = sequence;
        }
        sequence += subsequence_length;
      }
      memcpy( result, start_longest_subsequence, longest_subsequence_length );
      result[longest_subsequence_length] = 0;
    }
    
    int main( int argc, char **argv )
    {
      char data[] = "dehnijwdfbre4oto4tmpfe3TaacejkzREHY$%edft3GTE$HTSATSSERgdg";
      char result[sizeof(data)] = { 0 };
      get_longest_alpha_sequence( data, result );
      puts( result );
      return 0;
    }
    

    Dann wird aus

    3Taacejkz
    

    stattdessen

    aacejkz
    

  • Mod

    Mal angenommen, du könntest mich nicht fragen (Ja, schaut richtig aus): Wie würdest du prüfen, ob es wirklich korrekt ist?



  • Danke für eure Lösungen @Wutz @SeppJ @fairiestoy !!! Wobei meine Studienkollegin und ich, den Code von Wutz noch am simpelsten finden und daher schon super!
    Allerdings sind wir ja noch blutiger Anfänger und können eure Lösungen nicht zu 100% verstehen. Daher werden wir sie auch nicht einfach übernehmen.

    @Wutz
    Wieso benutzt du while und if mit unterschiedlichen Zeigern?
    Und was bedeutet z[strlen(z)-1]? Geht hierbei nicht um das Verständnis von z und strlen, sondern wofür stehen die eckigen Klammern? Wird das in den Klammern bevorzugt und danach mit z multipliziert?
    Der Rest ist für uns soweit verständlich!

    Ich möchte wenigstens die Schritte verstehen... auch meine Studienkollegin kommt in der Aufgabe nicht richtig weiter. Ich schicke euch auch nochmal diesen Code, auf ihrer Bitte hin hier rein. Wir haben getrennt voneinander gearbeitet, sodass unterschiedliche Lösungsansätze raus kamen.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    char * strcpy(char *ergebnis, char *array);
    int main()
    {
        char alpha[27] = "abcdefghijklmnopqrstuvwxyz";      // Alphabet als Abgleich
        int a=0;
        char array[21] = "sakdeidpoidweoidoijk";            // Buchstabensalat
        int i=0;
        char ergebnis[3];
    
    
        for(i=0; i<21; i++)                                 // Durchgang von jedem Buchstaben im Buchstabensalat
        {
            if(array[i] == alpha[a])
            {
                ergebnis[0] = strcpy(ergebnis, array);
                if(array[i+1] == alpha[a]++)
                {
                    ergebnis[1] = strcpy(ergebnis, array);
                    if(array[i+1] == alpha[a]++)
                    {
                        ergebnis[2] = strcpy(ergebnis, array);
                    }
                }
            }
        }
        printf("%s", ergebnis);
    
    
        return 0;
    }
    


  • @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    Und was bedeutet z[strlen(z)-1]?

    Die [ sind der ganz normale Arrayzugriff. Mit dem Ausdruck greifst du auf das letzte Zeichen im String z zu.

    @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    ergebnis[0] = strcpy(ergebnis, array);

    Das ist einfach nur Blödsinn. Das kann nicht funktionieren.

    strcpy liefert die Adresse von dem erste Element von ergebnis zurück. Dafür ist in ergebnis[0] kein Platz, zudem wird das gerade Kopierte wieder überschrieben und ergebnis ist auch zu klein (nur 3 Elemente).

    Daher ist eine weiter Erklärung wohl nicht nötig.


  • Mod

    @Luckyingmar sagte in String mit alphabetisch geordneten Substring:

    @Wutz
    Wieso benutzt du while und if mit unterschiedlichen Zeigern?

    Was soll man dazu sagen? Einmal will er halt was über sein s wissen und das andere Mal über sein z.

    Und was bedeutet z[strlen(z)-1]? Geht hierbei nicht um das Verständnis von z und strlen, sondern wofür stehen die eckigen Klammern? Wird das in den Klammern bevorzugt und danach mit z multipliziert?

    char str[] = "abc";
    

    Was wäre str[1]? Das hast du aber schon einmal gesehen? Was wäre str[1+1]? Was wäre str[irgendein total komplizierter Ausdruck, der irgendein Ergebnis hat]?

    Zeile 5 in deinem Programm gewöhnst du dir am besten sofort ab. Umdeklarieren interner Funktionen ist eine der bösesten Sachen, die du machen kannst.

    Feste Werte, die magisch im Programm stehen (z.B. die 21 in Zeile 15) zählen auch zu den schlimmeren Sachen, die man machen kann.

    strcpy habt ihr komplett falsch verstanden.

    Das Programm geht komplett an der Aufgabenstellung vorbei. Und das, was es versucht, macht es auch noch krass falsch. Das kann man gar nicht korrigieren, daher beschränke ich mich auf Tipps, wie man besser programmiert, anstatt darauf einzugehen.

    Das ganze Programm wirkt, als habe jemand irgendwie einen Haufen Zutaten genommen, von denen angenommen wird, dass sie irgendwie dazu gehören könnten, und dann zufällig zusammen geworfen, ohne jedweden Plan. Das funktioniert aber nicht. Code ist nicht irgendein zusammengewürfelter Haufen von Zeichen. Code ist Logik pur. Du musst von jedem einzelnen Zeichen in deinem Programm genau wissen, wo und warum du es setzt.

    Ihr habt es nicht einmal hinbekommen, die Dokumentation von strcpy zu lesen, sondern habt auch hier einfach geraten, dass da irgendwelche Zutaten zugehören, und dann zufällig versucht, dass etwas compilierbares heraus kommt, ohne irgendetwas davon zu verstehen. Das ist symptomatisch für eure Herangehensweise im gesamten Programm und man kann euch nicht helfen, so lange ihr mit diese Denkweise unterwegs seid.



  • An für sich ist es mit std::string doch recht einfach, hier wäre meine Herangehensweise:

    #include <iostream>
    #include <string>
    
    std::string getLongest(std::string str)
    {
        int32_t a[4] = {0};
        for (int i = 0; i < str.length() - 1; i++)
        {
            if (str[i] <= str[i + 1])
            {
                a[0]++;
                if (a[0] > a[1])
                {
                    a[1] = a[0];
                    a[2] = a[3];
                }
            }
            else
            {
                a[0] = 0;
                a[3] = i;
            }
        }
        if (a[1])
            return str.substr(a[2] + 1, a[1] + 1);
        else
            return "";
    }
    
    int main()
    {
        std::cout << getLongest("kotafgovlav") << std::endl;
        std::cout << getLongest("dcba") << std::endl;
    }
    

    Wobei ich nicht genau weiß, was passieren soll, wenn ein string keine aufeinanderfolgende Zeichen enthält...


  • Mod

    Ich weiß jetzt nicht, ob man die Kinder davor warnen soll, das nicht zuhause nachzumachen, oder ob das offensichtlich ist.



  • @SeppJ sagte in String mit alphabetisch geordneten Substring:

    Ich weiß jetzt nicht, ob man die Kinder davor warnen soll, das nicht zuhause nachzumachen, oder ob das offensichtlich ist.

    Ok 😂 Was wäre dMn. denn besonders schlimm?



  • @EinNutzer0 sagte in String mit alphabetisch geordneten Substring:

    Ok Was wäre dMn. denn besonders schlimm?

    Alles.

    • Du postest eine Lösung mit C++, wo die Frage doch um C geht. Thema verfehlt.
    • Deine Lösung ist brrrr
    • Variablennamen: a[4] - was soll das? Das ist semantisch kein Array, sondern 4 verschiedene Variablen. Also gib diesen Namen! Das ist das allerschlimmste, sogar noch schlimmer als der Leerstring-Fehler!
    • Parameterübergabe von std::string by value?
    • Was, wenn getLongest mit dem Leerstring aufgerufen wird?

  • Mod

    Als zweite Meinung dazu: wob hat absolut Recht, welchen Punkt er fett als allerschlimmsten hervorgehoben hat. Das alleine führt zur sofortigen Disqualifikation.



  • und kommentare fehlen auch noch!


  • Mod

    @Wade1234 sagte in String mit alphabetisch geordneten Substring:

    und kommentare fehlen auch noch!

    Ernsthafte Frage: Würdest du wirklich sagen, mein Code oben braucht Kommentare? Wenn ja, welche?


Log in to reply