WCM Forum - c++ Beispielfrage...

WCM Forum (http://www.wcm.at/forum/index.php)

- Programmierung (http://www.wcm.at/forum/forumdisplay.php?f=17)

- - c++ Beispielfrage... (http://www.wcm.at/forum/showthread.php?t=116396)

Groovy

23.11.2003 01:51

c++ Beispielfrage...

Könnt mir jemand in verständlichen Worten Erklären was ich beim 11. Beispiel genau tun soll? :rolleyes:

"Schreiben Sie eine Funktion sort(char string[]), das die Zeichen in der als Parameter übergebenen Zeichenkette sortiert."

http://www.pri.univie.ac.at/~itep/ws0304/hue/hue06.html

Wie sollen also die eingegebenen Zeichen sortiert werden?
Könnte das jemand anhand eines Beispiels erklären?

kikakater

23.11.2003 04:28

Du sollst das Zeichen 'a' vor das Zeichen 'b' reihen, wenn diese beiden Zeichen in der übergebenen Zeichenkette vorkommen usw.

Ein Beispiel:

Übergabe -> samba
Ergebnis -> aabms

Alles klar ?!

Code:

void sort (char string[])

{

 long i,start,len= strlen(string);

 int nochmal;

 char swap_char;



 if(len<2) return;



 for(start=0,nochmal=0;nochmal;start++)

 {

  for(i=start+1;i<len;i++)

  {

   if(string[start]>string[i])

   {

    nochmal= 1;

    swap_char= string[start];

    string[start]= string[i];

    string[i]= swap_char;    

   }

  }

 }

}

Das Sortierverfahren ist halt nicht sehr effektiv :(

mfg Kikakater

Groovy

23.11.2003 13:18

Achsoo also in alphabetischer Reihenfolge ausgeben, können die das nicht dazuschreiben?! :rolleyes:

Übrigens danke für dein Code, aber versteh ich ihn wieder nicht... :rolleyes:

Was ist strlen?

K@sperl

23.11.2003 13:20

Zitat:

Original geschrieben von Groovy
Was ist strlen?

strlen() gibt die Länge von string zurück.

Flink

23.11.2003 14:43

für lange Zeichenketten gibt es eine schnellere Variante:

Code:

#include <string.h>

void sort (char string[]);



int main()

{

        char string1[] = "abeejkieecccABEFE21342";



        sort(string1);



}



// sort bei längeren Strings

void sort (char string[])

{

 static int tabelle[255], akt_char;  // static, weil schneller

 long i, j, pos, len= strlen(string);



 // Initialisierung wegen static notwendig

 for(i=0;i<255;i++)

 {

    tabelle[i] = 0;

 }



  // sequentiell die Zeichen zählen

 for(i=0;i<len;i++)

 {

   tabelle [string[i]] ++;

 }



 for(i=0, pos=0;i<255;i++)

 {

   for (j = 0; j < tabelle[i]; ++j)

   {

     string[pos++] = (char) i;

   }

 }



}

kikakater

23.11.2003 16:32

2 Fehler:

Falsch: for(i=0;i<255;i++)

Richtig: for(i=0;i<=255;i++)

-

Falsch: for(i=0, pos=0;i<255;i++)

Richtig: for(i=1, pos=0;i<=255;i++)

~

mfg Kikakater

kikakater

23.11.2003 16:47

Außerdem muß folgende Zeile geändert werden:

Falsch: tabelle [string[i]] ++;

Richtig: tabelle [ (unsigned char)string[i] ] ++;

Es ist ein CASTen (ein Umtypisieren) notwendig, da für Zeichencodes > 127 - z.B. Umlaut A - ein negativer Index für das Array tabelle in der Funktion (besser Prozedur genannt da sort keinen Rückgabewert hat --> eben "void" sort (char string[])) herauskommt !

Der Wertebereich von char geht von -128 bis 127. Für tabelle[i], also das i (den Index) braucht man aber die Werte 1-255. Null zählt ja nicht, weil es (das Zeichen NUL (=binäre Null)) den Abschluß eines ASCII C Strings bildet. Deswegen braucht man das Element tabelle[0] nicht.

Oder:

tabelle [ ((unsigned char)string[i])-1 ] ++;

schreiben.

Dann stimmen die sogenannten beiden fehlerhaften Zeilen wieder.

kikakater

23.11.2003 16:58

Ich würde es aber nach Variante 1 machen, weil man sich die dauernde Subtraktion von 1 in der Zeile

tabelle [ ((unsigned char)string[i])-1 ] ++;

erspart.

Die Anzahl der Elemente von tabelle muß von 255 auf 256 erweitert werden - mit Element 0 als quasi nutzlosem Element.

static int tabelle[256], akt_char; // static, weil schneller

außerdem würde ich nicht static verwenden, weil das Feld tabelle sonst am Heap und nicht am Stack abgelegt wird (=Speicherplatzverschwendung).

akt_char wird nicht verwendet und ist demnach obsolet.

Groovy

23.11.2003 17:14

Zitat:

Original geschrieben von K@sperl
strlen() gibt die Länge von string zurück.

Ok Danke...
Was macht die ganzzahlige Variable "nochmal"?
Sie wird unten mit 1 initialisiert, was hat das für einen Zweck?

Sorry, ich check diesen Algorithmus nicht ganz...

Achja und noch eine Frage:
Wieso hat die Funktion void (if(len<2) return; )
einen Rückgabewert?

jak	23.11.2003 18:10

Hat sie doch eh nicht.
In diesem Fall bedeutet return einfach nur, daß die Funktion verlassen wird. Denk dir dort halt ein stop, break oder sonst was.

Jak

Groovy

23.11.2003 19:57

Kann mir jemand erklären wieso dieser Code nix ausgibt?:

Code:



#include <iostream.h>



void sort(char[]);



int main()



{



const int i=100;

char string[i];

cin>>string[i];

sort(string);



return 0;

}





void sort (char string[])

{

 long i,start,len= strlen(string);

 int nochmal;

 char swap_char;



 if(len<2) return;



 for(start=0,nochmal=0;nochmal;start++)

 {

  for(i=start+1;i<len;i++)

  {

   if(string[start]>string[i])

   {

    nochmal= 1;

    swap_char= string[start];

    string[start]= string[i];

    string[i]= swap_char;    

    cout<<string[i];

   

   }

  }

 }

}

*omg* ich hab wirklich die ärgsten Probleme beim Programmieren... :heul:

Flink

23.11.2003 21:02

Zitat:

Original geschrieben von kikakater
Ich würde es aber nach Variante 1 machen, weil man sich die dauernde Subtraktion von 1 in der Zeile

tabelle [ ((unsigned char)string[i])-1 ] ++;

erspart.

Die Anzahl der Elemente von tabelle muß von 255 auf 256 erweitert werden - mit Element 0 als quasi nutzlosem Element.

static int tabelle[256], akt_char; // static, weil schneller

außerdem würde ich nicht static verwenden, weil das Feld tabelle sonst am Heap und nicht am Stack abgelegt wird (=Speicherplatzverschwendung).

akt_char wird nicht verwendet und ist demnach obsolet.

Das hängt ab vom Gültigkeitsbereich der Ascii-Codes. '\0 ist wohl kein Zeichen. Man könnte auch andere Sonderzeichen weglassen. Tabelle[256] ist notwendig.
Guter Hinweis zum Heap.

kikakater

23.11.2003 21:15

Zitat:

Original geschrieben von Groovy
Ok Danke...
Was macht die ganzzahlige Variable "nochmal"?
Sie wird unten mit 1 initialisiert, was hat das für einen Zweck?

Sorry, ich check diesen Algorithmus nicht ganz...

Achja und noch eine Frage:
Wieso hat die Funktion void (if(len<2) return; )
einen Rückgabewert?

nochmal wird mit 0 initialisiert im Kopf der for Schleife.

Der Kopf der for schleife besteht immer aus

Code:

for ( Vorbereitung[,Vorbereitung[,...]];

Bedingung oder

Zuweisung/Funktionsaufruf als Bedingung[,Bedingung oder

Zuweisung/Funktionsaufruf als Bedingung[,...]];

Increment/Dekrement bzw.

zweckentfremdet Funktions/Prozeduraufruf(e) mit oder ohne logische Verknüpfungen[,Increment/Dekrement bzw.

zweckentfremdet Funktions/Prozeduraufruf(e) mit oder ohne logische Verknüpfungen[,...]] )



also kurz:



for ( Vorbereitung ; Bedingung ; Increment/Decrement )

nochmal wird nicht mit "1" initialisiert, sondern es wird 1 ("1" als Begriff, ein NUMERISCHES Literal) als Wert der Variablen zugewiesen.

Dann zieht die Bedingung der äussersten for Schleife ... ---> somit wird diese - also die äusserste for Schleife - nocheinmal durchlaufen.

Ein Fehler ist auch im Code:

Nach

for(start=0,nochmal=0;nochmal;start++)
{

müsste es

nochmal= 0;

heißen.

Sonst wird eine Endlosschleife produziert, falls auch nur ein Zeichen umsortiert worden ist (beim ersten Durchlaufen der gesamten Zeichenkette).

cin>>string[i];

ist außerdem falsch !

Du musst die ganze Zeichenkette einlesen und nicht nur ein Char Zeichen an der Indexstelle i des Char Arrays string[].

kikakater

23.11.2003 21:24

Das bzw. die Vorbereitungsstatements werden NUR EINMAL (nämlich am Anfang) der for Schleife ausgeführt, die Bedingung wird IMMER VOR DER AUSFÜHRUNG des Schleifenkörpers abgefragt, die Inkrement(bzw. Increment) usw. Statements werden IMMER NACH DER AUSFÜHRUNG des Schleifenkörpers durchgeführt. Ein vorzeitiger Abbruch der Schleife erfolgt mit break; bzw. in der Praxis mit if(irgendeine_abbruch_bedingung_erfuellt) break;

kikakater

23.11.2003 21:33

Noch zu Deiner Frage:

if(len<2) return;

ohne Rückgabewert wird kein Rückgabewert zurückgegeben :D

D.h. return; /* ohne return 0; oder return 1; oder return ret_variable; */

ist keine Rückgabe eines Wertes.

Es ist lediglich so, daß die PROZEDUR - oder void Funktion "sort" - (void bedeutet "kein Wert" bzw. "undefiniert" bzw. "nichts vorhanden") VORZEITIG verlassen wird. Es passiert nichts anderes, als daß die Rücksprungadresse (vom Stack) geladen wird und zur aufrufenden Funktion zurückverzweigt wird. Jedoch wird KEIN Rückgabewert bereitgestellt - es handelt sich eben um eine void Funktion (semantisch = bedeutungsmäßig eine Prozedur).

Groovy

23.11.2003 22:52

Vielen Dank für deine Beiträge.
Ich bekomm aber immer noch nichts raus..., bin halt zu unfähig
:heul:

Also es weden ganze Zeichenketten eingelesen, hast du es so gemeint?

Code:

#include <iostream.h>



void sort(char[]);



int main()



{





char eingabe[100];

cin>>eingabe;

sort(eingabe);



return 0;

}





void sort (char string[])

{

 long int i,start,len= strlen(string);

 int nochmal;

 char swap_char;



 if(len<2) return;



 for(start=0,nochmal=0;nochmal;start++)

 {

  for(i=start+1;i<len;i++)

  {

   if(string[start]>string[i])

   {

    nochmal= 0;

    swap_char= string[start];

    string[start]= string[i];

    string[i]= swap_char;    

    

    cout << string[i];

    

   

   }

  }

 }

}

:heul:

kikakater

23.11.2003 23:17

Code:

#include <iostream>

#include <stdlib.h>



using namespace std;



void sort(char[]);



int main(int argc, char *argv[])

{

 char eingabe[100];



 cin>>eingabe;

 sort(eingabe);

 cout << eingabe << endl;



 system("PAUSE");        

 return 0;

}



void sort (char string[])

{

 long int i,start,len= strlen(string);

 int nochmal;

 char swap_char;



 if(len<2) return;



 for(start=0,nochmal=1;nochmal;start++)

 {

  nochmal= 0;

  for(i=start+1;i<len;i++)

  {

   if(string[start]>string[i])

   {

    nochmal= 1;

    swap_char= string[start];

    string[start]= string[i];

    string[i]= swap_char;    

   }

  }

 }

}

Sollte jetzt ohne Probleme funktionieren.

nochmal muss am Anfang mit 1 initialisiert werden, hast recht und war mein Fehler. Im if Block jedenfalls auf 1 setzen und am Anfang des Schleifenblocks auf 0. 0 steht für die Annahme, daß alles bereits sortiert ist.

Groovy

24.11.2003 13:44

Vielen Dank für deine Hilfe.
Auf den Zeiger wär ich aber nicht gekommen, weil wir stoffmäßig noch nicht so weit sind.

hmm, funktioniert zwar unter Windows aber mit dem g++ Kompiler gehts nicht...eigenartig.

kikakater

24.11.2003 21:34

Poste die Fehlermeldung des g++ Compilers. Ich weiß nicht, was es da hat. Du musst mich aufklären.

Außerdem ist der einzige Zeiger in meinem Beispiel ein Feld (Array) aus mehreren char * Zeigern namens argv.

K@sperl

24.11.2003 21:39

Die Schnittstelle der Forward Deklaration stimmt mit der der Implementierung nicht überein:

Code:

void sort(char[])

void sort (char string[])

kikakater

24.11.2003 21:42

Streng genommen ja, wird wahrscheinlich der Fehler, respektive lediglich eine Warnung, sein.

Du kannst recht haben.

Normalerweise mach ich so etwas eh nicht, war ein Zugeständnis an die Schlacksichkeit hier im Forum :o *peinlich mir das eben geschriebene ist*

Alle Zeitangaben in WEZ +2. Es ist jetzt 04:52 Uhr.